Задача: 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, который хранит наивысший возможный счёт матрицы.

😎 Решение:

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;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 752. Open the Lock
Сложность: medium

Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно.

Пример:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6

👨‍💻 Алгоритм:

1⃣Используйте алгоритм BFS для поиска кратчайшего пути от начального состояния '0000' до целевого состояния, избегая тупиков. Инициализируйте очередь с начальным состоянием '0000' и начальным шагом 0. Используйте множество для отслеживания посещенных состояний, чтобы избежать повторного посещения одного и того же состояния.

2⃣Для каждого состояния в очереди: Проверьте все возможные переходы на следующий шаг, вращая каждое колесо на +1 и -1. Если найденное состояние является целевым, верните количество шагов. Если найденное состояние не является тупиком и не было посещено ранее, добавьте его в очередь и отметьте как посещенное.

3⃣Если очередь пуста и целевое состояние не найдено, верните -1.

😎 Решение:

public class Solution {
    public int OpenLock(string[] deadends, string target) {
        var dead = new HashSet<string>(deadends);
        var queue = new Queue<(string, int)>();
        queue.Enqueue(("0000", 0));
        var visited = new HashSet<string> { "0000" };

        while (queue.Count > 0) {
            var (node, steps) = queue.Dequeue();
            if (node == target) return steps;
            if (dead.Contains(node)) continue;
            foreach (var neighbor in Neighbors(node)) {
                if (!visited.Contains(neighbor)) {
                    visited.Add(neighbor);
                    queue.Enqueue((neighbor, steps + 1));
                }
            }
        }

        return -1;
    }

    private IEnumerable<string> Neighbors(string node) {
        var res = new List<string>();
        var nodeArray = node.ToCharArray();
        for (int i = 0; i < 4; i++) {
            var x = nodeArray[i] - '0';
            for (int d = -1; d <= 1; d += 2) {
                var y = (x + d + 10) % 10;
                nodeArray[i] = (char)(y + '0');
                res.Add(new string(nodeArray));
                nodeArray[i] = (char)(x + '0');
            }
        }
        return res;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 926. Flip String to Monotone Increasing
Сложность: medium

Двоичная строка является монотонно возрастающей, если она состоит из некоторого количества 0 (возможно, ни одного), за которым следует некоторое количество 1 (также возможно, ни одного). Вам дана двоичная строка s. Вы можете перевернуть s[i], изменив ее значение с 0 на 1 или с 1 на 0.

Пример:

Input: s = "00110"
Output: 1

👨‍💻 Алгоритм:

1⃣Создать массив left для подсчета количества операций, чтобы сделать подстроку до текущего индекса монотонной (только 0).

2⃣Создать массив right для подсчета количества операций, чтобы сделать подстроку после текущего индекса монотонной (только 1).
Пройти по строке и заполнить массивы left и right.

3⃣Пройти по строке и найти минимальное количество операций, чтобы сделать всю строку монотонной.

😎 Решение:

public class Solution {
    public int MinFlipsMonoIncr(string s) {
        int n = s.Length;
        int[] left = new int[n + 1];
        int[] right = new int[n + 1];
        
        for (int i = 0; i < n; i++) {
            left[i + 1] = left[i] + (s[i] == '1' ? 1 : 0);
        }
        
        for (int i = n - 1; i >= 0; i--) {
            right[i] = right[i + 1] + (s[i] == '0' ? 1 : 0);
        }
        
        int result = int.MaxValue;
        for (int i = 0; i <= n; i++) {
            result = Math.Min(result, left[i] + right[i]);
        }
        return result;
    }
}

Ставь 👍 и забирай 📚 Базу знаний