#medium
Задача: 372. Super Pow

Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива.

Пример:

Input: a = 2, b = [3]
Output: 8

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

1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди.

2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337.

3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337.

😎 Решение:

class Solution {
    func getSum(_ a: Int, _ b: Int) -> Int {
        var x = abs(a), y = abs(b)
        if x < y {
            return getSum(b, a)
        }
        let sign = a > 0 ? 1 : -1

        if a * b >= 0 {
            while y != 0 {
                let carry = (x & y) << 1
                x ^= y
                y = carry
            }
        } else {
            while y != 0 {
                let borrow = ((~x) & y) << 1
                x ^= y
                y = borrow
            }
        }
        return x * sign
    }
}

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

#hard
Задача: 332. Reconstruct Itinerary

Вам дан список авиабилетов, где tickets[i] = [fromi, toi] представляют собой аэропорты отправления и прибытия одного рейса. Восстановите маршрут в порядке следования и верните его.

Все билеты принадлежат человеку, который вылетает из "JFK", поэтому маршрут должен начинаться с "JFK". Если существует несколько возможных маршрутов, вы должны вернуть маршрут, который имеет наименьший лексикографический порядок при чтении как одна строка.
Например, маршрут ["JFK", "LGA"] имеет меньший лексикографический порядок, чем ["JFK", "LGB"].
Вы можете предположить, что все билеты формируют хотя бы один действительный маршрут. Вы должны использовать все билеты один раз и только один раз.

Пример:

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

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

1⃣Построение графа и сортировка:
Создайте граф flightMap, где ключи - это аэропорты отправления, а значения - это списки аэропортов прибытия.
Пройдите по всем билетам и заполните flightMap соответствующими значениями.
Отсортируйте списки аэропортов прибытия в лексикографическом порядке.

2⃣Пост-упорядоченный обход (DFS):
Создайте функцию DFS, которая будет рекурсивно проходить по всем ребрам (рейсам), начиная с аэропорта "JFK".
Во время обхода удаляйте использованные рейсы из графа, чтобы не проходить по ним повторно.

3⃣Формирование маршрута:
По мере завершения обхода добавляйте текущий аэропорт в начало списка результата.
После завершения DFS верните сформированный маршрут.

😎 Решение:

class Solution {
    var flightMap = [String: [String]]()
    var result = [String]()
    
    func findItinerary(_ tickets: [[String]]) -> [String] {
        for ticket in tickets {
            flightMap[ticket[0], default: [String]()].append(ticket[1])
        }
        
        for key in flightMap.keys {
            flightMap[key]?.sort()
        }
        
        dfs("JFK")
        return result
    }
    
    func dfs(_ origin: String) {
        while let destList = flightMap[origin], !destList.isEmpty {
            let nextDest = flightMap[origin]!.removeFirst()
            dfs(nextDest)
        }
        result.insert(origin, at: 0)
    }
}

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

#medium
Задача: 462. Minimum Moves to Equal Array Elements II

Дан массив целых чисел nums размера n, вернуть минимальное количество ходов, необходимых для того, чтобы сделать все элементы массива равными.

В одном ходе вы можете увеличить или уменьшить элемент массива на 1.

Тестовые случаи составлены так, что ответ поместится в 32-битное целое число.

Пример:

Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

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

1⃣Найти минимальный и максимальный элементы в массиве. Пусть k будет числом, к которому должны быть приведены все элементы массива.
2⃣Перебирать значения k в диапазоне между минимальным и максимальным элементами, вычисляя количество ходов, необходимых для каждого k.
3⃣Определить минимальное количество ходов среди всех возможных k, что и будет конечным результатом.

😎 Решение:

class Solution {
    func minMoves2(_ nums: [Int]) -> Int {
        var ans: Int64 = Int64.max
        var minval = Int.max
        var maxval = Int.min
        for num in nums {
            minval = min(minval, num)
            maxval = max(maxval, num)
        }
        for i in minval...maxval {
            var sum: Int64 = 0
            for num in nums {
                sum += Int64(abs(num - i))
            }
            ans = min(ans, sum)
        }
        return Int(ans)
    }
}

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

#medium
Задача: 333. Largest BST Subtree

