Leetcode【75、153、795、945、1109】

问题描述：【Two Pointers】75. Sort Colors

解题思路：

颜色排序。给一个 012 数组，0、1、2 分别代表红色、白色和蓝色，将数组升序排序。要求只能遍历数组一次，并使用常量级的空间。

这道题的 Follow up 说可以使用计数排序，但是计数排序需要遍历两遍数组。那么怎么遍历一次使得数组有序呢？

因为这个数组只有 0、1、2 三个元素，因此可以使用双指针做法：

• 设一个指针 red 指向开头，blue 指向末尾，从左到右遍历数组位置 i；
• 如果遇到 0（红色），就交换最左边去，red 向后移动一次；如果遇到 2 （蓝色），就交换到最右边去，blue 向前移动一次；这样 1 就会被保留在最中间；
• 注意：当 2 （蓝色）交换完毕后，数组在 i 处要停留一次，因为还需要继续检查被 2 交换回来的数字（比如 2 和 2 交换，如果不停留，交换回来的 2 就永远不能交换到后面了）；但是当遇到 0（红色）就不需要停留（因为交换回来的是 0），直接向后就可以。
• 当 i 和 blue 相遇，说明所有的 0 和 1 都在 i 之前排好了，在 blue 之后都是 2，这时候结束遍历，得到的就是排序好的数组。

以 nums = [2,1,0,1,0,2] 为例：

• red 指向开头 nums[0] = 2，blue 指向末尾 nums[5] = 2，从左到右遍历；
• i = 0，碰到 2，nums[0] 和 nums[5] 交换，得到 [2,1,0,1,0,2]，blue 向前指向 nums[4] = 0，这时数组要在 i = 0 处停留一下（不然交换回来的 2 就永远交换不到后面了）；
• i = 0，碰到 2，nums[0] 和 nums[4] 交换，得到 [0,1,0,1,2,2]，blue 向前指向 nums[3] = 1，数组还在 i = 0 处停留；
• i = 0，碰到 0，nums[0] 和 nums[0] 交换，得到 [0,1,0,1,2,2]，red 向后指向 nums[1] = 1，数组向后滑动到 i = 1 处；
• i = 1，碰到 1，什么都不操作，数组向后滑动到 i = 2 处；
• i = 2，碰到 0，nums[1] 和 nums[2] 交换，得到 [0,0,1,1,2,2]，red 向后指向 nums[2] = 1，数组向后滑动到 i = 3 处；
• i 和 blue 相遇，结束，数组排序完毕。

这样，我们使用双指针，只遍历了一次数组，同时使用了常量级别的空间复杂度，就完成了排序，满足题意。

Python3 实现：

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        red, blue = 0, len(nums) - 1
        i = 0
        while i <= blue:
            if nums[i] == 0:  # 交换到前面
                nums[i], nums[red] = nums[red], nums[i]
                red += 1
            elif nums[i] == 2:  # 交换到后面
                nums[i], nums[blue] = nums[blue], nums[i]
                blue -= 1
                i -= 1  # 2交换到后面，数组在i处停留
            i += 1

---

问题描述：【Divide and Conquer、Binary Search】153. Find Minimum in Rotated Sorted Array

解题思路：

这道题是给一个按照升序排列的旋转数组，找到旋转有序数组的最小值。

很明显，要用 O(logN) 的算法去求解。因为旋转有序数组的特殊性，故能想到用分治和二分查找两种算法求解。

方法1（分治）：

1、比如 [3,4,5,1,2]、[4,5,1,2,3]，我们发现：对于中间的数字 nums[mid]，它左右两边不满足 nums[mid-1] < nums[mid] < nums[mid+1]，那么说明最小值肯定是在这相邻三个数之间，直接返回三个数中的最小值即可；
2、再比如 [5,1,2,3,4]、[1,2,3,4,5]、[2,3,4,5,1]，中间的数字满足 nums[mid-1] < nums[mid] < nums[mid+1]，那么最小值就在 nums[:mid] 或 nums[mid+1:] 之中，可以采取分治的算法在这两部分中找最小值；
3、递归函数还有一个出口，就是如果 len(nums) <= 2，直接返回 nums 中的最小值即可，防止进行 nums[mid-1] < nums[mid] < nums[mid+1] 比较时数组越界。

