Задача: 1429. First Unique Number
Сложность: medium

У вас есть очередь целых чисел, необходимо извлечь первый уникальный элемент из очереди.

Реализуйте класс FirstUnique:
- FirstUnique(int[] nums) Инициализирует объект числами в очереди.
- int showFirstUnique() возвращает значение первого уникального элемента в очереди и возвращает -1, если такого элемента нет.
- void add(int value) вставляет значение в очередь.

Пример:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output: 
[null,2,null,2,null,3,null,-1]
Explanation: 
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5);            // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2);            // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1

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

1⃣Инициализируйте объект FirstUnique с числами в очереди, добавляя их в структуру данных для отслеживания уникальности и порядка.

2⃣Метод showFirstUnique возвращает значение первого уникального элемента в очереди, если таковой существует, или -1, если уникальных элементов нет.

3⃣Метод add добавляет новое значение в очередь. Если значение уже было добавлено ранее, обновляет его статус уникальности и удаляет его из множества уникальных значений, если оно больше не уникально.

😎 Решение:

class FirstUnique(nums: IntArray) {
    private val setQueue = LinkedHashSet<Int>()
    private val isUnique = mutableMapOf<Int, Boolean>()

    init {
        nums.forEach { add(it) }
    }

    fun showFirstUnique(): Int {
        return setQueue.firstOrNull() ?: -1
    }

    fun add(value: Int) {
        when (isUnique[value]) {
            null -> {
                isUnique[value] = true
                setQueue.add(value)
            }
            true -> {
                isUnique[value] = false
                setQueue.remove(value)
            }
        }
    }
}

// LinkedHashSet implementation in Kotlin
class LinkedHashSet<T> {
    private val array = mutableListOf<T>()
    private val set = mutableSetOf<T>()

    fun add(value: T) {
        if (set.add(value)) {
            array.add(value)
        }
    }

    fun remove(value: T) {
        if (set.remove(value)) {
            array.remove(value)
        }
    }

    fun firstOrNull(): T? = array.firstOrNull()
}

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

Задача: 517. Super Washing Machines
Сложность: hard

У вас есть n супер стиральных машин, расположенных в одну линию. Изначально каждая стиральная машина содержит некоторое количество платьев или пуста.

За один ход вы можете выбрать любые m (1 <= m <= n) стиральные машины и одновременно передать одно платье из каждой выбранной машины в одну из её соседних стиральных машин.

Дан целочисленный массив machines, представляющий количество платьев в каждой стиральной машине слева направо по линии. Верните минимальное количество ходов, необходимых для того, чтобы во всех стиральных машинах стало одинаковое количество платьев. Если это невозможно, верните -1.

Пример:

Input: machines = [1,0,5]
Output: 3
Explanation:
1st move:    1     0 <-- 5    =>    1     1     4
2nd move:    1 <-- 1 <-- 4    =>    2     1     3
3rd move:    2     1 <-- 3    =>    2     2     2

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

1⃣Проверьте, можно ли решить задачу: длина массива machines должна быть делителем суммы элементов массива machines. Если нет, верните -1. Вычислите количество платьев, которое должно быть в каждой машине: dresses_per_machine = sum(machines) / len(machines). Нормализуйте задачу, заменив количество платьев в каждой машине на количество платьев, которые нужно удалить из этой машины (может быть отрицательное значение).

2⃣Инициализируйте переменные curr_sum, max_sum и res нулем. Итеративно пройдитесь по всем машинам m в массиве machines, обновляя curr_sum и max_sum на каждом шагу: curr_sum += m, max_sum = max(max_sum, abs(curr_sum)).

3⃣Обновляйте результат res на каждом шагу: res = max(res, max_sum, m). Верните res.

😎 Решение:

class Solution {
    fun findMinMoves(machines: IntArray): Int {
        val n = machines.size
        val dressTotal = machines.sum()
        if (dressTotal % n != 0) return -1

        val dressPerMachine = dressTotal / n
        for (i in machines.indices) {
            machines[i] -= dressPerMachine
        }

        var currSum = 0
        var maxSum = 0
        var res = 0
        for (m in machines) {
            currSum += m
            maxSum = maxOf(maxSum, kotlin.math.abs(currSum))
            res = maxOf(res, maxOf(maxSum, m))
        }
        return res
    }
}

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

