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]