KK's blog

每天积累多一些

0%

括号题或者字符串运算题

Posted on Edited on Disqus:

括号题

算法思路：

  1. 优先考虑用Stack。Stack可以将字符压入比较或者字符的下标压入比较，后者信息量更大
    三种情况不合法： ‘[‘ (stack有余，for后发生), ‘]’ (要匹配的时候stack为空，for中发生), ‘{]’ (不匹配，for中发生)
  2. DP
  3. 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”, op = “*“, num=”6”.
公式： [prev][op][num][char] 

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