My code:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
public class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
List<Integer> ret = new ArrayList<Integer>();
if (nums == null || nums.length == 0) {
return ret;
}
Arrays.sort(nums);
HashMap<Integer, List<List<Integer>>> dp = new HashMap<>();
List<Integer> sublist = new ArrayList<Integer>();
sublist.add(nums[0]);
List<List<Integer>> list = new ArrayList<>();
list.add(sublist);
dp.put(0, list);
for (int i = 1; i < nums.length; i++) {
List<List<Integer>> currList = dp.get(i - 1);
Integer curr = new Integer(nums[i]);
boolean belongToSomething = false;
for (List<Integer> l : currList) {
boolean excluded = false;
for (Integer prev : l) {
if (curr.intValue() % prev.intValue() != 0) {
excluded = true;
break;
}
}
if (!excluded) {
belongToSomething = true;
l.add(curr);
}
}
if (!belongToSomething) {
List<Integer> newList = new ArrayList<Integer>();
newList.add(curr);
for (int j = 0; j < i; j++) {
boolean canInsert = true;
for (Integer temp : newList) {
if (temp % nums[j] != 0 && nums[j] % temp != 0) {
canInsert = false;
break;
}
}
if (canInsert) {
newList.add(nums[j]);
}
}
currList.add(newList);
}
dp.put(i, currList);
}
int max = 0;
for (List<Integer> currList : dp.get(nums.length - 1)) {
if (currList.size() >= max) {
max = currList.size();
ret = currList;
}
}
return ret;
}
}
这道题目自己硬是做完了。
虽然很丑。
我的思想是，DP
把数塞进去。
分组。
比如
dp[i] 对应了 一个 List<List<String>>
里面有 截止到 i 时，所有的可以整除的组合，or group
然后新进来一个数时，先去和所有的group进行比较。哪个group可以容得下他，就加进去。可以加入多个group
如果最后一个都没加进去，就自成一派。和之前的所有数字比较，做出一个新的 group.
然而这样子做，整体的代码很繁琐，涉及到太多的遍历。
时间复杂度，空间复杂度都很大。
然后我在想，到底哪里浪费时间了？？
我发现，我每次会把所有的group都保存起来。遍历的时候也是遍历所有的group。到后面group会越来越多，花的时间会越来越多。
真的有这个必要吗？？
完全没有。
我只用保存下长度最长的group
当新加入一个元素的时候，只会有两种情况。
- 新加入的元素同样可以融入之前的最长group
- 新加入的元素不能融入，然后自己做出了1个group。如果长度小于原长度，则继续保持原group。否则，就更新到新的group
这样子做，肯定能简单很多。
然后看了下答案。
发现更加简单。
My code:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
List<Integer> ret = new ArrayList<Integer>();
if (nums == null || nums.length == 0) {
return ret;
}
Arrays.sort(nums);
int n = nums.length;
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; i++) {
for (int j = i - 1; j >= 0; j--) {
if (nums[i] % nums[j] == 0) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int maxIndex = 0;
for (int i = 1; i < n; i++) {
maxIndex = (dp[i] > dp[maxIndex] ? i : maxIndex);
}
int temp = nums[maxIndex];
int prev = dp[maxIndex] + 1;
for (int i = maxIndex; i >= 0; i--) {
if (temp % nums[i] == 0 && dp[i] + 1 == prev) {
ret.add(nums[i]);
temp = nums[i];
prev = dp[i];
}
}
return ret;
}
public static void main(String[] args) {
Solution test = new Solution();
int[] nums = new int[]{1, 2, 4, 8, 9, 72};
List<Integer> ret = test.largestDivisibleSubset(nums);
for (Integer temp : ret) {
System.out.print(temp + "_");
}
}
}
reference:
https://discuss.leetcode.com/topic/49741/easy-understood-java-dp-solution-in-28ms-with-o-n-2-time/7
这里的答案是错的！！！需要看我改写后的代码
他就是先找出导致最长长度的那个index
然后再从他开始，把这个group给恢复了。
复杂度是 O(n ^ 2)
空间复杂度是： O(n)
比我之前的简单了很多。
感觉时间有点来不及了。自己的效率也不高。
一直想着刚回学校没多久，慢慢适应，慢慢提高强度。
但其实哪有那么多时间给你等。
以后吃饭什么的少花点时间吧。
Anyway, Good luck, Richardo! -- 08/28/2016