Задача: 399. Evaluate Division
Сложность: medium

Вам дан массив пар переменных equations и массив вещественных чисел values, где equations[i] = [Ai, Bi] и values[i] представляют уравнение Ai / Bi = values[i]. Каждая Ai или Bi - это строка, представляющая одну переменную. Вам также даны некоторые запросы, где queries[j] = [Cj, Dj] представляет j-й запрос, в котором вы должны найти ответ для Cj / Dj = ?. Верните ответы на все запросы. Если ни один ответ не может быть определен, верните -1.0. Замечание: входные данные всегда действительны. Можно предположить, что вычисление запросов не приведет к делению на ноль и что противоречия нет. Примечание: Переменные, которые не встречаются в списке уравнений, являются неопределенными, поэтому для них ответ не может быть определен.

Пример:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

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

1⃣Создание графа:
Представьте каждую переменную как узел в графе.
Используйте уравнения для создания ребер между узлами, где каждое ребро имеет вес, равный значению уравнения (Ai / Bi = values[i]).
Создайте также обратные ребра с обратным весом (Bi / Ai = 1 / values[i]).

2⃣Поиск пути:
Для каждого запроса используйте поиск в глубину (DFS) или поиск в ширину (BFS) для поиска пути от Cj до Dj.
Если путь найден, вычислите произведение весов вдоль пути, чтобы найти значение Cj / Dj.
Если путь не найден, верните -1.0.

3⃣Обработка запросов:
Пройдитесь по всем запросам и используйте граф для вычисления результатов каждого запроса.

😎 Решение:

class Solution {
    fun calcEquation(equations: List<List<String>>, values: List<Double>, queries: List<List<String>>): DoubleArray {
        val graph = mutableMapOf<String, MutableMap<String, Double>>()

        for ((i, equation) in equations.withIndex()) {
            val A = equation[0]
            val B = equation[1]
            val value = values[i]
            graph.computeIfAbsent(A) { mutableMapOf() }[B] = value
            graph.computeIfAbsent(B) { mutableMapOf() }[A] = 1.0 / value
        }

        fun bfs(start: String, end: String): Double {
            if (!graph.containsKey(start) || !graph.containsKey(end)) return -1.0
            val queue = ArrayDeque<Pair<String, Double>>()
            queue.add(start to 1.0)
            val visited = mutableSetOf<String>()

            while (queue.isNotEmpty()) {
                val (current, curProduct) = queue.removeFirst()
                if (current == end) return curProduct
                visited.add(current)
                for ((neighbor, value) in graph[current] ?: emptyMap()) {
                    if (neighbor !in visited) {
                        queue.add(neighbor to curProduct * value)
                    }
                }
            }
            return -1.0
        }

        return queries.map { bfs(it[0], it[1]) }.toDoubleArray()
    }
}

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

Задача: 296. Best Meeting Point
Сложность: hard

Дан бинарный сетка размером m x n, где каждая 1 обозначает дом одного друга. Верните минимальное общее расстояние путешествия.

Общее расстояние путешествия — это сумма расстояний между домами друзей и точкой встречи.

Расстояние рассчитывается по Манхэттенскому расстоянию, где distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Пример:

Input: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 6
Explanation: Given three friends living at (0,0), (0,4), and (2,2).
The point (0,2) is an ideal meeting point, as the total travel distance of 2 + 2 + 2 = 6 is minimal.
So return 6.

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

1⃣Определение координат домов:
Пройдите по сетке и соберите координаты всех домов (ячейки с значением 1) в два списка: один для координат x и один для координат y.

2⃣Нахождение медианы:
Отсортируйте списки координат x и y.
Найдите медианы в обоих списках. Медианы координат x и y укажут оптимальную точку встречи.

3⃣Вычисление минимального общего расстояния:
Вычислите сумму Манхэттенских расстояний от каждого дома до точки встречи, используя найденные медианы в качестве координат точки встречи.
Верните это значение как минимальное общее расстояние путешествия.

