FLAMEc隨手記

一陣風飄過~~~

0%

算出可用矩陣用ROW SUM和COL SUM

發表於 更新於

是leetcode的題目，題目如下(直接複製的)：

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.

Example 1:

Input: rowSum = [3,8], colSum = [4,7]
Output: [[3,0],
[1,7]]
Explanation:
0th row: 3 + 0 = 3 == rowSum[0]
1st row: 1 + 7 = 8 == rowSum[1]
0th column: 3 + 1 = 4 == colSum[0]
1st column: 0 + 7 = 7 == colSum[1]
The row and column sums match, and all matrix elements are non-negative.
Another possible matrix is: [[1,2],
[3,5]]
Example 2:

Input: rowSum = [5,7,10], colSum = [8,6,8]
Output: [[0,5,0],
[6,1,0],
[2,0,8]]

心得：

看來看去這一題主要是要知道這個問題的解法，就像魔術方塊有公式解，
這個問題應該也有類似的公式解，應該不是考推導而是考公式解如何轉化成Code。

一開始我是沒碰過這個問題的，所以卡了一下，要推導出公式還是有點難度的QQ
所以看了一下Hint，Hint中提到大概做法，可能是公式之一吧，其實也是有點懷疑真的嗎XD?

Hint 1
Find the smallest rowSum or colSum, and let it be x. Place that number in the grid, and subtract x from rowSum and colSum. Continue until all the sums are satisfied.

一步一步測試後確認可行。就像魔術方塊公式解也有多種，應該也是有更簡化的方法的，這邊就不繼續研究了。

最後如下；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {
        vector<vector<int>> ans(rowSum.size(), vector<int>(colSum.size(),0));


        int minRor = 0;
        int minCol = 0;

        while(true)
        {
            minRor = 0;
            minCol = 0;

            //找最小值
            for(int i = 1 ; i < rowSum.size(); i++)
            {
                if((rowSum[i] > 0 && rowSum[i] < rowSum[minRor]) || rowSum[minRor] == 0)
                {
                    minRor = i;
                }
            }

            //找最小值
            for(int i = 1 ; i < colSum.size(); i++)
            {
                if((colSum[i] > 0 && colSum[i] < colSum[minCol]) || colSum[minCol] == 0)
                {
                    minCol = i;
                }
            }

            //都是0結束
            if(rowSum[minRor] == 0 && colSum[minCol] == 0)
                break;

            //塞結果和更新值
            if(rowSum[minRor] > colSum[minCol])
            {
                ans[minRor][minCol] = colSum[minCol];
                rowSum[minRor] -= colSum[minCol]; //這邊就是一開始我最懷疑地方，直接改不會沒算出來嗎XD?結果沒事!!
                colSum[minCol] = 0;
            }
            else
            {
                ans[minRor][minCol] = rowSum[minRor];
                colSum[minCol] -= rowSum[minRor]; //這邊就是一開始我最懷疑地方，直接改不會沒算出來嗎XD?結果沒事!!
                rowSum[minRor] = 0;
            }
        }


        return ans;
    }
};