Дан корень бинарного дерева, найдите самое большое поддерево, которое также является деревом бинарного поиска (BST), где "самое большое" означает поддерево с наибольшим количеством узлов.

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

Пример:

Input: root = [10,5,15,1,8,null,7]
Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.

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

1⃣Пост-упорядоченный обход дерева:
Обходите каждую ноду дерева в пост-упорядоченном порядке (left-right-root). Это позволит гарантировать, что обе поддеревья ноды уже проверены на соответствие критериям BST перед проверкой самой ноды.

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

3⃣Возврат максимального размера BST:
Если текущее поддерево не является BST, верните максимальный размер BST из его левого или правого поддерева.
В конце рекурсивного обхода верните максимальный размер BST в дереве.

😎 Решение:

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) { self.val = val; self.left = nil; self.right = nil }
}

class NodeValue {
    var minNode: Int
    var maxNode: Int
    var maxSize: Int
    
    init(_ minNode: Int, _ maxNode: Int, _ maxSize: Int) {
        self.minNode = minNode
        self.maxNode = maxNode
        self.maxSize = maxSize
    }
}

class Solution {
    func largestBSTSubtreeHelper(_ root: TreeNode?) -> NodeValue {
        if root == nil {
            return NodeValue(Int.max, Int.min, 0)
        }
        
        let left = largestBSTSubtreeHelper(root?.left)
        let right = largestBSTSubtreeHelper(root?.right)
        
        if left.maxNode < root!.val && root!.val < right.minNode {
            return NodeValue(min(root!.val, left.minNode), max(root!.val, right.maxNode), 
                             left.maxSize + right.maxSize + 1)
        }
        
        return NodeValue(Int.min, Int.max, max(left.maxSize, right.maxSize))
    }
    
    func largestBSTSubtree(_ root: TreeNode?) -> Int {
        return largestBSTSubtreeHelper(root).maxSize
    }
}

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

#easy
Задача: 374. Guess Number Higher or Lower

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

Я загадываю число от 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 {
    func guessNumber(_ n: Int) -> Int {
        var low = 1
        var high = n
        while low <= high {
            let mid = low + (high - low) / 2
            let res = guess(mid)
            if res == 0 {
                return mid
            } else if res < 0 {
                high = mid - 1
            } else {
                low = mid + 1
            }
        }
        return -1
    }
}

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

#Medium
Задача: 477. Total Hamming Distance

Хэммингово расстояние между двумя целыми числами — это количество позиций, в которых соответствующие биты отличаются.

Дан целочисленный массив nums, верните сумму Хэмминговых расстояний между всеми парами чисел в nums.

Пример:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

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

1⃣Для каждой уникальной пары элементов из массива вычисляем битовое XOR, чтобы найти позиции, где биты различаются. Бит, равный 1 в результате, указывает на различие.
2⃣Для каждой пары элементов используем XOR, чтобы получить битовую разницу, и подсчитываем количество битов, равных 1, чтобы определить Хэммингово расстояние между парой.
3⃣Суммируем все Хэмминговы расстояния для всех пар, чтобы получить общую сумму Хэмминговых расстояний.

😎 Решение:

class Solution {
    func totalHammingDistance(_ nums: [Int]) -> Int {
        var ans = 0
        
        if nums.isEmpty {
            return ans
        }
        
        for i in 0..<nums.count - 1 {
            for j in i + 1..<nums.count {
                ans += (nums[i] ^ nums[j]).nonzeroBitCount
            }
        }
        
        return ans
    }
}

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

#easy
Задача: 375. Guess Number Higher or Lower II

Мы играем в угадайку. Правила игры следующие:

Я загадываю число между 1 и n.
Вы угадываете число.
Если вы угадаете правильное число, вы выигрываете игру.
Если вы угадаете неправильное число, я скажу вам, загаданное число больше или меньше, и вы продолжите угадывать.
Каждый раз, когда вы угадываете неправильное число x, вы платите x долларов. Если у вас закончились деньги, вы проигрываете игру.
Дано число n. Верните минимальную сумму денег, необходимую для гарантированной победы независимо от того, какое число я загадаю.
Пример:

Input: n = 1
Output: 0
Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.

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