😎 Решение:

class Solution {
    fun minTotalDistance(grid: Array<IntArray>): Int {
        var minDistance = Int.MAX_VALUE
        for (row in grid.indices) {
            for (col in grid[0].indices) {
                val distance = search(grid, row, col)
                minDistance = minOf(distance, minDistance)
            }
        }
        return minDistance
    }

    private fun search(grid: Array<IntArray>, row: Int, col: Int): Int {
        val q: ArrayDeque<Triple<Int, Int, Int>> = ArrayDeque()
        q.add(Triple(row, col, 0))
        val m = grid.size
        val n = grid[0].size
        val visited = Array(m) { BooleanArray(n) }
        var totalDistance = 0

        while (q.isNotEmpty()) {
            val (r, c, d) = q.removeFirst()

            if (r < 0 || c < 0 || r >= m || c >= n || visited[r][c]) {
                continue
            }

            if (grid[r][c] == 1) {
                totalDistance += d
            }

            visited[r][c] = true

            q.add(Triple(r + 1, c, d + 1))
            q.add(Triple(r - 1, c, d + 1))
            q.add(Triple(r, c + 1, d + 1))
            q.add(Triple(r, c - 1, d + 1))
        }

        return totalDistance
    }
}

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

Задача: 374. Guess Number Higher or Lower
Сложность: easy

Мы играем в игру "Угадай число". Правила игры следующие:

Я загадываю число от 1 до n. Вам нужно угадать, какое число я загадал.

Каждый раз, когда вы угадываете неправильно, я говорю вам, загаданное число больше или меньше вашего предположения.

Вы вызываете предопределенный API int guess(int num), который возвращает один из трех возможных результатов:

-1: Ваше предположение больше загаданного числа (т.е. num > pick).
1: Ваше предположение меньше загаданного числа (т.е. num < pick).
0: Ваше предположение равно загаданному числу (т.е. num == pick).
Верните загаданное число.

Пример:

Input: n = 10, pick = 6
Output: 6

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

1⃣Применяем бинарный поиск для нахождения загаданного числа. Начинаем с числа, расположенного в середине диапазона. Передаем это число функции guess.

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

3⃣Если функция guess возвращает 1, это означает, что загаданное число больше предположенного. Продолжаем бинарный поиск в диапазоне чисел, больших данного.

😎 Решение:

class Solution : GuessGame() {
    fun guessNumber(n: Int): Int {
        var low = 1
        var high = n
        while (low <= high) {
            val mid = low + (high - low) / 2
            val res = guess(mid)
            if (res == 0)
                return mid
            else if (res < 0)
                high = mid - 1
            else
                low = mid + 1
        }
        return -1
    }
}

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

Задача: 1461. Check If a String Contains All Binary Codes of Size K
Сложность: medium

Дана бинарная строка s и целое число k, верните true, если каждый бинарный код длины k является подстрокой s. В противном случае верните false.

Пример:

Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indices 0, 1, 3 and 2 respectively.

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

1⃣Определите количество возможных двоичных кодов длины k.

2⃣Создайте массив для отслеживания, какие коды были найдены. Итерируйте по строке s, вычисляя хэш для текущего окна длины k и обновляя массив отслеживания.

3⃣Возвращайте true, если все возможные коды найдены, иначе false.

😎 Решение:

class Solution {
    fun hasAllCodes(s: String, k: Int): Boolean {
        val need = 1 shl k
        val got = BooleanArray(need)
        val allOne = need - 1
        var hashVal = 0
        
        for (i in s.indices) {
            hashVal = ((hashVal shl 1) and allOne) or (s[i] - '0')
            if (i >= k - 1 && !got[hashVal]) {
                got[hashVal] = true
                if (got.all { it }) {
                    return true
                }
            }
        }
        return false
    }
}

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

Задача: 1466. Reorder Routes to Make All Paths Lead to the City Zero
Сложность: medium

Дано n городов, пронумерованных от 0 до n - 1, и n - 1 дорог, таких, что существует только один путь между двумя различными городами (эта сеть образует дерево). В прошлом году Министерство транспорта решило направить дороги в одном направлении, потому что они слишком узкие.

