Re: [閒聊] 每日leetcode
看板Marginalman作者smart0eddie (smart0eddie)時間1年前 (2024/07/20 09:16)推噓0(0推 0噓 0→)留言0則, 0人參與討論串528/1554 (看更多)
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
討論串 (同標題文章)
完整討論串 (本文為第 528 之 1554 篇)：