首页 > 代码库 > Leetcode 368. Largest Divisible Subset
Leetcode 368. Largest Divisible Subset
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.
If there are multiple solutions, return any subset is fine.
Example 1:
nums: [1,2,3] Result: [1,2] (of course, [1,3] will also be ok)
Example 2:
nums: [1,2,4,8] Result: [1,2,4,8]
这种类似求最大值的题一般用DP来解。首先排序,这样就可以只验证后面的数是不是可以整除前面的数。用DP list来保存从一开头到当前这个数字的最长subset的长度,但是由于本题需要返回的是一个list,我们用pre来保存在当前最长subset中上一个元素的位置。
1 class Solution(object): 2 def largestDivisibleSubset(self, nums): 3 """ 4 :type nums: List[int] 5 :rtype: List[int] 6 """ 7 nums.sort() 8 n = len(nums) 9 if n == 0: 10 return [] 11 elif n ==1: 12 return nums 13 dp = [1]*n 14 pre = [None]*n 15 16 for i in range(n): 17 for j in range(i): 18 if nums[i]% nums[j] == 0 and dp[j] +1 > dp[i]: 19 dp [i] = dp[j] + 1 20 pre[i] = j 21 22 idx = dp.index(max(dp)) 23 ans = [] 24 while idx is not None: 25 ans.append(nums[idx]) 26 idx = pre[idx] 27 return ans
Leetcode 368. Largest Divisible Subset
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。