Leetcode--Java--368. 最大整除子集
2021/12/15 11:17:01
本文主要是介绍Leetcode--Java--368. 最大整除子集,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
给你一个由 无重复 正整数组成的集合 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]
思路
贪心(先排序) + 整除具有传递性 + 动态规划(序列dp)
本题可以转化为先求最大子集的长度,先排序,根据求最长上升子序列的dp问题,在这里。在通过最大长度来递归出子集中的元素。
- 因此只要保证集合中所有相邻的两个数具有倍数关系,那么整个集合就具有这种倍数关系。
- 状态表示以及转化,f[i]表示以i结尾的最大整除子集的长度,考虑倒数第二个数j的取法,有0~i - 1种情况来选。
- 上面求出取子集最大值的下标后,倒着递归集合中的元素。根据集合的含义,f[k]表示是在第k个数选到了最大值。 如果f[k] = 1表示推到了第一个数,没有别的数了。就break。再看k是由哪个子集转移过来的。
- 由于不清楚子集的个数,先不断循环。
代码
class Solution { public List<Integer> largestDivisibleSubset(int[] nums) { Arrays.sort(nums); int n = nums.length; int k = 0; int f[] = new int[n]; for (int i = 0; i < n; i ++ ) { f[i] = 1; for (int j = 0; j < i; j ++ ) { if (nums[i] % nums[j] == 0) { f[i] = Math.max(f[i], f[j] + 1); } } //更新最长子集的结尾下标 if (f[i] > f[k]) { k = i; } } List<Integer> res = new ArrayList<>(); //由于不清楚多少个,先用不断循环,直到递推到dp数组长度为1就break while (true) { //先放入最后一个 res.add(nums[k]); if (f[k] == 1) { break; } //开始递推,看最后一个是由哪个子集转移过来的,不断向前递推 for (int i = 0; i < k; i ++ ) { if (nums[k] % nums[i] == 0 && f[k] == f[i] + 1) { k = i; break; } } } return res; } }
这篇关于Leetcode--Java--368. 最大整除子集的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行