1⃣В методе "грубой силы" для чисел в диапазоне (i, j) выбираем каждое число от i до j в качестве опорного и находим максимальную стоимость из его левых и правых сегментов. Если выбрать число из диапазона (i, (i + j) / 2) как опорное, правый сегмент будет длиннее левого, что приведет к большему максимальному затратам из правого сегмента.

2⃣Наша цель - уменьшить большие затраты, приходящиеся на правый сегмент. Поэтому целесообразно выбирать опорное число из диапазона ((i + j) / 2, j). В этом случае затраты на оба сегмента будут ближе друг к другу, что минимизирует общую стоимость.

3⃣Вместо перебора от i до j, итерируем от (i + j) / 2 до j, находя минимально возможные затраты аналогично методу грубой силы.

😎 Решение:

class Solution {
    func calculate(_ low: Int, _ high: Int) -> Int {
        if low >= high {
            return 0
        }
        var minres = Int.max
        for i in low...high {
            let res = i + max(calculate(i + 1, high), calculate(low, i - 1))
            minres = min(res, minres)
        }
        return minres
    }

    func getMoneyAmount(_ n: Int) -> Int {
        return calculate(1, n)
    }
}

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

#medium
Задача: 334. Increasing Triplet Subsequence

Дан массив целых чисел nums. Верните true, если существуют такие три индекса (i, j, k), что i < j < k и nums[i] < nums[j] < nums[k]. Если таких индексов не существует, верните false.

Пример:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

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

1⃣Инициализация переменных:
Создайте две переменные first_num и second_num и установите их значение на максимальное целое значение (Integer.MAX_VALUE или аналогичный максимум для выбранного языка программирования). Эти переменные будут хранить минимальные значения, необходимые для проверки существования возрастающей тройки.

2⃣Итерация по массиву:
Пройдите по каждому элементу массива nums. Для каждого элемента выполните следующие проверки:
- если текущий элемент меньше или равен first_num, обновите first_num текущим элементом.
- иначе, если текущий элемент меньше или равен second_num, обновите second_num текущим элементом.
- иначе, если текущий элемент больше second_num, это означает, что найдена возрастающая тройка, поэтому верните true.

3⃣Возврат результата:
Если после завершения итерации по массиву не была найдена возрастающая тройка, верните false.

😎 Решение:

class Solution {
    func increasingTriplet(_ nums: [Int]) -> Bool {
        var firstNum = Int.max
        var secondNum = Int.max
        
        for n in nums {
            if n <= firstNum {
                firstNum = n
            } else if n <= secondNum {
                secondNum = n
            } else {
                return true
            }
        }
        return false
    }
}

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

#medium
Задача: 377. Combination Sum IV

Дан массив различных целых чисел nums и целое число target. Верните количество возможных комбинаций, которые в сумме дают target.

Тестовые случаи сгенерированы так, что ответ помещается в 32-битное целое число.

Пример:

Input: nums = [9], target = 3
Output: 0

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

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

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

3⃣Здесь, соответственно, мы определяем рекурсивную функцию под названием combs(remain), которая возвращает количество комбинаций, где каждая комбинация в сумме дает значение remain.

😎 Решение:

class Solution {
    private var memo: [Int: Int] = [:]

    func combinationSum4(_ nums: [Int], _ target: Int) -> Int {
        return combs(nums, target)
    }

    private func combs(_ nums: [Int], _ remain: Int) -> Int {
        if remain == 0 {
            return 1
        }
        if let val = memo[remain] {
            return val
        }

        var result = 0
        for num in nums {
            if remain - num >= 0 {
                result += combs(nums, remain - num)
            }
        }
        memo[remain] = result
        return result
    }
}

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

#hard
Задача: 336. Palindrome Pairs

Вам дан массив уникальных строк words, индексируемый с 0.

Пара палиндромов — это пара целых чисел (i, j), таких что:
0 <= i, j < words.length,
i != j, и
words[i] + words[j] (конкатенация двух строк) является палиндромом.
Верните массив всех пар палиндромов из слов.

Вы должны написать алгоритм с временной сложностью O(сумма длин всех слов в words).

Пример:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

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

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

2⃣ Итерация по всем парам слов и проверка:
Пройдите по всем парам слов в массиве words, используя два вложенных цикла.
Для каждой пары слов проверяйте, образуют ли они палиндром при конкатенации. Это делается путем объединения строк и проверки, равна ли объединенная строка своей обратной версии.

