KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode

<div>

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:

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

Example 2:

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

Example 3:

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

Constraints:

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

</div>

题目大意：

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

解题思路：

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

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5
6
7
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代码：

1
2
3
4
5
6
7
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)

Posted on Edited on Disqus:

LeetCode

<div>

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:

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

Example 2:

<pre>Input: dungeon = [[0]] Output: 1 </pre>

Constraints:

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

</div>

题目大意：

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

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，而初始健康值也最小为1.
  2. 递归式：一开始的递归式跟下和右格的极小值有关，所以DP数组(比原数组多出的)最右和最下边界初始值为正无穷；但根据公式，右下格会出现正无穷，所以需要特别处理，将右下格的相邻下右两格初始为1，可以这样理解，从右下格走出健康值必须是1
  3. 递归式：一开始写若该格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即可
  4. 递归式：当dungeon为正数时，可以抵消它相邻格所要求的最低健康值，当然要保证健康值大于1，如[5, 4, -2], dp[0][0] = 1

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
# 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]

算法分析：

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

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

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

Example 1:

<pre>Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] Output: 3 Explanation: The repeated subarray with maximum length is [3,2,1]. </pre>

Example 2:

<pre>Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] Output: 5 </pre>

Constraints:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 100

</div>

题目大意：

两数组的最长相等子数组

解题思路：

由于是两数组匹配，所以是匹配性DP
dp[i][j]为以nums1[i-1], nums2[j-1]为结尾的最长重复数组，答案为滚动最大值 

1
2
dp[i][j] = dp[i-1][j-1] + 1 if nums1[i-1] == nums2[j-1]
         = 0                if nums1[i-1] != nums2[j-1]

类似题目： LeetCode 1143 Longest Common Subsequence, 求最长公共子字符串 Karat 002 Longest Common Continuous Subarray 一样的题目，结果类型不同：最长长度和结果

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5
6
7
8
9
10
11
# dp[i][j] = dp[i-1][j-1] + 1 if nums1[i-1] == nums2[j-1]
#          = 0                if nums1[i-1] != nums2[j-1]
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
	max_length = 0
	dp = [[0 for _ in range(len(nums2) + 1)] for _ in range(len(nums1) + 1)]
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			if nums1[i - 1] == nums2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			max_length = max(max_length, dp[i][j])
	return max_length

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

A certain bug's home is on the x-axis at position x. Help them get there from position 0.

The bug jumps according to the following rules:

  • It can jump exactly a positions forward (to the right).
  • It can jump exactly b positions backward (to the left).
  • It cannot jump backward twice in a row.
  • It cannot jump to any forbidden positions.

The bug may jump forward beyond its home, but it cannot jump to positions numbered with negative integers.

Given an array of integers forbidden, where forbidden[i] means that the bug cannot jump to the position forbidden[i], and integers a, b, and x, return the minimum number of jumps needed for the bug to reach its home. If there is no possible sequence of jumps that lands the bug on position x, return -1.

Example 1:

<pre>Input: forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9 Output: 3 Explanation: 3 jumps forward (0 -> 3 -> 6 -> 9) will get the bug home. </pre>

Example 2:

<pre>Input: forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11 Output: -1 </pre>

Example 3:

<pre>Input: forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7 Output: 2 Explanation: One jump forward (0 -> 16) then one jump backward (16 -> 7) will get the bug home. </pre>

Constraints:

  • 1 <= forbidden.length <= 1000
  • 1 <= a, b, forbidden[i] <= 2000
  • 0 <= x <= 2000
  • All the elements in forbidden are distinct.
  • Position x is not forbidden.

</div>

题目大意：

求从0到x的最小步数，可以往前跳a步，往后跳b步，不能跳到负数，不能连续两次往前跳，不能跳到被禁止的位置。

算法思路：

类似于Jump game，不过此题要用真的BFS，用三个元素push如queue: (point, distance, is_backward), is_backward记录是否回退两次而剪枝，distance是结果。

