【leetcode】132双周赛，前二题（栈，模拟）——python

一.100324. 清除数字

给你一个字符串 s 。

你的任务是重复以下操作删除 所有 数字字符：

• 删除 第一个数字字符 以及它左边 最近 的 非数字 字符。

请你返回删除所有数字字符以后剩下的字符串。

示例 1：

输入：s = "abc"

输出："abc"

解释：

字符串中没有数字。

示例 2：

输入：s = "cb34"

输出：""

解释：

一开始，我们对 s[2] 执行操作，s 变为 "c4" 。

然后对 s[1] 执行操作，s 变为 "" 。

提示：

• 1 <= s.length <= 100
• s 只包含小写英文字母和数字字符。
• 输入保证所有数字都可以按以上操作被删除。

答案：

#这道题用了栈的数据结构，用来记录并维护一个里数字最近的字母。
#思路：从左往右遍历，如果遇到字母就把他的索引值入栈，如果遇到数字就弹出栈顶元素（最近的字母的索引值），由于题目给出在左面，这么一想一定是栈顶元素。
class Solution:
    def clearDigits(self, s: str) -> str:
        stack = []
        s = list(s)
        for i,j in enumerate(s):
            if j in "0123456789":
                s[stack.pop()] = ""
                s[i] = ""
            else:
                stack.append(i)
        return "".join(s)

时间复杂度：o（n），空间复杂度：o（n） 

 二 .100297. 找到连续赢 K 场比赛的第一位玩家

有 n 位玩家在进行比赛，玩家编号依次为 0 到 n - 1 。

给你一个长度为 n 的整数数组 skills 和一个 正 整数 k ，其中 skills[i] 是第 i 位玩家的技能等级。skills 中所有整数 互不相同 。

所有玩家从编号 0 到 n - 1 排成一列。

比赛进行方式如下：

• 队列中最前面两名玩家进行一场比赛，技能等级 更高 的玩家胜出。
• 比赛后，获胜者保持在队列的开头，而失败者排到队列的末尾。

这个比赛的赢家是 第一位连续 赢下 k 场比赛的玩家。

请你返回这个比赛的赢家编号。

示例 1：

输入：skills = [4,2,6,3,9], k = 2

输出：2

解释：

一开始，队列里的玩家为 [0,1,2,3,4] 。比赛过程如下：

• 玩家 0 和 1 进行一场比赛，玩家 0 的技能等级高于玩家 1 ，玩家 0 胜出，队列变为 [0,2,3,4,1] 。
• 玩家 0 和 2 进行一场比赛，玩家 2 的技能等级高于玩家 0 ，玩家 2 胜出，队列变为 [2,3,4,1,0] 。
• 玩家 2 和 3 进行一场比赛，玩家 2 的技能等级高于玩家 3 ，玩家 2 胜出，队列变为 [2,4,1,0,3] 。

玩家 2 连续赢了 k = 2 场比赛，所以赢家是玩家 2 。

示例 2：

输入：skills = [2,5,4], k = 3

输出：1

解释：

一开始，队列里的玩家为 [0,1,2] 。比赛过程如下：

• 玩家 0 和 1 进行一场比赛，玩家 1 的技能等级高于玩家 0 ，玩家 1 胜出，队列变为 [1,2,0] 。
• 玩家 1 和 2 进行一场比赛，玩家 1 的技能等级高于玩家 2 ，玩家 1 胜出，队列变为 [1,0,2] 。
• 玩家 1 和 0 进行一场比赛，玩家 1 的技能等级高于玩家 0 ，玩家 1 胜出，队列变为 [1,2,0] 。

玩家 1 连续赢了 k = 3 场比赛，所以赢家是玩家 1 。

提示：

• n == skills.length
• 2 <= n <= 10 ** 5
• 1 <= k <= 10 ** 9
• 1 <= skills[i] <= 10 ** 6
• skills 中的整数互不相同。

答案：一暴力模拟：

由于数字量不是很大，直接按照题目进行模拟。
class Solution:
    def findWinningPlayer(self,skills: List[int], k: int) -> int:
        nums = [(i,j) for i,j in enumerate(skills)]
        max_num = max(skills)
        while 1:
            q = 0
            while nums[0][1] > nums[1][1]:
                nums.append(nums.pop(1))
                q += 1
                if nums[0][1] == max_num:
                    return nums[0][0]
                if q >= k:
                    return nums[0][0]
            nums[0],nums[1] = nums[1],nums[0]

时间复杂度：基于函数实现，空间复杂度(o(n))

由于循环和操作次数过多，所以比较耗时

二：暴力模拟优化

#如何减少操作次数，进行优化呢？
#其实遍历一遍就可以，因为战败的数组会删掉，前面的数只会越来越大，所以只要找两个，要么这个数的后k个，比他小，要么就是找最大值（因为最大值一定是正确的），遍历一遍一定能找到最大值。
class Solution:
    def findWinningPlayer(self,skills: List[int], k: int) -> int:
        mx_i = 0
        win = -1
        for i,x in enumerate(skills):
            if x > skills[mx_i]:
                mx_i = i 
                win = 0
            win += 1
            if win == k:
                break
        return mx_i

时间复杂度：o（n），空间复杂度：o（1）