KK's blog

每天积累多一些

0%

Posted on Disqus:

LeetCode



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:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}


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:



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.


Example 2:



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.


Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1


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.

题目大意：

求带父节点的树中的两个节点的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为所有父亲路径长

Posted on Edited on Disqus:

LeetCode



Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]


Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]


Constraints:

2 <= nums.length <= 10<sup>5</sup> -30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1)extra space complexity? (The output array *does not count as extra space for space complexity analysis.)

题目大意：

求每个数对应的结果： 数组出自己外全部相乘

解题思路：

累计思想

解题步骤：

N/A

注意事项：

  1. 两轮计算，从左到右，再从右到左，用res数组作为临时计算结果。从左到右，计算res[i] = num[0] x nums[i - 1], 从右到左类似
  2. res初始值为1，因为从左到右是跳过第0个值的，而从右到左中res[i] *= product，若初始为0，结果res[i] = 0

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def productExceptSelf(self, nums: List[int]) -> List[int]:
	n = len(nums)
	res, product = [1] * n, nums[0]
	for i in range(1, n):
		res[i] = product # [1, 1]
		product *= nums[i]
	product = nums[-1] # 2
	for i in range(n - 2, -1, -1):
		res[i] *= product # [2, 1]
		product *= nums[i]
	return res

算法分析：

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

若可以用除法算法II解题思路：

按照定义用数学方法，但只要注意一个0和两个0的情况

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def productExceptSelf(self, nums: List[int]) -> List[int]:
	product, zero_count = 1, 0
	for n in nums:
		if n != 0:
			product *= n
		else:
			zero_count += 1
	if zero_count > 1:
		return [0] * len(nums)
	res = []
	for i in range(len(nums)):
		if nums[i] == 0:
			res.append(product)
		elif zero_count > 0:
			res.append(0)
		else:
			res.append(int(product / nums[i]))
	return res

算法分析：

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

Posted on Disqus:

LeetCode

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: 

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:




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.

题目大意：

日本游戏。需要保证每行每列每个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

算法分析：

三重循环，时间复杂度为O(9n*n)，空间复杂度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

算法分析：

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

Posted on Edited on Disqus:

LeetCode



A car travels from a starting position to a destination which is target miles east of the starting position.

There are gas stations along the way. The gas stations are represented as an array stations where stations[i] = [position<sub>i</sub>, fuel<sub>i</sub>] indicates that the i<sup>th</sup> gas station is position<sub>i</sub> miles east of the starting position and has fuel<sub>i</sub> liters of gas.

The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses one liter of gas per one mile that it drives. When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.

Return the minimum number of refueling stops the car must make in order to reach its destination. If it cannot reach the destination, return -1.

Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.

Example 1:

Input: target = 1, startFuel = 1, stations = []
Output: 0
Explanation: We can reach the target without refueling.


Example 2:

Input: target = 100, startFuel = 1, stations = [[10,100]]
Output: -1
Explanation: We can not reach the target (or even the first gas station).


Example 3:

Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation: We start with 10 liters of fuel.
We drive to position 10, expending 10 liters of fuel.  We refuel from 0 liters to 60 liters of gas.
Then, we drive from position 10 to position 60 (expending 50 liters of fuel),
and refuel from 10 liters to 50 liters of gas.  We then drive to and reach the target.
We made 2 refueling stops along the way, so we return 2.


Constraints:

1 <= target, startFuel <= 10<sup>9</sup> 0 <= stations.length <= 500
0 <= position<sub>i</sub> <= position<sub>i+1</sub> < target 1 <= fuel<sub>i</sub> < 10<sup>9</sup>

题目大意：

其最小加油次数使得能到达目标

Heap解题思路(推荐)：

由于是重叠区间题且贪婪法加找最大油加油站，考虑用heap。求最小值，所以用最大堆。heap存的油数。

