【JavaScript】Leetcode每日一题-最大整除子集

时间:2023-03-09 00:28:35
【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每日一题-最大整除子集