KK's blog

LeetCode 987 Vertical Order Traversal of a Binary Tree

Posted on 2022-02-01 Edited on 2026-06-03 Disqus:

Given the root of a binary tree, calculate the vertical order traversal of the binary tree.

For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0).

The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.

Return the vertical order traversal of the binary tree.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Column -1: Only node 9 is in this column.
Column 0: Nodes 3 and 15 are in this column in that order from top to bottom.
Column 1: Only node 20 is in this column.
Column 2: Only node 7 is in this column.

Example 2:

Input: root = [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
Column -2: Only node 4 is in this column.
Column -1: Only node 2 is in this column.
Column 0: Nodes 1, 5, and 6 are in this column.
          1 is at the top, so it comes first.
          5 and 6 are at the same position (2, 0), so we order them by their value, 5 before 6.
Column 1: Only node 3 is in this column.
Column 2: Only node 7 is in this column.

Example 3:

Input: root = [1,2,3,4,6,5,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
This case is the exact same as example 2, but with nodes 5 and 6 swapped.
Note that the solution remains the same since 5 and 6 are in the same location and should be ordered by their values.

Constraints:

The number of nodes in the tree is in the range [1, 1000]. 0 <= Node.val <= 1000

题目大意：

按列顺序打印二叉树，若列号同，同一行的节点按值排序

解题思路：

与LeetCode 314 Binary Tree Vertical Order Traversal类似，用BFS

LeetCode 314 Binary Tree Vertical Order Traversal 同一列，从上到下，从左到右排序
LeetCode 987 Vertical Order Traversal of a Binary Tree 同一列，从上到下，同一行值从小到大排序

解题步骤：

N/A

注意事项：

与LeetCode 314实现的区别

一开始以为同一列的同一行的节点在queue是一个紧接一个出列。但同一行节点可能先出列col=3, col=4， col=3。而且同一列同一行的节点有多个，不止两个。所以将row_id也加入到queue节点和map中
遍历结果时，map中的value排序**, value是先row_id再node.val，所以直接可以排序，最后直接取出第二维度

Python代码：

def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
	if not root:
		return []
	col_to_node_list = collections.defaultdict(list)
	min_col, max_col = float('inf'), float('-inf')
	queue = collections.deque([(root, 0, 0)])
	while queue:
		node, row_id, col_id = queue.popleft()
		col_to_node_list[col_id].append((row_id, node.val))
		min_col, max_col = min(min_col, col_id), max(max_col, col_id)
		if node.left:
			queue.append((node.left, row_id + 1, col_id - 1))
		if node.right:
			queue.append((node.right, row_id + 1, col_id + 1))
	res = []
	for i in range(min_col, max_col + 1):
		col_to_node_list[i].sort()
		res.append([_[1] for _ in col_to_node_list[i]])
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)，稍大于O(n), 因为同一列同一行节点要排序

LeetCode 065 Valid Number

Posted on 2022-01-31 Edited on 2026-06-03 Disqus:

LeetCode

A valid number can be split up into these components (in order):

1. A decimal number or an integer.
2. (Optional) An 'e' or 'E', followed by an integer.

A decimal number can be split up into these components (in order):

1. (Optional) A sign character (either '+' or '-').
2. One of the following formats:
1. One or more digits, followed by a dot '.'.
2. One or more digits, followed by a dot '.', followed by one or more digits.
3. A dot '.', followed by one or more digits.

An integer can be split up into these components (in order):

1. (Optional) A sign character (either '+' or '-').
2. One or more digits.

For example, all the following are valid numbers: ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"], while the following are not valid numbers: ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"].

Given a string s, return true if s is a valid number.

Example 1:

Input: s = “0”
Output: true

Example 2:

Input: s = “e”
Output: false

Example 3:

Input: s = “.”
Output: false

Constraints:

1 <= s.length <= 20 s consists of only English letters (both uppercase and lowercase), digits (0-9), plus '+', minus '-', or dot '.'.

题目大意：

求合法小数指数形式

类括号法解题思路(推荐)：

有四种symbol，要保证先后关系。

解题步骤：

先写基本框架：

def isNumber(self, s: str) -> bool:
	seen_sign, seen_num, seen_exp, seen_dot = False, False, False, False
	for char in s:
		if char = '+-':
			if seen_sign:
				return False
			seen_sign = True
		elif char.isdigit():

			seen_num = True
		elif char in 'eE':
			if seen_exp:
				return False
			seen_exp = True
		elif char == '.':
			if seen_dot:
				return False
			seen_dot = True
		else:
			return False
	return True

if语句加入前面字符不能出现什么，每种其他字符过一遍。还有字符必须出现什么，此情况只有一种： e字符前必须有数字
for循环后return语句检查单个字符

注意事项：

有四种symbol：符号，数字，dot，exp。保证先后关系。exp的前后部分是独立的，唯一区别是后部分不能有dot，如1e2.2
实现类似于括号题用if语句来分别处理每种symbol：前面不能出现什么符号(e后面不能出现小数，也就是小数前面不能出现e)，或必须出现什么符号(仅一种情况：e前面必须出现数字)，如1e2. 然后该符号赋True
for循环后检查单个字符且不含数字情况
见解题步骤

