题目描述:
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]
题目大意:
给定一个不重复正整数集合,寻找最大子集,使得子集中的任意一对元素 (Si, Sj) 均满足Si % Sj = 0或者Sj % Si = 0。
如果存在多种答案,返回其中之一即可。
测试用例如题目描述。
解题思路:
动态规划(Dynamic Programming)
状态转移方程:
dp[x] = max(dp[x], dp[y] + 1) 其中: 0 <= y < x 且 nums[x] % nums[y] == 0
返回结果利用辅助数组pre记录
Python代码:
class Solution(object):
def largestDivisibleSubset(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
nums = sorted(nums)
size = len(nums)
dp = [1] * size
pre = [None] * size
for x in range(size):
for y in range(x):
if nums[x] % nums[y] == 0 and dp[y] + 1 > dp[x]:
dp[x] = dp[y] + 1
pre[x] = y
idx = dp.index(max(dp))
ans = []
while idx is not None:
ans += nums[idx],
idx = pre[idx]
return ans
一种简短的解法,来自LeetCode Dicuss:https://leetcode.com/discuss/110905/4-lines-in-python
Python代码:
class Solution(object):
def largestDivisibleSubset(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
S = {-1: set()}
for x in sorted(nums):
S[x] = max((S[d] for d in S if x % d == 0), key=len) | {x}
return list(max(S.values(), key=len))
本文链接:http://bookshadow.com/weblog/2016/06/27/leetcode-largest-divisible-subset/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。