Leetcode 368. Largest Divisible Subset

题目链接:368. Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.
If there are multiple solutions, return any subset is fine.
  题目意思也很简单,给出一个不含重复数字的数组,找到最长的一个子数组,子数组里的元素必须两两整除。

  这里有个很简单的数学性质,就是整除的传递性,如果a%b==0 且 b%c == 0,那么a%c == 0,说白了如果c是b的因子,b又是a的因子,那么c肯定是a的因子。这样我们就可以在数组中找出很多整除链(a->b->c->d,其中b是a的因子,c是b的因子,d是c的因子),这样的链条就满足两两整除的条件,题目就变成了求最长的链条。
  先上代码,然后我再解释下我的代码。

<code>import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List&lt;Integer&gt; largestDivisibleSubset(int[] nums) {
        List&lt;Integer&gt; ret = new ArrayList&lt;Integer&gt;();
        if (nums.length &lt; 2) {
            if (nums.length == 0)
                return ret;
            ret.add(nums[0]);
            return ret;
        }
        Arrays.sort(nums);
        int[] prefactors = new int[nums.length];
        int[] factorcount = new int[nums.length];
        int maxlength = 0;
        int maxnum = 0;
        for (int i = nums.length-1; i &gt;= 0; i--) {
            for (int j = i; j &lt; nums.length; j++) {
                if (nums[j]%nums[i] == 0 &amp;&amp; factorcount[i] &lt; factorcount[j]+1) {
                    factorcount[i] = factorcount[j]+1;
                    prefactors[i] = j;
                    if (factorcount[i] &gt; maxlength) {
                        maxlength = factorcount[i];
                        maxnum = i;
                    }
                }
            }
        }

        for (int i = 0; i &lt; maxlength; i++) {
            ret.add(nums[maxnum]);
            maxnum = prefactors[maxnum];
        }
        return ret;
    }
}
</code>

  首先我先对nums排序,这里我用了两个数组prefactors[]和factorcount[],prefactors[i]里其实保存的是以nums[i]未结尾的整除链前面一个数的下标,factorcount[i]存的是以nums[i]结尾的整除链长度。这里我们就可以用动态规划的方式求出factorcount[i]的值了,取最大的一个,然后再根据prefactors[i]推算出整除链中所有的元素。
  
  这里开两个脑洞,发散下思维。

脑洞1:

  其实所有整除链可以合并为一个多叉整除树,这里得增加一个额外的根节点,使得根节点可以被nums中任何一个数整除。这个整除树有个很重要的性质——除根节点以为任意节点可以整除其父节点。 这道题就会演变成求整除树中最深的路径。 对于树的问题,我们往往能用递归的方式解决,代码也会变得比较好理解。

脑洞2:

  看下代码,是不是很像01背包,其实我觉得这到题可以认为是带限制条件的01背包,限制条件可以简化为放入背包的数必须能整除背包中最小的一个数,背包为无穷大,每个数的价值为1。

打赏

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.