Leetcode 368.最大整除子集

Posted on |

368. 最大整除子集

题目

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。

如果有多个目标子集，返回其中任何一个均可。

1
2
3
4
5
6
7
8
示例 1:

输入: [1,2,3]
输出: [1,2] (当然, [1,3] 也正确)
示例 2:

输入: [1,2,4,8]
输出: [1,2,4,8]

方法

方法1：动态规划

dp[i]：表示nums[:i+1]的最长整除子集
pre[i]：表示nums[:i+1]的最长整除子集中前一个数的位置
dp[0]=1,pre[0]=-1

i>j>k, i % j = 0，j % k = 0, 那么i % k = 0.所以给了dp状态转移的思路

如果a%b==0，则a=mb，所以如果把数组排序后如果a%b==0，且b%c==0则a%c==0。这就为用动态规划实现提供了可能性。设置一个数组result，result[i]表示i出包含的满足条件的子集个数。则如果nums[i]%nums[j]==0，则result[i]=result[j]+1;同时由于函数要返回的是一个List，所以我们要保存最长集合的路径。这个功能可以通过设置一个pre数组保存能被nums[i]整除的上一个数的索引。并在保存max值的同时保存max所在的位置maxIndex即可

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
class Solution(object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums:
            return []
        n=len(nums)
        nums.sort()
        dp=[1]*n ##表示集合元素个数,初始是1，表示至少自己单独成为合法的集合
        pre=[-1]*n

        for i in range(1,n):
            for j in range(i):
                if nums[i]%nums[j]==0:
                    if dp[j]+1>dp[i]:
                        dp[i]=dp[j]+1
                        pre[i]=j

        max_index=dp.index(max(dp))
        ans=[]
        while max_index!=-1:
            ans.append(nums[max_index])
            max_index=pre[max_index]
        return ans

输入是[2,3,8,9,27]
dp=[1]*n所得的dp=[1, 1, 2, 2, 3]，这是正确的
dp=[0]*n dp[0]=1所得的dp=[1, 0, 2, 1, 2]，这是错误的。
当数组里无法组成任何一个整除子集，dp=1