【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;
};