【JavaScript】Leetcode每日一题-最大整除子集
2021/4/23 14:25:36
本文主要是介绍【JavaScript】Leetcode每日一题-最大整除子集,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
【JavaScript】Leetcode每日一题-最大整除子集
【题目描述】
给你一个由 无重复 正整数组成的集合 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 * 10^9 nums 中的所有整数 互不相同
【分析】
-
思路:
可以根据代码理解。
具体请参见三叶姐姐题解。
-
/** * @param {number[]} nums * @return {number[]} */ var largestDivisibleSubset = function(nums) { nums.sort(function(a, b){return a>b?1:-1;}); //数组排序(从小到大,有序集 var len = nums.length; var dp = new Array(len).fill(0); //dp[i]表示从0到i包括第i+1个数时,最大集合 var back = new Array(len).fill(0); //back[i]用以回溯可属于同一集合的元素 for(var i=0;i<len;i++){ //赋值dp[i] var max = 1, pre = i; for(var j=0;j<i;j++){ //遍历i前元素,寻找满足的最大dp[j],并记录下来用以回溯 if(dp[j]+1 > max && nums[i] % nums[j] == 0){ max = dp[j]+1; pre = j; } } dp[i] = max; back[i] = pre; } var maxIndex = 0, max = 0; for(var i=0;i<len;i++){ //遍历dp,寻找最大集合 if(dp[i] > max){ maxIndex = i; max = dp[i]; } } var ans = new Array(max); for(var i=0;i<max;i++){ //回溯,寻找最大集合元素 ans[i] = nums[maxIndex]; maxIndex = back[maxIndex]; } return ans; };
这篇关于【JavaScript】Leetcode每日一题-最大整除子集的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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漏洞挖掘-有意思的命令执行