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

By Long Luo

Leetcode 42. 接雨水 题目如下：

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

42. 接雨水

给定$n$个非负整数表示每个宽度为$1$的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

![接雨水 1](https://www.longluo.me/assets/blog/images/leetcode/leetcode-42-trapping-rain-water.png)

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
 
提示：
n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

方法一： 按列求（木桶原理）

思路与算法：

很容易想到，装水的多少，根据木桶原理，只需要关注左边最高的木板和右边最高的模板中较矮的一个就够了，那么存储的水，等于两边木板的较小值减去当前高度的值。

1. 从左向右遍历数组：
   • 从当前元素向左扫描并更新：\(\text{max\_left}=\max(\text{max\_left}, \text{height}[j])\)
   • 从当前元素向右扫描并更新：\(\text{max\_right}=\max(\text{max\_right}, \text{height}[j])\)
2. 更新 \(\text{ans} += \min(\text{max\_left}, \text{max\_right}) - \text{height}[i]\) 。

代码如下所示：

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

public static int trap(int[] height) {
    if (height == null || height.length <= 2) {
        return 0;
    }

    int ans = 0;
    int len = height.length;
    for (int i = 1; i < len - 1; i++) {
        int maxRight = 0;
        int maxLeft = 0;
        for (int right = i; right < len; right++) {
            maxRight = Math.max(maxRight, height[right]);
        }

        for (int left = i; left >= 0; left--) {
            maxLeft = Math.max(maxLeft, height[left]);
        }

        ans += Math.min(maxLeft, maxRight) - height[i];
    }

    return ans;
}

复杂度分析：

• 时间复杂度：\(O(n^2)\) ，遍历每一列需要 \(n\)，找出左边最高和右边最高的木板加起来刚好又是一个 \(n\)，所以是 \(n^2\)。
• 空间复杂度：\(O(1)\) 。

方法二：按行求

思路与算法：

求第 \(i\) 层的水，遍历每个位置，如果当前的高度小于 \(i\)，并且两边有高度大于等于 \(i\) 的，说明这个地方一定有水，水就可以加 \(1\)。

如果求高度为 \(i\) 的水，首先用一个变量 \(water\) 保存当前累积的水，初始化为 \(0\)。从左到右遍历墙的高度，遇到 \(h \ge i\) 的时候，开始更新 \(water\) 。

第一次遇到已经开始计算时并且 \(h < i\) 的就把 \(water+1\) ，再次遇到 \(h \ge i\) 的，说明这个地方一定有水，就把 \(water\) 加到最终的答案 \(ans\) 里， \(water=0\) ， \(flag=false\) ，然后继续循环。

代码如下所示：

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

public static int trap_row(int[] height) {
    if (height == null || height.length <= 2) {
        return 0;
    }

    int ans = 0;
    int len = height.length;
    int maxHeight = 0;

    for (int x : height) {
        maxHeight = Math.max(maxHeight, x);
    }

    for (int i = 1; i <= maxHeight; i++) {
        boolean flag = false;
        int water = 0;
        for (int j = 0; j < len; j++) {
            if (flag && height[j] < i) {
                water++;
            }

            if (height[j] >= i) {
                ans += water;
                water = 0;
                flag = true;
            }
        }
    }

    return ans;
}

复杂度分析：

• 时间复杂度：\(O(maxHeight \times n)\)，其中 \(maxHeight\) 是数组元素的最大值。
• 空间复杂度：\(O(1)\)。

By Long Luo

1. 冒泡排序(Bubble Sort)

思路与算法：

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

public static int[] bubbleSort(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return nums;
    }

    int len = nums.length;
    for (int i = len - 1; i >= 0; i--) {
        boolean isSorted = true;
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                isSorted = false;
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
        if (isSorted) {
            break;
        }
    }

    return nums;
}

复杂度分析：

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

2. 选择排序(Select Sort)

思路与算法：

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

public static int[] selectSort(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return nums;
    }

    int len = nums.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (nums[j] < nums[i]) {
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
            }
        }
    }

    return nums;
}

复杂度分析：

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