Re: [閒聊] 每日leetcode已回收
2392. Build a Matrix With Conditions
給一個整數k
有兩個矩陣 rowConditions、colConditions
其中rowConditions[i]=[above_i,below_i]
colConditions[i]=[left_i,right_i]
這兩個矩陣包含1~k
請根據上列訊息，建立出一個2-D矩陣
思路:
去遍歷rowConditions、colConditions
並用indegree矩陣紀錄每個node被指入的次數
用一個outnode去紀錄每個node指出些node
接著找出被指入次數為0的node，這些node就是最上/左邊的node
用一個queue去紀錄這些node
去遍歷queue，每遇到一個node就把他放到sorted矩陣
並把它指出的node的indegree扣掉1
如果indegree被扣到剩0，那就放到queue
最後檢查sorted的長度有沒有k，沒有的話代表有出現矛盾
把rowCondtions、colConditions都經過上述操作
就可以得到2個sorted矩陣，
一個是上而下排放著node
一個是由左而右排放著node
就依序填入最後答案就好
golang code :
func toposprt(k int, condition [][]int) (bool, []int) {
indegree := make([]int, k+1)
outnode := make([][]int, k+1)
sorted := make([]int, 0)
for _, val := range condition {
indegree[val[1]]++
outnode[val[0]] = append(outnode[val[0]], val[1])
}
queue := []int{}
for i := 1; i <= k; i++ {
if indegree[i] == 0 {
queue = append(queue, i)
}
}
for len(queue) > 0 {
tmp := queue[0]
sorted = append(sorted, tmp)
queue = queue[1:]
for _, val := range outnode[tmp] {
indegree[val]--
if indegree[val] == 0 {
queue = append(queue, val)
}
}
}
if len(sorted) != k {
return false, []int{}
}
return true, sorted
}
func buildMatrix(k int, rowConditions [][]int, colConditions [][]int) [][]int
{
worked, rowsorted := toposprt(k, rowConditions)
if !worked {
return [][]int{}
}
worked, colsorted := toposprt(k, colConditions)
if !worked {
return [][]int{}
}
nodes := make([]struct {
row int
col int
}, k+1)
res := make([][]int, k)
for i := 0; i < k; i++ {
res[i] = make([]int, k)
nodes[rowsorted[i]].row = i
nodes[colsorted[i]].col = i
}
for i := 1; i <= k; i++ {
res[nodes[i].row][nodes[i].col] = i
}
return res
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.213.232 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721554940.A.CD0.html
推
07/21 17:43,
1年前
, 1F
07/21 17:43, 1F
推
07/21 17:47,
1年前
, 2F
07/21 17:47, 2F
推
07/21 18:25,
1年前
, 3F
07/21 18:25, 3F
討論串 (同標題文章)
完整討論串 (本文為第 538 之 1548 篇)：