Python3 实现：

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if len(nums) <= 2:  # 最小值出口2
            return min(nums)
        mid = (len(nums) - 1) // 2  # 计算中间的坐标
        if nums[mid-1] < nums[mid] < nums[mid+1]:
            return min(self.findMin(nums[:mid]), self.findMin(nums[mid+1:]))  # 分治求解
        else:
            return min(nums[mid-1], nums[mid], nums[mid+1])  # 最小值出口1

方法1（二分查找）：

二分查找的思想是每次中间的数字和最后一个数字比较。如果 nums[mid] < nums[high]，说明最小值在 nums[:mid+1] 中，更新 high 为 mid；如果 nums[mid] > nums[high]，说明最小值在 nums[mid+1:] 中，更新 low 为 mid + 1；最后 nums[low] 就是最小值。**

举例，nums = [5,6,1,2,3,4]，low = 0，high = 5，mid = 2

• nums[mid] < nums[high]，则 high = mid = 2，mid = 1；
• nums[mid] > nums[high]，则 low = mid + 1 = 2；
• 不满足 low < high，退出，nums[low] = 1 就是最小值。

Python3 实现：

class Solution:
    def findMin(self, nums: List[int]) -> int:
        low, high = 0, len(nums) - 1
        while low < high:
            mid = low + (high - low) // 2
            if nums[mid] < nums[high]:  # [5,6,1,2,3,4] -> high = mid
                high = mid
            elif nums[mid] > nums[high]:
                low = mid + 1
        return nums[low]

---

问题描述：【Math】795. Number of Subarrays with Bounded Maximum

解题思路：

这道题是给一个数组，求最大值大于等于 L 且小于等于 R 的连续子数组个数。

首先看了一下数据范围，采取 O(n^2) 的暴力求解方法肯定超时，排序又不行，因此只能使用 O(n) 的解法。又思考了 DP 发现貌似也不可行，因此就只能从数学上找找规律了。

以 A = [73,55,36,5,55,14,9,7,72,52]，L = 32，R = 69 为例：
1、因为是连续子数组，所以可以根据 A[i] > R 进行分段。以上述为例，可以分为 3 段，即 [73]、[55,36,5,55,14,9,7]、[72,52]；
2、以中间一段为例，共有 21 个符合题意的子数组。那么这个 21 是怎么计算得到的呢？首先，总共有 (1+7) * 7 // 2 = 28 个子数组，然后我们排除连续的 A[i] < L 的子数组个数，即 [5] 和 [14,9,7]，共有 1 + (1+3) * 3 // 2 = 7 个子数组，因此就得到了该段子数组的个数为 21；
3、每一段都进行这样的操作，就可以得到最终结果 ans = 0 + 21 + 1 = 22。

代码实现细节：

• 使用两个变量 cntLessR 和 cntLessL 分别记录小于等于 R 的连续子数组长度和小于 L 的连续子数组长度，对结果 ans 进行累加 cntLessR，同时累减 cntLessL；
• 如果 A[i] >= L，说明小于 L 的子数组不连续，则置 cntLessL 为 0； 如果 A[i] > R，说明小于等于 R 的子数组不连续，则置 cntLessR 为 0；

这种做法的时间复杂度为 O(N)，空间复杂度为 O(1)。

Python3 实现：

class Solution:
    def numSubarrayBoundedMax(self, A: List[int], L: int, R: int) -> int:
        ans = 0
        cntLessR = 0  # 记录小于R的连续子数组长度
        cntLessL = 0  # 记录小于L的连续子数组长度
        for i in range(len(A)):
            if A[i] <= R:  # 小于R的连续子数组个数累加
                cntLessR += 1
                ans += cntLessR
            if A[i] < L:  # 小于L的连续子数组个数累减
                cntLessL += 1
                ans -= cntLessL
            if A[i] >= L:  # 不连续，将cntLessL置0
                cntLessL = 0
            if A[i] > R:  # 不连续，将cntLessR置0
                cntLessR = 0
        return ans

---

问题描述：【Sort】945. Minimum Increment to Make Array Unique

