Leetcode【368、986】

问题描述：【DP】368. Largest Divisible Subset

解题思路：

最大可除子集。给一个包含不同数字的数组，找一个最大的子集，对于子集中的每个元素对 (Si, Sj) 满足 Si % Sj = 0 或者 Sj % Si = 0，返回这个子集。

首先可以想到，先对数组进行从小到大排序（这样的话我们只需要判断 Si % Sj = 0 即可，i > j）。这时候，这道题就和最长上升子序列问题 Leetcode 【DP】300. Longest Increasing Subsequence 几乎一样了，因此可以使用动态规划的方法求解。

在 Leetcode 300 中，用 dp[i] 表示以 i 位置结尾的最长上升子序列的长度；而这道题中，可以用 dp[i] 表示以 i 位置结尾的满足条件的最大子集的长度。因为这道题要返回的是最大子集（而不是最大子集的长度），因此我们还需要借助一个辅助数组 pre（初始值设为 -1，表示不可达），在每次更新最大子集长度的时候，用 pre 记录当前数的前一个位置的索引。当我们遍历完数组后，我们先在 dp 中找到最大子集长度的位置，然后再利用 pre 数组，从最大子集长度的位置开始，回溯前面保存的位置，直到回溯到位置值为 -1，就代表找到了这个子集中的所有数字。

举个例子：nums = [4, 8, 10, 240]（已经先升序排序）

• dp = [1,1,1,1] 表示每个单独的数字子集长度为 1， pre = [-1,-1,-1,-1] 表示不可达；
• 对于 nums[1] = 8，往前找：8 % 4 == 0，因此 dp[1] = dp[0] + 1 = 2，并且更新 pre[1] = 0，表示 nums[1] = 8 前面的数字是 nums[0] = 4；
• 对于 nums[2] = 10，往前找：10 % 8 != 0，10 % 4 != 0，因此 dp[2] 不变；
• 对于 nums[3] = 240，往前找：240 % 10 == 0，240 % 8 == 0，240 % 4 == 0，因此 dp[3] = max(dp[2], dp[1], dp[0]) = dp[1] + 1 = 3，并且更新 pre[3] = 1，表示 nums[3] = 240 前面的数字是 nums[1] = 8；
• 数组遍历结束，找到最大长度 max(dp) = 3，其位置也为 3；然后，利用 pre = [-1, 0, -1, 1]， pre[3] -> pre[1] -> pre[0]，找到 [240, 8, 4] 就是答案，返回即可。

因为每次都需要从位置 i 开始，遍历前面的数字 j < i，因此时间复杂度为 O(n^2)；空间复杂度为 O(n)。

Python3 实现：

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        if not nums:
            return []
        N = len(nums)
        nums.sort()  # 升序排序
        dp = [1] * N
        pre = [-1] * N  # 辅助数组，记录最大子集数字的索引
        for i in range(1, len(nums)):
            for j in range(i-1, -1, -1):  # 往前找
                if nums[i] % nums[j] == 0:  # 如果能整除
                    if dp[j] + 1 > dp[i]:  # 更新最大子集长度、用辅助数组记录前一个数的索引
                        dp[i] = dp[j] + 1
                        pre[i] = j
                    
        ind = dp.index(max(dp))  # 找到最大子集长度的索引
        ans = []
        while ind != -1:  # 利用辅助数组逆向查找最大子集中的所有数字，保存到ans中
            ans.append(nums[ind])
            ind = pre[ind]
        return ans

---

问题描述：【Two Pointers】986. Interval List Intersections

解题思路：

区间列表的交集。给定两个由一些闭区间组成的列表 A、B，每个区间列表都是成对不相交的，并且已经排序。返回这两个区间列表的交集。

首先，可以在纸上画出存在相交区域的 4 种情况：

因此，我们只需要两个指针 i 和 j，分别指向列表 A 和列表 B，只要存在图中条件，就产生一个相交区间加入到结果列表中。

接下来，还要考虑指针 i 和指针 j 何时移动到下一个位置。还是可以观察上图，只要 A1 <= B1，则 i 移动；否则 j 移动。

时间复杂度为 O(len(A) + len(B))。

Python3 实现：

class Solution:
    def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
        ans = []
        i = j = 0
        while i < len(A) and j < len(B):  # 双指针，4种情况
            if A[i][0] >= B[j][0] and A[i][1] <= B[j][1]:
                ans.append([A[i][0], A[i][1]])
            elif A[i][0] <= B[j][0] and A[i][1] >= B[j][1]:
                ans.append([B[j][0], B[j][1]])
            elif A[i][0] <= B[j][0] and A[i][1] >= B[j][0]:
                ans.append([B[j][0], A[i][1]])
            elif A[i][0] >= B[j][0] and A[i][0] <= B[j][1]:
                ans.append([A[i][0], B[j][1]])
            
            if A[i][1] <= B[j][1]:  # 下一个判断的区间
                i += 1
            elif A[i][1] >= B[j][1]:
                j += 1
            
        return ans

改进：

实际上，上述代码可以进一步优化，即上述 4 种存在相交区域的情况可以合并成一种，即判断 max(A0, B0) <= min(A1, B1)，如果为 True，则相交区域就是 [max(A0, B0), min(A1, B1)]。代码如下：

class Solution:
    def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
        ans = []
        i = j = 0
        while i < len(A) and j < len(B):
            left = max(A[i][0], B[j][0])
            right = min(A[i][1], B[j][1])
            if left <= right:  # 存在相交区域
                ans.append([left, right])
            
            if A[i][1] <= B[j][1]:  # 下一个判断的区间
                i += 1
            else:
                j += 1
        return ans