KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



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

Example 1:

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


Example 2:

Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output: 5


Constraints:

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

题目大意：

两数组的最长相等子数组

解题思路：

由于是两数组匹配，所以是匹配性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

算法分析：

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

Posted on Edited on Disqus:

LeetCode



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:

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.


Example 2:

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


Example 3:

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.


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.

题目大意：

求从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，因为它破坏连接，可能导致连通性变小。

Posted on Edited on Disqus:

LeetCode



You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1


Example 2:

Input: coins = [2], amount = 3
Output: -1


Example 3:

Input: coins = [1], amount = 0
Output: 0


Example 4:

Input: coins = [1], amount = 1
Output: 1


Example 5:

Input: coins = [1], amount = 2
Output: 2


Constraints:

1 <= coins.length <= 12 1 <= coins[i] <= 2<sup>31</sup> - 1
* 0 <= amount <= 10<sup>4</sup>

题目大意：

求兑换硬币的最小个数

解题思路：

用数值->个数DP模板

注意事项：

  1. amount为0时候，返回0，表示不用coin也能满足，属于合法情况, dp[0] = 0(第二步)
  2. 返回值，若dp[-1]为初始值，表示无解，返回-1(第5步)
  3. 实现中dp[i] = min(dp[i], dp[i - j] + 1), +1在min内而不是min外。
  4. 此题内外循环顺序不重要，跟LeetCode 518 Coin Change 2有区别

Python代码：

1
2
3
4
5
6
7
8
9
def coinChange(self, coins: List[int], amount: int) -> int:
	coins.sort()
	dp = [float('inf')] * (amount + 1)
	dp[0] = 0
	for coin in coins:
		for i in range(len(dp)):
			if i + coin <= amount:
				dp[i + coin] = min(dp[i + coin], dp[i] + 1)
	return dp[-1] if dp[-1] < float('inf') else -1  # remember

算法分析：

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

Posted on Edited on Disqus:

LeetCode

Given a string s containing an out-of-order English representation of digits 0-9, return the digits in ascending order. Example 1:

Input: s = “owoztneoer”
Output: “012”


Example 2:

Input: s = “fviefuro”
Output: “45”


Constraints: 1 <= s.length <= 10<sup>5</sup> s[i] is one of the characters ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"]. s is *guaranteed to be valid.

题目大意：

数字用英语单词表示如12 -> onetwo, 但打乱顺序otwone. 求如何获得原数字

算法思路：

统计每个字母的个数，根据个数来决定数字
规律见代码： 有些字母但唯一的，如two，w可以知道数字含2
但有些字母是多个数字的和如s，six和seven都含有s，减去用上述的six的个数就知道seven的个数

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
def originalDigits(self, s: str) -> str:
	char_to_num = {
		'z': '0',
		'w': '2',
		'u': '4',
		'x': '6',
		'g': '8',
		'o': '1',  # decided by previous keys
		'h': '3',  # decided by previous keys
		'f': '5',  # decided by previous keys
		's': '7',  # decided by previous keys
		'i': '9',  # decided by previous keys
	}
	res = []
	char_to_freq = collections.defaultdict(int)
	for char in s:
		char_to_freq[char] += 1
	char_to_freq['o'] -= char_to_freq['z'] + char_to_freq['w'] + char_to_freq['u']
	char_to_freq['h'] -= char_to_freq['g']
	char_to_freq['f'] -= char_to_freq['u']
	char_to_freq['s'] -= char_to_freq['x']
	char_to_freq['i'] -= char_to_freq['x'] + char_to_freq['g'] + char_to_freq['f']
	for char, num in char_to_num.items():
		if char in char_to_freq and char_to_freq[char] > 0:
			for _ in range(char_to_freq[char]):
				res.append(num)
	res.sort()
	return ''.join(res)

算法分析：

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

Free mock interview