专栏首页Michael阿明学习之路LeetCode 368. 最大整除子集(DP)

LeetCode 368. 最大整除子集(DP)

1. 题目

给出一个由无重复正整数组成的集合,找出其中最大的整除子集,子集中任意一对 (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]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/largest-divisible-subset 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

类似题目:动态规划应用–最长递增子序列 LeetCode 300

  • 先排序,从后往前找能够整除的
  • 记录最大长度,同时记录最长的序列 前一个可以整除的 idx
  • 时间复杂度O(n2),空间复杂度O(n)
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        if(nums.empty()) return {};
    	sort(nums.begin(), nums.end());
    	int i, j, n = nums.size();
    	int maxlen = 1, maxlenid = 0;
    	vector<pair<int,int>> dp(n);//到该位置的最大长度,前一个idx
    	for(i = 0; i < n; ++i)
    		dp[i] = make_pair(1, -1);
    	for(i = 1; i < n; ++i)
    	{
    		for(j = i-1; j >= 0; --j)
    		{
    			if(nums[i]%nums[j] == 0 && dp[j].first+1 > dp[i].first)
    			{
    				dp[i].first = dp[j].first + 1;//最大长度
    				dp[i].second = j;//前一个数的idx
    			}
    		}
    		if(dp[i].first > maxlen)
    		{
    			maxlen = dp[i].first;//最大长度
    			maxlenid = i;//最大长度的结束数字
    		}
    	}
    	vector<int> ans(maxlen);
    	ans[maxlen-1] = nums[maxlenid];//最后一个数字
    	for(i = maxlen-2; i >= 0; --i)
    	{
    		ans[i] = nums[dp[maxlenid].second];//前一个数字
    		maxlenid = dp[maxlenid].second;//向前递推
    	}
    	return ans;
    }
};

52 ms 8.7 MB

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 697. 数组的度

    给定一个非空且只包含非负数的整数数组 nums 数组的度的定义是指数组里任一元素出现频数的最大值

    Michael阿明
  • LeetCode 462. 最少移动次数使数组元素相等 II(数学)

    给定一个非空整数数组,找到使所有数组元素相等所需的最小移动数,其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。

    Michael阿明
  • 程序员面试金典 - 面试题 16.17. 连续数列(DP/分治)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/contiguous-sequence-lcci 著...

    Michael阿明
  • LeetCode---两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    TrueDei
  • LeetCode 324. Wiggle Sort II

    这道题目很有意思,有意思的是使用O(n)的时间效率和O(1)的空间效率解决。我会写一篇专业的博客来介绍一下

    ShenduCC
  • leetcode158|数组中的k-diffs数对

    给定一个整数数组和一个整数 k,你需要在数组里找到不同的 k-diff 数对,并返回不同的 k-diff 数对 的数目。

    码农王同学
  • LeetCode 219: 存在重复元素 II Contains Duplicate II

    给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的绝对值最大为...

    爱写bug
  • 【leetcode刷题】T162-打家劫舍 II

    你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有...

    木又AI帮
  • 442. Find All Duplicates in an Array

    Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appe...

    luozhiyun
  • leetcode 16 3Sum Closest

    @坤的

扫码关注云+社区

领取腾讯云代金券