注意事项：

  1. 每到一个加油站，先将油预存到heap中。startFuel为到达某个站后的剩余油数，若startFuel为负，从heap中取油，且累计加油次数。
  2. 用heap模板，遍历数组也就是加油站。
  3. 若加完油后，仍为负数，返回-1。
  4. 因为要计算target是否能达到，所以不妨将target加入到stations中，这样startFuel的计算可以包括target

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
	heap, res, prev_pos = [], 0, 0
	stations.append([target, 0])
	for pos, fuel in stations:
		startFuel -= pos - prev_pos
		while heap and startFuel < 0:
			startFuel += -heapq.heappop(heap)
			res += 1
		if startFuel < 0:
			return -1
		heapq.heappush(heap, -fuel)
		prev_pos = pos
	return res

算法分析：

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

DP算法II解题思路：

一开始考虑用jump game，但此题可以在同一层加多次油。比如start fuel有100 mi，而加油站有3个，所以同一层可以加3次油。所以层数和加油次数不是一个概念。
既然是最值考虑另一种方法DP。这题有两个难点:
第一个难点是DP式： dp不采用题目的最小加油次数，考虑jump game的分析，转化成dp[i]为停i个站加油能达到的最远距离。或者这样思考，若定义走到第n个站需要最小加油次数，这个n颗粒度不够细，可以换成miles，不如将下标和数值互换。
第二个难点是递归式。首先知道假设dp[2]能到达的范围内有一个加油站，加油后dp[3] = dp[2] + 该油站的油数。递归式为： 

1
dp[i] = max{dp[i-1] + stations[i-1][1]}, dp[i-1] >= stations[i-1][0], stations[i..n]

有个前提条件是dp[2]必须能达到当前的加油站。比如要更新dp[3]从任意两个加油站dp[2] + 加油站[i]可能获得。还可能是从dp[2] + 加油站[i+1]获得，如此类推，要试完stations[i..n]。
dp值从后往前更新，因为当前加油站在后方。

解题步骤：

N/A

注意事项：

  1. dp定义和递归式

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
# dp[i] = max{dp[i-1] + stations[i-1][1]}, dp[i-1] >= stations[i-1][0], stations[i..n]
def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
	dp = [startFuel] + [0] * len(stations)
	for i, (pos, fuel) in enumerate(stations):
		for j in range(i, -1, -1):
			if dp[j] >= pos:
				dp[j + 1] = max(dp[j + 1], dp[j] + fuel)

	for i, miles in enumerate(dp):
		if miles >= target:
			return i
	return -1

算法分析：

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

Posted on Edited on Disqus:

LeetCode



You are given an n x n integer matrix board where the cells are labeled from 1 to n<sup>2</sup> in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:

Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n<sup>2</sup>)]. This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next. The game ends when you reach the square n<sup>2</sup>.

A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n<sup>2</sup> do not have a snake or ladder.

Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.

Return the least number of moves required to reach the square n<sup>2</sup>. If it is not possible to reach the square, return -1.

Example 1:



Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Output: 4
Explanation:
In the beginning, you start at square 1 (at row 5, column 0).
You decide to move to square 2 and must take the ladder to square 15.
You then decide to move to square 17 and must take the snake to square 13.
You then decide to move to square 14 and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
This is the lowest possible number of moves to reach the last square, so return 4.


Example 2:

Input: board = [[-1,-1],[-1,3]]
Output: 1


Constraints: n == board.length == board[i].length
2 <= n <= 20 grid[i][j] is either -1 or in the range [1, n<sup>2</sup>].
* The squares labeled 1 and n<sup>2</sup> do not have any ladders or snakes.

题目大意：

二维版上每格label从1到n^2, 从左到右或从右到左(梅花间竹)，从下到上。每次走1-6步，格上可能有梯子和蛇，梯子是快进，蛇是回退直接到达目标格。求从1到n^2所需要步数。始点和目标不含梯子和蛇。

BFS解题思路(推荐)：

求最值两个方法：DP和BFS。一开始考虑用DP，但状态很复杂，因为存在回退，这样回退后要重新计算回退之后的DP值。
由于此题没有方向性而且似jump game，所以考虑用DP。

解题步骤：

N/A

