Leetcode — 861. Score After Flipping Matrix (中文)

問題連結: https://leetcode.com/problems/score-after-flipping-matrix/

給予一個二維矩陣A , 僅包含 0 或1

我們若想改變數字, 一動就會必須牽連他所在的整列 或整行的其他數字值, 比如我們想改變某格的數字, 那我們必須選擇是它的同行還是同列的所有數字都變成相反數字 (也就是互補數字, 0會變1, 1會變0)

改變完我們要的某行或某列後, 我們將會把各列的數字都讀成一整個二位數字, 而最後每列數字的總和就是我們的最終得分

題目要求回傳我們可以從這個二位矩陣中, 在允許改變數字的情況下, 可得到的最高得分

條件:

1. 1 <= A.length <= 20
2. 1 <= A[0].length <= 20
3. A[i][j] is 0 or 1.

範例
Input: [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
解釋:
一開始我們的矩陣長這樣: 
0 0 1 1
1 0 1 0
1 1 0 0
當我們決定改變第一列的數字:
1 1 0 0 
1 0 1 0
1 1 0 0
當我們決定改變第二行的數字:
1 1 1 0 
1 0 0 0
1 1 1 0
當我們決定改變第三行的數字:
1 1 1 1 
1 0 0 1
1 1 1 1
我們可得最高得分: 1111 + 1001 + 1111 = 15+9+15 = 39

想法:

乍看之下這個問題很難, 會讓人有點不知所措從何決定起我們要從哪一行還是哪一列開始改變, 但是沒關係的, 不用緊張, 我們再來好好解析我們的目標 — 找到最高的最終得分

因為最終得分就是我們在每列得到的二位數字, 代表要是我們想要找到最高的最終得分, 我們先必須讓各列的二位數字越高越好

因為我們知道一個二位數字就算1再多也沒有用, 1需要在正確的位置才有用, 比如說011絕對仍然輸100, 因此我們解這題的第一要點就是把每列的第一個位置都強制換成1

因此我們會選那些第一個數字不是1的列, 把那個列的所有其他位置的數字都相反過來, 這樣我們就完成每列數字的最佳狀態了, 但先別急, 我們真的確定現在各列數字加總起來可以讓我們拿到最高分嗎?

比如說 我們的矩陣一開始長這樣:

Original 2D Matrix

在翻轉完需要改變數字的列後:

After flipping row by row

你可以看到我們其實也只有改變了最後一列, 因為我們也知道我們就算改變前兩列也不能讓數字更大, 因為他們二位數字的第一個數字已是1開頭

但我們如果只看上面的矩陣, 很明顯的看出我們在某些行太多0了, 造成最終得分不高, 因此我們還可以再翻特定幾行的數字讓最終得分再更高

因此我們的第二個任務就是 — 翻轉0的數字過多的行, 而要怎麼決定0過多, 我們將判斷0的數目是否過半(也就是假設我們總共有m列, 那0的數字應該小於m的一半, 要是沒有, 那我們就直接把這些0變成1)

Final matrix

以下為根據上述邏輯的程式碼—

public int matrixScore(int[][] A) {
        int m = A.length; //number of rows
        int n = A[0].length; //num of cols
        
        //count[i] represents num of 1s in col i
        int[] count = new int[n];
        
        //flip row and count 1s in each col
        for(int i=0;i<m;i++)
        {
            boolean flip = A[i][0] == 0;
            for(int j=0;j<n;j++)
            {
                if(flip)
                    A[i][j] ^= 1;
                count[j] += A[i][j];
            }
        }
        
        int rst = 0;
        //calculate rst and also flip col if needed
        for(int j=n-1, temp=1;j>=0; j--, temp*=2)
        {
            int num0 = m - count[j];
            if(num0 > count[j]) //flip col
                count[j] = num0;
            rst += temp* count[j];
        }
        
        return rst;
    }

上述1ms的程式碼花了 O(m*n+n) 的時間複雜度, 假設m和n分別代表矩陣的列數與行數, 在Leetcode上只贏過了37% 的人

以下為我們如何改善我們程式碼的時間複雜度 —

程式邏輯:

而我們在上述程式碼中會額外跑一個O(n)的迴圈的根本原因是因為我們是用列的方式走訪矩陣, 一列走完才會訪下一列, 每列做的事情就是把需要翻轉的數字都翻過去, 外加累加各行的1的個數, 這些花O(m*n)的時間後, 我們才去用O(n)的時間去決定是否要翻轉各行 跟同時計算我們最終得分, 但實際上我們有點繞路了, 我們實際應該要可以在O(m*n)的時間內 就要在決定我們是否要翻行跟翻列的同時, 計算出最終得分

但我們上面程式碼寫法無法在第一個O(m*n)迴圈決定是否要翻行的根本原因就是因為我們並不知道那行主要是由0還是1組成, 我們只有在我們走到最後一列的時候, 才真的知道每行中1和0的個數

因此若我們改變我們的走訪方式, 我們改成用 行的方式走訪矩陣, 這樣我們就可以在邁向下一行之前, 就知道我們需不需要翻轉這行的數字, 並進行計算最終得分, 我們也不用擔心我們是否會忽略 "翻轉列的條件", 因為我們是否需要翻轉列的條件, 只有當現在這個位置的數字arr[i][j]在他所在的row i 上的第一個數字(arr[i][0])是0的時候, 因此我們就可以在 考慮翻轉列的情況下, 既又同時計算這行有幾個1, 然後再走訪完整行後, 我們又可以按照行中1的比率來考慮是否要翻轉行, 並把現在整行的數字總和加進最終得分

⚠️而下列程式碼我們將會從最後一行走訪回去至第一行的原因是因為我們每次都是依靠arr[i][0]的值來決定我們是否要翻轉這個數字arr[i][j], 因此我們若一開始就先翻轉第一行的數字的話, 我們就必須要多用一個boolean陣列來儲存我們是否需要翻轉某行的數字們了

以下為0ms的程式碼, 贏過100% —

public int matrixScore(int[][] A) {
        int m = A.length; //number of rows
        int n = A[0].length; //num of cols
        
        int rst = 0;
        for(int j=n-1, temp=1;j>=0;j--, temp*=2)
        {
            int count = 0;
            for(int i=0;i<m;i++)
            {
                boolean flip = A[i][0]==0; //flip row
                if(flip)
                    A[i][j] ^= 1;
                count += A[i][j];
            }
            //flip col if needed
            count = Math.max(count, m-count);
            rst += temp * count;
        }
        
        return rst;
    }