注意事项：

  1. 用BFS模板，但此题到了某个位置可以有两个状态：向前跳和向后跳。所以visited不能只含位置，必须包含方向，(position, is_backward). if (neighbor, neighbor_is_backward) in visited也记得包含方向，否则LTE，因为Python不会检查是否tuple
  2. upper limit为max(x, max(forbidden)) + a + b，否则LTE，这个比较推导，可以这么理解max(x, max(forbidden))之后可以自由不受限制地走，必定存在一个点之后会重复且无意义，如a和b的最小倍数。举个例子找规律，a=2, b=1, x=10, 要走到11的话就要先到x+a+b再往回走

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
	forbidden_set = set(forbidden)
	limit = max(x, max(forbidden)) + a + b
	queue = collections.deque([(0, 0, False)])
	visited = set([(0, False)])  # remember two states
	while queue:
		node = queue.popleft()
		if node[0] == x:
			return node[1]
		for neighbor in [node[0] + a, node[0] - b]:
			if neighbor in forbidden_set or neighbor < 0 or neighbor > limit: # remember limit
				continue
			if neighbor == node[0] - b and node[2]: # no backward twice
				continue
			neighbor_is_backward = True if neighbor == node[0] - b else False
			if (neighbor, neighbor_is_backward) in visited: # remember not neighbor in visited - LTE
				continue
			queue.append((neighbor, node[1] + 1, neighbor_is_backward))
			visited.add((neighbor, neighbor_is_backward))
	return -1

算法分析：

时间复杂度为O(max(x, max(forbidden)) + a + b)，空间复杂度O(max(x, max(forbidden)) + a + b)

Posted on Edited on Disqus:

LeetCode 200 Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

题目大意：

给定一个由字符‘1’（陆地）和‘0’（水域）组成的二维网格地图，计算岛屿的个数。岛屿被水域环绕，由竖直或者水平方向邻接的陆地构成。你可以假设网格地图的四条边都被水域包围。

BFS解题思路：

BFS入列后立即标记为已访问，否则会有空间和时间问题。
二维变成一维，不但节省空间，还可以避免创建Point的新class。a = x * C + y(C为列数) <=> x = a/C, y = a%C

注意事项：

  1. 注意到题目给定输入数组的类型，用其来标记已访问的单元（节点）。
  2. BFS中如果cell为0或X就要跳过，不要漏掉0，因为如果是海不应做BFS。根据题目要求，可能还要将X恢复为1.

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
OFFSETS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.bfs(grid, i, j)
                    count += 1
        return count

    def bfs(self, nums, i, j):
        queue = deque([(i, j)])
        nums[i][j] = 'X'
        while queue:
            island = queue.popleft()
            for dx, dy in OFFSETS:
                x, y = island[0] + dx, island[1] + dy
                if x < 0 or x >= len(nums) or y < 0 or y >= len(nums[0]) or nums[x][y] in ['0', 'X']:
                    continue
                queue.append((x, y))
                nums[x][y] = 'X'

Java代码：

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
public int numIslands2(char[][] grid) {
	if (grid ==null || grid.length == 0 || grid[0].length == 0)
		return 0;
	
	boolean[][] visited = new boolean[grid.length][grid[0].length];
	int islands = 0;
	for(int i = 0; i < grid.length; i++)
		for(int j=0; j < grid[0].length; j++) {
			if(grid[i][j] == '0' || visited[i][j])
				continue;
	
			bfs3(grid, i, j, visited);
			islands++;
		}
	return islands;
}

