KK's blog

每天积累多一些

0%

括号题或者字符串运算题

Posted on Edited on Disqus:

括号题

算法思路：

  1. 优先考虑用Stack。Stack可以将字符压入比较或者字符的下标压入比较，后者信息量更大
    三种情况不合法： '[' (stack有余，for后发生), ']' (要匹配的时候stack为空，for中发生), '{]' (不匹配，for中发生)
  2. DP
    1. 左括号的数量在每一位都大于等于右括号数量
    2. 右括号的总和要等于右括号总和
      以上两个条件都满足的话，左右括号匹配，但此法只能用于单种括号

应用：

  1. 括号题
  2. 字符串运算题如, 3+4, (3+4)*5

括号运算题

stack的作用是存储优先级较低的操作数(暂时不能计算) 定义公式

res是作为同一层的临时计算结果，若遇到左括号，res保留在stack中且reset，若遇到右括号，stack的结果还原到res
num也是临时变量负责储存整数

注意事项：

  1. char.isdigit()的计算
  2. 左括号：入栈和reset res和num。
  3. 右括号:出栈和还原res = tmp + f(res)。

括号运算题模板：

1
2
3
4
5
6
7
8
9
10
def parenthesis(self, s: str) -> int:
    (Optional) s边界处理如s += '+' 
	stack, num = [], 0 数据结构用stack以及stack的一个元素
	for char in s:
	    所有字符的可能情况
		比如
		if char.isdigit(): 
			num = num * 10 + int(char)
        如果某情况入栈就一定要重置参数num=0		
		如果某情况出栈，代入公式计算

算法分析：

时间复杂度为O(n)，空间复杂度O(n).

LeetCode 394 Decode String

两个stack存储优先级较低的字符以及数字，类似于多重括号2*(3*(4)) 公式：prev_res+prev_num*[res]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def decodeString(self, s: str) -> str:
	stack_num, stack_char, num, char_str = [], [], 0, ""
	# char_str + num[<>]
	for c in s:
		if c.isdigit():
			num = 10 * num + int(c)
		if c.isalpha():
			char_str += c
		if c == "[":
			stack_num.append(num)
			stack_char.append(char_str)
			num = 0
			char_str = ""
		if c == "]":
			prev_char = stack_char.pop()
			prev_num = stack_num.pop()
			char_str = prev_char + prev_num * char_str
	return char_str

LeetCode 227 Basic Calculator II

stack=只存加号操作符 核心思想是只有出现运算符，才能计算前一个数[op]num. 所以op和num是记录前一个符号和数字 字符三种类别:空格，数字和运算符
若遇到运算符，就处理四种的op，目标是都要把num压栈，但是op是乘除要计算积或商后才能压栈。压栈后num=0， 若5*6+, char="+"的时候, prev = "5", prev_op = "*", num="6".
公式： [prev][prev_op][num][c=op]
实现时候先写只有加减的，再处理乘除，思维从简单开始。注意减法容易遗漏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def calculate(self, s: str) -> int:
	# prev_num[prev_op]num, 2+3+4+, 2+3*4+
	stack, prev_op, num = [], '+', 0
	s += "+"
	for c in s:
		if c == "":
			continue
		if c.isdigit():
			num = num * 10 + int(c)
		elif c in '+-*/':
			if prev_op in '*/':
				prev_num = stack.pop()
				if prev_op == "*":
					num = prev_num * num
				else:
					num = int(prev_num / num)               
			if prev_op == "-":
				num = -num
			stack.append(num)
			num = 0
			prev_op = c
	return sum(stack)

Free mock interview