3⃣ Добавление найденных пар в результат:
Если проверка на палиндром проходит, добавьте текущую пару индексов в список результатов.
Верните итоговый список всех найденных пар.

😎 Решение:

class Solution {
    func palindromePairs(_ words: [String]) -> [[Int]] {
        var pairs = [[Int]]()
        
        for i in 0..<words.count {
            for j in 0..<words.count {
                if i == j { continue }
                let combined = words[i] + words[j]
                if combined == String(combined.reversed()) {
                    pairs.append([i, j])
                }
            }
        }
        
        return pairs
    }
}

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

#medium
Задача: 465. Optimal Account Balancing

Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi.

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

Пример:

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2

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

1⃣Создать хеш-таблицу для хранения чистого баланса каждого человека.

2⃣Собрать все ненулевые чистые балансы в массив balance_list.

3⃣Определить рекурсивную функцию dfs(cur) для очистки всех балансов в диапазоне balance_list[0 ~ cur]:
Игнорировать cur, если баланс уже равен 0. Пока balance_list[cur] = 0, переходить к следующему человеку, увеличивая cur на 1.
Если cur = n, вернуть 0.
В противном случае установить cost на большое значение, например, inf.
Пройтись по индексу nxt от cur + 1, если balance_list[nxt] * balance_list[cur] < 0,
Добавить баланс balance_list[cur] к balance_list[nxt]: balance_list[nxt] += balance_list[cur].
Рекурсивно вызвать dfs(cur + 1) как dfs(cur) = 1 + dfs(cur + 1).
Убрать ранее переданный баланс от cur: balance_list[nxt] -= balance_list[cur] (откат).
Повторить с шага 5 и отслеживать минимальное количество операций cost = min(cost, 1 + dfs(cur + 1)), найденных в итерации.
Вернуть cost, когда итерация завершена. Вернуть dfs(0).

😎 Решение:

class Solution {
    var creditList = [Int]()
    
    func minTransfers(_ transactions: [[Int]]) -> Int {
        var creditMap = [Int: Int]()
        for t in transactions {
            creditMap[t[0], default: 0] += t[2]
            creditMap[t[1], default: 0] -= t[2]
        }
        
        for amount in creditMap.values {
            if amount != 0 {
                creditList.append(amount)
            }
        }
        
        let n = creditList.count
        return dfs(0, n)
    }
    
    private func dfs(_ cur: Int, _ n: Int) -> Int {
        var cur = cur
        while cur < n && creditList[cur] == 0 {
            cur += 1
        }
        
        if cur == n {
            return 0
        }
        
        var cost = Int.max
        for nxt in cur+1..<n {
            if creditList[nxt] * creditList[cur] < 0 {
                creditList[nxt] += creditList[cur]
                cost = min(cost, 1 + dfs(cur + 1, n))
                creditList[nxt] -= creditList[cur]
            }
        }
        
        return cost
    }
}

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

#medium
Задача: 337. House Robber III

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

Дано корневое дерево бинарного дерева, верните максимальную сумму денег, которую вор может украсть, не уведомляя полицию.

Пример:

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

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

1⃣ Инициализация и базовый случай:
Создайте вспомогательную функцию helper, которая принимает узел в качестве входных данных и возвращает массив из двух элементов, где первый элемент представляет максимальную сумму денег, которую можно украсть, если не грабить этот узел, а второй элемент - если грабить этот узел.
Базовый случай для вспомогательной функции - узел null, и в этом случае функция возвращает массив из двух нулей [0, 0].

2⃣ Рекурсивное исследование дерева:
В функции helper вызывайте её рекурсивно для левого и правого поддеревьев текущего узла.
Если грабить текущий узел, то нельзя грабить его потомков, поэтому сумма будет равна значению текущего узла плюс максимальные суммы для случаев, когда потомки не грабятся.
Если не грабить текущий узел, то можно свободно выбирать, грабить потомков или нет, поэтому сумма будет равна максимальной сумме из двух вариантов для каждого потомка.

3⃣ Возврат результата:
В основной функции rob вызовите helper для корня дерева и верните максимальное значение из двух элементов массива, возвращенного функцией helper.

