Re: [閒聊] 每日leetcode

作者: smart0eddie (smart0eddie)   2024-07-20 09:16:06
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 選比較小的填進去
就可以消掉一個條件
另一個扣掉對應數字以後繼續往下走填格

Links booklink

Contact Us: admin [ a t ] ucptt.com