KK's blog

Amazon Prime Free Trial

This Prime Day, save up to 70% on speakers, smart TVs, smart watches and more!

Blink Outdoor Camera - Early Prime Day Deals

Ads by Amazon

算法知识点目录

Posted on 2026-05-27 Edited on 2026-06-05 Disqus:

实现易错点

if not nums, not s，查看input
BFS中popleft() ，不是pop()
stack[-1] 等于peek，不是stack[0]
it = it.next记得移动指针

常见思路

数组或者string的连续或区间问题用递减栈或者sliding Window
最值用BFS(图)或heap(数值)
数组累计思想
nonlocal. See L543

LinkedList

注意事项： [4步]

fake_node
while it or it.next
删除节点.next = None
it = it.next

快慢指针找循环，找中点(注意中位数有1-2个, 用fast是否为None来判断)
LeetCode 142 Linked List Cycle II
LeetCode 234 Palindrome Linked List
反转LL及其模板
LeetCode 206 Reverse Linked List
LeetCode 092 Reverse Linked List II
其他：
LeetCode 021 Merge Two Sorted Lists
LeetCode 002 Add Two Numbers
LeetCode 138 Copy List with Random Pointer
LeetCode 023 Merge k Sorted Lists

Stack

递减栈
适用条件：数组元素之间大小关系(包括相等)且顺序不能变，可以动态处理(一个个处理)
求较大值 -> 递减栈
求较小值 -> 递增栈
Stack
LeetCode 503 Next Greater Element II 此题不能用向左最值，因为向右第一个较大不是最大
LeetCode 042 Trapping Rain Water 推荐向左向右最值不用stack
LeetCode 316 Remove Duplicate Letters 结果要按原顺序
LeetCode 1209 Remove All Adjacent Duplicates in String II 元素需连续(有序)
LeetCode 239 Sliding Window Maximum stream

BST的非递归遍历

BST的非递归中序，前序，后序遍历
 LeetCode 272 Closest Binary Search Tree Value II
Iterator题目基本是List转Stack
LeetCode 173 Binary Search Tree Iterator

Heap

Heap
递减栈 vs heap：实现上几乎一样，详见算法知识点目录。区别在于元素间是否需要保持顺序或者是否是stream
LeetCode 347 Top K Frequent Elements
LeetCode 253 Meeting Rooms II endTime的Heap (最常见)
LeetCode 218 The Skyline Problem 高度的Heap
Heap + BFS(本质是图，求点或点的和或线段路径的最值)
LeetCode 264 Ugly Number II
LeetCode 373 Find K Pairs with Smallest Sums
LeetCode 378 Kth Smallest Element in a Sorted Matrix

数据结构

题目大多都是HashMap + LL 或 HashMap + List

题目	LL	Map	其他数据结构
LRU	按时间顺序，头删尾入	值->LL节点	N/A
First Unique	按时间顺序，任意删尾入	值->LL节点	Set存两次以上
LFU	多个时间顺序的LL	值->LL节点	第二个Map存freq-> LL的首节点以及min_freq

LeetCode 1429 First Unique Number
LeetCode 380 Insert Delete GetRandom O(1)
LeetCode 146 LRU Cache
LeetCode 460 LFU Cache
Trie
适用条件： prefix搜索和文件系统
变体：Trie+DFS, search中迭代变递归
LeetCode 588 Design In-Memory File System
LeetCode 211 Design Add and Search Words Data Structure search含TrieNode参数 + DFS
LeetCode 212 Word Search II search含TrieNode参数
Iterator
LeetCode 251 Flatten 2D Vector
LeetCode 281 Zigzag Iterator
LeetCode 341 Flatten Nested List Iterator
LeetCode 173 Binary Search Tree Iterator
数组二分法:
LeetCode 981 Time Based Key-Value Store
LeetCode 2080 Range Frequency Queries
其他：
LeetCode 155 Min Stack

Two pointers(sliding window)