Дороги представлены массивом connections, где connections[i] = [ai, bi] представляет дорогу от города ai до города bi.
В этом году в столице (город 0) будет большое событие, и многие люди хотят приехать в этот город.
Ваша задача состоит в том, чтобы переориентировать некоторые дороги так, чтобы каждый город мог посетить город 0. Верните минимальное количество изменённых дорог.

Гарантируется, что каждый город может добраться до города 0 после перенаправления.

Пример:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

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

1⃣Создайте переменную count для подсчета количества рёбер, которые необходимо изменить. Инициализируйте её нулём. Создайте список смежности adj, который содержит список пар целых чисел так, чтобы adj[node] содержал всех соседей node в форме (neighbor, sign), где neighbor - соседний узел, а sign обозначает направление ребра (оригинальное или искусственное).

2⃣Начните обход в глубину (DFS). Используйте функцию dfs для выполнения обхода. В каждом вызове передавайте параметры node, parent и adj. Начните с узла 0 и parent равным -1.

3⃣Перебирайте всех соседей узла с помощью adj[node]. Для каждого neighbor, sign в adj[node], проверьте, равен ли neighbor родителю. Если равен, не посещайте его снова. Если neighbor не равен parent, выполните count += sign и рекурсивно вызовите dfs с node = neighbor и parent = node. По завершении обхода DFS, в count будет содержаться количество рёбер, которые необходимо изменить. Верните count.

😎 Решение:

class Solution {
    var count = 0

    fun dfs(node: Int, parent: Int, adj: Map<Int, List<Pair<Int, Int>>>) {
        adj[node]?.forEach { (neighbor, sign) ->
            if (neighbor != parent) {
                count += sign
                dfs(neighbor, node, adj)
            }
        }
    }

    fun minReorder(n: Int, connections: Array<IntArray>): Int {
        val adj = mutableMapOf<Int, MutableList<Pair<Int, Int>>>()
        for (connection in connections) {
            adj.computeIfAbsent(connection[0]) { mutableListOf() }.add(connection[1] to 1)
            adj.computeIfAbsent(connection[1]) { mutableListOf() }.add(connection[0] to 0)
        }
        dfs(0, -1, adj)
        return count
    }
}

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

Задача: 1286. Iterator for Combination
Сложность: medium

Создайте класс CombinationIterator:

CombinationIterator(string characters, int combinationLength) Инициализирует объект строкой characters, содержащей отсортированные различные строчные буквы английского алфавита, и числом combinationLength в качестве аргументов.
next() Возвращает следующую комбинацию длины combinationLength в лексикографическом порядке.
hasNext() Возвращает true, если и только если существует следующая комбинация.

Пример:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

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

1⃣Сгенерируйте все возможные бинарные битовые маски длины n: от 0 до 2^n - 1.

2⃣Используйте битовые маски с k установленными битами для генерации комбинаций из k элементов. Если n - 1 - j-й бит установлен в битовой маске, это указывает на присутствие символа characters[j] в комбинации и наоборот.

3⃣Теперь у вас есть все заранее вычисленные комбинации. Извлекайте их одну за другой по каждому запросу.

😎 Решение:

class CombinationIterator(characters: String, combinationLength: Int) {
    private val combinations: MutableList<String> = mutableListOf()

    init {
        val n = characters.length
        val k = combinationLength
        for (bitmask in 0 until (1 shl n)) {
            if (bitmask.countOneBits() == k) {
                val curr = StringBuilder()
                for (j in 0 until n) {
                    if (bitmask and (1 shl (n - j - 1)) != 0) {
                        curr.append(characters[j])
                    }
                }
                combinations.add(curr.toString())
            }
        }
    }

    fun next(): String {
        return combinations.removeAt(combinations.size - 1)
    }

    fun hasNext(): Boolean {
        return combinations.isNotEmpty()
    }
}

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

Задача: 98. Validate Binary Search Tree
Сложность: medium

