Leetcode【56、670】

问题描述：【Sort】56. Merge Intervals

解题思路：

这道题是给一个区间集合，合并所有重叠区间。

首先可以想到按照区间的起始点进行升序排序。假设合并后的区间保存在数组 ans 中。从左到右遍历各个区间 interval，会有以下 3 种情况：

• ans = [[...], [...], [5, 9]]，interval = [6, 10]，因为 6 <= 9 并且 10 >= 9，因此有重叠部分，可以合并，只需要修改 ans 最后一个区间的终止点为 10 即可。
• ans = [[...], [...], [5, 9]]，interval = [10, 12]，因为 10 > 9，因此没有重叠部分，不能和前一个区间合并，需要在 ans 中添加 interval 即可。
• ans = [[...], [...], [5, 9]]，interval = [6, 8]，属于完全覆盖的情况，不需要进行任何操作。

这样，只需要遍历一次，就可以得到答案。时间复杂度主要来自于排序的开销 O(nlogn)，空间复杂度为 O(n)。

Python3 实现：

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        lens = len(intervals)
        if lens == 0: return []
        intervals.sort()  # 按照第一维升序，第一维相同按照第二维升序
        ans = [intervals[0]]
        for i in range(1, lens):
            interval = intervals[i]
            if interval[0] <= ans[-1][1] and interval[1] >= ans[-1][1]:
                ans[-1][1] = interval[1]
            elif interval[1] > ans[-1][1]:
                ans.append(interval)
        return ans

---

问题描述：【Greedy、Brute Force】670. Maximum Swap

解题思路：

这道题是给一个非负整数，对其中的两个数位最多允许交换一次，返回最大数字。

方法 1（贪心思想）：

这道题观察一下规律就可以得到方法：

• 对于 2736、7236 这种，对于每个数字 i（外层循环），需要找到后面的 i+1, i+2, .. n 中比 i 大的最大数字（内层循环），交换即可；如果没有找到，则需要移动到下一位 i+1 继续寻找。因此这里是两层循环。
• 对于 1939 这种，对于数字 1，我们不仅要找到最大数字 9， 还要交换最后一个 9，因此在 i+1, i+2, .. n 中找比 i 大的最大数字时，要从后往前遍历，找最后一个最大的数字，和它进行交换（贪心思想）。
• 对于 9876，因为对于每个数字 i，都没有办法在 i+1, i+2, .. n 中找到比 i 大的最大数字，因此返回原数字就行。

时间复杂度为 O(n^2)，因为要把数字拆成列表一个一个判断，因此空间复杂度为 O(n)。

class Solution:
    def maximumSwap(self, num: int) -> int:
        nums = [int(i) for i in list(str(num))]
        for i in range(len(nums)):
            mval = mind = -1
            for j in range(len(nums)-1, i, -1):
                if nums[j] > mval:
                    mval = nums[j]
                    mind = j
            if nums[i] < mval:
                nums[i], nums[mind] = nums[mind], nums[i]
                break   
        res = 0
        for i in range(len(nums)):
            res = res * 10 + nums[i]
        return res

方法 2（暴力搜索）：

由于这道题最多只进行一次交换，因此可以双层循环，暴力每个交换位置 (i, j) 的所有情况，更新最大数字的结果进行。时间复杂度为 O(n^2)，空间复杂度为 O(n)。尽管是暴力，但是这种方法和方法 1 的执行时间差不多。

class Solution:
    def maximumSwap(self, num: int) -> int:
        nums = list(str(num))
        res = nums[:]  # 不交换
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                nums[i], nums[j] = nums[j], nums[i]  # 进行交换
                if nums > res: res = nums[:]  # 更新最大数字
                nums[i], nums[j] = nums[j], nums[i]  # 恢复，交换回来
        return int("".join(res))