Leetcode【435、452、738、991】

问题描述：【Greedy】435. Non-overlapping Intervals

解题思路：

这道题是给一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

实际上，这道题和 贪心算法之活动安排问题 很类似，贪心策略应该是每次选取结束时间最早的活动。直观上也很好理解，按这种方法选择相容活动为没有安排的活动留下尽可能多的时间。这也是把各项活动按照结束时间单调递增排序的原因。

到这道题中，我们求的是“不相容的活动”的数量。还是同样的做法，先按照右区间从小到大排序，然后遍历数组，找到重叠的区域（不相容的活动），将结果加 1；如果相容，指针向后移动。

Python3 实现：

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        N = len(intervals)
        ans = 0
        intervals.sort(key=lambda x: x[1])  # 按照结束时间升序
        i, j = 0, 1
        while i < N and j < N:
            if intervals[j][0] < intervals[i][1]:  # 有重叠，要删除一个
                ans += 1
            else:  # 不重叠
                i = j
            j += 1
        return ans

print(Solution().eraseOverlapIntervals([[1,100],[11,22],[1,11],[2,12]]))  # 2

问题描述：【Greedy】452. Minimum Number of Arrows to Burst Balloons

解题思路：

这道题实际上是给一个气球区间的集合，求用最少数量的箭引爆所有气球。

我们的目的是用最少的箭来引爆所有气球，因此我们要尽量保证一支箭能穿过足够多的气球区间。其实，这道题和上面的 Leetcode 435 很类似，也属于活动时间安排问题。

因此，我们先按照右区间进行升序排列，遍历区间的过程中，左区间如果小于前面区间的右区间，说明两者有重叠；否则，说明需要增加一支箭来满足后面的区间。这种贪婪的思想可以保证尽量多的区间合并，因此能得到最少的箭数。

Python3 实现：

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        N = len(points)
        if N == 0:
            return 0
        points.sort(key=lambda x: x[1])
        ans = 1
        i, j = 0, 1
        while i < N and j < N:
            if points[j][0] > points[i][1]:  # 两者没有重叠，增加一支箭
                i = j
                ans += 1
            j += 1
        return ans

问题描述：【Math】738. Monotone Increasing Digits

解题思路：

这道题是给一个数字 N，找到小于等于 N 的单调递增数字。

这道题需要找规律，我们先全排列一下 148 看一下结果：

148 -> 148；184 -> 179；418 -> 399；481 -> 479；814 -> 799；841 -> 799

由上面可以发现规律：从左到右遍历每一位数字，找到第一个逆序对（如 481 的第一个逆序对是 (8, 1)）；然后，将逆序对的第一个位置处的数字减 1，后面补够 9；最后，答案为：逆序对前面的数字 + 逆序对位置处数字减 1 + 逆序对后面补够 9。

以 481 为例，做法如下：

• 使用两个指针 i 和 j，i 指向 4，j 指向 8；
• 因为 4 < 8，则 i 和 j 都向后移动，i 指向 8，j 指向 1；
• 因为 8 > 1，则找到第一个逆序对，8-1=7，后面补 9，最后得到答案 479。

注意：如果是 13555884 这种，结果应该为 13555799，但是按照上述规律会得到 13555879 的错误答案。因此，如果前面不是严格递增，i 不滑动（停留在第一个 8 的位置），只有 j 滑动（滑动到 4），这样我们就能定位第一个 8 的位置，从而得到正确答案。

Python3 实现：

class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        S = str(N)
        i, j = 0, 1
        while i < len(S) and j < len(S):
            if S[i] < S[j]:  # 如果严格递增，i和j都向后滑动
                i = j; j += 1
            elif S[i] == S[j]:  # 如果非严格递增，只有j向后滑动 
                j += 1
            else:  # S[i]>S[j]，即第一个逆序对位置
                return int(S[:i] + str(int(S[i]) - 1) + '9' * (len(S) - i - 1))
        return N

问题描述：【Math】991. Broken Calculator

解题思路：

这道题是给 X 和 Y，X 每次只能执行乘 2 或者减 1 操作，求得到 Y 所需的最少操作步数。

很明显，如果 X >= Y，那么 X - Y 就是最后的答案。对于 X < Y，刚开始想的是用广搜 BFS 求解： 从M走到N最少步数，但是由于 X 和 Y 的取值范围都为 10^9 次方，开辟一个 10^9 的空间会造成内存溢出（最大只能开 10^8 次方的空间大小）。

那么，这道题很明显不是这样求解的，具体怎么做呢？我们可以从下面的例子中观察到一些规律：

X = 3，Y = 8：3 -> 2 -> 4 -> 8；

X = 5，Y = 8：5 -> 4 -> 8；

X = 6，Y = 8：6 -> 5 -> 4 -> 8；

X = 7，Y = 8：7 -> 6 -> 5 -> 4 -> 8；

X = 7，Y = 9：7 -> 6 -> 5 -> 10 -> 9；

我们发现，可以使用逆向思维，即从 Y 到 X 去考虑。当 Y > X 时，如果 Y 为奇数，就执行加 1 操作；如果 Y 为偶数，就执行除以 2 操作。当 Y 变得比 X 小后（如 X = 7，Y = 9 中，Y 变成了 5 后，5 < X），再一步一步执行加 1 的操作，最终得到 X。

这是一种贪婪的思想，即每次考虑让 Y 先除以 2，不行的话再执行加 1 操作。时间复杂度为 O(log Y)，空间复杂度为 O(1)。

为什么这样会得到正确的答案？以下是证明，写得很清楚：坏了的计算器题解 。

Python3 实现：

class Solution:
    def brokenCalc(self, X: int, Y: int) -> int:
        ans = 0
        while Y > X:  # 从Y到X逆向思维考虑
            if Y % 2 == 1:  #Y为奇数+1
                Y += 1
            else:  #Y为偶数除以2
                Y //= 2
            ans += 1
        return ans + (X - Y)  # 最后还要加上X-Y，即Y<=X后，X一步一步到达Y