Дан корень бинарного дерева. Определите, является ли это дерево допустимым бинарным деревом поиска (BST), где левое поддерево содержит только узлы с ключами меньше текущего, а правое — только с ключами больше текущего. Оба поддерева также должны быть BST.

Пример:

Input: root = [2,1,3]
Output: true

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

1⃣Используем симметричный обход дерева (inorder), при котором значения должны идти строго по возрастанию.

2⃣Храним значение предыдущего узла и сравниваем его с текущим: если текущее значение не больше предыдущего — дерево не BST.

3⃣Таким образом, проходим дерево один раз, не храня весь список обхода, что экономит память.

😎 Решение:

class TreeNode(var value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

class Solution {
    private var prev: Long = Long.MIN_VALUE

    private fun inorder(root: TreeNode?): Boolean {
        if (root == null) {
            return true
        }
        if (!inorder(root.left)) {
            return false
        }
        if (root.value <= prev) {
            return false
        }
        prev = root.value.toLong()
        return inorder(root.right)
    }

    fun isValidBST(root: TreeNode?): Boolean {
        return inorder(root)
    }
}

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

Задача: 754. Reach a Number
Сложность: medium

Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения.

Пример:

Input: target = 2
Output: 3

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

1⃣Инициализируйте переменную для текущей позиции (position) и счетчик шагов (steps).

2⃣Используйте цикл, чтобы добавлять к position текущее количество шагов и увеличивать steps.

3⃣Если position достигает или превышает target и разница между position и target четная, остановите цикл и верните steps.

😎 Решение:

fun reachTarget(target: Int): Int {
    var target = kotlin.math.abs(target)
    var position = 0
    var steps = 0
    while (position < target || (position - target) % 2 != 0) {
        steps++
        position += steps
    }
    return steps
}

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

Задача: 125. Valid Palindrome
Сложность: easy

Фраза является палиндромом, если после преобразования всех заглавных букв в строчные и удаления всех неалфавитно-цифровых символов она читается одинаково как слева направо, так и справа налево. Алфавитно-цифровые символы включают в себя буквы и цифры.

Для данной строки s верните true, если она является палиндромом, и false в противном случае.

Пример:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

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

1⃣Установите два указателя — с начала и конца строки.

2⃣Пропускайте неалфавитно-цифровые символы, сравнивая символы, пока указатели не сойдутся.

3⃣Если встретились несовпадающие символы — это не палиндром, иначе — да.

😎 Решение:

class Solution {
    fun isPalindrome(s: String): Boolean {
        var i = 0
        var j = s.length - 1

        while (i < j) {
            while (i < j && !s[i].isLetterOrDigit()) {
                i++
            }
            while (i < j && !s[j].isLetterOrDigit()) {
                j--
            }

            if (s[i].toLowerCase() != s[j].toLowerCase()) {
                return false
            }

            i++
            j--
        }

        return true
    }
}

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

Задача: 1243. Array Transformation
Сложность: easy

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

Пример:

Input: arr = [6,2,3,4]
Output: [6,3,3,4]

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

1⃣Инициализация нового массива с такими же значениями, как у исходного массива.
Циклически изменяем массив в соответствии с правилами, пока он не перестанет меняться.

2⃣Для каждого элемента массива проверяем, изменяется ли он в зависимости от его левого и правого соседей.
Если элемент меньше своего левого и правого соседей, увеличиваем его.
Если элемент больше своего левого и правого соседей, уменьшаем его.

3⃣Первый и последний элементы массива остаются неизменными.

😎 Решение:

class Solution {
    fun transformArray(arr: IntArray): IntArray {
        var arr = arr
        var changed: Boolean
        do {
            changed = false
            val newArr = arr.copyOf()
            for (i in 1 until arr.size - 1) {
                if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) {
                    newArr[i]++
                    changed = true
                } else if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
                    newArr[i]--
                    changed = true
                }
            }
            arr = newArr
        } while (changed)
        return arr
    }
}

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

Задача: 250. Count Univalue Subtrees
Сложность: medium

Дан корень бинарного дерева, верните количество поддеревьев с одинаковыми значениями.