同向双指针：应用条件需要移动右指针连续直到达到target，然后移动左指针直到达不到target，梅花间竹
收缩条件固定字符种数, 若字符种树不固定，要试1-26种字符
Two pointers
LeetCode 243 Shortest Word Distance
LeetCode 209 Minimum Size Subarray Sum
LeetCode 438 Find All Anagrams in a String
LeetCode 076 Minimum Window Substring
LeetCode 340 Longest Substring with At Most K Distinct Characters 最长类型
LeetCode 395 Longest Substring with At Least K Repeating Characters 种数不固定
相向双指针
Hash(value -> index, value -> count)适用条件：数组元素之间的关系，相加相减等于target，复杂度为O(n)
LeetCode 1010 Pairs of Songs With Total Durations Divisible by 60 value -> count变体
Two points适用条件：数组元素之间的关系，相加相减等于target，元素相等或有序，复杂度为O(n)
回文题首先考虑用相向双指针
LeetCode 125 Valid Palindrome
LeetCode 680 Valid Palindrome II

Sorting

Quick sort
Partition的应用, O(1)空间且注意循环外处理最后一部分：

双指针，i和后部分的首指针index。 2. 若nums[i]属于前部分与nums[index]交换，否则只移动i
LeetCode 283 Move Zeroes
LeetCode 443 String Compression
LeetCode 075 Sort Colors
LeetCode 696 Count Binary Substrings
LeetCode 041 First Missing Positive
Quick select
Merge sort
LeetCode 244 Shortest Word Distance II
LeetCode 315 Count of Smaller Numbers After Self
LeetCode 493 Reverse Pairs
Bucket sort
LeetCode 347 Top K Frequent Elements
LeetCode 2080 Range Frequency Queries

Binary Search

Binary Search
LeetCode 278 First Bad Version
LeetCode 153 Find Minimum in Rotated Sorted Array
LeetCode 033 Search in Rotated Sorted Array
LeetCode 540 Single Element in a Sorted Array
LeetCode 275 H-Index II
Binary Select
适用条件：试某个数接近于最优解，全部试一遍就是*logn的复杂度
LeetCode 378 Kth Smallest Element in a Sorted Matrix
LeetCode 004 Median of Two Sorted Arrays

Tree

检查方法： None, 一个节点，两个节点(只有左或右)，三个节点
nonlocal方法，不用定义全局变量见LeetCode 543 Diameter of Binary Tree
LeetCode 104 Maximum Depth of Binary Tree
LeetCode 230 Kth Smallest Element in a BST
LeetCode 114 Flatten Binary Tree to Linked List
LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal
LeetCode 314 Binary Tree Vertical Order Traversal
方法：用Map记录子节点到父节点关系等价于形成双向Tree
LeetCode 1650 Lowest Common Ancestor of a Binary Tree III
LeetCode 236 Lowest Common Ancestor of a Binary Tree
LeetCode 863 All Nodes Distance K in Binary Tree

BFS

适用条件：可行性，最大和最小值且每个点不能重复访问
注意事项： [3步]建图没有边的节点也要加到邻接表, 输入参数不等于迭代参数, 返回-1,
图BFS
LeetCode 200 Number of Islands 连通集问题, 对所有节点BFS
LeetCode 1048 Longest String Chain 多源最长路劲，对所有节点BFS
LeetCode 1197 Minimum Knight Moves
LeetCode 133 Clone Graph
LeetCode 297 Serialize and Deserialize Binary Tree
LeetCode 127 Word Ladder
LeetCode 301 Remove Invalid Parenthesess
LeetCode 055 Jump Game
LeetCode 1654 Minimum Jumps to Reach Home
LeetCode 286 Walls and Gates 多始点一次BFS
LeetCode 490 The Maze 一组节点作为一层的BFS
LeetCode 815 Bus Routes 一组节点作为一层的BFS
[LeetCode 1293 Shortest Path in a Grid with Obstacles Elimination] 多状态BFS
拓扑排序
 LeetCode 210 Course Schedule II
LeetCode 310 Minimum Height Trees
LeetCode 269 Alien Dictionary

DFS

适用条件：种数(优先用DP，次选用DFS)，可行性
图DFS/填位法
 排列
 LeetCode 526 Beautiful Arrangement
组合
 LeetCode 039 Combination Sum
