LeetCode_动态规划_中等_368.最大整除子集

x33g5p2x  于2022-08-17 转载在 其他  
字(1.1k)|赞(0)|评价(0)|浏览(358)

1.题目

给你一个由 无重复 正整数组成的集合 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 * 109
nums 中的所有整数互不相同

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/largest-divisible-subset

2.思路

(1)动态规划
思路参考该 LeetCode 用户题解

3.代码实现(Java)

//思路1————动态规划
class Solution {
    public static List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> res = new ArrayList<>();
        Arrays.sort(nums);
        int length = nums.length;
        // f[i] 表示数组 nums 中以第 i 个数结尾的最长整除子集的长度
        int[] f = new int[length];
        // g[i] 记录 f[i] 是由哪个下标的状态转移而来,如果 f[i] = f[j] + 1, 则有 g[i] = j
        int[] g = new int[length];
        for (int i = 0; i < length; i++) {
            int len = 1, prev = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    if (f[j] + 1 > len) {
                        len = f[j] + 1;
                        prev = j;
                    }
                }
            }
            //记录最终长度和从何转移而来
            f[i] = len;
            g[i] = prev;
        }
        //遍历所有的 f[i],取得最大长度和对应下标
        int max = -1, idx = -1;
        for (int i = 0; i < length; i++) {
            if (f[i] > max) {
                idx = i;
                max = f[i];
            }
        }
        //使用数组 g 回溯出具体方案
        while (res.size() != max) {
            res.add(nums[idx]);
            idx = g[idx];
        }
        return res;
    }
}

相关文章

微信公众号

最新文章

更多