20 394 735
# 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。 # 有效字符串需满足： # 左括号必须用相同类型的右括号闭合。 # 左括号必须以正确的顺序闭合。 # 注意空字符串可被认为是有效字符串。 # 思路： # # 字典储存对应括号 # # 遍历字符串： # 左括号入栈 # 右括号分三种情况： # 1.若此时栈为空，直接返回False # 2.若此时右括号和栈顶左括号不匹配，直接返回False # 3.若此时右括号和栈顶左括号匹配，栈顶左括号出栈 # # 遍历结束后 # 若栈为空栈，说明所有括号都匹配完成，返回True # 否则，返回False def isValid(s) -> bool: dic = {'(':')','[':']','{':'}'} stack = [] for i in s: if i in dic: stack.append(i) else: if len(stack) == 0: return False elif i == dic[stack.pop()]: pass else: return False return len(stack) == 0 if __name__ == '__main__': print(isValid("()[]{}")) print(isValid("(]")) print(isValid("{[]}")) pass
#给定一个经过编码的字符串，返回它解码后的字符串。 #编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 #你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。 #此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入 # sta = [] # 记录每次重复运算的开始位置，即‘[’的后一个位置 # num = [] # 将重复次数存在栈number中 # res = [] # 记录当前乘数 # end = 0 # 记录当前运算的最后一个数字 # result = [] # 记录结果 def decodeString(s) -> str: sta = [] num = [] res = [] end = 0 result = [] for i, ch in enumerate(s): if '0' <= ch <= '9': res.append(s[i]) elif ch == '[': num.append("".join(res)) res = [] sta.append(end) elif ch == ']': start = sta.pop() # 重复运算的开始位置 k = int(num.pop()) # 当前重复次数 result[start:end] *= k end += (end - start) * (k - 1) else: result.append(s[i]) end += 1 return "".join(result) if __name__ == '__main__': s="3[a]2[bc]" print(decodeString(s)) pass
# 本题核心思路是在栈里面每次存储两个信息, (左括号前的字符串, 左括号前的数字), 比如abc3[def], 当遇到第一个左括号的时候，压入栈中的是("abc", 3), 然后遍历括号里面的字符串def, 当遇到右括号的时候, 从栈里面弹出一个元素(s1, n1), 得到新的字符串为s1+n1*"def", 也就是abcdefdefdef。对于括号里面嵌套的情况也是同样处理方式。 # 凡是遇到左括号就进行压栈处理，遇到右括号就弹出栈，栈中记录的元素很重要。 def decodeString(s) -> str: stack = [] # (str, int) 记录之前的字符串和括号外的上一个数字 num = 0 res = "" # 实时记录当前可以提取出来的字符串 for c in s: if c.isdigit(): num = num * 10 + int(c) elif c == "[": stack.append((res, num)) res, num = "", 0 elif c == "]": top = stack.pop() res = top[0] + res * top[1] else: res += c return res if __name__ == '__main__': s="3[a]2[bc]" print(decodeString(s)) pass
# 本题核心思路是在栈里面每次存储两个信息, (左括号前的字符串, 左括号前的数字), 比如abc3[def], 当遇到第一个左括号的时候，压入栈中的是("abc", 3), 然后遍历括号里面的字符串def, 当遇到右括号的时候, 从栈里面弹出一个元素(s1, n1), 得到新的字符串为s1+n1*"def", 也就是abcdefdefdef。对于括号里面嵌套的情况也是同样处理方式。 # 凡是遇到左括号就进行压栈处理，遇到右括号就弹出栈，栈中记录的元素很重要。 def decodeString(s) -> str: stack = [] # (str, int) 记录之前的字符串和括号外的上一个数字 num = 0 res = "" # 实时记录当前可以提取出来的字符串 for c in s: if c.isdigit(): num = num * 10 + int(c) elif c == "[": stack.append((res, num)) res, num = "", 0 elif c == "]": top = stack.pop() res = top[0] + res * top[1] else: res += c return res if __name__ == '__main__': s="3[a]2[bc]" print(decodeString(s)) pass
# 给定一个整数数组 asteroids，表示在同一行的行星。 # 对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。 # 找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。 # 示例 4: # 输入: asteroids = [-2, -1, 1, 2] # 输出: [-2, -1, 1, 2] # 解释: -2 和 -1 向左移动，而 1 和 2 向右移动。由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。 #利用栈的思想，遍历给定数组里的数，大于0直接入栈；小于0的话，则从栈尾开始向前遍历，如果栈不为空且栈尾数字大于0小于当前数字，则依次去除栈尾元素。若栈为空或栈尾元素小于0，则直接入栈；若栈尾元素等于当前数的绝对值则去除栈尾元素；否则不对栈进行操作。 class Solution: def asteroidCollision( asteroids) -> [int]: res = [asteroids[0]] for num in asteroids[1:]: if num < 0: if res == [] or res[-1] < 0: res.append(num) else: while res != [] and res[-1] > 0 and res[-1] < abs(num): res = res[:-1] if res == [] or res[-1] < 0: res.append(num) elif res[-1] == abs(num): res = res[:-1] else: res.append(num) return res
