861. Score After Flipping Matrix

LeetCode medium оригинал: C# #array #csharp #leetcode #matrix #medium #string

LeetCode Static

Вам дана бинарная матрица 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# решение

сопоставлено/оригинал

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++ решение

auto-draft, проверить перед отправкой

#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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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
}

Algorithm

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

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

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

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.