LeetCode 077 Combinations
LeetCode 216 Combination Sum III
LeetCode 017 Letter Combinations of a Phone Number 填位法
LeetCode 051 N-Queens 填位法
LeetCode 037 Sudoku Solver 填位法, 单边DFS + 循环DFS
LeetCode 093 Restore IP Addresses 分割型，结果分组型DFS
LeetCode 291 Word Pattern II 分割型, 单边DFS + 循环DFS
LeetCode 079 Word Search 图DFS + 分割型
LeetCode 126 Word Ladder II 图DFS
记忆性搜索
 LeetCode 140 Word Break II 分割型
LeetCode 095 Unique Binary Search Trees II Catalan型DFS
LeetCode 241 Different Ways to Add Parentheses Catalan型DFS

DP

适用条件：最值，种数，可行性。输入数据有序,暴力法非多项式
注意事项： [5步]多1, 初始化, 多1, 少1, 答案
DP
LeetCode 070 Climbing Stairs 单序列型
LeetCode 091 Decode Ways 单序列型
LeetCode 198 House Robber 单序列型
LeetCode 377 Combination Sum IV 数值到个数DP
LeetCode 322 Coin Change 数值到个数DP
LeetCode 518 Coin Change 2 数值到个数DP(元素无序)
LeetCode 063 Unique Paths II 坐标型DP
LeetCode 064 Minimum Path Sum 坐标型DP
LeetCode 221 Maximal Square 坐标型DP
LeetCode 174 Dungeon Game 坐标型DP
LeetCode 718 Maximum Length of Repeated Subarray 匹配型DP
LeetCode 300 LIS 匹配型DP
LeetCode 139 Word Break 匹配型DP
LeetCode 072 Edit Distance 匹配型DP
LeetCode 044 Wildcard Matching 匹配型DP
LeetCode 010 Regular Expression Matching 匹配型DP
LeetCode 516 Longest Palindromic Subsequence 区间型DP
LeetCode 312 Burst Balloons 区间型DP
Karat 002 Longest Common Continuous Subarray 打印路径
LeetCode 300 Longest Increasing Subsequence 打印路径
LeetCode 368 Largest Divisible Subset 打印路径
LeetCode 1143 Longest Common Subsequence 打印路径
多状态DP需要同时赋值
LeetCode 152 Maximum Product Subarray 多状态DP
LeetCode 926 Flip String to Monotone Increasing 多状态DP
LeetCode 256 Paint House 多状态DP
多状态DP-fg双函数(g为累计DP) - 和前状态不能相邻
LeetCode 337 House Robber III 多状态DP-fg双函数
LeetCode 309 Best Time to Buy and Sell Stock with Cooldown 多状态DP-fg双函数
LeetCode 329 Longest Increasing Path in a Matrix Floyd

其他

动态计算连接数，其他均用BFS
Union Find
LeetCode 721 Accounts Merge
[双向BFS]LeetCode 127 Word Ladder
[线段树]LeetCode 729 My Calendar I

最大的k个/最大的前k个数(无序数值数组)

LeetCode 347 Top K Frequent Elements
优先考虑Heap，因为Heap支持动态和静态数据。适用范围最广，动态包括Data stream，不将整个数组读入从而优化复杂度
LeetCode 295 Find Median from Data Stream
LeetCode 378 Kth Smallest Element in a Sorted Matrix
Binary select，数值法计算个数，不能用于动态，实现较复杂
LeetCode 004 Median of Two Sorted Arrays
Quick select, binary select的特殊版，只能用于一维数组

数组区间内动态最大值最小值或保留数组顺序(数值数组)

由于保留顺序，首选stack
LeetCode 2104 Sum of Subarray Ranges

二维坐标最短距离

BFS首选，然后DP。若状态转移是无序用BFS，否则DP(可从上到下，从左到右)
BFS
LeetCode 1197 Minimum Knight Moves
LeetCode 909 Snakes and Ladders
DP
LeetCode 174 Dungeon Game 坐标型DP

累计思想

将相连的批量计算提高效率或者满足累计条件
LeetCode 032 Longest Valid Parentheses 统计左括号个数保证其一直为非负数
LeetCode 134 Gas Station 保证gas一直为非负数
数组的presum
加入presum[0] = 0
LeetCode 696 Count Binary Substrings
LeetCode 560 Subarray Sum Equals K
LeetCode 238 Product of Array Except Self
子矩阵的presum
同数组，presum矩阵大小为长度 + 1