注意事项：

  1. 题意：对于梯子和蛇，它不能停留在梯子和蛇的起点，只能够停在终点，所以梯子和蛇的起点到1的距离为无穷大。其实可以留在起点，比如一个格同时是蛇的终点和梯子的起点。题意表明不能在同一步中两次用梯子或蛇。
  2. 根据上述题意，程序中对应是如碰到儿子中有梯子和蛇的起点，完全忽略它，立刻转换成终点，也就是不入列，不入visited，不计算距离，完全当其透明。开始犯的错误是将其入列，出列才计算梯子终点。此算法仍然可以满足上述题意，此时梯子的起点会被加入到visited和distance，queue中，因为它确实停在那里了。
  3. visited在计算完梯子和蛇的终点后才处理，而不是进入for loop后
  4. neighbor不能超过n，达不到目标返回-1
  5. 另一个难点在label转成坐标从而查找是否有梯子和蛇

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
def snakesAndLadders(self, board: List[List[int]]) -> int:
	n = len(board) * len(board)
	queue = collections.deque([1])
	visited = set([1])
	distance = {1: 0}
	while queue:
		node = queue.popleft()
		if node == n:
			return distance[node]
		for neighbor in range(node + 1, node + 7):
			if neighbor > n:  # remember
				continue

			board_x, board_y = self.get_board_cell(len(board), neighbor)
			dest_label = board[board_x][board_y]
			next_step = dest_label if dest_label != -1 else neighbor

			if next_step in visited: # remember to put it after dest_label
				continue

			queue.append(next_step)
			visited.add(next_step)
			distance[next_step] = distance[node] + 1
	return -1  # remember

def get_board_cell(self, n, label): # 6, 6
	label -= 1 # rememeber
	row_id = label // n # 0
	col_id = label % n
	return n - 1 - row_id, n - 1 - col_id if row_id % 2 == 1 else col_id

算法分析：

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

另一种优化是只入最远的节点和蛇梯子的终点，类似于jump两种，类似于jump game。

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
def snakesAndLadders(self, board: List[List[int]]) -> int:
    n = len(board) * len(board)
	queue = collections.deque([1])
	visited = set([1])
	distance = {1: 0}
	while queue:
		node = queue.popleft()
		if node == n:
			return distance[node]
		max_non_jump = node
		for neighbor in range(node + 1, node + 7):
			if neighbor > n:  # remember
				continue

			board_x, board_y = self.get_board_cell(len(board), neighbor)
			dest_label = board[board_x][board_y]
			next_step = dest_label if dest_label != -1 else neighbor

			if next_step in visited:  # remember to put it after dest_label
				continue
			if dest_label != -1:
				queue.append(next_step)
				visited.add(next_step)
				distance[next_step] = distance[node] + 1
			else:
				max_non_jump = next_step
		if max_non_jump in visited:  # remember to put it after dest_label
			continue
		queue.append(max_non_jump)
		visited.add(max_non_jump)
		distance[max_non_jump] = distance[node] + 1
	return -1  # remember

def get_board_cell(self, n, label): # 6, 6
	label -= 1 # rememeber
	row_id = label // n # 0
	col_id = label % n
	return n - 1 - row_id, n - 1 - col_id if row_id % 2 == 1 else col_id

算法分析：

时间复杂度为O(n2/6)，空间复杂度O(n2/6)

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

非常容易错，且效率更低，需要回退重新计算dp值。 dp[i] + 1 < dp[dest_label]保证不会在无限回退，i = dest_label - 1要在break前做，而不是更前，否二影响dp[dest_label]计算

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def snakesAndLadders_dp(self, board: List[List[int]]) -> int:
	N = len(board) * len(board) + 1
	dp = [float('inf') for _ in range(N)]
	dp[1] = 0 # remember
	# i is label id
	i = 1
	# for i in range(2, N):
	while i < N:
		for k in range(1, 7):
			if i + k < N:
				board_x, board_y = self.get_board_cell(len(board), i + k)
				dest_label = board[board_x][board_y]
				next_step = dest_label if dest_label != -1 else i + k
				if dest_label != -1:
					if dest_label < i and dp[i] + 1 < dp[dest_label]: # remember 
						dp[dest_label] = min(dp[dest_label], dp[i] + 1)
						i = dest_label - 1 # remember to assign at the end
						break

				dp[next_step] = min(dp[next_step], dp[i] + 1) # remember + 1 inside min
		i += 1
	return dp[-1] if dp[-1] != float('inf') else -1 # remember

算法分析：

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

Free mock interview