KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given a n * n matrix grid of 0's and 1's only. We want to represent the grid with a Quad-Tree.

Return the root of the Quad-Tree representing the grid.

Notice that you can assign the value of a node to True or False when isLeaf is False, and both are accepted in the answer.

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

val: True if the node represents a grid of 1’s or False if the node represents a grid of 0’s. isLeaf: True if the node is leaf node on the tree or False if the node has the four children.

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}


We can construct a Quad-Tree from a two-dimensional area using the following steps:

1. If the current grid has the same value (i.e all 1's or all 0's) set isLeaf True and set val to the value of the grid and set the four children to Null and stop.
2. If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo.
3. Recurse for each of the children with the proper sub-grid.



If you want to know more about the Quad-Tree, you can refer to the wiki.

Quad-Tree format:

The output represents the serialized format of a Quad-Tree using level order traversal, where null signifies a path terminator where no node exists below.

It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list [isLeaf, val].

If the value of isLeaf or val is True we represent it as 1 in the list [isLeaf, val] and if the value of isLeaf or val is False we represent it as 0.

Example 1:



Input: grid = [[0,1],[1,0]]
Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Explanation: The explanation of this example is shown below:
Notice that 0 represnts False and 1 represents True in the photo representing the Quad-Tree.



Example 2:



Input: grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
Explanation: All values in the grid are not the same. We divide the grid into four sub-grids.
The topLeft, bottomLeft and bottomRight each has the same value.
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
Explanation is shown in the photo below:



Constraints:

n == grid.length == grid[i].length n == 2<sup>x</sup> where 0 <= x <= 6

题目大意：

由矩阵建四叉树。矩阵有0和1组成。按以下步骤：若子矩阵(变成为2的幂)只含1或0，生成一个叶子节点，值为该值；子矩阵含0和1混合，值为0或1(均为答案)，非叶子节点，递归四个同样大小的矩阵生成相应节点。
矩阵大小为2的幂，最小长度为1.

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

也是DFS，但递归终止条件为长度1，也就是每个cell都是叶子节点，先递归然后再归纳，若四个儿子节点都是叶子节点且值都相等，合并为一个叶子节点。否则为非叶子节点。
此算法实现更简单，但比较难想出。上述方法思想是按照题意。

注意事项：

  1. size = 1作为终止条件
  2. 两个条件该轮递归的节点为叶子节点，第一值相等，第二儿子节点都是叶子节点

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def construct(self, grid: List[List[int]]) -> 'Node':
	return self.dfs(grid, 0, 0, len(grid))