1
2
3

res = presum[x][y] - left - top + diag

presum[i][j] = row_sum + (presum[i - 1][j] if i > 0 else 0)

LeetCode 304 Range Sum Query 2D - Immutable
LeetCode 427 Construct Quad Tree

括号题或者字符串运算题

括号题或者字符串运算题优先用Stack
LeetCode 020 Valid Parentheses
LeetCode 032 Longest Valid Parentheses
LeetCode 1249 Minimum Remove to Make Valid Parentheses 括号下标
LeetCode 678 Valid Parenthesis String
LeetCode 022 Generate Parentheses
LeetCode 071 Simplify Path
字符串运算题
LeetCode 227 Basic Calculator II
LeetCode 224 Basic Calculator
LeetCode 394 Decode String

游戏题

数据结构设计 + 模拟
[LeetCode 348 Design Tic-Tac-Toe] 设计游戏
LeetCode 051 N-Queens 求游戏所有解
LeetCode 037 Sudoku Solver 求游戏是否有解

区间重合题

条件区间重合且区间始点有序。用端点排序法(更常用)或Heap(处理重合情况下的计算)
LeetCode 253 Meeting Rooms II
LeetCode 056 Merge Intervals
LeetCode 759 Employee Free Time
LeetCode 1235 Maximum Profit in Job Scheduling
LeetCode 871 Minimum Number of Refueling Stops
LeetCode 218 The Skyline Problem 端点排序法 + Heap

所有子串和子数组

用presum, stack, DP
LeetCode 560 Subarray Sum Equals K
LeetCode 696 Count Binary Substrings
LeetCode 907 Sum of Subarray Minimums
LeetCode 2104 Sum of Subarray Ranges
Leetcode 828 Count Unique Characters of All Substrings of a Given String

26字母存储法

条件，若题目含所有字母，且求最值，需要存储每个字母对应的结果
LeetCode 395 Longest Substring with At Least K Repeating Characters
LeetCode 1857 Largest Color Value in a Directed Graph

水王法

candidate取首元素，遍历每一个元素，若candidate不符合条件就换成当前元素为candidate
LeetCode 169 Majority Element
LeetCode 277 Find the Celebrity
LeetCode 134 Gas Station

Word相关题目

DFS: word pattern, word search
BFS: word ladder
DP: word break

LeetCode 017 Letter Combinations of a Phone Number

Posted on 2026-05-27 Edited on 2026-06-03 Disqus:

LeetCode 017 Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

**Input:** digits = "23"
**Output:** ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

**Input:** digits = ""
**Output:** []

Example 3:

**Input:** digits = "2"
**Output:** ["a","b","c"]

Constraints:

0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].

题目大意：

在拨号键盘上按下了几个键，问能打出来的字符串的所有组合是多少。。

递归法解题思路：

DFS的典型题目。

与Java的区别：

直接用Str作为临时结果，不需要用char array，因为str可以含有array的性质

注意事项：

输入值为空的情况
终止条件记得return
用常量

Python代码：

DIGIT2CHAR = {
    '0': '',
    '1': '',
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz',
}

class Solution(TestCases):

	# filling dfs (type 3) LeetCode 017 Letter Combinations of a Phone Number 
	def letterCombinations(self, digits: str) -> List[str]:
		if not digits:
			return []
		path, res = [], []
		self.dfs3(digits, 0, path, res)
		return res

	def dfs3(self, digits, start, path, res):
		if len(path) == len(digits): # len(path) == TARGET
			res.append("".join(path))
			return
		keys = DIGIT2CHAR[digits[start]]
		for letter in keys:
			path.append(letter)
			self.dfs3(digits, start + 1, path, res) # remember start + 1
			path.pop()

迭代法解题思路：

第二种方法，用迭代法，三种循环，输入数字串的每个数字，每个数字对应的字符加到当前的结果字符串列表中。

注意事项：

要[‘’]而不是[]否则循环不会进行