😎 Решение:

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) { self.val = val; self.left = nil; self.right = nil }
}

class Solution {
    func rob(_ root: TreeNode?) -> Int {
        let answer = helper(root)
        return max(answer[0], answer[1])
    }
    
    func helper(_ node: TreeNode?) -> [Int] {
        if node == nil {
            return [0, 0]
        }
        let left = helper(node?.left)
        let right = helper(node?.right)
        let rob = node!.val + left[1] + right[1]
        let notRob = max(left[0], left[1]) + max(right[0], right[1])
        return [rob, notRob]
    }
}

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

#medium
Задача: 468. Validate IP Address

Допустимый IPv4-адрес — это IP в форме "x1.x2.x3.x4", где 0 <= xi <= 255 и xi не может содержать ведущие нули. Например, "192.168.1.1" и "192.168.1.0" являются допустимыми IPv4-адресами, тогда как "192.168.01.1", "192.168.1.00" и "[email protected]" являются недопустимыми IPv4-адресами.

Допустимый IPv6-адрес — это IP в форме "x1:x2:x3:x4:x5:x6:x7
", где:
1 <= xi.length <= 4
xi — это шестнадцатеричная строка, которая может содержать цифры, строчные английские буквы ('a' до 'f') и прописные английские буквы ('A' до 'F').
Ведущие нули в xi допускаются.

Пример:

Input: queryIP = "172.16.254.1"
Output: "IPv4"
Explanation: This is a valid IPv4 address, return "IPv4".

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

1⃣Для проверки адреса IPv4:
Разделить IP на четыре части по разделителю ".".
Проверить каждую подстроку:
Является ли она целым числом между 0 и 255.
Не содержит ли она ведущих нулей (исключение — число "0").

2⃣Для проверки адреса IPv6:
Разделить IP на восемь частей по разделителю ":".
Проверить каждую подстроку:
Является ли она шестнадцатеричным числом длиной от 1 до 4 символов.

3⃣Если IP не соответствует ни одному из форматов, вернуть "Neither".

😎 Решение:

class Solution {
    func validateIPv4(_ IP: String) -> String {
        let nums = IP.split(separator: ".", omittingEmptySubsequences: false)
        for x in nums {
            if x.count == 0 || x.count > 3 {
                return "Neither"
            }
            if x.first == "0" && x.count != 1 {
                return "Neither"
            }
            for ch in x {
                if !ch.isNumber {
                    return "Neither"
                }
            }
            if Int(x)! > 255 {
                return "Neither"
            }
        }
        return "IPv4"
    }

    func validateIPv6(_ IP: String) -> String {
        let nums = IP.split(separator: ":", omittingEmptySubsequences: false)
        let hexdigits = "0123456789abcdefABCDEF"
        for x in nums {
            if x.count == 0 || x.count > 4 {
                return "Neither"
            }
            for ch in x {
                if !hexdigits.contains(ch) {
                    return "Neither"
                }
            }
        }
        return "IPv6"
    }

    func validIPAddress(_ IP: String) -> String {
        if IP.filter({ $0 == "." }).count == 3 {
            return validateIPv4(IP)
        } else if IP.filter({ $0 == ":" }).count == 7 {
            return validateIPv6(IP)
        } else {
            return "Neither"
        }
    }
}

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

#easy
Задача: 338. Counting Bits

Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i.

Пример:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

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

1⃣ Инициализация массива:
Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n.

2⃣ Итерация и вычисление:
Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x.

3⃣ Возврат результата:
Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n.

😎 Решение:

class Solution {
    func countBits(_ num: Int) -> [Int] {
        var ans = [Int](repeating: 0, count: num + 1)
        for x in 1...num {
            ans[x] = ans[x & (x - 1)] + 1
        }
        return ans
    }
}

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

#medium
Задача: 538. Convert BST to Greater Tree

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

Напоминаем, что бинарное дерево поиска — это дерево, удовлетворяющее следующим условиям:

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

Пример:

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

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

1⃣Поддерживаем глобальное состояние, чтобы каждая рекурсивная функция могла получать и изменять текущую сумму. Проверяем существование текущего узла, рекурсивно обрабатываем правое поддерево.

2⃣Посещаем текущий узел, обновляем его значение и общую сумму.