Поддерево с одинаковыми значениями означает, что все узлы поддерева имеют одно и то же значение.

Пример:

Input: root = [5,1,5,5,5,null,5]
Output: 4

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

1⃣Создайте целочисленную переменную count для подсчета количества поддеревьев с одинаковыми значениями. Инициализируйте её значением 0.

2⃣Выполните обход в глубину (DFS) для данного бинарного дерева. Выполните dfs(root), где dfs — это рекурсивный метод, который принимает узел TreeNode в качестве параметра, от которого начинается обход. Метод возвращает логическое значение, указывающее, является ли поддерево, укоренённое в этом узле, поддеревом с одинаковыми значениями. Выполните следующие действия в этом методе:
Если узел равен null, верните true.
Рекурсивно проверьте, образует ли левый потомок поддерево с одинаковыми значениями. Выполните isLeftUniValue = dfs(node.left).
Рекурсивно проверьте, образует ли правый потомок поддерево с одинаковыми значениями. Выполните isRightUniValue = dfs(node.right).
Если оба потомка образуют поддеревья с одинаковыми значениями, т.е. isLeftUniValue && isRightUniValue равно true, сравните значения потомков узла со значением самого узла. Если левый потомок существует и node.left.val != node.val, верните false, так как значения не совпадают и мы не имеем поддерева с одинаковыми значениями. Аналогично, если правый потомок существует и node.right.val != node.val, верните false. В противном случае, увеличьте count на 1 и верните true.
В противном случае, одно или оба поддерева потомков не образуют поддеревья с одинаковыми значениями, поэтому дерево, укоренённое в node, также не может быть таким поддеревом. Верните false.

3⃣Верните count.

😎 Решение:

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    private var count = 0

    private fun dfs(node: TreeNode?): Boolean {
        if (node == null) {
            return true
        }

        val isLeftUniValue = dfs(node.left)
        val isRightUniValue = dfs(node.right)

        if (isLeftUniValue && isRightUniValue) {
            if (node.left != null && node.left!!.`val` != node.`val`) {
                return false
            }
            if (node.right != null && node.right!!.`val` != node.`val`) {
                return false
            }
            count++
            return true
        }
        return false
    }

    fun countUnivalSubtrees(root: TreeNode?): Int {
        dfs(root)
        return count
    }
}

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

Задача: 36. Valid Sudoku
Сложность: medium

Определите, является ли доска Судоку 9x9 валидной. Проверяются только заполненные ячейки, следуя правилам:
- В каждой строке числа 1-9 не повторяются.
- В каждом столбце числа 1-9 не повторяются.
- В каждом 3x3 блоке числа 1-9 не повторяются.

Пример:

Input: board =  
[["5","3",".",".","7",".",".",".","."]  
,["6",".",".","1","9","5",".",".","."]  
,[".","9","8",".",".",".",".","6","."]  
,["8",".",".",".","6",".",".",".","3"]  
,["4",".",".","8",".","3",".",".","1"]  
,["7",".",".",".","2",".",".",".","6"]  
,[".","6",".",".",".",".","2","8","."]  
,[".",".",".","4","1","9",".",".","5"]  
,[".",".",".",".","8",".",".","7","9"]]  
Output: true  

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

1⃣Создаем три массива Set, чтобы отслеживать числа в строках, столбцах и 3x3 блоках.

2⃣Проходим по каждой ячейке, проверяя наличие дубликатов в соответствующих множествах.

3⃣Если не найдено повторений, возвращаем true, иначе false.

😎 Решение:

class Solution {
    fun isValidSudoku(board: Array<CharArray>): Boolean {
        val N = 9
        val rows = Array(N) { mutableSetOf<Char>() }
        val cols = Array(N) { mutableSetOf<Char>() }
        val boxes = Array(N) { mutableSetOf<Char>() }

        for (r in 0 until N) {
            for (c in 0 until N) {
                val value = board[r][c]
                if (value == '.') continue

                if (!rows[r].add(value) || !cols[c].add(value) || !boxes[(r / 3) * 3 + (c / 3)].add(value)) {
                    return false
                }
            }
        }

        return true
    }
}

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