Сообщения

Раскрасить n домов k красками

Изображение
Даны n домов на улице, каждый из них может быть выкрашен в один из k цветов. Стоимость нанесения одного и того же цвета на разные дома может быть разной. Стоимость покраски довом представлена таблицей cost размером n x k. Например, costs[0][0] - это стоимость окраски дома 0 в цвет 0; costs[1][2] - стоиомсть окраски дома й в цвет 2 и т.д.  Нужно раскрасить все дома так, чтобы: рядом стоящие дома были окрашены в разный цвет; стоимость всеобщаей покраски должна быть минимальной. Ограничение: все стоимости - положительные числа. Пример: Дано: [[1,5,3],[2,9,4]] Результат: 5 Объяснение: Красим дом 0 в цвет 0, дом 1 в цвет 1. Стоимость минимальна: 1 + 4 = 5; Красим дом 0 в цвет 2, дом 1 в цвет 0. Стоимость минимальна: 3 + 2 = 5; Вопрос на засыпку: можно ли решить задачу за время O(nk)? Вариант решения 1: Мемоизация Корректность входных данных. Если k = 0, значит у нас нет красок. Если нет красок, то логично предположить, что нет и домов, то есть n = 0....

Самый левый элемент в последнем ярусе бинарного дерева

Дано не нулевое бинарное дерево (бинарное = в котором у каждой вершины не более двух детей), найти самый левый элемент в послднем ярусе дерева Пример 1: Дано: 2 / \ 1 3 Результат: 1 Пример 2: Дано: 1 / \ 2 3 / / \ 4 5 6 / 7 Результат: 7 Идея решения Обход дерева можно совершать в глубину или в ширину. При обходе в глубину, нам нужно передавать в с тек рекурсии ярус, который мы рассматриваем. И чем глубже мы продвигаемся, на каждом ярусе фиксируем значение самого левого элемента. При обходе в ширину, мы рассматриваем весь ярус целиком и берем из него самую левую вершину. Компилируемое решение DFS (поиск в глубину) // две глобальные перемнные int level = 0 ; // самый глубокий ярус дерева, который мы посетим int leftMost; // результат // основная функция public int findBottomLeftValue(TreeNode root) { //вырожденная ситуация: вместо дерева мы получили одну вершину if (root.left == nul...

Удалить внешние скобки

Корректная строка из скобок либо пустая ("") , либо "(" + A + ")" , либо A + B , где A и B - это коррекстные строки, а + представляет собой операцию конкатенации.  Например,  "" ,  "()" ,  "(())()" , и "(()(()))" - корректные строки со скобками. корректная строка S со скобками называется примитивной , если она не пустая, и не существет ещё разделения S = A+B , с A и B непустые корректсные строки со скобками. Дана корректная строка со скобками S , допустим, у неё есть притимная декомпозиция:  S = P_1 + P_2 + ... + P_k , где P_i - примитивные корректные строки со скобками. Вернуть S , в которой удалены внешние скобки каждой примитивной подстроки в декомпозиции. Пример 1: Дано: "(()())(())" Результат: "()()()" Появнение: Исходная строка "(()())(())" может быть декомпонована в примитивные строки так: "(()())" + "(())". После удаления внешних скобок ...

Конвертировать бинарную матрицу в 0-матрицу за миниальное число шагов

Изображение
Дана бинарная матрица 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] со...