3⃣Рекурсивно обрабатываем левое поддерево.

😎 Решение:

class Solution {
    private int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root != null) {
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}

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

#hard
Задача: 470. Implement Rand10() Using Rand7()

Дано API rand7(), которое генерирует случайное целое число в диапазоне [1, 7]. Напишите функцию rand10(), которая генерирует случайное целое число в диапазоне [1, 10]. Вы можете вызывать только API rand7(), и не должны вызывать другие API. Пожалуйста, не используйте встроенные в язык функции для генерации случайных чисел.

Каждый тестовый случай будет содержать один внутренний аргумент n, который указывает количество вызовов вашей реализованной функции rand10() во время тестирования. Обратите внимание, что это не аргумент, передаваемый в rand10().

Пример:

Input: n = 1
Output: [2]

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

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

2⃣Очевидно, что функцию rand7() необходимо вызвать минимум дважды, так как чисел в диапазоне от 1 до 7 недостаточно для генерации чисел от 1 до 10. При двукратном вызове функции rand7() можно получить равномерно распределенные целые числа от 1 до 49. Почему?

3⃣Использование таблицы отбора:
Таблица используется для иллюстрации концепции отбрасывающей выборки. Двукратный вызов rand7() даст индексы строки и столбца, которые соответствуют уникальной позиции в таблице. Представьте, что вы выбираете число случайным образом из таблицы. Если попадаете на число, немедленно возвращаете его. Если попадаете на *, повторяете процесс, пока не попадете на число.
Так как 49 не является кратным 10, необходимо использовать метод отбрасывающей выборки. Наш желаемый диапазон - это целые числа от 1 до 40, которые можно вернуть немедленно. Если выпадает число между 41 и 49, оно отбрасывается и процесс повторяется.

😎 Решение:

class Solution {
    func rand10() -> Int {
        var row: Int, col: Int, idx: Int
        repeat {
            row = rand7()
            col = rand7()
            idx = col + (row - 1) * 7
        } while (idx > 40)
        return 1 + (idx - 1) % 10
    }
}

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

#hard
Задача: 472. Concatenated Words

Дан массив строк words (без дубликатов). Верните все составные слова из данного списка слов.

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

Пример:

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; 
"dogcatsdog" can be concatenated by "dog", "cats" and "dog"; 
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

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

1⃣Для каждого слова в списке:
Построить неявный граф, в котором узлы представляют индексы символов в слове, а ребра представляют возможность перехода от одного индекса к другому, если подстрока между ними является словом из списка.

2⃣Использовать поиск в глубину (DFS) для проверки, можно ли достигнуть узел с индексом word.length от узла с индексом 0 в графе.

3⃣Если узел word.length достижим от узла 0, добавить слово в ответ.

😎 Решение:

class Solution {
    private func dfs(_ word: String, _ length: Int, _ visited: inout [Bool],
                     _ dictionary: Set<String>) -> Bool {
        if length == word.count {
            return true
        }
        if visited[length] {
            return false
        }
        visited[length] = true
        for i in stride(from: word.count - (length == 0 ? 1 : 0), to: length, by: -1) {
            let startIndex = word.index(word.startIndex, offsetBy: length)
            let endIndex = word.index(word.startIndex, offsetBy: i)
            let substring = String(word[startIndex..<endIndex])
            if dictionary.contains(substring) && dfs(word, i, &visited, dictionary) {
                return true
            }
        }
        return false
    }

    func findAllConcatenatedWordsInADict(_ words: [String]) -> [String] {
        let dictionary = Set(words)
        var answer = [String]()
        for word in words {
            var visited = [Bool](repeating: false, count: word.count)
            if dfs(word, 0, &visited, dictionary) {
                answer.append(word)
            }
        }
        return answer
    }
}

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

#medium
Задача: 378. Kth Smallest Element in a Sorted Matrix

Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице.

Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент.

Вы должны найти решение с использованием памяти лучше, чем O(n²).

Пример:

Input: matrix = [[-5]], k = 1
Output: -5

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

1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список.

2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку.

3⃣Мин-куча будет содержать тройки информации (значение, строка, столбец). Куча будет упорядочена по значениям, и мы будем использовать номера строк и столбцов для добавления следующего элемента, если текущий элемент будет удален из кучи.

