Re: [閒聊] 每日leetcode已回收
※ 引述 《enmeitiryous (enmeitiryous)》 之銘言：
:
2392.build a matrix with condition
給兩個二維陣列
rowconditions, colconditions和一常數k,
其中rowcondition陣列
每一項[a,b]代表a會在b的上方列中，
例如b在i-th row,
a就一定只能在0-i-1 th row中，
colconditions類似，
[a,b]代表a一定在b的左邊col中，
給定1-k的數字回傳
k*k合乎規定的matrix,
如果條件出現矛盾則回傳empty matrix.
怎麼是圖 幹 我吐了
思路:
先想想看要如果只有一條
row的情況
就是要依照他的上下順序關係
要找上下順序關係
就要用Topological sort
我是用kahn's 的方法來找
kahn's 方法簡單說就是
記錄每個節點進入的路徑 indegree
還有他們能到達的地方
然後沒有路徑能到
indegree=0的地方就拿去找
被找到的就 indegree -1
又=0就再拿去找
這樣能夠避免迴圈出現
因為有迴圈的 indegree 永遠不會是0
這樣可以找到他們的順序
然後知道順序就
兩個一起找 丟進去
結束
```cpp
class Solution {
public:
vector<int> test(vector<vector<int>>& rowConditions , int k)
{
unordered_map<int,vector<int>> rowsave;
vector<int> rowind(k+1,0);
vector<int> rowint;
queue<int> rowq;
for(auto k : rowConditions)
{
rowsave[k[0]].push_back(k[1]);
rowind[k[1]]++;
}
for(int i = 1 ; i <= k ; i ++)
{
if(rowind[i]==0)rowq.push(i);
}
while(!rowq.empty())
{
int now = rowq.front();
rowq.pop();
rowint.push_back(now);
for(int k : rowsave[now])
{
rowind[k]--;
if(rowind[k] == 0)
{
rowq.push(k);
}
}
}
return rowint;
}
vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, v
ector<vector<int>>& colConditions)
{
vector<vector<int>> res (k,vector<int>(k,0));
int rlen = rowConditions.size();
int clen = colConditions.size();
vector<int> rowint;
vector<int> colint;
rowint = test(rowConditions , k);
if(rowint.size()<k)return {};
colint = test(colConditions , k);
if(colint.size()<k)return {};
for(int i = 0 ; i < k ; i ++)
{
int jiwp = 0;
for(int j = 0 ; j < k ; j ++)
{
if(colint[j]==rowint[i])jiwp = j;
}
res[i][jiwp] = rowint[i];
}
return res;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.58.218 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721553455.A.CCA.html
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 537 之 1548 篇)：