public void bfs3(char[][] grid, int a, int b, boolean[][] visited) {
	Queue<Point> q = new LinkedList<>();
	int[][] directions = new int[][] {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
	q.offer(new Point(a, b));
	visited[a][b] = true;
	while(!q.isEmpty()) {
		Point point = q.poll();
		for(int i = 0; i < 4; i++) {
			Point neighbor = new Point(point.x + directions[i][0], point.y + directions[i][1]);
			if(!isValid(grid, neighbor.x, neighbor.y) || visited[neighbor.x][neighbor.y])
				continue;
			
			q.offer(neighbor);
			visited[neighbor.x][neighbor.y] = true;
		}
	}
}

算法分析：

时间复杂度为O(MN)，空间复杂度O(min{M,N})。M,N分别为矩阵长宽。因为最坏情况下，以矩形中心为root，最大的一层为矩形里面的最大正方形，它的长度为min{M,N}。

DFS解题思路：

遍历矩阵的每一个元素，对每个元素进行DFS四个方位搜索陆地，访问过的元素在原数组中进行标记。每次DFS搜索后，层数加1。

Java代码：

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
public int numIslands(char[][] grid) {
	int layer = 0;
	for(int i=0; i<grid.length;i++)
		for(int j=0;j<grid[0].length;j++)
			if(grid[i][j]=='1'){
				dfs(grid,i,j);
				layer++;
		}
	
	return layer;
}

public void dfs(char[][] grid, int a, int b){
	if(!isValid(grid,a,b))
		return;
	
	grid[a][b] = 'x';
	dfs(grid, a+1, b);
	dfs(grid, a-1, b);
	dfs(grid, a, b+1);
	dfs(grid, a, b-1);
}

public boolean isValid(char[][] grid, int x, int y){
	if(x<0||x>=grid.length||y<0||y>=grid[0].length||grid[x][y]!='1')
		return false;
	return true;
}

算法分析：

时间复杂度为O(MN)，空间复杂度O(MN)。M,N分别为矩阵长宽。最坏情况，全为陆地，DFS退化成线性。

Union Find解题思路：

见Union Find算法详解。

  1. 初始化UnionFind类，包括3个属性：count（独立连通数）, parent（某节点的父节点）, rank（连通集排名）。合格的节点的parent初始化为自己的id，rank为0，count为所有合格节点数量。
  2. 遍历所有节点，union此节点及其相邻的节点（如上下左右）
  3. union时候，先find两节点的根节点，若相同忽略。若不同，合并此两连通集：rank大的连通集，作为rank小的连通集的父节点。若rank相等，选任一作为另一个的父节点且把它的rank加1。count减1。
    如下图，union 6和11的，find(6)会进行压缩路径，把6接到5下。
  4. find寻找根节点的同时，压缩成与根节点路径为1的连通。

Java代码：

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class UnionFind {
	int count; // # of connected components
	int[] parent;
	int[] rank;

	public UnionFind(char[][] grid) { // for problem 200
		count = 0;
		int m = grid.length;
		int n = grid[0].length;
		parent = new int[m * n];
		rank = new int[m * n];
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (grid[i][j] == '1') {
					parent[i * n + j] = i * n + j;
					++count;
				}
				rank[i * n + j] = 0;
			}
		}
	}

	public int find(int i) {
		if (parent[i] != i) {
			parent[i] = find(parent[i]); // path compression
		}
		return parent[i];
	}

	// union with rank
	public void union(int x, int y) {
		int rootx = find(x);
		int rooty = find(y);
		if (rootx != rooty) {
			if (rank[rootx] > rank[rooty]) {
				parent[rooty] = rootx;
			} else if (rank[rootx] < rank[rooty]) {
				parent[rootx] = rooty;
			} else {
				parent[rooty] = rootx;
				rank[rootx] += 1;
			}
			--count;
		}
	}

	public int getCount() {
		return count;
	}
}

public int numIslands3(char[][] grid) {
	if (grid == null || grid.length == 0) {
		return 0;
	}

	int nr = grid.length;
	int nc = grid[0].length;
	int num_islands = 0;
	UnionFind uf = new UnionFind(grid);
	for (int r = 0; r < nr; ++r) {
		for (int c = 0; c < nc; ++c) {
			if (grid[r][c] == '1') {
				grid[r][c] = '0';
				if (r - 1 >= 0 && grid[r - 1][c] == '1') { 
					uf.union(r * nc + c, (r - 1) * nc + c);
				}
				if (r + 1 < nr && grid[r + 1][c] == '1') {
					uf.union(r * nc + c, (r + 1) * nc + c);
				}
				if (c - 1 >= 0 && grid[r][c - 1] == '1') {
					uf.union(r * nc + c, r * nc + c - 1);
				}
				if (c + 1 < nc && grid[r][c + 1] == '1') {
					uf.union(r * nc + c, r * nc + c + 1);
				}
			}
		}
	}

	return uf.getCount();
}

算法分析：

时间复杂度为O(MN)，空间复杂度O(MN)。M,N分别为矩阵长宽。遍历每个节点，而每个节点只会遍历4个相邻节点。

Follow-up:

  1. 打印所有island坐标
  2. 计算湖的数量。湖是被island维住的水域，与海有区别。解法是先从四条边界的海域进行DFS，标记为-1，然后采用上述算法，只要将搜寻1改为搜寻0即可。
  3. 如果内存有限，不能一次读整个矩阵。方案是分块做，然后保留边界信息作为下一块的输入。
  4. 地图中途被改动。分情况，若0->1，若此单元邻居只有一种label（即使多个邻居），岛屿数不变。无邻居，岛屿数+1。邻居有多种label为n，岛屿数减少n-1。Union Find也是一个更简洁方案。
    此情况比较简单，只要查看邻居即可，因为它只会增加连接。 若1->0, 对此单元相邻的四个单元进行DFS重新label新数，新数的种数-四单元的DSF岛屿个数=岛屿增加的个数。
    此情况需要重新做DFS，因为它破坏连接，可能导致连通性变小。
Free mock interview