Python代码：

def isNumber(self, s: str) -> bool:
	seen_sign, seen_num, seen_exp, seen_dot = False, False, False, False
	for char in s:
		if char in '+-':
			if seen_sign or seen_num or seen_dot:
				return False
			seen_sign = True
		elif char.isdigit():
			seen_num = True
		elif char in 'eE':
			if seen_exp or not seen_num:
				return False
			seen_exp = True
			seen_sign = False
			seen_num = False
			seen_dot = False
		elif char == '.':
			if seen_dot or seen_exp:
				return False
			seen_dot = True
		else:
			return False
	return False if (seen_sign or seen_exp or seen_dot) and not seen_num else True

算法分析：

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

DFA算法II解题思路(不推荐)：

Deterministic Finite Automaton (DFA)状态机，也就是将状态写入一个map中作为config，代码较简洁，但很难想。

算法分析：

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

LeetCode 1268 Search Suggestions System

Posted on 2022-01-31 Edited on 2026-06-03 Disqus:

LeetCode

You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character of searchWord is typed.

Example 1:

Input: products = [“mobile”,”mouse”,”moneypot”,”monitor”,”mousepad”], searchWord = “mouse”
Output: [
[“mobile”,”moneypot”,”monitor”],
[“mobile”,”moneypot”,”monitor”],
[“mouse”,”mousepad”],
[“mouse”,”mousepad”],
[“mouse”,”mousepad”]
]
Explanation: products sorted lexicographically = [“mobile”,”moneypot”,”monitor”,”mouse”,”mousepad”]
After typing m and mo all products match and we show user [“mobile”,”moneypot”,”monitor”]
After typing mou, mous and mouse the system suggests [“mouse”,”mousepad”]

Example 2:

Input: products = [“havana”], searchWord = “havana”
Output: [[“havana”],[“havana”],[“havana”],[“havana”],[“havana”],[“havana”]]

Example 3:

Input: products = [“bags”,”baggage”,”banner”,”box”,”cloths”], searchWord = “bags”
Output: [[“baggage”,”bags”,”banner”],[“baggage”,”bags”,”banner”],[“baggage”,”bags”],[“bags”]]

Constraints:

1 <= products.length <= 1000 1 <= products[i].length <= 3000
`1 <= sum(products[i].length) <= 2 10⁴* All the strings ofproducts

are **unique**.
*

products[i]

consists of lowercase English letters.
*

1 <= searchWord.length <= 1000*searchWord` consists of lowercase English letters.

题目大意：

实现搜索结果为3个autocomplete的功能

Prefix解题思路(推荐)：

Prefix

解题步骤：

N/A

注意事项：

用Trie，另一种思路是用prefix，此法采用prefix法，将所有单词按前缀加入到字典中

Python代码：

def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
	products.sort()
	prefix_dict = collections.defaultdict(list)
	for word in products:
		for i in range(len(word)):
			prefix = word[:i + 1]
			if len(prefix_dict[prefix]) < 3:
				prefix_dict[prefix].append(word)
	res = []
	for i in range(len(searchWord)):
		prefix = searchWord[:i + 1]
		res.append(prefix_dict[prefix])
	return res

算法分析：

时间复杂度为O(nL1 + L2)，空间复杂度O(nL1), L1为单词列表中最长的长度，L2为搜索单词长度，n为单词个数

Trie + DFS算法II解题思路：

建Trie，然后根据搜索的前缀定位到Trie节点，然后对此节点做DFS找到3个单词，因为DFS和字母顺序是一致的，所以DFS可行
具体参考Leetcode solution

Two pointers算法III解题思路：

先排序，用双指针相向搜索，根据搜索单词的每一个字母，不断收缩搜索范围，左指针和右指针之间即为满足条件的结果。每轮将左指针往后三个结果加到结果集
具体参考Leetcode discussion

LeetCode 174 Dungeon Game

Posted on 2022-01-31 Edited on 2026-06-03 Disqus:

LeetCode

The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of m x n rooms laid out in a 2D grid. Our valiant knight was initially positioned in the top-left room and must fight his way through dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight’s health (represented by positive integers).

To reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Return the knight’s minimum initial health so that he can rescue the princess.

Note that any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Example 1:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

Example 2:

Input: dungeon = [[0]]
Output: 1

Constraints:

m == dungeon.length n == dungeon[i].length
1 <= m, n <= 200 -1000 <= dungeon[i][j] <= 1000

题目大意：

保持正数健康值从左上走到右下

DP解题思路(推荐)：

坐标型DP。
dp[n][m]为通过这一格前的最小健康值，也就是题目所求，这意味着需要保证通过最后一个后的健康值为1，所以引入它相邻的两个cell为1
递归式为：

1 2	dp[n][m] = -dungeon[n][m] + min(dp[n+1][m], dp[n][m+1]) if dungeon[n][m] < 0 = max{1, min(dp[n+1][m], dp[n][m+1]) - dungeon[n][m]} if dungeon[n][m] > 0

