By Long Luo

Leetcode 299. 猜数字游戏 。

方法一：HashMap –> Array

思路与算法：

首先，\(\textit{Bulls}\) 最好计算，遍历，如果相同，那么 \(Bulls+1\)。但是 \(\textit{Cows}\) 如何计算呢？

1. 首先想到的是使用 \(\texttt{HashMap}\) 来记录数字及其出现次数，因为可能会出现多个数字，所以出现位置是没有办法记录的；
2. 遇到 \(\textit{Cows}\)，则 \(2\) 个 \(HashMap\) 都减去相应数字；
3. 最后遍历 \(0 \to 9\)，如果 \(2\) 个 \(\texttt{HashMap}\) 都大于 \(0\) ，那么把较小数相加即得到 \(\textit{Cows}\)。

代码如下所示：

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 String getHint(String secret, String guess) {
	int len = secret.length();
	int bulls = 0;
	int cows = 0;
	Map<Integer, Integer> secretMap = new HashMap<>();
	Map<Integer, Integer> guessMap = new HashMap<>();
	for (int i = 0; i < len; i++) {
		int secVal = secret.charAt(i) - '0';
		int guessVal = guess.charAt(i) - '0';
		secretMap.put(secVal, secretMap.getOrDefault(secVal, 0) + 1);
		guessMap.put(guessVal, guessMap.getOrDefault(guessVal, 0) + 1);
		if (secVal == guessVal) {
			bulls++;
			secretMap.put(secVal, secretMap.getOrDefault(secVal, 0) - 1);
			guessMap.put(guessVal, guessMap.getOrDefault(guessVal, 0) - 1);
		}
	}

	for (int i = 0; i <= 9; i++) {
		int secFreq = secretMap.getOrDefault(i, 0);
		int guessFreq = guessMap.getOrDefault(i, 0);
		if (secFreq > 0 && guessFreq > 0) {
			cows += Math.min(secFreq, guessFreq);
		}
	}

	return bulls + "A" + cows + "B";
}

上述代码其实可以优化，因为 \(\textit{map}\) 中的 \(\textit{key}\) 只有 \(0 \to 9\)，所以我们可以用数组取代 \(\textit{map}\) 以节省空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public String getHint(String secret, String guess) {
	int len = secret.length();
	int bulls = 0;
	int cows = 0;
	int[] secNums = new int[10];
	int[] gusNums = new int[10];
	for (int i = 0; i < len; i++) {
		int secVal = secret.charAt(i) - '0';
		int guessVal = guess.charAt(i) - '0';
		secNums[secVal]++;
		gusNums[guessVal]++;
		if (secVal == guessVal) {
			bulls++;
			secNums[secVal]--;
			gusNums[guessVal]--;
		}
	}

	for (int i = 0; i <= 9; i++) {
		cows += Math.min(secNums[i], gusNums[i]);
	}

	return bulls + "A" + cows + "B";
}

复杂度分析

• 时间复杂度：\(O(N)\)，其中 \(N\) 是字符串的长度。
• 空间复杂度：\(O(C)\)，需要常数个空间统计字符出现次数，由于我们统计的是数字字符，\(C=10\)。

By Long Luo

Leetcode 598. 范围求和 II。

方法一： 模拟

思路与算法：

首先按照题意，对矩阵进行操作，最后遍历矩阵看最大的数有几个即可。

而最大的值显然是 \(M[0][0]\)。

代码如下所示：

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 maxCount(int m, int n, int[][] ops) {
	if (ops == null || ops.length == 0 || ops[0].length == 0) {
		return m * n;
	}

	int ans = 0;
	int[][] mat = new int[m][n];
	for (int[] op : ops) {
		int row = op[0];
		int col = op[1];
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				mat[i][j]++;
			}
		}
	}

	int maxVal = mat[0][0];
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (maxVal == mat[i][j]) {
				ans++;
			}
		}
	}

	return ans;
}

复杂度分析

• 时间复杂度：\(O(km^2n^2)\)，其中 \(k\) 是数组 \(\textit{ops}\) 的长度。
• 空间复杂度：\(O(mn)\)，需要创建一个新的二维数组。

方法二： 找到所有操作的交集

思路与算法：

方法一显然会超时，而且因为我们只需要找到最大值的个数，而有满足要求的次数恰好等于操作次数的位置。

我们只需要找到所有操作中的最小值。

代码如下所示：

By Long Luo

Leetcode 268. 丢失的数字 的题解，English version is 4 Approaches: Sorting, Hash, XOR, Math 。

方法一：暴力 + 排序

思路与算法

这是一道简单题。首先想到的方法是先进行排序，然后遍历数组，找到值不同的那个数字，如果都相同，那么结果就是 \(len\)。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11

public int missingNumber(int[] nums) {
	int len = nums.length;
	Arrays.sort(nums);
	for (int i = 0; i < len; i++) {
		if (i != nums[i]) {
			return i;
		}
	}

	return len;
}

复杂度分析：