def dfs(self, grid, start_x, start_y, n):
	if n == 1:
		return Node(grid[start_x][start_y], True, None, None, None, None)
	top_left = self.dfs(grid, start_x, start_y, n // 2)
	top_right = self.dfs(grid, start_x, start_y + n // 2, n // 2)
	bottom_left = self.dfs(grid, start_x + n // 2, start_y, n // 2)
	bottom_right = self.dfs(grid, start_x + n // 2, start_y + n // 2, n // 2)
	if top_left.val == top_right.val == bottom_left.val == bottom_right.val and \
			top_left.isLeaf and top_right.isLeaf and bottom_left.isLeaf and bottom_right.isLeaf: # remmember
		return Node(top_left.val, True, None, None, None, None)
	else:
		return Node(1, False, top_left, top_right, bottom_left, bottom_right)

算法分析：

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

presum解题思路(不推荐)：

这是我的方法，按照定义求解，定义是递归的，所以用DFS。而统计子矩阵和用presum提高效率。但实现比较复杂

解题步骤：

N/A

注意事项：

  1. 子矩阵presum用模板
  2. 终止条件为子矩阵sum是0或n平方

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
def construct(self, grid: List[List[int]]) -> 'Node':
	presum = self.get_presum(grid)
	return self.dfs(grid, (0, 0), (len(grid) - 1, len(grid[0]) - 1), presum)

def dfs(self, grid, top_left, bottom_right, presum):
	grim_sum = self.get_grid_sum(top_left, bottom_right, presum)
	if grim_sum == 0:
		return Node(0, True, None, None, None, None)
	if grim_sum == (bottom_right[0] - top_left[0] + 1) * (bottom_right[0] - top_left[0] + 1):
		return Node(1, True, None, None, None, None)

	node = Node(1, False, None, None, None, None)
	row_mid = top_left[0] + (bottom_right[0] - top_left[0]) // 2
	col_mid = top_left[1] + (bottom_right[1] - top_left[1]) // 2
	node.topLeft = self.dfs(grid, top_left, (row_mid, col_mid), presum)
	node.topRight = self.dfs(grid, (top_left[0], col_mid + 1), (row_mid, bottom_right[1]), presum)
	node.bottomLeft = self.dfs(grid, (row_mid + 1, top_left[1]), (bottom_right[0], col_mid), presum)
	node.bottomRight = self.dfs(grid, (row_mid + 1, col_mid + 1), bottom_right, presum)
	return node

def get_grid_sum(self, top_left, bottom_right, presum):
	left = 0 if top_left[1] < 1 else presum[bottom_right[0]][top_left[1] - 1]
	top = 0 if top_left[0] < 1 else presum[top_left[0] - 1][bottom_right[1]]
	diag = 0 if top_left[0] < 1 or top_left[1] < 1 else presum[top_left[0] - 1][top_left[1] - 1]
	return presum[bottom_right[0]][bottom_right[1]] - left - top + diag

def get_presum(self, grid):
	presum = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
	for i in range(len(grid)):
		row_sum = 0
		for j in range(len(grid[0])):
			row_sum += grid[i][j]
			presum[i][j] = row_sum + (presum[i - 1][j] if i > 0 else 0)
	return presum

算法分析：

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

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)

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



Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]


Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]


Constraints:

1 <= nums.length <= 10<sup>5</sup> -2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1
0 <= k <= 10<sup>5</sup>

Follow up: Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
* Could you do it in-place with O(1) extra space?

题目大意：

数组原地向右旋转k位

解题思路：


证明如上图，比如[1,2,3,4,5,6,7]中，A = [1,2,3,4], B = [5,6,7]先整体reverse再分别reverse。

解题步骤：

N/A

注意事项：

  1. k会大于数组大小，所以取mod
  2. Python中reverse一个sublist，方法先取sublist再倒转

Python代码：

1
2
3
4
5
def rotate(self, nums: List[int], k: int) -> None:
	k = k % len(nums) # remember
	nums[:] = nums[::-1]
	nums[:k] = nums[:k][::-1] # remember how to reverse sublist
	nums[k:] = nums[k:][::-1]

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given an integer n, return the number of prime numbers that are strictly less than n.

Example 1:

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.


Example 2:

Input: n = 0
Output: 0


Example 3:

Input: n = 1
Output: 0


Constraints:

`0 <= n <= 5 106`

题目大意：

求n内的素数个数

解题思路：

排除法：知道一个素数后删除它的倍数，剩下的就是下一个素数

解题步骤：

N/A

初始方法

Python代码：

1
2
3
4
5
6
7
8
9
10
def countPrimes(self, n: int) -> int:
	if n < 2:
		return 0
	primes = [True] * n # remember less than n
	primes[0] = primes[1] = False
	for i in range(2, int(math.sqrt(n)) + 1):
		if primes[i]:
			for j in range(i * i, n, i): # starting from i rather than 2
				primes[j] = False
	return sum(primes)

注意事项：

  1. 开一个prime大小数组，初始值为True表示是素数。这样可以遍历到n开方+1. 是最主要的优化步骤，可以优化90%。
  2. 提高效率：i遍历到n开方+1，删除的数不能超过n(一开始写没有break导致TLE), 最后用sum统计比for循环效率高点
  3. 删除数字从i * i开始而不是i * 2,因为很多重复计算如2x3与3x2。此时第二个优化步骤。优化15%
  4. 用数组记录primes而不是set，第三个优化步骤。优化2%
  5. 题目要求素数小于n，所以不含n

Python代码：

1
2
3
4
5
6
7
8
9
10
def countPrimes(self, n: int) -> int:
	if n < 2:
		return 0
	primes = [True] * n # remember less than n
	primes[0] = primes[1] = False
	for i in range(2, int(math.sqrt(n)) + 1):
		if primes[i]:
			for j in range(i * i, n, i): # starting from i rather than 2
				primes[j] = False
	return sum(primes)

算法分析：

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

Free mock interview