🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 861. Score After Flipping Matrix
Сложность: medium
Вам дана бинарная матрица 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
👨💻 Алгоритм:
1⃣Инициализируйте переменные: m и n для количества строк и столбцов в grid, score для хранения максимального счёта матрицы. Пройдитесь по первому столбцу матрицы. Если элемент равен 0, переверните всю строку.
2⃣Пройдитесь по матрице от второго до последнего столбца. Для каждого столбца посчитайте количество нулей (countZero). Если количество нулей больше, переверните весь столбец.
3⃣Пройдитесь по модифицированной матрице. Для каждого элемента добавьте его к score, сдвинув влево на значение текущего столбца. Верните score, который хранит наивысший возможный счёт матрицы.
😎 Решение:
class Solution {
function matrixScore($grid) {
$m = count($grid);
$n = count($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
