Re: [閒聊] 每日LeetCode

[oin1104 (是oin的說)]

※ 引述 《Rushia (みけねこ的鼻屎)》 之銘言：
: 　
: https://leetcode.com/problems/largest-divisible-subset/description
: 368. Largest Divisible Subset
: 給你一個陣列nums，找出由他的元素組成的最大子集合，所有元素滿足
: nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0，如果有多個解返回任意一個。






我的解法是n^2

先sort一下

用陣列的陣列當dp的東西

每次都會回頭找能夠整除的元素

然後找到擁有最長的陣列的元素

加上去

對每個元素做同樣的事

接著再找最長的那個就是答案了

其實好像可以邊找邊做



這題有更快的解法嗎

像是利用lis最長子字串的方法做

但是因為他是看能不能整除

所以好像不太可以？

姆咪




```cpp
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums)
    {
        sort(nums.begin() , nums.end() , less());
        int len = nums.size();

        vector<int> res ;

        vector<vector<int>> cnt(len , vector<int>());


        for(int i = 0 ; i < len ; i ++)
        {
            int icnt = 1;
            int ij = 0;
            for(int j = i-1 ; j >= 0 ; j --)
            {
                if((nums[i] % nums[j] == 0)||(nums[j] % nums[i] == 0))
                {
                    if(cnt[j].size()+1 > cnt[i].size())
                    {
                        cnt[i] = cnt[j];
                    }
                }
            }
            cnt[i].push_back(nums[i]);
        }

        for(int i = 0 ; i < len ; i ++)
        {
            if(cnt[i].size() > res.size())
            {
                res = cnt[i];
            }
        }


        return res;


    }
};
```








--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.41.234 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1707460697.A.646.html
噓 JIWP: 你好爛
推 wu10200512: n^2爛吐了 過年停止內捲
→ oin1104: 可是n^2 贏70幾趴欸 這題還有其他解法嗎
→ JIWP: 爛透了
推 DJYOSHITAKA: 單純記下回頭找到能整除寫最長陣列的index，這樣可以
→ DJYOSHITAKA: 不用記整條
→ DJYOSHITAKA: *整除且最長
→ oin1104: 好像也不錯