Re: [閒聊] 每日LeetCode
寫了兩個小時還是改不出來
只能超時了
懶得寫了
==
2709. Greatest Common Divisor Traversal
class Solution {
public:
int GCD(int a, int b){
if(b==0) return a;
return GCD(b, a%b);
}
bool canTraverseAllPairs(vector<int>& nums) {
set<int> snums;
int ones=0;
for(auto& n:nums){
if(n==1) ones++;
if(ones>1) return false;
snums.insert(n);
}
unordered_set<int> visited;
unordered_map<int, vector<int>> mp;
for(auto& n:snums){
mp[n].push_back(n);
for(auto& k:mp){
if(n!=k.first && GCD(n, k.first)!=1){
mp[n].push_back(k.first);
mp[k.first].push_back(n);
}
}
}
for(auto& v:mp){
if(v.second.size()<2 && v.second.size()<mp.size()) return false;
}
queue<int> q;
q.push(nums[0]);
while(!q.empty()){
visited.insert(q.front());
for(auto& v:mp[q.front()]){
if(visited.count(v)) continue;
visited.insert(v);
q.push(v);
}
q.pop();
if(snums.size()==visited.size()) return true;
}
return false;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.149.184 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1708859930.A.675.html
推
02/25 19:20,
2月前
, 1F
02/25 19:20, 1F
推
02/25 19:22,
2月前
, 2F
02/25 19:22, 2F
討論串 (同標題文章)
完整討論串 (本文為第 718 之 719 篇)：
閒聊
1
3