仅供自己学习记录

LeetCode刷题日记2021-4-23

题目描述：

给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：

• answer[i] % answer[j] == 0 ，或
• answer[j] % answer[i] == 0

如果存在多个有效解子集，返回其中任何一个均可。

示例 1：

输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。

示例 2：

输入：nums = [1,2,4,8]
输出：[1,2,4,8]

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 2 * 109
nums 中的所有整数 **互不相同**

题解思路

对于满足题解要求的结果中 任意大的数必定是小的数的倍数

定义 f[i] 为考虑前i个数字，且以第i个数字为结尾的最长整除子集的长度

考虑i有两种情况：

• 在i之前找不到符合条件nums[i]%nums[j]==0的位置j 那么num[i]就只能自己作为整除子集的第一个数了
• 在i之前可以找到符合条件的位置j 则取所有符合条件的f[j]的最大值，代表如果希望找到以num[i]为结尾的最长整除子集将nums[i]接到符合条件的最长的num[j]后面 此时状态转移方程为f[i]=f[j]+1

同时需要定义一个新的数组g 来记录每个状态是由哪个状态转移过来的

定义 g[i] 为记录 f[i] 是由哪个下标的状态转移而来，如果 f[i] = f[j] + 1, 则有 g[i] = j。

题解代码

nums.sort()
n=len(nums)
f,g=[0]*n,[0]*n
for i in range(n):
至少为自身的一个数 起始长度为1 由自身转移而来
length,prev=1,i
for j in range(i):
if nums[i]%nums[j]:
如果可以接在更长的后面则更新最大长度和由何转移
if f[j]+1>length:
length=f[j]+1
prev=j
f[i]=length
g[i]=prev
max_len,ind=-1,-1
for i in range(n):
if
f[i]>max_len:
ind=i
max_len=f[i]
ans=[]
while len(ans)<max_len:
ans.append(num[ind])
ind=g[ind]
ans.reverse()
return ans

来源
https://leetcode-cn.com/problems/largest-divisible-subset/solution/gong-shui-san-xie-noxiang-xin-ke-xue-xi-0a3jc/

最后

以上就是细腻小鸽子为你收集整理的LeetCode刷题日记2021-4-23/368. 最大整除子集/动态规划解决问题LeetCode刷题日记2021-4-23的全部内容，希望文章能够帮你解决LeetCode刷题日记2021-4-23/368. 最大整除子集/动态规划解决问题LeetCode刷题日记2021-4-23所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。