KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode

<div>

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:

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

Example 2:

<pre>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 </pre>

Constraints:

  • 1 <= n <= 45

</div>

题目大意：

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

解题思路：

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

<div>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:

<pre>Input: root = [1,2,5,3,4,null,6] Output: [1,null,2,null,3,null,4,null,5,null,6] </pre>

Example 2:

<pre>Input: root = [] Output: [] </pre>

Example 3:

<pre>Input: root = [0] Output: [0] </pre>

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)?</div>

题目大意：

将二叉树转成以右节点相连的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 Edited on Disqus:

LeetCode

<div>

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

  • Only numbers 1 through 9 are used.
  • Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

<pre>Input: k = 3, n = 7 Output: [[1,2,4]] Explanation: 1 + 2 + 4 = 7 There are no other valid combinations.</pre>

Example 2:

<pre>Input: k = 3, n = 9 Output: [[1,2,6],[1,3,5],[2,3,4]] Explanation: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 There are no other valid combinations. </pre>

Example 3:

<pre>Input: k = 4, n = 1 Output: [] Explanation: There are no valid combinations. Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination. </pre>

Constraints:

  • 2 <= k <= 9
  • 1 <= n <= 60

</div>

题目大意：

数字1-9的组合个数为k的组合和等于k，每个元素最多用一次

解题思路：

用组合模板，先排序

解题步骤：

N/A

注意事项：

  1. Leetcode 40和77的结合。个数和target都要达到。用if k == 0 and target == 0

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
	nums = [_ for _ in range(1, 10)]
	res = []
	self.dfs(nums, 0, k, n, [], res)
	return res

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

算法分析：

时间复杂度为<code>O(2<sup>k</sup>)</code>，空间复杂度O(n)

Posted on Edited on Disqus:

LeetCode

<div>Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: 1. Each of the digits 1-9 must occur exactly once in each row. 2. Each of the digits 1-9 must occur exactly once in each column. 3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. The '.' character indicates empty cells. Example 1:

<pre>Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]] Explanation: The input board is shown above and the only valid solution is shown below:

</pre>

Constraints: * board.length == 9 * board[i].length == 9 * board[i][j] is a digit or '.'. * It is guaranteed that the input board has only one solution.</div>

题目大意：

日本游戏。需要保证每行每列每个9个方块的数是1-9里唯一。

Global dict解题思路(推荐)：

DFS。利用DFS模板

解题步骤：

N/A

注意事项：

  1. 用三种全局性dict(row, col, box)来记录所有已填的数，方便dfs时候迅速判断是否合法。这是比算法II优胜的地方。Python中不存在list of set只能用list of dict： [collections.defaultdict(int) for _ in range(len(board))]
  2. 初始化要将棋局上所有已有的数加入到dict中。一开始是dfs时候才加，但这样填的数不知道后面的格是否已经存在。题意保证有解，所以这些数不需验证重复。
  3. for循环是1-9是数字但棋盘是字符，所以要字符和数字转化，选择统一转成数字，不转的话dict会实效。
  4. box_dict的id转换： i // 3 * 3 + j // 3
  5. 终止条件为start_x == len(board) - 1 and start_y == len(board[0])

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def solveSudoku(self, board: List[List[str]]) -> None:
	row_dict = [collections.defaultdict(int) for _ in range(len(board))] # remember
	col_dict = [collections.defaultdict(int) for _ in range(len(board))]
	box_dict = [collections.defaultdict(int) for _ in range(len(board))]

	for i in range(len(board)):
		for j in range(len(board[0])):
			if board[i][j] != '.':
				self.add_to_dict(board, i, j, row_dict, col_dict, box_dict) # rememeber
	return self.dfs(board, 0, 0, row_dict, col_dict, box_dict)

def dfs(self, board, start_x, start_y, row_dict, col_dict, box_dict):
	if start_x == len(board) - 1 and start_y == len(board[0]):
		return True
	if start_y == len(board[0]):
		start_x += 1
		start_y = 0
	if board[start_x][start_y] != '.':
		return self.dfs(board, start_x, start_y + 1, row_dict, col_dict, box_dict) # guarantee solution
	for k in range(1, 10):
		if not self.is_valid(board, k, start_x, start_y, row_dict, col_dict, box_dict):
			continue
		board[start_x][start_y] = str(k)
		self.add_to_dict(board, start_x, start_y, row_dict, col_dict, box_dict)
		if self.dfs(board, start_x, start_y + 1, row_dict, col_dict, box_dict):
			return True
		self.remove_from_dict(board, start_x, start_y, row_dict, col_dict, box_dict)
		board[start_x][start_y] = '.'
	return False