😎 Решение:

class MyHeapNode {
    var row: Int
    var column: Int
    var value: Int

    init(_ value: Int, _ row: Int, _ column: Int) {
        self.value = value
        self.row = row
        self.column = column
    }
}

class Solution {
    func kthSmallest(_ matrix: [[Int]], _ k: Int) -> Int {
        let N = matrix.count
        var minHeap = PriorityQueue<MyHeapNode> { $0.value < $1.value }

        for r in 0..<min(N, k) {
            minHeap.enqueue(MyHeapNode(matrix[r][0], r, 0))
        }

        var element: MyHeapNode = minHeap.peek()!
        var k = k
        while k > 0 {
            element = minHeap.dequeue()!
            let r = element.row, c = element.column

            if c < N - 1 {
                minHeap.enqueue(MyHeapNode(matrix[r][c + 1], r, c + 1))
            }
            k -= 1
        }

        return element.value
    }
}

struct PriorityQueue<Element: Equatable> {
    private var elements: [Element]
    private let priorityFunction: (Element, Element) -> Bool

    init(priorityFunction: @escaping (Element, Element) -> Bool) {
        self.elements = []
        self.priorityFunction = priorityFunction
    }

    var isEmpty: Bool {
        return elements.isEmpty
    }

    func peek() -> Element? {
        return elements.first
    }

    mutating func enqueue(_ element: Element) {
        elements.append(element)
        siftUp(elementAtIndex: elements.count - 1)
    }

    mutating func dequeue() -> Element? {
        guard !isEmpty else { return nil }
        if elements.count == 1 {
            return elements.removeLast()
        } else {
            let value = elements[0]
            elements[0] = elements.removeLast()
            siftDown(elementAtIndex: 0)
            return value
        }
    }

    private mutating func siftUp(elementAtIndex index: Int) {
        let parent = parentIndex(of: index)
        guard !isRoot(index), isHigherPriority(at: index, than: parent) else { return }
        swapElement(at: index, with: parent)
        siftUp(elementAtIndex: parent)
    }

    private mutating func siftDown(elementAtIndex index: Int) {
        let childIndex = highestPriorityIndex(for: index)
        if index == childIndex { return }
        swapElement(at: index, with: childIndex)
        siftDown(elementAtIndex: childIndex)
    }

    private func isRoot(_ index: Int) -> Bool {
        return index == 0
    }

    private func leftChildIndex(of index: Int) -> Int {
        return 2 * index + 1
    }

    private func rightChildIndex(of index: Int) -> Int {
        return 2 * index + 2
    }

    private func parentIndex(of index: Int) -> Int {
        return (index - 1) / 2
    }

    private func isHigherPriority(at firstIndex: Int, than secondIndex: Int) -> Bool {
        return priorityFunction(elements[firstIndex], elements[secondIndex])
    }

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

#medium
Задача: 235. Lowest Common Ancestor of a Binary Search Tree

Дано бинарное дерево поиска (BST). Найдите наименьший общий предок (LCA) двух заданных узлов в BST.

Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)."

Пример:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

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

1⃣Начало обхода дерева с корня: Начните обход дерева с корневого узла. Проверьте, находятся ли узлы p и q в правом или левом поддереве текущего узла.

2⃣Продолжение поиска в поддереве: Если оба узла p и q находятся в правом поддереве текущего узла, продолжайте поиск в правом поддереве, начиная с шага 1. Если оба узла p и q находятся в левом поддереве текущего узла, продолжайте поиск в левом поддереве, начиная с шага 1.

3⃣Нахождение LCA: Если узлы p и q находятся в разных поддеревьях относительно текущего узла или один из узлов равен текущему узлу, то текущий узел является наименьшим общим предком (LCA). Верните этот узел как результат.

😎 Решение:

class Solution {
    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode, _ q: TreeNode) -> TreeNode? {
        guard let root = root else { return nil }
        
        let parentVal = root.val
        let pVal = p.val
        let qVal = q.val

        if pVal > parentVal && qVal > parentVal {
            return lowestCommonAncestor(root.right, p, q)
        } else if pVal < parentVal && qVal < parentVal {
            return lowestCommonAncestor(root.left, p, q)
        } else {
            return root
        }
    }
}

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