def letterCombinations(self, digits: str) -> List[str]:
	if digits == '':
		return []
	result = ['']
	for d in digits:
		result = [s + c for s in result for c in DIGIT2CHAR[d]]
	return result

算法分析：

这是NP问题。时间复杂度为O(4ⁿn)，解大小乘以path长度，空间复杂度O(1)。

LeetCode 077 Combinations

Posted on 2026-05-27 Edited on 2026-06-03 Disqus:

LeetCode

Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Example 2:

Input: n = 1, k = 1
Output: [[1]]

Constraints:

1 <= n <= 20 1 <= k <= n

题目大意：

求大小为k的所有可能组合

解题思路：

用组合模板，先排序

解题步骤：

N/A

注意事项：

引入k作为模板API中的target，k为0作为终止条件。

Python代码：

# char dfs (type 2 linear) Leetcode 77 Given two integers n and k, return all possible combinations of k numbers out of the range [1, n]
def combine(self, n: int, k: int) -> List[List[int]]:
	nums = [i + 1 for i in range(n)]
	path, res = [], []
	self.dfs2(nums, 0, k, [], res)
	return res

def dfs2(self, nums, start, k, path, res):
	if len(path) == k:
		res.append(list(path))
		return
	for i in range(start, len(nums)):
		path.append(nums[i])
		self.dfs2(nums, i + 1, k, path, res)
		path.pop()

算法分析：

时间复杂度为O(kC^k_n)，解大小乘以path长度, 空间复杂度O(n)

LeetCode 140 Word Break II

Posted on 2026-05-27 Edited on 2026-06-03 Disqus:

LeetCode 140 Word Break II

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = “catsanddog“
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output: [
  "cats and dog",
  "cat sand dog"
]

Example 2:

Input: s = “pineapplepenapple”
wordDict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”]
Output: [
  “pine apple pen apple”,
  “pineapple pen apple”,
  “pine applepen apple”
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = “catsandog”
wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
Output: []

题目大意：

一个字符串s，求被“字典集合”（wordDict）中的单词拼接的所有方案。

解题思路：

这是经典题。求所有可能性想到DFS，前面Lintcode 683提到可能会有重复解。所以用Cache。

Cache模板：

key为子问题索引st，value为子问题的解。不含path和res因为类似于Catalan(属于单边Catalan)，用子问题返回结果来组成此轮结果。f(input, st, endIndex, cache)
紧跟终结条件，若在cache中，返回子问题的解。
循环结束，将子问题的结果存于cache。

注意事项：

终止条件返回[‘’]而不是[]，正如L017，空字符串作为初始结果。返回到上层要strip(), 因为ss可能为空
子问题用f=word + f并不是f=f + word, 这样最后结果避免反转。
s[:i + 1]判断是否在字典中，而不是s[:i]，单词包括整个字符串。

Python代码：

def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
	word_set = set(wordDict)
	res = []
	cache = {}
	res = self.dfs(s, word_set, cache) #cat
	return res
# dfs(s) = word + dfs(s[i+1:])
def dfs(self, s, word_set, cache):
	if s == "":
		return [""]
	if s in cache:
		return cache[s]
	res = []
	for i in range(len(s)):
		if s[:i + 1] not in word_set:
			continue
		cur_list = self.dfs(s[i + 1:], word_set, cache) # i = 2, dfs("")
		for _s in cur_list: # [""]
			res.append((s[:i + 1] + " " + _s).strip()) #cat
	cache[s] = res
	return res

注意事项：

将两个输入都转换成小写。
复制子问题的解，不能直接在解List上编辑。

Java代码：

public List<String> wordBreak(String s, List<String> wordDict) {
	List<String> res = new ArrayList<>();
	if(s == null || s.isEmpty())
		return res;
	Set<String> wordDictLower = new HashSet<>();
	for(String c : wordDict)
		wordDictLower.add(c.toLowerCase());
	s = s.toLowerCase();
	Map<Integer, List<String>> cache = new HashMap<>();
	return dfs(s, wordDictLower, s.length(), cache);
}

List<String> dfs(String s, Set<String> wordDict, int st, Map<Integer, List<String>> cache) {
	if(st == 0) 
		return new ArrayList<>(Arrays.asList(""));
	if(cache.containsKey(st))
		return cache.get(st);
	List<String> result = new ArrayList<>();
	for(int i = 0; i < st; i++) {
		String word = s.substring(i, st);
		if(!wordDict.contains(word))
			continue;

		List<String> sub = dfs(s, wordDict, i, cache); 
		// copy solution for subproblem, don't edit on sub
		for(int j = 0; j < sub.size(); j++)
			result.add((sub.get(j) + " " + word).trim());
	}
	cache.put(st, result);
	return result;
}

算法分析：

时间复杂度为O(解大小)，空间复杂度为O(解大小)。

LeetCode 227 Basic Calculator II

Posted on 2026-05-27 Edited on 2026-06-03 Disqus:

LeetCode

Given a string s which represents an expression, evaluate this expression and return its value.

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = “3+2*2”
Output: 7

Example 2:

Input: s = “ 3/2 “
Output: 1

Example 3:

Input: s = “ 3+5 / 2 “
Output: 5

Constraints:

`1 <= s.length <= 3 10⁵*sconsists of integers and operators(‘+’, ‘-‘, ‘‘, ‘/‘)` separated by some number of spaces. s represents a valid expression.
All the integers in the expression are non-negative integers in the range [0, 231 - 1]. The answer is guaranteed to fit in a 32-bit integer.

题目大意：

实现字符串加减乘除，但无括号。

算法思路：

逆波兰式的实现用Stack。Stack只存数，而且只存加号操作符的数，也就是说，
核心思想是只有出现运算符，才能计算前一个数[op]num. 所以op和num是记录前一个符号和数字
字符三种类别:空格，数字和运算符
若遇到运算符，就处理四种的op，目标是都要把num压栈，但是op是乘除要计算积或商后才能压栈。压栈后num=0，

如果是减，就将-num入栈，
如果是乘除，立刻计算stack[-1]乘除num的结果再压入栈，因为乘除是最高优先级可以直接计算，而加减不可以。
所以用一个stack

举一个例子: 2+3

2-3+
char=”-“的时候, op = “+”, num=”2”. op和num是一对的。
char=”+”的时候, op = “-“, num=”3”. op和num是一对的。

若5*6+, char=”+”的时候, prev = “5”, op = “*“, num=”6”.
[prev][op][num][char]
stack=只存加号操作符

代码中含三种情况：空格，运算符，数字

LeetCode 224 Basic Calculator 括号加减法, 同一层括号内求和遇括号入栈
LeetCode 227 Basic Calculator II 加减乘除, 和的每一项入栈，方便出栈计乘除
LeetCode 772 Basic Calculator III 加减乘除括号, L227的递归版

注意事项：

此题没有括号，不能用模板，要借用op来记录前一个操作符

op记录前一个运算符，char为运算符或当前字符。计算时候根据op，因为char(+)只是第二个操作数(1-2+)的终结字符，此时表明操作数stack[-1], num以及操作符op均已完成，可以计算
最容易错的是向下取整Line 18, 题目返回要求整数。所以要除法后取整int(prev / num)
s末尾加入加号，方便parse最后一个num

Python代码：

def calculate(self, s: str) -> int:
	# prev[op]+num[char]
	# 2-3
	stack, num, op, res = [], 0, '+', 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)

算法分析：

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

实现易错点

常见思路

数组题

整数题

整洁题

Map

LinkedList

Stack

BST的非递归遍历

Heap

数据结构

Two pointers(sliding window)

Sorting

Binary Search

Tree

BFS

DFS

DP

其他

最大的k个/最大的前k个数(无序数值数组)

数组区间内动态最大值最小值或保留数组顺序(数值数组)

二维坐标最短距离

累计思想

括号题或者字符串运算题

游戏题

区间重合题

所有子串和子数组

26字母存储法

水王法

Word相关题目

题目大意：

递归法解题思路：

注意事项：

Python代码：

迭代法解题思路：

注意事项：

算法分析：

题目大意：

解题思路：

解题步骤：

注意事项：

Python代码：

算法分析：

题目大意：

解题思路：

注意事项：

Python代码：

注意事项：

Java代码：

算法分析：

题目大意：

算法思路：

注意事项：

Python代码：

算法分析：