翻转矩阵后的得分

约定不等于承诺〃 2022-12-27 01:45 95阅读 0赞

> leetcode 861 \[medium\]  
> 中：[翻转矩阵后的得分][Link 1]  
> 英：[Score After Flipping Matrix][]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]

### 题解 ###

##### 1. 思路：贪心 #####

1.  旋转行使得第一列全为1
2.  旋转列使得每列1最多

##### 2. 时间复杂度：O(n \* m) #####

1.  n: 行数；m：列数
2.  第一次遍历完成 “旋转行使得第一列全为1”；同时统计每一列1的个数
3.  第二次遍历完成 “旋转列使得每列1最多”

##### 3. 空间复杂度：O(m) #####

1.  第一次遍历后记录每一列1的个数

##### 4. 实现 #####

/** * @param {number[][]} A * @return {number} */
    var matrixScore = function(A) { 
        // 预处理
        let rowLen = A.length;          // 行数
        let columnLen = A[0].length;    // 列数
    
        // 行旋转，列统计
        let columnOneCount = Array.from({ length: columnLen}, v=>0);
        for(let i=0; i<rowLen; i++){ 
            if(A[i][0] !== 1) { 
                for(let j=0; j<columnLen; j++){ 
                    // 行旋转
                    A[i][j] = (A[i][j] + 1) % 2;
                    // 列统计
                    A[i][j] === 1 && columnOneCount[j]++;
                }
            }
            else{ 
                for(let j=0; j<columnLen; j++){ 
                    // 列统计
                    A[i][j] === 1 && columnOneCount[j]++;
                }
            }
        }
        
        // 列旋转
        let shouldHave = Math.ceil(rowLen / 2)
        for(let j=0; j<columnLen; j++){ 
            if(columnOneCount[j] < shouldHave){ 
                for(let i=0; i<rowLen; i++){ 
                    // 列旋转
                    A[i][j] = (A[i][j] + 1) % 2;
                }
            }
        }
    
        // 计算结果
        return A.reduce((pre, curr) => { 
            return pre + parseInt(curr.join(''), 2);
        }, 0)
    };

[Link 1]: https://leetcode-cn.com/problems/score-after-flipping-matrix/
[Score After Flipping Matrix]: https://leetcode.com/problems/score-after-flipping-matrix/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]: /images/20221120/43b38bd8845543a09cb3f6accb978af0.png