#medium
Задача: 279. Perfect Squares

Дано целое число n, верните наименьшее количество чисел, являющихся совершенными квадратами, сумма которых равна n.

Совершенный квадрат — это целое число, являющееся квадратом целого числа; другими словами, это произведение некоторого целого числа на самого себя. Например, 1, 4, 9 и 16 являются совершенными квадратами, тогда как 3 и 11 не являются.

Пример:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

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

1⃣Инициализация:
Создайте массив dp размером n + 1 и заполните его значениями Integer.MAX_VALUE, кроме dp[0], которое установите в 0.
Предварительно вычислите все совершенные квадраты, которые меньше или равны n, и сохраните их в массиве square_nums.

2⃣Заполнение массива dp:
Для каждого числа i от 1 до n:
Для каждого совершенного квадрата s из массива square_nums:
Если i меньше текущего совершенного квадрата s, прервите внутренний цикл.
Обновите dp[i], чтобы он содержал минимальное количество чисел, сумма которых равна i.

3⃣Возврат результата:
Верните значение dp[n], которое будет содержать наименьшее количество совершенных квадратов, сумма которых равна n.

😎 Решение:

class Solution {
    func numSquares(_ n: Int) -> Int {
        var dp = [Int](repeating: Int.max, count: n + 1)
        dp[0] = 0
        
        let maxSquareIndex = Int(Double(n).squareRoot()) + 1
        var squareNums = [Int](repeating: 0, count: maxSquareIndex)
        for i in 1..<maxSquareIndex {
            squareNums[i] = i * i
        }
        
        for i in 1...n {
            for s in 1..<maxSquareIndex {
                if i < squareNums[s] {
                    break
                }
                dp[i] = min(dp[i], dp[i - squareNums[s]] + 1)
            }
        }
        
        return dp[n]
    }
}

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

#medium
Задача: 382. Linked List Random Node

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

Реализуйте класс Solution:

Solution(ListNode head) Инициализирует объект с головой односвязного списка head.
int getRandom() Выбирает узел случайным образом из списка и возвращает его значение. Все узлы списка должны иметь равные шансы быть выбранными.

Пример:

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

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

1⃣Реализуйте интерфейс init(head), который будет вызываться при создании объекта. Преобразуйте связанный список в массив для дальнейшего использования.

2⃣В интерфейсе init(head) преобразуйте переданный связанный список в массив, чтобы его можно было использовать позже.

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

😎 Решение:

class Solution {
    private var range = [Int]()

    init(_ head: ListNode?) {
        var current = head
        while current != nil {
            range.append(current!.val)
            current = current!.next
        }
    }

    func getRandom() -> Int {
        let pick = Int.random(in: 0..<range.count)
        return range[pick]
    }
}

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

#easy
Задача: 383. Ransom Note

Даны две строки ransomNote и magazine, верните true, если ransomNote можно составить, используя буквы из magazine, и false в противном случае.

Каждая буква из magazine может быть использована в ransomNote только один раз.

Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

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

1⃣Поскольку строки являются неизменяемым типом, их нельзя изменять, поэтому у них нет операций "вставки" и "удаления".

2⃣По этой причине необходимо заменять строку magazine новой строкой, в которой отсутствует символ, который мы хотели удалить.

3⃣Повторяйте этот процесс, пока не будут удалены все необходимые символы.

😎 Решение:

func canConstruct(_ ransomNote: String, _ magazine: String) -> Bool {
    var magazine = magazine
    
    for char in ransomNote {
        if let index = magazine.firstIndex(of: char) {
            magazine.remove(at: index)
        } else {
            return false
        }
    }
    return true
}

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

#medium
Задача: 368. Largest Divisible Subset

Дан набор различных положительных целых чисел nums. Вернуть наибольшее подмножество answer, такое что каждая пара (answer[i], answer[j]) элементов в этом подмножестве удовлетворяет условию:

answer[i] % answer[j] == 0, или
answer[j] % answer[i] == 0
Если существует несколько решений, вернуть любое из них.

Пример:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

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

