KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:



Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]


Example 2:

Input: root = [1]
Output: [[1]]


Example 3:

Input: root = []
Output: []


Constraints:

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

题目大意：

二叉树按层遍历

解题思路：

用BFS模板

解题步骤：

N/A

注意事项：

  1. res.append(level)不是res.append(list(level))因为level = []已重新初始化。
  2. 关键行： 多这一行level.append(node.val)，其他一样

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def levelOrder(self, root: TreeNode) -> List[List[int]]:
	if not root:
		return []
	queue, res = collections.deque([root]), []
	while queue:
		level = []
		for _ in range(len(queue)):
			node = queue.popleft()
			level.append(node.val)

			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		res.append(level)
	return res

算法分析：

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

Posted on Disqus:

LeetCode



Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:



Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]


Example 2:

Input: root = [1]
Output: [[1]]


Example 3:

Input: root = []
Output: []


Constraints:

The number of nodes in the tree is in the range [0, 2000]. -100 <= Node.val <= 100

题目大意：

按层遍历二叉树。偶数层逆向

解题思路：

用BFS按层遍历模板

解题步骤：

N/A

注意事项：

  1. 多这一行level.append(node.val)

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
	if not root:
		return []
	res = []
	queue = collections.deque([root])
	while queue:
		level = []
		for _ in range(len(queue)):
			node = queue.popleft()
			level.append(node.val)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		if len(res) % 2 == 1:
			res.append(level[::-1])
		else:
			res.append(level)
	return res

算法分析：

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

Posted on Disqus:

LeetCode

Given the root of a binary tree, flatten the tree into a “linked list”: The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. The “linked list” should be in the same order as a pre-order traversal of the binary tree. Example 1: 

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]


Example 2:

Input: root = []
Output: []


Example 3:

Input: root = [0]
Output: [0]


Constraints: The number of nodes in the tree is in the range [0, 2000]. -100 <= Node.val <= 100 Follow up: Can you flatten the tree in-place (with O(1) extra space)?

题目大意：

将二叉树转成以右节点相连的LL

解题思路：

递归需要知道左右递归末尾节点，这样才可以将右节点的首节点接到左节点的末尾。所以递归函数输入是root，返回LL末尾节点

解题步骤：

N/A

注意事项：

  1. 递归函数输入是root，返回LL末尾节点
  2. 如果left_end是空，也就是没有左节点，就不用交换。返回right_end, left_end, root三者中非空者。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def flatten(self, root: TreeNode) -> None:
	self.dfs(root)

def dfs(self, root: TreeNode) -> None:
	if not root:
		return None
	left_end = self.dfs(root.left)
	right_end = self.dfs(root.right)

	if left_end: # remember
		left_end.right = root.right
		root.right, root.left = root.left, None
	if right_end:
		return right_end
	elif left_end:
		return left_end
	else:
		return root

算法分析：

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

Posted on Disqus:

LeetCode



You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps


Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step


Constraints:

* 1 <= n <= 45

题目大意：

爬楼梯的方法数。一次可以爬一级或二级

解题思路：

DP的经典题
递归式

1
dp[n] = dp[n - 1] + dp[n - 2]

解题步骤：

N/A

注意事项：

  1. 递归式含两个前状态，所以用两个变量。Python的优势是可以同时赋值，所以不需要用临时变量

Python代码：

1
2
3
4
5
6
# dp[n] = dp[n - 1] + dp[n - 2]
def climbStairs(self, n: int) -> int:
	prev, cur = 1, 1
	for i in range(2, n + 1): # 4
		cur, prev = cur + prev, cur # 5, 3
	return cur

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Numbers can be regarded as the product of their factors.

For example, 8 = 2 x 2 x 2 = 2 x 4.

Given an integer n, return all possible combinations of its factors. You may return the answer in any order.

Note that the factors should be in the range [2, n - 1].

Example 1:

Input: n = 1
Output: []


Example 2:

Input: n = 12
Output: [[2,6],[3,4],[2,2,3]]


Example 3:

Input: n = 37
Output: []


Constraints: 1 <= n <= 10<sup>7</sup>

题目大意：

求所有因式分解

解题思路：

求所有解，所以用DFS。类似于LeetCode 039 Combination Sum元素可复用。

解题步骤：

N/A

注意事项：

  1. 类似于元素可复用的组合和。但更似全组合模板，append发生在循环中，而不是终止条件中。比如12，遇到2就把商[2, 6]加入到结果
  2. 数值区间的组合，start和target都是数值，而不是数组长度。i是从start开始，而不是从2开始，保证path里的数有序
  3. target // i < i 保证path里的数有序，否则12=232，不可行
  4. i从start循环到math.sqrt(n) + 1，否则会TLE

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def getFactors(self, n: int) -> List[List[int]]:
	res = []
	self.dfs(n, 2, n, [], res)
	return res

def dfs(self, n, start, target, path, res):
	if target == 1:
		return
	for i in range(start, int(math.sqrt(n) + 1)): # remember to use start
		if target % i != 0 or target // i < i: # remember
			continue
		path.append(i)
		res.append(list(path + [target // i]))
		self.dfs(n, i, target // i, path, res) 
		path.pop()

算法分析：

时间复杂度为O(2n)，空间复杂度O(# of prime factors)

Free mock interview