Задача: 101. Symmetric Tree
Сложность: easy

Дан корень бинарного дерева. Проверьте, является ли это дерево зеркальным отражением самого себя (то есть симметричным относительно своего центра).

Пример:

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

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

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

2⃣Следовательно, вопрос заключается в том, когда два дерева являются зеркальным отражением друг друга?
Два дерева являются зеркальным отражением друг друга, если:
- Их корни имеют одинаковое значение.
- Правое поддерево каждого дерева является зеркальным отражением левого поддерева другого дерева.

3⃣Это похоже на человека, смотрящего в зеркало. Отражение в зеркале имеет ту же голову, но правая рука отражения соответствует левой руке настоящего человека и наоборот.
Вышеописанное объяснение естественным образом превращается в рекурсивную функцию.

😎 Решение:

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

class Solution {
    func isSymmetric(_ root: TreeNode?) -> Bool {
        return isMirror(root, root)
    }

    private func isMirror(_ t1: TreeNode?, _ t2: TreeNode?) -> Bool {
        if t1 == nil && t2 == nil {
            return true
        }
        if t1 == nil || t2 == nil {
            return false
        }
        return t1!.val == t2!.val && isMirror(t1!.right, t2!.left) && isMirror(t1!.left, t2!.right)
    }
}

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

Задача: 1031. Maximum Sum of Two Non-Overlapping Subarrays
Сложность: medium

Если задан целочисленный массив nums и два целых числа firstLen и secondLen, верните максимальную сумму элементов в двух непересекающихся подмассивах с длинами firstLen и secondLen. Массив с длиной firstLen может находиться до или после массива с длиной secondLen, но они должны быть непересекающимися. Подмассив - это смежная часть массива.

Пример:

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20

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

1⃣Предварительные вычисления:
Вычислите сумму всех подмассивов длины firstLen и secondLen и сохраните их в списках.

2⃣Поиск максимальной суммы:
Переберите все возможные позиции для подмассива длины firstLen и для каждого такого подмассива найдите максимальную сумму для подмассива длины secondLen, который не пересекается с текущим подмассивом длины firstLen.

3⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.

😎 Решение:

class Solution {
    func maxSumTwoNoOverlap(_ nums: [Int], _ firstLen: Int, _ secondLen: Int) -> Int {
        func maxSumNonOverlap(_ nums: [Int], _ firstLen: Int, _ secondLen: Int) -> Int {
            let n = nums.count
            var prefix = [Int](repeating: 0, count: n + 1)
            for i in 0..<n {
                prefix[i + 1] = prefix[i] + nums[i]
            }
            
            var maxFirst = [Int](repeating: 0, count: n)
            for i in firstLen - 1..<n {
                maxFirst[i] = max((i > 0 ? maxFirst[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - firstLen])
            }
            
            var maxSecond = [Int](repeating: 0, count: n)
            for i in secondLen - 1..<n {
                maxSecond[i] = max((i > 0 ? maxSecond[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - secondLen])
            }
            
            var maxSum = 0
            for i in firstLen + secondLen - 1..<n {
                maxSum = max(maxSum, maxFirst[i - secondLen] + (prefix[i + 1] - prefix[i + 1 - secondLen]))
            }
            
            return maxSum
        }
        
        return max(maxSumNonOverlap(nums, firstLen, secondLen), maxSumNonOverlap(nums.reversed(), secondLen, firstLen))
    }
}

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

Задача: 395. Longest Substring with At Least K Repeating Characters
Сложность: medium

Дана строка s и целое число k, верните длину самой длинной подстроки строки s, такая что частота каждого символа в этой подстроке больше или равна k.

Если такой подстроки не существует, верните 0.

Пример:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

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

1⃣Генерируйте подстроки из строки s, начиная с индекса start и заканчивая индексом end. Используйте массив countMap для хранения частоты каждого символа в подстроке.

2⃣Метод isValid использует countMap для проверки, что каждый символ в подстроке встречается как минимум k раз. Если условие выполняется, текущая подстрока считается допустимой.

3⃣Отслеживайте максимальную длину допустимой подстроки, обновляя её, когда найдена более длинная подстрока, удовлетворяющая условиям. В конце возвращайте длину самой длинной подстроки.

😎 Решение:

class Solution {
    func longestSubstring(_ s: String, _ k: Int) -> Int {
        let n = s.count
        if n == 0 || k > n {
            return 0
        }
        var countMap = [Int](repeating: 0, count: 26)
        var result = 0
        let sArray = Array(s)
        
        for start in 0..<n {
            countMap = [Int](repeating: 0, count: 26)
            for end in start..<n {
                countMap[Int(sArray[end].asciiValue! - Character("a").asciiValue!)] += 1
                if isValid(countMap, k) {
                    result = max(result, end - start + 1)
                }
            }
        }
        return result
    }
    
    func isValid(_ countMap: [Int], _ k: Int) -> Bool {
        var countLetters = 0, countAtLeastK = 0
        for count in countMap {
            if count > 0 { countLetters += 1 }
            if count >= k { countAtLeastK += 1 }
        }
        return countAtLeastK == countLetters
    }
}

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

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

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

Анаграмма — это слово или фраза, сформированная путём перестановки букв другого слова или фразы, обычно используя все исходные буквы ровно один раз.

Пример:

Input: s = "anagram", t = "nagaram"
Output: true

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

1⃣Создайте массив размером 26 для подсчета частот каждой буквы (поскольку s и t содержат только буквы от 'a' до 'z').

2⃣Пройдитесь по строке s, увеличивая счетчик соответствующей буквы. Затем пройдитесь по строке t, уменьшая счетчик для каждой буквы.

3⃣Проверьте, не опустился ли счетчик ниже нуля во время обхода строки t. Если это произошло, значит в t есть лишняя буква, которой нет в s, и следует вернуть false. Если после проверки всех букв все счетчики равны нулю, возвращайте true, указывая на то, что t является анаграммой s.

😎 Решение:

func isAnagram(_ s: String, _ t: String) -> Bool {
    if s.count != t.count {
        return false
    }
    var counts = Array(repeating: 0, count: 26)
    let aAscii = Int(Character("a").asciiValue!)
    for char in s.unicodeScalars {
        counts[Int(char.value) - aAscii] += 1
    }
    for char in t.unicodeScalars {
        let index = Int(char.value) - aAscii
        counts[index] -= 1
        if counts[index] < 0 {
            return false
        }
    }
    return true
}

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

Задача: 443. String Compression
Сложность: medium

Дан массив символов chars, сжать его, используя следующий алгоритм:

Начните с пустой строки s. Для каждой группы последовательных повторяющихся символов в chars:

Если длина группы равна 1, добавьте символ к строке s.
В противном случае добавьте символ, а за ним длину группы.
Сжатая строка s не должна возвращаться отдельно, а вместо этого должна быть сохранена в входном массиве символов chars. Обратите внимание, что длины групп, которые равны 10 или более, будут разделены на несколько символов в chars.

После того как вы закончите модификацию входного массива, верните новую длину массива.

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

Пример:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

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

1⃣Объявите переменные i – первый индекс текущей группы, и res – длина ответа (сжатой строки). Инициализируйте i = 0, res = 0.

2⃣Пока i меньше длины chars: Найдите длину текущей группы последовательных повторяющихся символов groupLength. Добавьте chars[i] к ответу (chars[res++] = chars[i]). Если groupLength > 1, добавьте строковое представление groupLength к ответу и увеличьте res соответственно. Увеличьте i на groupLength и перейдите к следующей группе.

3⃣Верните res.

😎 Решение:

class Solution {
    func compress(_ chars: inout [Character]) -> Int {
        var i = 0
        var res = 0
        while i < chars.count {
            var groupLength = 1
            while i + groupLength < chars.count && chars[i + groupLength] == chars[i] {
                groupLength += 1
            }
            chars[res] = chars[i]
            res += 1
            if groupLength > 1 {
                let strRepr = String(groupLength)
                for ch in strRepr {
                    chars[res] = ch
                    res += 1
                }
            }
            i += groupLength
        }
        return res
    }
}

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

Задача: 139. Word Break
Сложность: medium

Дана строка s и словарь строк wordDict. Верните true, если строку s можно разделить на последовательность одного или нескольких слов из словаря, разделённых пробелами.

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

Пример:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

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

1⃣Инициализация структур данных:
Преобразуйте wordDict в множество words для быстрой проверки вхождения.
Инициализируйте очередь queue начальным значением 0 (индекс начала строки) и множество seen для отслеживания посещённых индексов.

2⃣Обход в ширину (BFS):
Пока очередь не пуста, извлекайте первый элемент из очереди, обозначающий начальную позицию start.
Если start равен длине строки s, возвращайте true, так как достигнут конец строки, и строку можно разделить на слова из словаря.
Итерируйте end от start + 1 до s.length включительно. Для каждого end, проверьте, посещён ли он уже.

3⃣Проверка подстроки и обновление структур:
Проверьте подстроку начиная с start и заканчивая перед end. Если подстрока находится в множестве words, добавьте end в очередь и отметьте его в seen как посещённый.
Если BFS завершается и конечный узел не достигнут, возвращайте false.

😎 Решение:

func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
    let words = Set(wordDict)
    var queue = [0]
    var seen = Set<Int>()
    
    while !queue.isEmpty {
        let start = queue.removeFirst()
        if start == s.count {
            return true
        }
        for end in (start + 1)...s.count {
            if seen.contains(end) {
                continue
            }
            let startIndex = s.index(s.startIndex, offsetBy: start)
            let endIndex = s.index(s.startIndex, offsetBy: end)
            let substring = String(s[startIndex..<endIndex])
            if words.contains(substring) {
                queue.append(end)
                seen.insert(end)
            }
        }
    }
    return false
}

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

Задача: 362. Design Hit Counter
Сложность: medium

Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.

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

Пример:

Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]

Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.

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