• 时间复杂度：\(O(n \log n)\)，其中 \(n\) 是数组 \(\textit{nums}\) 的长度。排序的时间复杂度是 \(O(n \log n)\)，遍历数组寻找丢失的数字的时间复杂度是 \(O(n)\)，因此总时间复杂度是 \(O(n \log n)\)。
• 空间复杂度：\(O(\log n)\)，其中 \(n\) 是数组 \(\textit{nums}\) 的长度。空间复杂度主要取决于排序的递归调用栈空间。

方法二：HashSet

可以使用一个 \(\texttt{HashSet}\) 来记录数组中出现的数，将时间复杂度降低为 \(O(n)\)。

首先遍历数组 \(\textit{nums}\)，记录数组中的每个元素，然后检查从 \(0\) 到 \(n\) 的每个整数是否在哈希集合中，不在哈希集合中的数字即为丢失的数字。由于哈希集合的每次添加元素和查找元素的时间复杂度都是 \(O(1)\)，因此总时间复杂度是 \(O(n)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public static int missingNumber_set(int[] nums) {
	int len = nums.length;
	Set<Integer> set = new HashSet<>();
	for (int i = 0; i < len; i++) {
		set.add(nums[i]);
	}

	for (int i = 0; i <= len; i++) {
		if (set.add(i)) {
			return i;
		}
	}

	return len;
}

复杂度分析：

• 时间复杂度：\(O(n)\)
• 空间复杂度：\(O(n)\)

By Long Luo

Leetcode 1218. 最长定差子序列 题目如下：

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

1218. 最长定差子序列

给你一个整数数组arr和一个整数difference，请你找出并返回arr中最长等差子序列的长度，该子序列中相邻元素之间的差等于difference。

子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从arr派生出来的序列。

示例 1：
输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是[1,2,3,4]。

示例 2：
输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。

示例 3：
输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是[7,5,3,1]。

提示：
1 <= arr.length <= 10^5
-10^4 <= arr[i], difference <= 10^4
 
进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

方法一：暴力

思路与算法：

首先想到的是暴力法，在第二个循环中寻找构成等差数列的数字并更新长度，找到最大长度。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public int longestSubsequence(int[] arr, int difference) {
    int len = arr.length;
    int ans = 1;
    for (int i = 0; i < len; i++) {
        int value = arr[i];
        int cnt = 1;
        for (int j = i + 1; j < len; j++) {
            if (arr[j] == value + difference) {
                cnt++;
                value = arr[j];
            }
        }

        ans = Math.max(ans, cnt);
    }

    return ans;
}

复杂度分析：

• 时间复杂度：\(O(N^2)\) ，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
• 空间复杂度：\(O(1)\)。

By Long Luo

Leetcode 407. 接雨水 II 题目如下：

407. 接雨水 II

给你一个 \(m \times n\) 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

示例 1:

输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 输出: 4 解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。

示例 2:

输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]] 输出: 10

提示: m == heightMap.length n == heightMap[i].length 1 <= m, n <= 200 0 <= heightMap[i][j] <= 2 * 10^4

这道题是 42. 接雨水 的3D版本，区别于2D版本只需要维护左右两个最高的木板，这里需要维护一个围栏，用堆（优先队列）来维护周围这个围栏中的最小元素。

方法一：优先队列 + 最小堆

思路与算法：

因为需要维护一个圈，用来存储水，所以需要从矩阵的最外围往里面遍历，不断缩小圈，直到遍历每个方块，在这个过程中计算每个方块能装多少水，更新 \(\textit{ans}\) 。

那么什么方块能存水呢？

• 该方块不是在圈外；
• 该方块高度比其上下左右四个相邻的方块接水后的高度都要低。

假设方块的索引为 \((i,j)\)，方块高度为 \(\textit{heightMap}[i][j]\)，方块接水后的高度为 \(\textit{water}[i][j]\)，则方块 \((i,j)\) 的接水后的高度为：

\[ \textit{water}[i][j] = \max( \textit{heightMap}[i][j], \min( \textit{water}[i-1][j], \textit{water}[i+1][j], \textit{water}[i][j-1], \textit{water}[i][j+1])) \]

每个方块 \((i,j)\) 实际接水量为：\(\textit{water}[i][j] - \textit{heightMap}[i][j]\)。

那问题变成了如何知道每个方块的 \(\textit{water}[i][j]\) 呢？

1. 因为最外层的方块无法接水，所以最外层的方块接水后的高度 \(\textit{water}[i][j]=\textit{heightMap}[i][j]\)；

2. 根据木桶原理，而每层水的高度则取决于每层方块中高度最低的方块；

3. 从矩阵的四周边界开始，则可以知道最外层方块接水后的高度最小值。之后遍历每层中的每个方块周围\(4\) 个方块，如果比当前方块低，那么说明这个方块可以接水，接水后的高度就是当前层的最小高度，反之更高的话，将其加入优先队列中；

4. 更新最外层的方块标记，在新的最外层的方块再次找到接水后的高度的最小值，依次迭代直到求出所有的方块的接水高度，即可知道矩阵中的接水容量。