推 sustainer123: 大師 07/20 23:18
https://i.imgur.com/r9FBAGO.gif
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.213.232 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721488622.A.EA3.html
1605. Find Valid Matrix Given Row and Column Sums
給兩個array : rowsum、colsum
rowsum[i]表示第i列數字的總和
colsum[j]表示第j行數字的總和
請根據回傳一個符合這些資訊的2D矩陣
這個2D矩陣不會有負數
思路:
rowsum[i]、colsum[j]兩個中比較小的那一個就是matrix[i][j]可以放的最大值
採用貪婪法
每次都在matrix[i][j]放入可允許的最大值
之後將rowsum[i]-matrix[i][j]、colsum[j]-matrix[i][j]
最後去遍歷整個matrix就可以得到答案了
golang code :
func restoreMatrix(rowSum []int, colSum []int) [][]int {
n,m:=len(rowSum),len(colSum)
matrix:=make([][]int,n)
for i:=0;i<n;i++{
matrix[i]=make([]int,m)
for j:=0;j<m;j++{
matrix[i][j]=min(rowSum[i],colSum[j])
rowSum[i]-=matrix[i][j]
colSum[j]-=matrix[i][j]
if rowSum[i]==0{
break
}
}
}
return matrix
}
--