1⃣При вызове метода hit(int timestamp), добавьте временную метку в очередь.

2⃣ При вызове метода getHits(int timestamp), удалите все временные метки из очереди, которые старше 300 секунд от текущей временной метки.

3⃣Верните размер очереди как количество попаданий за последние 5 минут.

😎 Решение:

class HitCounter {
    private var hits: [Int]

    init() {
        self.hits = [Int]()
    }

    func hit(_ timestamp: Int) {
        self.hits.append(timestamp)
    }

    func getHits(_ timestamp: Int) -> Int {
        while let first = self.hits.first, timestamp - first >= 300 {
            self.hits.removeFirst()
        }
        return self.hits.count
    }
}

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

Задача: 1151. Minimum Swaps to Group All 1's Together
Сложность: medium

Дан бинарный массив data, необходимо вернуть минимальное количество перестановок, чтобы сгруппировать все 1, присутствующие в массиве, вместе в любом месте массива.

Пример:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

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

1⃣Используем два указателя, left и right, чтобы поддерживать скользящее окно длиной ones и проверяем каждый фрагмент массива data, подсчитывая количество единиц в нем (cnt_one) и запоминая максимальное значение max_one.

2⃣Пока окно скользит по массиву data, поддерживаем его длину равной ones.

3⃣Обновляем количество единиц в окне, добавляя новую границу data[right] и вычитая левую границу data[left].

😎 Решение