由于-dungeon[n][m] + min(dp[n+1][m]一定为正数，所以可以归并两种情况：

1	dp[n][m] = max{1, min(dp[n+1][m], dp[n][m+1]) - dungeon[n][m]}

解题步骤：

N/A

注意事项：

从右下走回左上倒推初始值。每一格的最小健康值在为1，而初始健康值也最小为1.
递归式：一开始的递归式跟下和右格的极小值有关，所以DP数组(比原数组多出的)最右和最下边界初始值为正无穷；但根据公式，右下格会出现正无穷，所以需要特别处理，将右下格的相邻下右两格初始为1，可以这样理解，从右下格走出健康值必须是1
递归式：一开始写若该格dungeon值为负数，1 - dungeon[n][m] + min(dp[n+1][m], dp[n][m+1])这个1的确保证了最小健康值为1，但其实它只要加一次，而上述右下边界已经处理，所以递归式不需要+1，如[[-2, -3]], dp[0][1]=4, 而dp[0][0]为6即可
递归式：当dungeon为正数时，可以抵消它相邻格所要求的最低健康值，当然要保证健康值大于1，如[5, 4, -2], dp[0][0] = 1

Python代码：

# dp[n][m] = 1 - dungeon[n][m] + min(dp[n+1][m], dp[n][m+1]) if dungeon[n][m] < 0
#          = 1 + min(dp[n+1][m], dp[n][m+1]) if dungeon[n][m] > 0
# dp[n][m] = -dungeon[n][m] + min(dp[n+1][m], dp[n][m+1]) if dungeon[n][m] < 0
#          = min(dp[n+1][m], dp[n][m+1]) if dungeon[n][m] > 0
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
	dp = [[float('inf') for _ in range(len(dungeon[0]) + 1)] for _ in range(len(dungeon) + 1)]
	dp[-1][-2] = dp[-2][-1] = 1
	for i in reversed(range(len(dungeon))):
		for j in reversed(range(len(dungeon[0]))):
			'''
			min_neighbor = float('inf')
			if i + 1 < len(dungeon):
				min_neighbor = min(min_neighbor, dp[i + 1][j])
			if j + 1 < len(dungeon[0]):
				min_neighbor = min(min_neighbor, dp[i][j + 1])
			if min_neighbor == float('inf'):
				min_neighbor = 0

			if dungeon[i][j] < 0:
				dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
			else:
				dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])
			'''
			dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])
	return dp[0][0]

算法分析：

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

Binary select算法II解题思路：

Binary select + DP
暴力法，假设某个初始健康值，然后用从左到右从上到下计算这一格后的健康值，dp[m][n] = max{dp[m-1][n], dp[m][n-1]} + dungeon[r][c], 可以看出dp定义和递归式max都是跟上述方法相反。求最后一个是否正数
暴力法是O(n^2), 而用binary select试0, 1000 * (m + n) + 1，1000是cell的最大值，m+n是路径长度，1是最小健康值，二分法试每个数值

参考https://leetcode.com/problems/dungeon-game/discuss/1498367

算法分析：

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

LeetCode 1762 Buildings With an Ocean View

Posted on 2022-01-31 Edited on 2026-06-04 Disqus:

LeetCode

There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings in the line.

The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstructions. Formally, a building has an ocean view if all the buildings to its right have a smaller height.

Return a list of indices (0-indexed) of buildings that have an ocean view, sorted in increasing order.

Example 1:

Input: heights = [4,2,3,1]
Output: [0,2,3]
Explanation: Building 1 (0-indexed) does not have an ocean view because building 2 is taller.

Example 2:

Input: heights = [4,3,2,1]
Output: [0,1,2,3]
Explanation: All the buildings have an ocean view.

Example 3:

Input: heights = [1,3,2,4]
Output: [3]
Explanation: Only building 3 has an ocean view.

Constraints:

1 <= heights.length <= 10<sup>5</sup> 1 <= heights[i] <= 10<sup>9</sup>

题目大意：

大海在右边，求看到大海的大厦的下标

解题思路：

数组元素之间大小关系且保持顺序，用stack

解题步骤：

N/A

注意事项：

Python代码：

def findBuildings(self, heights: List[int]) -> List[int]:
	stack = []
	for i in range(len(heights)):
		while stack and heights[i] >= heights[stack[-1]]:
			stack.pop()
		stack.append(i) # 4 3 1
	return stack

算法分析：

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

算法II解题思路(推荐)：

储水或者低谷题用向左向右的局部最值法。这题只需要单边最值

解题步骤：

类似于Leetcode 42的trapping rain water，看不到大海表示在低位。此题只求单边，从右往左扫描一次。

注意事项：

Python代码：

def findBuildings2(self, heights: List[int]) -> List[int]:
	right_max, res = 0, []
	for i in reversed(range(len(heights))):
		if heights[i] > right_max:
			res.append(i)
		right_max = max(right_max, heights[i])
	return res[::-1]

算法分析：

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