861. Score After Flipping Matrix

leetcode medium

#array#csharp#leetcode#matrix#medium#string

Task

Вам дана бинарная матрица grid размером m x n.

Ход состоит из выбора любой строки или столбца и переключения каждого значения в этой строке или столбце (т.е. изменение всех 0 на 1, и всех 1 на 0).

Каждая строка матрицы интерпретируется как двоичное число, и счёт матрицы — это сумма этих чисел.

Верните наивысший возможный счёт после выполнения любого количества ходов (включая ноль ходов).

Пример:

Input: grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]

Output: 39

Explanation: 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

C# solution

matched/original

public class Solution {
    public int MatrixScore(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 0) {
                for (int j = 0; j < n; j++) {
                    grid[i][j] ^= 1;
                }
            }
        }
        for (int j = 1; j < n; j++) {
            int countZero = 0;
            for (int i = 0; i < m; i++) {
                if (grid[i][j] == 0) {
                    countZero++;
                }
            }
            if (countZero > m / 2) {
                for (int i = 0; i < m; i++) {
                    grid[i][j] ^= 1;
                }
            }
        }
        int score = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    score += 1 << (n - j - 1);
                }
            }
        }
        return score;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MatrixScore(int[][] grid) {
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 0) {
                for (int j = 0; j < n; j++) {
                    grid[i][j] ^= 1;
                }
            }
        }
        for (int j = 1; j < n; j++) {
            int countZero = 0;
            for (int i = 0; i < m; i++) {
                if (grid[i][j] == 0) {
                    countZero++;
                }
            }
            if (countZero > m / 2) {
                for (int i = 0; i < m; i++) {
                    grid[i][j] ^= 1;
                }
            }
        }
        int score = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    score += 1 << (n - j - 1);
                }
            }
        }
        return score;
    }
}

Java solution

matched/original

class Solution {
    public int matrixScore(int[][] grid) {
        int m = grid.length, n = grid[0].length;

        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 0) {
                for (int j = 0; j < n; j++) {
                    grid[i][j] ^= 1;
                }
            }
        }

        for (int j = 1; j < n; j++) {
            int countZero = 0;
            for (int i = 0; i < m; i++) {
                if (grid[i][j] == 0) {
                    countZero++;
                }
            }
            if (countZero > m / 2) {
                for (int i = 0; i < m; i++) {
                    grid[i][j] ^= 1;
                }
            }
        }

        int score = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    score += 1 << (n - j - 1);
                }
            }
        }

        return score;
    }
}

JavaScript solution

matched/original

var matrixScore = function(grid) {
    const m = grid.length, n = grid[0].length;

    for (let i = 0; i < m; i++) {
        if (grid[i][0] === 0) {
            for (let j = 0; j < n; j++) {
                grid[i][j] ^= 1;
            }
        }
    }

    for (let j = 1; j < n; j++) {
        let countZero = 0;
        for (let i = 0; i < m; i++) {
            if (grid[i][j] === 0) countZero++;
        }
        if (countZero > m / 2) {
            for (let i = 0; i < m; i++) {
                grid[i][j] ^= 1;
            }
        }
    }

    let score = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                score += 1 << (n - j - 1);
            }
        }
    }

    return score;
};

Go solution

matched/original

func matrixScore(grid [][]int) int {
    m, n := len(grid), len(grid[0])

    for i := 0; i < m; i++ {
        if grid[i][0] == 0 {
            for j := 0; j < n; j++ {
                grid[i][j] ^= 1
            }
        }
    }

    for j := 1; j < n; j++ {
        countZero := 0
        for i := 0; i < m; i++ {
            if grid[i][j] == 0 {
                countZero++
            }
        }
        if countZero > m/2 {
            for i := 0; i < m; i++ {
                grid[i][j] ^= 1
            }
        }
    }

    score := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                score += 1 << (n - j - 1)
            }
        }
    }

    return score
}

Explanation

Algorithm

Инициализируйте переменные: m и n для количества строк и столбцов в grid, score для хранения максимального счёта матрицы. Пройдитесь по первому столбцу матрицы. Если элемент равен 0, переверните всю строку.

Пройдитесь по матрице от второго до последнего столбца. Для каждого столбца посчитайте количество нулей (countZero). Если количество нулей больше, переверните весь столбец.

Пройдитесь по модифицированной матрице. Для каждого элемента добавьте его к score, сдвинув влево на значение текущего столбца. Верните score, который хранит наивысший возможный счёт матрицы.

😎