class Solution {
    func minSwaps(_ data: [Int]) -> Int {
        let ones = data.reduce(0, +)
        var cnt_one = 0, max_one = 0
        var left = 0, right = 0

        while right < data.count {
            cnt_one += data[right]
            right += 1
            if right - left > ones {
                cnt_one -= data[left]
                left += 1
            }
            max_one = max(max_one, cnt_one)
        }
        return ones - max_one
    }
}

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

Задача: 1213. Intersection of Three Sorted Arrays
Сложность: easy

Даны три целочисленных массива arr1, arr2 и arr3, отсортированных в строго возрастающем порядке. Верните отсортированный массив, содержащий только те целые числа, которые присутствуют во всех трех массивах.

Пример:

Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
Output: [1,5]
Explanation: Only 1 and 5 appeared in the three arrays.

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

1⃣Инициализируйте counter как TreeMap для записи чисел, которые появляются в трех массивах, и количество их появлений.

2⃣Пройдитесь по массивам arr1, arr2 и arr3, чтобы посчитать частоты появления элементов.

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

😎 Решение:

class Solution {
    func arraysIntersection(_ arr1: [Int], _ arr2: [Int], _ arr3: [Int]) -> [Int] {
        var counter = [Int: Int]()
        for e in arr1 {
            counter[e, default: 0] += 1
        }
        for e in arr2 {
            counter[e, default: 0] += 1
        }
        for e in arr3 {
            counter[e, default: 0] += 1
        }

        var ans = [Int]()
        for (key, value) in counter where value == 3 {
            ans.append(key)
        }

        return ans
    }
}

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

Задача: 1275. Find Winner on a Tic Tac Toe Game
Сложность: easy

В игру "Крестики-нолики" играют два игрока A и B на сетке 3 x 3. Правила игры "Крестики-нолики" таковы: игроки по очереди помещают символы в пустые квадраты ' '. Первый игрок A всегда помещает символы "X", а второй игрок B - "O". Символы "X" и "O" всегда помещаются в пустые квадраты, а не в заполненные.
Игра заканчивается, когда три одинаковых (непустых) символа заполняют любую строку, столбец или диагональ. Игра также заканчивается, если все клетки непустые. Больше ходов не может быть сыграно, если игра закончена. Учитывая двумерный целочисленный массив moves, где moves[i] = [rowi, coli] указывает, что i-й ход будет сыгран на сетке[rowi][coli]. верните победителя игры, если он существует (A или B). Если игра закончилась вничью, верните "Ничья". Если еще есть ходы для игры, верните "Pending". Можно предположить, что ходы действительны (т.е. соответствуют правилам игры в Крестики-нолики), сетка изначально пуста, и A будет играть первым.

Пример:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"

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

1⃣Инициализируйте пустую 3x3 сетку.

2⃣Пройдите по списку ходов и обновите сетку в соответствии с ходами игроков A и B.

3⃣После каждого хода проверяйте, есть ли победитель. Если все ходы сделаны и нет победителя, проверьте, завершена ли игра вничью или еще есть ходы.

😎 Решение:

class Solution {
    func tictactoe(_ moves: [[Int]]) -> String {
        var grid = Array(repeating: Array(repeating: "", count: 3), count: 3)
        for (i, move) in moves.enumerated() {
            grid[move[0]][move[1]] = i % 2 == 0 ? "X" : "O"
        }

        for i in 0..<3 {
            if grid[i][0] == grid[i][1] && grid[i][1] == grid[i][2] && grid[i][0] != "" {
                return grid[i][0] == "X" ? "A" : "B"
            }
            if grid[0][i] == grid[1][i] && grid[1][i] == grid[2][i] && grid[0][i] != "" {
                return grid[0][i] == "X" ? "A" : "B"
            }
        }

        if grid[0][0] == grid[1][1] && grid[1][1] == grid[2][2] && grid[0][0] != "" {
            return grid[0][0] == "X" ? "A" : "B"
        }
        if grid[0][2] == grid[1][1] && grid[1][1] == grid[2][0] && grid[0][2] != "" {
            return grid[0][2] == "X" ? "A" : "B"
        }

        return moves.count == 9 ? "Draw" : "Pending"
    }
}

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

