admin管理员组

文章数量:1622542

LeetCode 368. Largest Divisible Subset

考点难度
DPMedium
题目

Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:

answer[i] % answer[j] == 0, or
answer[j] % answer[i] == 0

If there are multiple solutions, return any of them.

思路

从小到大排序，如果后面的数能整除前面的数，在前面的数的位置的后面加这个后面的数，然后和ans比较，保留更长的

答案
class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        
        nums.sort()
        ans = []
        dp = []
        
        for i in nums:
            dp.append([i])
        
        for i in range(len(nums)):
            
            for j in range(i):
                if nums[i]%nums[j] == 0 and len(dp[j])>=len(dp[i]):
                    dp[i] = dp[j]+[nums[i]]
                    
            if len(ans) < len(dp[i]):
                ans = dp[i]
                
                    
        return(ans)

本文标签： 知识点LeetCode

版权声明：本文标题：LeetCode知识点总结 - 368 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/xitong/1728871071a1177287.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。