解题思路：

这道题是给一个数组，每次移动可以把一个数字增加 1，最后使得数组元素都不同，求最小移动次数。

首先看了数据范围，O(n^2) 的暴力解法肯定会超时，先 pass。可以先对数组升序排序，然后使用一个变量保存当前不重复的数字已经增加到哪里了。所以，当下一个数字到来的时候，它应该增加到这个数字的位置，可以直接求出它需要移动的次数。

举个例子，A = [1,1,1,2,5,5]（已经排序），用 pre 记录不重复数字增加到了哪里，pre 初始化为 A[0]，即 pre = 1，用 ans 累加结果

• A[1] <= pre，说明 A[1] 要向后移动，则将 pre += 1 = 2，表示 A[1] 移动到 2 的位置，ans += pre - A[1] = 1；
• A[2] <= pre，说明 A[2] 要向后移动，则将 pre += 1 = 3，表示 A[2] 移动到 3 的位置，ans += pre - A[2] = 3；
• A[3] <= pre，说明 A[3] 要向后移动，则将 pre += 1 = 4，表示 A[3] 移动到 4 的位置，ans += pre - A[3] = 5；
• A[4] > pre，说明 A[4] 不需要向后移动，保持在自己的位置就好，但是要把 pre 更新到 pre = A[4] = 5，表示下一次从 5 开始移动；因为没有移动，ans 不变；
• A[5] <= pre，说明 A[5] 要向后移动，则将 pre += 1 = 6，表示 A[5] 移动到 6的位置，ans += pre - A[5] = 6；
• 结束，最少移动次数为 ans = 6。

Python3 实现：

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        N = len(A)
        if N == 0:
            return 0
        A.sort()  # 升序排序
        ans = 0
        pre = A[0]  # 记录当前不重复的数字已经增加到哪里了
        for i in range(1, N):
            if A[i] <= pre:
                pre += 1
                ans += pre - A[i]
            else:
                pre = A[i]
        return ans

---

问题描述：【DP】1109. Corporate Flight Bookings

解题思路：

这道题是给一个航班行程，每一项 (i, j, k) 表示在 [i, j] 之间预定 k 个座位。求每一时刻预定的座位数。

这道题和 Leetcode 【Greedy、DP、DP2】1094. Car Pooling 拼车问题以及 Leetcode 253：Meeting Rooms II（超详细的解法！！！） 几乎一模一样。刚开始使用 Leetcode 194 中的方法 2，结果超时，但是使用方法 3 不会超时。

Leetcode 1094 方法 3 的做法是对于每个区间，左加右减人数；而这道题也类似，不过根据题意，只有超过右端点才减，因为我们的统计要包括右端点。最后，循环 n 次，对于 dp[i] 进行累加即可得到各个时刻座位数。

时间复杂度和空间复杂度均为 O(N)。注意：dp 大小为 N + 2 而不是 N + 1，因为我们到 dp[i+1] 还要执行相减操作。

举个例子： bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5

• 对于 (1, 2, 10)，dp[1] += 10 = 10，dp[2+1] -= 10 = -10 （因为我们要统计右端点，所以要到 dp[3] 才执行相减操作）；
• 对于 (2, 3, 20)，dp[2] += 20 = 20，dp[3+1] -= 20 = -20；
• 对于 (2, 5, 25)，dp[2] += 25 = 45，dp[5+1] -= 45 = -45；
• 循环 n 次，累加，ans[1] = dp[1] = 10，ans[2] = dp[1] + dp[2] = 55，ans[3] = dp[1] + dp[2] + dp[3] = 45，ans[4] = dp[1] + dp[2] + dp[3] + dp[4] = 25，ans[5] = dp[1] + dp[2] + dp[3] + dp[4] + dp[5] = 25。
• 最终答案为 ans = [10, 55, 45, 25, 25]。

Python3 实现：

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        dp = [0] * 20002
        for (i, j, k) in bookings:
            dp[i] += k
            dp[j+1] -= k  # 右端点要包括在内，所以到j+1时再减
        cnt = 0
        ans = []
        for i in range(1, n + 1):
            cnt += dp[i]
            ans.append(cnt)
        return ans