Coding interview scrapbook

Дана бинарная матрица mat (состоит из 0 и 1) размера m x n . За один шаг можно любую ячейку и её соседей (если они существуют) инвертировать (0 станет 1, а 1 - 0). Пара ячеек называется соседями, если у них общее "ребро". Нужно вернуть минимальное клочисество шагов, чтобы конвертировать mat в 0-матрицу (состоит только из 0) или -1 , если это невозможно. Пример 1: Дано: mat = [[0,0],[0,1]] Результат: 3 Пояснение: Мы инвертируем ячейку [1,0], затем [0, 1], затем [1, 1]. Результаты этой инверсии показаны на рисунке выше. Пример 2: Дано: mat = [[0]] Результат: 0 Пояснение: Исходная матрица уже 0-матрица, никаких инверсий не требуется. Пример 3: Дано: mat = [[1,1,1],[1,0,1],[0,0,0]] Результат: 6 Пример 4: Дано: mat = [[1,0,0],[1,0,0]] Результат: -1 Пояснение: Не существует такой последовательности шагов инверсии, чтобы получилась 0-матрица. Ограничения: m == mat.length n == mat[0].length 1 <= m <= 3 1 <= n <= 3 mat[i][j] со...

Дана двухмерная матрица grid состоящая из  0 (земля) и 1 (вода).  Остров - это группа смежных 0 , а замкнутый остров - это остров, окруженный (сверху, снизу, справа и слева) водой, то есть 1. Вернуть количество завкнутых островов. Пример 1: Дано: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]] Результат: 2 Пояснение: Острова, помеченные серым цветом, замкнутые, потому что они окружены водой (единичками) сверху, снизу, слева и справа. Пример 2: Дано: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]] Результат: 1 Пример 3: Дано: grid = [[1,1,1,1,1,1,1],   [1,0,0,0,0,0,1],   [1,0,1,1,1,0,1],   [1,0,1,0,1,0,1],   [1,0,1,1,1,0,1],   [1,0,0,0,0,0,1], [1,1,1,1,1,1,1]] Результат: 2 (остров внутри острова) Ограничения: 1 <= grid.length, grid[0].length <= 100 0 <= grid[i][j] <=1 Идея реше...

Допустим, вы - многодетный родитель и хотите угостить всех своих детей печеньками. Вы должны дать хотя бы одну печеньку каждому ребенку. Каждый ребенок обладает своим фактором жадности g i до печенек.  Фактор жадности - это минимальный размер печеньки, которой ребенок будет доволен. И у каждой печеньки есть свой размер s j . Если s j  >= g i , мы можем дать печеньку j ребенку i, и тот будет доволен. Ваша задача максимизировать число довольных детей и в качестве ответа выдать число довольных детей. Примечания: Фактор жадности всегда положителен. Каждый ребенок может взять только одну печеньку. Пример 1: Дано: [1,2,3], [1,1] Результат: 1 Пояснение: у вас 3 детей и 2 печеньки. Факторы эадности детей соответственно 1, 2, 3. Даже если у вас 2 печеньки, их размер равен 1, поэтому доволен останется только ребенок с фактором жадности 1. Пример 2: Дано: [1,2], [1,2,3] Результат: 2 Пояснение: У вас 2 детей (с фактором жадности 1 и 2) и 3 печеньки. У трёх печ...

Задача. Дана таблица умножения размером m * n и целое число k , нужно найти the  k-й элемент таблицы умножения, если взять все значения таблицы и отсортировать их в возрастающем порядке. Пример 1: Дано: m = 3, n = 3, k = 5 Результат: 3 Пояснение: Таблица умножения 3х3: 1 2 3 2 4 6 3 6 9 5-й наименьший элемент - это 3 (1, 2, 2, 3, 3 , 4, 6, 6, 9) Пример 2: Дано: m = 2, n = 3, k = 6 Результат: 6 Пояснение: Таблица умножения 2х3: 1 2 3 2 4 6 6-й наименьший элемент - это 6 (1, 2, 2, 3, 4, 6 ). Ограничения: m и n из интервала [1, 30000]. k из интервала [1, m * n] Брутфорс-идея: берем все элементы матрицы (предварительно их посчитав) , сор тируем и берем k-й элемент. Анализ сложности: Сложность по времени:  O(m*n) O ( m ∗ n ) на подсёт элементов таблицы, и O(m*n\log(m*n)) O ( m ∗ n ∗ lo g ( m ∗ n ) ) на их сортировку. Затраты на память:  O(m*n) O ( m ∗ n ) . Оптимизация: мы знаем наименьший элемент (1) и наибольший элемент (m*n) таблиц...