Re: [閒聊] 每日leetcode
看板Marginalman作者enmeitiryous (enmeitiryous)時間1年前 (2024/08/29 09:38)推噓1(1推 0噓 1→)留言2則, 2人參與討論串778/1554 (看更多)
題目:
947. Most Stones Removed with Same Row or Column:
給你一個二維矩陣mx，mx[i][0],mx[i][1]代表這邊有一顆石頭，今天在任一row/column上
如果有兩顆以上的石頭，我們可以任意移除直到該row/column上只剩一顆石頭，求我們
最大的可能石頭移除量
思路:
第一眼看到就可以很明確知道這是找compoment數目的題目，所以可以用union find
或是dfs找，但本來一想到mx[i][0]<=10**4，但mx.size()<1000，所以應該用mx[i]當基底
而不是開一個10**4長度的vector做union，結果爆爛，用mx[i][0]當基底才是正解
int removeStones(vector<vector<int>>& stones) {
vector<vector<set<int>>> pre_ans;
vector<int> ans;
vector<int> sugar;
for(int i=0;i<stones.size();++i){
if(pre_ans.empty()){
set<int> paper1;
set<int> paper2;
paper1.insert(stones[i][0]);
paper2.insert(stones[i][1]);
pre_ans.push_back({paper1,paper2});
ans.push_back(0);
sugar.push_back(0);
}
else{
bool lokfor=true;
int prelab;
for(int j=0;j<pre_ans.size();++j){
if((pre_ans[j][0].count(stones[i][0]) ||
pre_ans[j][1].count(stones[i][1])) &&lokfor){
if(sugar[j]==j){
prelab=j;
pre_ans[j][0].insert(stones[i][0]);
pre_ans[j][1].insert(stones[i][1]);
ans[j]++;
lokfor=false;
}
else{
int prelab=sugar[j];
pre_ans[prelab][0].insert(stones[i][0]);
pre_ans[prelab][1].insert(stones[i][1]);
ans[prelab]++;
lokfor=false;
}
}
else if((pre_ans[j][0].count(stones[i][0]) ||
pre_ans[j][1].count(stones[i][1])) && !lokfor){
if(sugar[j]==j){
sugar[j]=prelab;
for(auto &h: pre_ans[j][0]){
pre_ans[prelab][0].insert(h);
}
for(auto &h:pre_ans[j][1]){
pre_ans[prelab][1].insert(h);
}
ans[prelab]+=(ans[j]+1);
pre_ans[prelab][0].insert(stones[i][0]);
pre_ans[prelab][1].insert(stones[i][1]);
ans[j]=-1;
pre_ans[j][0].clear();
pre_ans[j][1].clear();
}
}
}
if(lokfor){
set<int> paper1;
set<int> paper2;
paper1.insert(stones[i][0]);
paper2.insert(stones[i][1]);
pre_ans.push_back({paper1,paper2});
ans.push_back(0);
int yo=sugar.size();
sugar.push_back(yo);
}
}
}
int ola=0;
for(auto h:ans){
if(h!=-1){
ola+=h;
}
}
return ola;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.205.129 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724895525.A.3D3.html
→
08/29 09:43,
1年前
, 1F
08/29 09:43, 1F
推
08/29 10:23,
1年前
, 2F
08/29 10:23, 2F
討論串 (同標題文章)
完整討論串 (本文為第 778 之 1554 篇)：