1⃣Если число 8 может быть разделено на элемент X_i, то добавив число 8 к EDS(X_i), мы получим еще одно делимое подмножество, которое заканчивается на 8, согласно нашему следствию I. И это новое подмножество является потенциальным значением для EDS(8). Например, поскольку 8 % 2 == 0, то {2,8} может быть конечным значением для EDS(8), и аналогично для подмножества {2,4,8}, полученного из EDS(4).

2⃣Если число 8 не может быть разделено на элемент X_i, то можно быть уверенным, что значение EDS(X_i) не повлияет на EDS(8), согласно определению делимого подмножества. Например, подмножество EDS(7)={7} не имеет влияния на EDS(8).

3⃣Затем мы выбираем наибольшие новые подмножества, которые мы формируем с помощью EDS(X_i). В частности, подмножество {8} является допустимым кандидатом для EDS(8). И в гипотетическом случае, когда 8 не может быть разделено ни на один из предыдущих элементов, мы бы имели EDS(8)={8}.

😎 Решение:

class Solution {
    func largestDivisibleSubset(_ nums: [Int]) -> [Int] {
        let n = nums.count
        if n == 0 { return [] }

        var EDS = Array(repeating: [Int](), count: n)
        var nums = nums.sorted()

        // Calculate all the values of EDS(X_i)
        for i in 0..<n {
            var maxSubset = [Int]()

            for k in 0..<i {
                if nums[i] % nums[k] == 0 && maxSubset.count < EDS[k].count {
                    maxSubset = EDS[k]
                }
            }

            EDS[i] = maxSubset + [nums[i]]
        }

        var ret = [Int]()
        for subset in EDS {
            if ret.count < subset.count {
                ret = subset
            }
        }
        return ret
    }
}

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

#medium
Задача: 384. Shuffle an Array

Дан целочисленный массив nums. Разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятны в результате перемешивания.

Реализуйте класс Solution:

Solution(int[] nums): Инициализирует объект целочисленным массивом nums.
int[] reset(): Сбрасывает массив в его исходную конфигурацию и возвращает его.
int[] shuffle(): Возвращает случайное перемешивание массива.

Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

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

1⃣Алгоритм Фишера-Йейтса удивительно похож на решение грубой силы. На каждой итерации алгоритма мы генерируем случайное целое число между текущим индексом и последним индексом массива.

2⃣Затем мы меняем местами элементы на текущем индексе и выбранном индексе. Это симулирует выбор (и удаление) элемента из "шляпы", так как следующий диапазон, из которого мы выбираем случайный индекс, не будет включать последний обработанный элемент.

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

😎 Решение:

class Solution {
    private var array: [Int]
    private let original: [Int]

    init(_ nums: [Int]) {
        self.array = nums
        self.original = nums
    }

    func reset() -> [Int] {
        self.array = self.original
        return self.original
    }

    func shuffle() -> [Int] {
        for i in 0..<array.count {
            let randIndex = Int.random(in: i..<array.count)
            array.swapAt(i, randIndex)
        }
        return array
    }
}

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

#easy
Задача: 387. First Unique Character in a String

Дана строка s, найдите первый неповторяющийся символ в ней и верните его индекс. Если такого символа не существует, верните -1.

Пример:

Input: s = "leetcode"
Output: 0

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

1⃣Постройте хеш-таблицу, где ключами являются символы строки, а значениями — количество их появлений. Для этого пройдите по строке и для каждого символа увеличивайте его счетчик в хеш-таблице.

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

3⃣Если найдется символ с количеством появлений, равным 1, верните его индекс. Если такой символ не найден, верните -1.

😎 Решение:

class Solution {
    private var original: [Int]
    private var array: [Int]

    init(_ nums: [Int]) {
        self.original = nums
        self.array = nums
    }

    func reset() -> [Int] {
        self.array = self.original
        return self.original
    }

    func shuffle() -> [Int] {
        let n = array.count
        for i in 0..<n {
            let randIndex = Int.random(in: i..<n)
            array.swapAt(i, randIndex)
        }
        return array
    }
}

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

#hard
Задача: 369. Plus One Linked List

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

Цифры хранятся таким образом, что самая значимая цифра находится в начале списка.

Пример:

Input: head = [1,2,3]
Output: [1,2,4]

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

1⃣Инициализируйте стражевой узел как ListNode(0) и установите его как новую голову списка: sentinel.next = head. Найдите крайний правый элемент, не равный девяти.

2⃣Увеличьте найденную цифру на единицу и установите все следующие девятки в ноль.

3⃣Верните sentinel, если его значение было установлено на 1, иначе верните head (sentinel.next).

😎 Решение:

class ListNode {
    var val: Int
    var next: ListNode?
    init(_ val: Int) { self.val = val; self.next = nil }
}

class Solution {
    func plusOne(_ head: ListNode?) -> ListNode? {
        let sentinel = ListNode(0)
        sentinel.next = head
        var notNine = sentinel

        var current = head
        while current != nil {
            if current!.val != 9 {
                notNine = current!
            }
            current = current!.next
        }

        notNine.val += 1
        notNine = notNine.next

        while notNine != nil {
            notNine!.val = 0
            notNine = notNine!.next
        }

        return sentinel.val == 0 ? sentinel.next : sentinel
    }
}

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

#easy
Задача: 389. Find the Difference

Даны две строки s и t.

Строка t генерируется путем случайного перемешивания строки s с добавлением еще одной буквы в случайную позицию.

Верните букву, которая была добавлена в t.

Пример:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

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

1⃣Отсортируйте строки s и t.

2⃣Итерируйте по длине строк и сравнивайте их посимвольно. Это позволяет проверить, присутствует ли текущий символ строки t в строке s.

3⃣Как только встретится символ, который есть в строке t, но отсутствует в строке s, мы найдем лишний символ, который скрывала строка t все это время.

😎 Решение:

class Solution {
    func findTheDifference(_ s: String, _ t: String) -> Character {
        let sortedS = s.sorted()
        let sortedT = t.sorted()

        for i in 0..<sortedS.count {
            if sortedS[i] != sortedT[i] {
                return sortedT[i]
            }
        }

        return sortedT[sortedS.count]
    }
}

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

#easy
Задача: 290. Word Pattern

Дан шаблон и строка s, необходимо определить, следует ли строка s этому шаблону.

Здесь "следует" означает полное соответствие, такое что существует биекция между буквой в шаблоне и непустым словом в строке s.

Пример:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true

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

1⃣Разделение строки на слова:
Разделите строку s на отдельные слова.
Если количество слов не равно длине шаблона, возвращаем false.

2⃣Создание отображений:
Создайте два словаря: один для отображения букв шаблона на слова, другой для слов на буквы шаблона.

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

😎 Решение:

class Solution {
    func wordPattern(_ pattern: String, _ s: String) -> Bool {
        var mapChar = [Character: String]()
        var mapWord = [String: Character]()
        let words = s.split(separator: " ")

        if words.count != pattern.count {
            return false
        }

        for (i, word) in words.enumerated() {
            let c = pattern[pattern.index(pattern.startIndex, offsetBy: i)]
            let w = String(word)
            if mapChar[c] == nil {
                if mapWord[w] != nil {
                    return false
                } else {
                    mapChar[c] = w
                    mapWord[w] = c
                }
            } else {
                if mapChar[c] != w {
                    return false
                }
            }
        }

        return true
    }
}

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

#easy
Задача: 392. Is Subsequence

Даны две строки s и t. Верните true, если s является подпоследовательностью t, иначе верните false.

Подпоследовательность строки — это новая строка, которая формируется из исходной строки путем удаления некоторых (возможно, ни одного) символов без нарушения относительных позиций оставшихся символов. (например, "ace" является подпоследовательностью "abcde", тогда как "aec" не является).

Пример:

Input: s = "abc", t = "ahbgdc"
Output: true

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

1⃣Назначьте два указателя: левый для исходной строки и правый для целевой строки. Эти указатели будут использоваться для итерации по строкам и сравнения их символов.

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

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

😎 Решение:

class Solution {
    func isSubsequence(_ s: String, _ t: String) -> Bool {
        let leftBound = s.count, rightBound = t.count
        var pLeft = 0, pRight = 0

        let sArray = Array(s)
        let tArray = Array(t)

        while pLeft < leftBound && pRight < rightBound {
            if sArray[pLeft] == tArray[pRight] {
                pLeft += 1
            }
            pRight += 1
        }
        return pLeft == leftBound
    }
}

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

#medium
Задача: 291. Word Pattern II

Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.

Строка s соответствует шаблону, если существует биективное отображение отдельных символов на непустые строки так, что если каждый символ в шаблоне заменить на строку, которой он отображается, то результирующая строка будет равна s. Биективное отображение означает, что ни два символа не отображаются на одну и ту же строку, и ни один символ не отображается на две разные строки.

Пример:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

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

1⃣Инициализация структур данных и определение рекурсивной функции:
Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s.
Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ.
Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону.

2⃣Рекурсивная проверка соответствия:
Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false.
Получите символ из шаблона по индексу pIndex.
Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне.

3⃣Отображение новых подстрок:
Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки.
Для каждой новой подстроки проверьте, существует ли она уже в `

😎 Решение:

class Solution {
    func wordPatternMatch(_ pattern: String, _ s: String) -> Bool {
        var symbolMap = [Character: String]()
        var wordSet = Set<String>()
        return isMatch(s, 0, pattern, 0, &symbolMap, &wordSet)
    }

    private func isMatch(_ s: String, _ sIndex: Int, _ pattern: String, _ pIndex: Int,
                         _ symbolMap: inout [Character: String], _ wordSet: inout Set<String>) -> Bool {
        if pIndex == pattern.count {
            return sIndex == s.count
        }
        let symbol = pattern[pattern.index(pattern.startIndex, offsetBy: pIndex)]
        if let word = symbolMap[symbol] {
            if !s.hasPrefix(word, from: sIndex) {
                return false
            }
            return isMatch(s, sIndex + word.count, pattern, pIndex + 1, &symbolMap, &wordSet)
        }
        for k in sIndex + 1...s.count {
            let newWord = String(s[s.index(s.startIndex, offsetBy: sIndex)..<s.index(s.startIndex, offsetBy: k)])
            if wordSet.contains(newWord) {
                continue
            }
            symbolMap[symbol] = newWord
            wordSet.insert(newWord)
            if isMatch(s, k, pattern, pIndex + 1, &symbolMap, &wordSet) {
                return true
            }
            symbolMap[symbol] = nil
            wordSet.remove(newWord)
        }
        return false
    }
}

extension String {
    func hasPrefix(_ prefix: String, from index: Int) -> Bool {
        return self[index..<index + prefix.count] == prefix
    }

    subscript (bounds: Range<Int>) -> Substring {
        let start = index(startIndex, offsetBy: bounds.lowerBound)
        let end = index(startIndex, offsetBy: bounds.upperBound)
        return self[start..<end]
    }
}

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

#easy
Задача: 292. Nim Game

Вы играете в следующую игру Nim со своим другом:

Изначально на столе лежит куча камней.
Вы и ваш друг поочередно делаете ходы, и вы ходите первым.
Каждый ход игрок, чей ход, будет убирать от 1 до 3 камней из кучи.
Тот, кто убирает последний камень, становится победителем.
Дано n, количество камней в куче. Верните true, если вы можете выиграть игру, предполагая, что и вы, и ваш друг играете оптимально, иначе верните false.

Пример:

Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

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

1⃣Определите базовый случай:
Если количество камней n меньше или равно 3, вы всегда можете выиграть, убрав все камни. В этом случае верните true.

2⃣Анализ оставшихся камней:
Если количество камней n делится на 4 без остатка (n % 4 == 0), вы не можете выиграть, так как независимо от вашего хода ваш друг всегда сможет оставить вам кратное 4 количество камней. В этом случае верните false.

3⃣Выигрышная стратегия:
Если количество камней n не кратно 4 (n % 4 != 0), вы можете выиграть, оставляя вашему другу кратное 4 количество камней после вашего хода. В этом случае верните true.

😎 Решение:

class Solution {
    func canWinNim(_ n: Int) -> Bool {
        return n % 4 != 0
    }
}

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

#easy
Задача: 293. Flip Game

Вы играете в игру Flip со своим другом.

Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда один из игроков больше не может сделать ход, и, следовательно, другой игрок становится победителем.

Верните все возможные состояния строки currentState после одного допустимого хода. Вы можете вернуть ответы в любом порядке. Если допустимых ходов нет, верните пустой список [].

Пример:

Input: currentState = "++++"
Output: ["--++","+--+","++--"]

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

1⃣Создайте пустой массив nextPossibleStates для хранения всех возможных следующих состояний после одного хода.

2⃣Запустите цикл от index = 0 до currentState.size() - 1. Для каждого индекса:
Если символы на позициях index и index + 1 равны '+':
Создайте новую строку nextState, заменив две последовательные '+' на '--'.
Используйте конкатенацию строк для создания nextState из подстроки до первого '+', "--" и подстроки после второго '+' до конца.
Сохраните созданное nextState в массив nextPossibleStates.

3⃣После цикла верните массив nextPossibleStates, содержащий все возможные следующие состояния.

😎 Решение:

class Solution {
    func generatePossibleNextMoves(_ currentState: String) -> [String] {
        var nextPossibleStates: [String] = []

        for index in 0..<(currentState.count - 1) {
            let currentIndex = currentState.index(currentState.startIndex, offsetBy: index)
            let nextIndex = currentState.index(currentState.startIndex, offsetBy: index + 1)
            if currentState[currentIndex] == "+" && currentState[nextIndex] == "+" {
                let nextState = (
                    currentState.prefix(index) + 
                    "--" + 
                    currentState.suffix(from: currentState.index(currentState.startIndex, offsetBy: index + 2))
                )
                nextPossibleStates.append(String(nextState))
            }
        }

        return nextPossibleStates
    }
}

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

#medium
Задача: 393. UTF-8 Validation

Дан целочисленный массив data, представляющий данные, верните, является ли это допустимой UTF-8 кодировкой (т.е. переводится в последовательность допустимых UTF-8 закодированных символов).

Символ в UTF-8 может быть от 1 до 4 байтов в длину, при этом соблюдаются следующие правила:

Для 1-байтового символа первый бит — 0, за которым следует его Unicode код.
Для n-байтового символа первые n битов — все единицы, (n + 1)-й бит — 0, за которыми следуют n - 1 байт с наиболее значимыми 2 битами, равными 10.
Это работает следующим образом:

     Количество байтов  |        UTF-8 Октетная последовательность
                       |              (бинарная)
   --------------------+-----------------------------------------
            1          |   0xxxxxxx
            2          |   110xxxxx 10xxxxxx
            3          |   1110xxxx 10xxxxxx 10xxxxxx
            4          |   11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

x обозначает бит в бинарной форме байта, который может быть как 0, так и 1.

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

Пример:

Input: data = [197,130,1]
Output: true
Explanation: data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

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

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

2⃣Далее нужно рассмотреть два сценария. Первый — мы находимся в процессе обработки некоторого UTF-8 закодированного символа. В этом случае нужно просто проверить первые два бита строки и посмотреть, равны ли они "10", т.е. наиболее значимые два бита целого числа равны 1 и 0. bin_rep[:2] == "10". Второй сценарий — мы уже обработали несколько допустимых UTF-8 символов и должны начать обработку нового UTF-8 символа. В этом случае нужно посмотреть на префикс строкового представления и посчитать количество единиц, которые мы встречаем до первой нули. Это скажет нам, каков размер следующего UTF-8 символа.

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

Теперь давайте перейдем к реализации этого алгоритма.

😎 Решение:

class Solution {
    func validUtf8(_ data: [Int]) -> Bool {
        var nBytes = 0
        
        for num in data {
            let binRep = String(num, radix: 2).suffix(8).padLeft(toLength: 8, withPad: "0")
            
            if nBytes == 0 {
                for bit in binRep {
                    if bit == "0" { break }
                    nBytes += 1
                }
                
                if nBytes == 0 {
                    continue
                }
                
                if nBytes == 1 || nBytes > 4 {
                    return false
                }
            } else {
                if !(binRep.prefix(2) == "10") {
                    return false
                }
            }
            
            nBytes -= 1
        }
        
        return nBytes == 0
    }
}

extension String {
    func padLeft(toLength: Int, withPad: String) -> String {
        let newLength = self.count
        if newLength < toLength {
            return String(repeatElement(withPad, count: toLength - newLength)) + self
        } else {
            return String(self.suffix(toLength))
        }
    }
}

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

#medium
Задача: 294. Flip Game II

Вы играете в игру Flip со своим другом.

Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда игрок больше не может сделать ход, и, следовательно, другой игрок становится победителем.

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

Пример:

Input: currentState = "++++"
Output: true
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".

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

1⃣Генерация всех возможных следующих ходов:
Для текущего состояния currentState, создайте все возможные новые состояния, заменяя каждую пару "++" на "--".

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

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

😎 Решение:

class Solution {
    func canWin(_ currentState: String) -> Bool {
        var stateArray = Array(currentState)
        
        for i in 0..<(stateArray.count - 1) {
            if stateArray[i] == "+" && stateArray[i + 1] == "+" {
                stateArray[i] = "-"
                stateArray[i + 1] = "-"
                let newState = String(stateArray)
                
                if !canWin(newState) {
                    stateArray[i] = "+"
                    stateArray[i + 1] = "+"
                    return true
                }
                
                stateArray[i] = "+"
                stateArray[i + 1] = "+"
            }
        }
        
        return false
    }
}

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

#hard
Задача: 295. Find Median from Data Stream

Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, то медианы нет, и медиана — это среднее арифметическое двух средних значений.

Например, для arr = [2, 3, 4] медиана равна 3.
Например, для arr = [2, 3] медиана равна (2 + 3) / 2 = 2.5.

Реализуйте класс MedianFinder:

MedianFinder() инициализирует объект MedianFinder.
void addNum(int num) добавляет целое число num из потока данных в структуру данных.
double findMedian() возвращает медиану всех элементов на данный момент. Ответы с точностью до 10^-5 от фактического ответа будут приниматься.

Пример:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

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

1⃣Храните числа в контейнере с возможностью изменения размера:
Создайте массив для хранения чисел.

2⃣Добавление нового числа:
Добавьте новое число в массив.

3⃣Вычисление и вывод медианы:
Отсортируйте массив.
Если размер массива нечетный, верните среднее значение массива.
Если размер массива четный, верните среднее арифметическое двух средних значений массива.

😎 Решение:

class MedianFinder {
    private var numbers: [Int] = []

    func addNum(_ num: Int) {
        numbers.append(num)
    }

    func findMedian() -> Double {
        numbers.sort()
        let n = numbers.count
        if n % 2 == 0 {
            return Double(numbers[n / 2 - 1] + numbers[n / 2]) / 2.0
        } else {
            return Double(numbers[n / 2])
        }
    }
}

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

#hard
Задача: 296. Best Meeting Point

Дан бинарный сетка размером 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⃣Вычисление минимального общего расстояния:
Вычислите сумму Манхэттенских расстояний от каждого дома до точки встречи, используя найденные медианы в качестве координат точки встречи.
Верните это значение как минимальное общее расстояние путешествия.

😎 Решение:

import Foundation

class Solution {
    func minTotalDistance(_ grid: [[Int]]) -> Int {
        var minDistance = Int.max
        for row in 0..<grid.count {
            for col in 0..<grid[0].count {
                let distance = search(grid, row, col)
                minDistance = min(distance, minDistance)
            }
        }
        return minDistance
    }

    private func search(_ grid: [[Int]], _ row: Int, _ col: Int) -> Int {
        var q: [(Int, Int, Int)] = [(row, col, 0)]
        let m = grid.count
        let n = grid[0].count
        var visited = Array(repeating: Array(repeating: false, count: n), count: m)
        var totalDistance = 0
        
        while !q.isEmpty {
            let point = q.removeFirst()
            let r = point.0
            let c = point.1
            let d = point.2
            
            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.append((r + 1, c, d + 1))
            q.append((r - 1, c, d + 1))
            q.append((r, c + 1, d + 1))
            q.append((r, c - 1, d + 1))
        }
        
        return totalDistance
    }

    public class Point {
        var row: Int
        var col: Int
        var distance: Int
        
        public init(_ row: Int, _ col: Int, _ distance: Int) {
            self.row = row
            self.col = col
            self.distance = distance
        }
    }
}

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

#hard
Задача: 297. Serialize and Deserialize Binary Tree

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

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

Уточнение: формат ввода/вывода такой же, как в LeetCode для сериализации бинарного дерева. Вам не обязательно придерживаться этого формата, так что будьте креативны и придумайте свои подходы.

Пример:

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

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

1⃣Сериализация дерева:
Используйте рекурсивный обход дерева в порядке root -> left subtree -> right subtree.
Для каждого узла добавляйте его значение в строку сериализации. Если узел пустой, добавляйте "None".

2⃣Пример:
Начните с корня, узел 1, строка сериализации становится "1,".
Переходите к левому поддереву с корнем 2, строка сериализации становится "1,2,".
Для узла 2, посетите его левый узел 3 ("1,2,3,None,None,") и правый узел 4 ("1,2,3,None,None,4,None,None").
Возвращайтесь к корню 1 и посетите его правое поддерево, узел 5 ("1,2,3,None,None,4,None,None,5,None,None,").

3⃣Десериализация строки:
Разделите строку на список значений.
Используйте рекурсивную функцию для создания узлов дерева, извлекая значения из списка и восстанавливая структуру дерева. Если значение "None", узел пустой.

😎 Решение:

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

public class Codec {
    func rserialize(_ root: TreeNode?, _ str: inout String) {
        if root == nil {
            str += "null,"
        } else {
            str += "\(root!.val),"
            rserialize(root!.left, &str)
            rserialize(root!.right, &str)
        }
    }

    public func serialize(_ root: TreeNode?) -> String {
        var str = ""
        rserialize(root, &str)
        return str
    }

    func rdeserialize(_ data: inout [String]) -> TreeNode? {
        if data[0] == "null" {
            data.remove(at: 0)
            return nil
        }

        let root = TreeNode(Int(data.remove(at: 0))!)
        root.left = rdeserialize(&data)
        root.right = rdeserialize(&data)

        return root
    }

    public func deserialize(_ data: String) -> TreeNode? {
        var dataArray = data.split(separator: ",").map { String($0) }
        return rdeserialize(&dataArray)
    }
}

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

#medium
Задача: 394. Decode String

Дана закодированная строка, вернуть её декодированную версию.

Правило кодирования следующее: k[закодированная_строка], где закодированная_строка внутри квадратных скобок повторяется ровно k раз. Обратите внимание, что k гарантированно является положительным целым числом.

Можно предположить, что входная строка всегда допустима; нет лишних пробелов, квадратные скобки корректно сформированы и т.д. Более того, можно предположить, что исходные данные не содержат никаких цифр, и что цифры используются только для обозначения количества повторений, k. Например, не будет таких входных данных, как 3a или 2[4].

Тестовые случаи сгенерированы так, что длина выходной строки никогда не превысит 105.

Пример:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

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

1⃣Проходите по строке s и обрабатывайте каждый символ. Если текущий символ не является закрывающей скобкой ], поместите его в стек.

2⃣Если текущий символ является закрывающей скобкой ], начните декодировать последнюю пройденную строку. Извлекайте из стека символы, пока следующий символ не станет открывающей скобкой [, и добавляйте каждый символ (a-z) к decodedString. Затем извлеките открывающую скобку [ из стека и извлекайте символы, пока следующий символ является цифрой (0-9), чтобы собрать число k.

3⃣Декодируйте шаблон k[decodedString], помещая decodedString в стек k раз. После того как вся строка будет пройдена, извлеките результат из стека и верните его.

😎 Решение:

class Solution {
    func decodeString(_ s: String) -> String {
        var stack = [Character]()
        
        for char in s {
            if char == "]" {
                var decodedString = ""
                while let last = stack.last, last != "[" {
                    decodedString = String(stack.removeLast()) + decodedString
                }
                stack.removeLast()
                
                var k = 0
                var base = 1
                while let last = stack.last, let digit = last.wholeNumberValue {
                    k += digit * base
                    base *= 10
                    stack.removeLast()
                }
                
                for _ in 0..<k {
                    for c in decodedString {
                        stack.append(c)
                    }
                }
            } else {
                stack.append(char)
            }
        }
        
        return String(stack)
    }
}

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

#medium
Задача: 298. Binary Tree Longest Consecutive Sequence

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

Путь последовательных значений — это путь, где значения увеличиваются на единицу вдоль пути.

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

Пример:

Input: root = [1,null,3,2,4,null,null,null,5]
Output: 3
Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

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

1⃣Инициализация и начало обхода:
Начните обход дерева с корневого узла.
Инициализируйте переменную length, чтобы хранить текущую длину последовательного пути, и передавайте её вниз по дереву.

2⃣Сравнение текущего узла с родительским узлом:
Для каждого узла сравните его значение со значением родительского узла.
Если значение текущего узла на единицу больше значения родительского узла, увеличьте length.
Если значение текущего узла не является последовательным (не больше на единицу), сбросьте length на 1.

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

😎 Решение:

class Solution {
    private var maxLength = 0

    func longestConsecutive(_ root: TreeNode?) -> Int {
        dfs(root, nil, 0)
        return maxLength
    }

    private func dfs(_ node: TreeNode?, _ parent: TreeNode?, _ length: Int) {
        guard let node = node else { return }
        var currentLength = length
        if let parent = parent, node.val == parent.val + 1 {
            currentLength += 1
        } else {
            currentLength = 1
        }
        maxLength = max(maxLength, currentLength)
        dfs(node.left, node, currentLength)
        dfs(node.right, node, currentLength)
    }
}

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

#medium
Задача: 299. Bulls and Cows

Вы играете в игру "Быки и коровы" со своим другом.

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

Количество "быков", то есть цифры в предположении, которые находятся на правильной позиции.
Количество "коров", то есть цифры в предположении, которые есть в вашем секретном числе, но находятся на неправильной позиции. Конкретно, это не-бычьи цифры в предположении, которые можно переставить так, чтобы они стали быками.
Дано секретное число secret и предположение вашего друга guess, верните подсказку для предположения вашего друга.

Подсказка должна быть в формате "xAyB", где x — количество быков, а y — количество коров. Обратите внимание, что и secret, и guess могут содержать повторяющиеся цифры.

Пример:

Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
  |
"7810"

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

1⃣Инициализация счетчиков:
Инициализируйте количество быков и коров значениями ноль.
Создайте хеш-таблицу для хранения символов строки secret и их частот.


2⃣Обход строки guess:
Для каждого символа ch в строке guess:
Если ch присутствует в строке secret:
Если текущий символ ch совпадает с символом на той же позиции в secret (ch == secret[idx]):
Увеличьте количество быков: bulls += 1.
Обновите количество коров, если количество текущего символа в хеш-таблице отрицательное или равно нулю (то есть этот символ уже использовался для коров): cows -= int(h[ch] <= 0).
Если текущий символ ch не совпадает с символом на той же позиции в secret (ch != secret[idx]):
Увеличьте количество коров, если количество текущего символа в хеш-таблице больше нуля: cows += int(h[ch] > 0).
Обновите хеш-таблицу, помечая текущий символ как использованный: h[ch] -= 1.


3⃣Возврат результата:
Верните количество быков и коров в формате "xAyB".

😎 Решение:

class Solution {
    func getHint(_ secret: String, _ guess: String) -> String {
        var h = [Character: Int]()
        for ch in secret {
            h[ch, default: 0] += 1
        }

        var bulls = 0
        var cows = 0
        let n = guess.count
        let secretArray = Array(secret)
        let guessArray = Array(guess)

        for idx in 0..<n {
            let ch = guessArray[idx]
            if h[ch] != nil {
                if ch == secretArray[idx] {
                    bulls += 1
                    if h[ch]! <= 0 {
                        cows -= 1
                    }
                } else {
                    if h[ch]! > 0 {
                        cows += 1
                    }
                }
                h[ch]! -= 1
            }
        }

        return "\(bulls)A\(cows)B"
    }
}

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