【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)