Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者oin1104 (是oin的說)時間1年前 (2024/02/09 14:38)推噓1(2推 1噓 5→)

留言8則, 4人參與討論串665/719 (看更多)

※ 引述《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

02/09 14:46, 1年前 , 1^F

02/09 14:46, 1^F

推

wu10200512

02/09 14:51, 1年前 , 2^F

02/09 14:51, 2^F

→

oin1104

02/09 14:57, 1年前 , 3^F

02/09 14:57, 3^F