打卡群刷题总结0930——最大整除子集
题目：368. 最大整除子集
链接：https://leetcode-cn.com/problems/largest-divisible-subset
给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。 如果有多个目标子集，返回其中任何一个均可。 示例 1: 输入: [1,2,3] 输出: [1,2] (当然, [1,3] 也正确) 示例 2: 输入: [1,2,4,8] 输出: [1,2,4,8]
解题：
1、dp问题。将数组排序，这道题就和【300. 最长上升子序列】非常类似，只是把判断条件换成nums[i] % nums[j]是否等于0，同时需要记录前一个元素进而生成子集。
梳理一下，主要步骤如下：
1）数组排序。
2）使用递推式生成dp数组及pre数组。
使用dp数组记录含当前元素的目标子集的元素个数，pre数组记录子集中该元素的上一个元素。
遍历数组，当nums[i] % nums[j]等于0时，如果dp[i] < dp[j] + 1，则dp[i] = dp[j] + 1，同时pre[i] = j。
3）生成目标子集。
得到dp数组最大元素所在下标index，通过在pre数组中迭代得到目标子集。
假设pre数组的默认值是-1，只要pre[index]不为-1，则添加到结果，同时，index = pre[index]。
代码
class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
if len(nums) == 0:
return []
nums.sort()
dp = [1] * len(nums)
pre = [-1] * len(nums)
# 先得到子集的长度
for i in range(1, len(nums)):
for j in range(i - 1, -1, -1):
if nums[i] % nums[j] == 0:
# 比dp[i]更大，则赋值
if dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
pre[i] = j
# 得到子集
last_index = dp.index(max(dp))
res = []
while last_index != -1:
res.append(nums[last_index])
last_index = pre[last_index]
return res PS：刷了打卡群的题，再刷另一道题，并且总结，确实耗费很多时间。如果时间不够，以后的更新会总结打卡群的题。
PPS：还是得日更呀，总结一下总是好的。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-10-01，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读