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问题,在这里。在通过最大长度来递归出子集中的元素。
Leetcode--Java--368. 最大整除子集

  1. 因此只要保证集合中所有相邻的两个数具有倍数关系,那么整个集合就具有这种倍数关系。
  2. 状态表示以及转化,f[i]表示以i结尾的最大整除子集的长度,考虑倒数第二个数j的取法,有0~i - 1种情况来选。
    Leetcode--Java--368. 最大整除子集
  3. 上面求出取子集最大值的下标后,倒着递归集合中的元素。根据集合的含义,f[k]表示是在第k个数选到了最大值。 如果f[k] = 1表示推到了第一个数,没有别的数了。就break。再看k是由哪个子集转移过来的。
  4. 由于不清楚子集的个数,先不断循环。

代码

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;

    }
}
上一篇:在GNU / Linux系统上,应该从哪里加载应用程序数据?


下一篇:PHP安装swoole扩展