2024-07-20
1605. Find Valid Matrix Given Row and Column Sums
You are given two arrays rowSum and colSum of non-negative integers where
rowSum[i] is the sum of the elements in the ith row and colSum[j] is the sum
of the elements of the jth column of a 2D matrix. In other words, you do not
know the elements of the matrix, but you do know the sums of each row and
column.
Find any matrix of non-negative integers of size rowSum.length x
colSum.length that satisfies the rowSum and colSum requirements.
Return a 2D array representing any matrix that fulfills the requirements.
It's guaranteed that at least one matrix that fulfills the requirements
exists.
偷看解答.jpg
用 greedy 從左上開始填
讓每次填格都能直接消掉一個 sum 條件
也就是 rowSum, colSum 選比較小的填進去
就可以消掉一個條件
另一個扣掉對應數字以後繼續往下走填格
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.173.211.221 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721438168.A.A6B.html