368. Largest Divisible Subset

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/largest-divisible-subset/description/

想法

没有什么思路…或许贪心？

不，应该可以从数学的角度上解决的。
如果能任意地被整除，需要满足什么条件呢？
每添加进一个，都可以被这个set中的每一个整除
这样一来，是个O(n^2 )的复杂度，可以吗？
先试试吧
不对，不是O(n^2 )，排序需要nlog n，因为已经序的了，应该只用O(n k)，k是set的数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        if (nums.empty())
            return vector<int>();
        std::sort(nums.begin(), nums.end());
        vector<vector<int>> sets;
        bool inserted = false;
        int maxSize = 1;
        int maxSizeIdx = 0;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = 0; j < sets.size(); ++j) {
                if (nums[i] % sets[j][sets[j].size() - 1] == 0) {
                    sets[j].push_back(nums[i]);
                    if (maxSize < sets[j].size()) {
                        maxSize = sets[j].size();
                        maxSizeIdx = j;
                    }
                    inserted = true;
                    break;
                }
            }
            if (inserted == false) {
                vector<int> vec;
                sets.push_back(vec);
                sets[sets.size() - 1].push_back(nums[i]);
            } else {
                inserted = false;
            }
        }
        return sets[maxSizeIdx];
    }
};

嗯，看来自己本来有一些Naive了

没有考虑到这样的情况
那看来原来的想法是不行的
一个更明显的例子：

考虑用DP做
因为，大数可以表示成因式的和

看问题的样子，是很符合贪心的策略的，但是怎么用呢？
唔，有必要补一补基础知识了，唉，先看下答案吧，不想想了orz

尝试建一个多叉树
做完之后，调了好多bug，却发现也同样没有考虑到那个问题，唉，本质上和原来是一样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//
// Created by Zhao Xiaodong on 2017/8/1.
//
#include <iostream>
#include <vector>
using namespace std;
class Solution {
    struct TreeNode {
        int val;
        vector<TreeNode*> children;
        TreeNode(int x) : val(x) {}
    };
    std::vector<int> result;
    std::vector<int> current;
    bool insert(TreeNode *tree, int num) {
        if (num % tree->val != 0)
            return false;
        bool inserted = false;
        current.push_back(tree->val);
        for (int i = 0; i < tree->children.size(); ++i) {
            if (insert((tree->children)[i], num)) {
                inserted = true;
            }
        }
        if (!inserted) {
            TreeNode *newNode = new TreeNode(num);
            (tree->children).push_back(newNode);
            current.push_back(num);
        }
        if (current.size() > result.size())
            result = current;
        current = vector<int>{};
        return true;
    }
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        if (nums.empty())
            return vector<int>();
        if (nums.size() == 1)
            return vector<int>{nums[0], };
        std::sort(nums.begin(), nums.end());
        TreeNode *tree = new TreeNode(1);
        for (int i = 0; i < nums.size(); ++i) {
            insert(tree, nums[i]);
        }
        result.erase(result.begin());
        return result;
    }
};

参考答案

哈？答案一票都是用DP的？？？

https://discuss.leetcode.com/topic/49456/c-solution-with-explanations

勉强看懂，看是不保证自己能写出来，这题就先放过吧，日后再做。