Задача: 126.Word Ladder II
Сложность: Hard

Последовательность преобразований от слова beginWord до слова endWord с использованием словаря wordList — это последовательность слов beginWord -> s1 -> s2 -> ... -> sk, для которой выполняются следующие условия:

Каждая пара соседних слов отличается ровно одной буквой.
Каждое si для 1 <= i <= k находится в wordList. Отметим, что beginWord не обязательно должно быть в wordList.
sk == endWord.
Для двух слов, beginWord и endWord, и словаря wordList, вернуть все самые короткие последовательности преобразований от beginWord до endWord или пустой список, если такая последовательность не существует. Каждая последовательность должна возвращаться в виде списка слов [beginWord, s1, s2, ..., sk].

Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation: There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

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

1⃣Сохранение слов из списка слов (wordList) в хэш-таблицу (unordered set) для эффективного удаления слов в процессе поиска в ширину (BFS).

2⃣Выполнение BFS, добавление связей в список смежности (adjList). После завершения уровня удалять посещенные слова из wordList.

3⃣Начать с beginWord и отслеживать текущий путь как currPath, просматривать все возможные пути, и когда путь ведет к endWord, сохранять путь в shortestPaths.

😎 Решение:

class Solution {
    var adjList = [String: [String]]()
    var shortestPaths = [[String]]()

    func findLadders(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> [[String]] {
        var wordSet = Set(wordList), queue = [beginWord]
        var isEnqueued = [beginWord: true]
        while !queue.isEmpty {
            var visited = [String]()
            for currWord in queue {
                queue.removeFirst()
                for i in 0..<currWord.count {
                    var wordArray = Array(currWord)
                    let oldChar = wordArray[i]
                    for c in Character("a").asciiValue!...Character("z").asciiValue! {
                        wordArray[i] = Character(UnicodeScalar(c))
                        let newWord = String(wordArray)
                        if newWord == currWord || !wordSet.contains(newWord) { continue }
                        visited.append(newWord)
                        adjList[newWord, default: []].append(currWord)
                        if !isEnqueued[newWord, default: false] {
                            queue.append(newWord)
                            isEnqueued[newWord] = true
                        }
                    }
                    wordArray[i] = oldChar
                }
            }
            visited.forEach { wordSet.remove($0) }
        }
        
        func backtrack(_ path: [String], _ word: String) {
            if word == endWord {
                shortestPaths.append(path.reversed())
                return
            }
            for neighbor in adjList[word, default: []] {
                backtrack(path + [neighbor], neighbor)
            }
        }
        
        backtrack([beginWord], beginWord)
        return shortestPaths
    }
}

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

🔥 Записал видос "Как за 3 минуты настроить Автоотклики на вакансии HeadHunter" больше не придется заниматься этой унылой рутиной

📺 Видео: https://youtu.be/G_FOwEGPwlw

Задача: 326. Power of Three
Сложность: easy

Дано целое число n. Верните true, если оно является степенью тройки, иначе верните false.

Целое число n является степенью тройки, если существует целое число x такое, что n == 3^x.

Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

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

1⃣Проверка начального значения
Если n меньше или равно нулю, вернуть false, так как степени тройки всегда положительны.

2⃣Цикл деления на 3
Пока n делится на 3 без остатка, делите n на 3. Повторяйте этот процесс до тех пор, пока n делится на 3.

3⃣Проверка конечного значения
Если после всех делений значение n стало равно 1, значит исходное число является степенью тройки, вернуть true. В противном случае вернуть false.

😎 Решение:

class Solution {
    func isPowerOfThree(_ n: Int) -> Bool {
        if n <= 0 {
            return false
        }
        var num = n
        while num % 3 == 0 {
            num /= 3
        }
        return num == 1
    }
}

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