def add_to_dict(self, board, i, j, row_dict, col_dict, box_dict):
	row_dict[i][int(board[i][j])] = 1 # remember
	col_dict[j][int(board[i][j])] = 1
	box_dict[i // 3 * 3 + j // 3][int(board[i][j])] = 1

def remove_from_dict(self, board, i, j, row_dict, col_dict, box_dict):
	row_dict[i].pop(int(board[i][j]))
	col_dict[j].pop(int(board[i][j]))
	box_dict[i // 3 * 3 + j // 3].pop(int(board[i][j]))

def is_valid(self, board, k, i, j, row_dict, col_dict, box_dict):
	if k in row_dict[i] or k in col_dict[j] or k in box_dict[i // 3 * 3 + j // 3]: # remember
		return False
	return True

算法分析：

三重循环，时间复杂度为<code>O(9<sup>n*n</sup>)</code>，空间复杂度O(n)，n为边长

常量空间算法II解题思路：

我一开始的方法，每填一位就验证。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def solveSudoku2(self, board: List[List[str]]) -> None:
	return self.dfs2(board, 0, 0)

def dfs2(self, board, start_x, start_y):
	if start_x == len(board) - 1 and start_y == len(board[0]):
		return True
	if start_y == len(board[0]):
		start_x += 1
		start_y = 0
	if board[start_x][start_y] != '.':
		return self.dfs2(board, start_x, start_y + 1) # guarantee solution
		'''
		if self.is_sudoku(board, start_x, start_y):
			return self.dfs(board, start_x, start_y + 1)
		else:
			return False
		'''
	for k in range(1, 10):
		board[start_x][start_y] = str(k)
		if self.is_sudoku2(board, start_x, start_y) and self.dfs2(board, start_x, start_y + 1):
			return True
		board[start_x][start_y] = '.'
	return False

def is_sudoku2(self, board, x, y):
	# row, # col, # square
	if self.is_valid(board, x, 0, x, len(board[0]) - 1) and self.is_valid(board, 0, y, len(board) - 1, y) and \
			self.is_valid(board, x // 3 * 3, y // 3 * 3, x // 3 * 3 + 2, y // 3 * 3 + 2):
		return True
	else:
		return False

def is_valid(self, board, start_x, start_y, end_x, end_y):
	num_set = set()
	for i in range(start_x, end_x + 1):
		for j in range(start_y, end_y + 1):
			val = board[i][j]
			if val == '.':
				continue
			if int(val) in num_set:
				return False
			num_set.add(int(val))
	return True

算法分析：

三重循环，时间复杂度为<code>O(81<sup>n*n</sup>)</code>，空间复杂度O(1)，n为边长

Posted on Edited on Disqus:

LeetCode

<div>

Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).

Each node will have a reference to its parent node. The definition for Node is below:

<pre>class Node { public int val; public Node left; public Node right; public Node parent; } </pre>

According to the definition of LCA on Wikipedia: "The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)."

Example 1:

<pre>Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3. </pre>

Example 2:

<pre>Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5 since a node can be a descendant of itself according to the LCA definition. </pre>

Example 3:

<pre>Input: root = [1,2], p = 1, q = 2 Output: 1 </pre>

Constraints:

  • The number of nodes in the tree is in the range [2, 10<sup>5</sup>].
  • -10<sup>9</sup> <= Node.val <= 10<sup>9</sup>
  • All Node.val are unique.
  • p != q
  • p and q exist in the tree.

</div>

题目大意：

求带父节点的树中的两个节点的LCA。节点值唯一，且两输入节点不同，且一定存在

解题思路：

N/A

解题步骤：

N/A

注意事项：

  1. 某一个节点的左右父节点存入set中，另一节点的每个父节点在set中找

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
	parent_set = set()
	it = p
	while it:
		parent_set.add(it)
		it = it.parent
	it = q
	while it:
		if it in parent_set:
			return it
		it = it.parent
	return None

算法分析：

时间复杂度为O(n + m)，空间复杂度O(n)，n和m为所有父亲路径长

Free mock interview