原题链接:
https://leetcode.cn/problems/removing-stars-from-a-string/
这题虽然披着字符串的外衣 但其实是栈的应用
关键在于相邻两个字 然后是消除 如果没有提取好特征直接用遍历去写那这题就十分麻烦了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution:
def removeStars(self, s: str) -> str:
stk = []
n = len(s)
for i in range(n):
if s[i] == "*":
stk.pop()
else:
stk.append(s[i])
return ''.join(stk)
|
leetcode 包括很多算法题都是在原题基础上 或者一些经典算法的基础上改编而来 周赛的时候就是没反应过来在那里直接做 花了很多时间…
leetcode20 非常靠前的一道题了 应该算是这道题的原题了
https://leetcode.cn/problems/valid-parentheses/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution:
def isValid(self, s: str) -> bool:
n = len(s)
if n == 1 :
return False
stk = []
for i in range(n):
if s[i] == "(" or s[i] == "[" or s[i] == "{":
stk.append(s[i])
continue
if len(stk) == 0 :
return False
if s[i] == ")" and stk[-1] == "(":
stk.pop()
elif s[i] == "}" and stk[-1] == "{":
stk.pop()
elif s[i] == "]" and stk[-1] == "[":
stk.pop()
else:
return False
return len(stk) == 0
|
