[LeetCode] 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.

Example 1:

Input: [1,2,3]
Output: [1,2] (of course, [1,3] will also be ok)

Example 2:

Input: [1,2,4,8]
Output: [1,2,4,8]

最大整除子集。题意是给一个整数数组,请你找出最长的一个子串,子串满足任意两个数之间可以互相整除,即任意两个数之间互相整除的时候余数为0。比如两个数A和B好了,A%B = 0或者B%A = 0都可以满足题意。

思路是DP动态规划。这个题的思路跟300题很像。一个写的很好的帖子。首先,两个不同的数字A和B,既然不同,那么一定一大一小,那么一定意味着小的除以大的的余数一定不为0。题目既然规定了A%B = 0或者B%A = 0都可以满足题意,我们可以先将input从小到大排序。这样扫描数组的时候可以从当前位置往前看,看当前数字nums[i]是否可以整除比他小的数字。

接着创建一个数组count[i],记录的是以nums[i]结尾的,最长的满足题意的子串的长度。这个数组count[i]初始化的时候每个位置都是1,因为每个数字除以他本身的余数都为0。接着会用到两个for loop,一个是遍历nums数组,一个是将nums[i]去跟比他自己小的所有的数字都去做一下除法,看看有多少数字能跟nums[i]相除 == 0。此时count[i]数组会被改写。

接着再次扫描count[i]数组,找出最大值maxIndex。这个最大值是最长的子串的长度。同时找到的最大值背后的nums[maxIndex],也是这个子串的最后一个元素。

最后一步是从nums[maxIndex]开始往前扫描,如果遇到任何一个数字能被nums[maxIndex]整除,则把这个数字加入结果集。

时间O(n^2)

sort - O(nlogn)

扫描,写入count[i]的值 - O(n^2)

空间O(n)

Java实现

 1 class Solution {
 2     public List<Integer> largestDivisibleSubset(int[] nums) {
 3         List<Integer> res = new ArrayList<>();
 4         int n = nums.length;
 5         if (n == 0) {
 6             return res;
 7         }
 8         Arrays.sort(nums);
 9         int[] count = new int[nums.length];
10         Arrays.fill(count, 1);
11         for (int i = 1; i < nums.length; i++) {
12             for (int j = i - 1; j >= 0; j--) {
13                 if (nums[i] % nums[j] == 0) {
14                     count[i] = Math.max(count[i], count[j] + 1);
15                 }
16             }
17         }
18         
19         int maxIndex = 0;
20         for (int i = 1; i < nums.length; i++) {
21             maxIndex = count[i] > count[maxIndex] ? i : maxIndex;
22         }
23         
24         int temp = nums[maxIndex];
25         int curCount = count[maxIndex];
26         for (int i = maxIndex; i >= 0; i--) {
27             if (temp % nums[i] == 0 && count[i] == curCount) {
28                 res.add(nums[i]);
29                 temp = nums[i];
30                 curCount--;
31             }
32         }
33         return res;
34     }
35 }

 

相关题目

300. Longest Increasing Subsequence

368. Largest Divisible Subset

LeetCode 题目总结

上一篇:[LeetCode] 1010. Pairs of Songs With Total Durations Divisible by 60


下一篇:1010. Pairs of Songs With Total Durations Divisible by 60