Задача: 392. Is Subsequence
Сложность: easy

Даны две строки 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
    }
}

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

Задача: 780. Reaching Points
Сложность: hard

Даны четыре целых числа sx, sy, tx и ty, верните true, если возможно преобразовать точку (sx, sy) в точку (tx, ty) с помощью некоторых операций, иначе верните false.

Допустимая операция для некоторой точки (x, y) заключается в преобразовании её либо в (x, x + y), либо в (x + y, y).

Пример:

Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: true
Explanation:
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

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

1⃣Повторно вычитайте меньшее из {tx, ty} из большего из {tx, ty}.

2⃣Продолжайте вычитание, пока tx и ty больше или равны sx и sy соответственно.

3⃣Ответ будет true, если и только если в конечном итоге мы достигнем точки sx, sy.

😎 Решение:

class Solution {
    func reachingPoints(_ sx: Int, _ sy: Int, _ tx: Int, _ ty: Int) -> Bool {
        var tx = tx
        var ty = ty
        while tx >= sx && ty >= sy {
            if sx == tx && sy == ty {
                return true
            }
            if tx > ty {
                tx -= ty
            } else {
                ty -= tx
            }
        }
        return false
    }
}

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

Задача: 211. Design Add and Search Words Data Structure
Сложность: medium

Спроектируйте структуру данных, которая поддерживает добавление новых слов и проверку, соответствует ли строка любому ранее добавленному слову.

Реализуйте класс WordDictionary:
WordDictionary() инициализирует объект.
void addWord(word) добавляет слово в структуру данных, оно может быть сопоставлено позже.
bool search(word) возвращает true, если в структуре данных есть строка, которая соответствует слову, или false в противном случае. Слово может содержать точки '.', где точки могут быть сопоставлены с любой буквой.

Пример:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

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

1⃣Инициализация и добавление слова:
Создайте класс WordDictionary с конструктором, который инициализирует корневой узел TrieNode.
Метод addWord(String word) добавляет слово в структуру данных. Инициализируйте текущий узел как корневой и пройдите по каждому символу слова. Если символ отсутствует среди дочерних узлов текущего узла, создайте новый узел. Перемещайтесь к следующему узлу. В конце отметьте текущий узел как конец слова.

2⃣Поиск слова в узле:
Метод searchInNode(String word, TrieNode node) ищет слово в переданном узле TrieNode. Пройдите по каждому символу слова. Если символ не найден среди дочерних узлов текущего узла, проверьте, является ли символ точкой '.'. Если да, рекурсивно выполните поиск в каждом дочернем узле текущего узла. Если символ не точка и не найден, верните false. Если символ найден, перейдите к следующему узлу. В конце проверьте, является ли текущий узел концом слова.

3⃣Поиск слова в структуре данных:
Метод search(String word) использует метод searchInNode() для поиска слова, начиная с корневого узла. Верните результат поиска. Если слово найдено, верните true, иначе false.

😎 Решение:

class TrieNode {
    var children = [Character: TrieNode]()
    var isWord = false
}

class WordDictionary {
    private var root: TrieNode

    init() {
        root = TrieNode()
    }

    func addWord(_ word: String) {
        var node = root
        for ch in word {
            if node.children[ch] == nil {
                node.children[ch] = TrieNode()
            }
            node = node.children[ch]!
        }
        node.isWord = true
    }

    private func searchInNode(_ word: String, _ node: TrieNode) -> Bool {
        var node = node
        for (i, ch) in word.enumerated() {
            if let nextNode = node.children[ch] {
                node = nextNode
            } else if ch == "." {
                for childNode in node.children.values {
                    if searchInNode(String(word.dropFirst(i + 1)), childNode) {
                        return true
                    }
                }
                return false
            } else {
                return false
            }
        }
        return node.isWord
    }

    func search(_ word: String) -> Bool {
        return searchInNode(word, root)
    }
}

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

Задача: 965. Univalued Binary Tree
Сложность: medium

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

Для данного слова запроса, проверка орфографии обрабатывает две категории ошибок правописания:
Заглавные буквы: если запрос совпадает со словом в списке слов (без учета регистра), то слово запроса возвращается с таким же регистром, как и в списке слов.
Пример: wordlist = ["yellow"], query = "YellOw": correct = "yellow"
Пример: wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
Пример: wordlist = ["yellow"], query = "yellow": correct = "yellow"

Ошибки гласных: если после замены гласных ('a', 'e', 'i', 'o', 'u') в слове запроса на любую гласную по отдельности оно совпадает со словом в списке слов (без учета регистра), то слово запроса возвращается с таким же регистром, как и совпадающее слово в списке слов.
Пример: wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
Пример: wordlist = ["YellOw"], query = "yeellow": correct = "" (нет совпадения)
Пример: wordlist = ["YellOw"], query = "yllw": correct = "" (нет совпадения)

Кроме того, проверка орфографии работает по следующим правилам приоритета:
Когда запрос точно совпадает со словом в списке слов (с учетом регистра), вы должны вернуть это же слово.
Когда запрос совпадает со словом за исключением регистра, вы должны вернуть первое такое совпадение в списке слов.
Когда запрос совпадает со словом за исключением ошибок гласных, вы должны вернуть первое такое совпадение в списке слов.
Если запрос не имеет совпадений в списке слов, вы должны вернуть пустую строку.
Дан массив запросов, верните список слов answer, где answer[i] — правильное слово для query = queries[i].

Пример:

Input: wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
Output: ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

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

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

2⃣Используйте хэш-таблицу для хранения слов в нижнем регистре и соответствующих слов из списка для проверки совпадений без учета регистра.

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

😎 Решение:

class Solution {
    var wordsPerfect: Set<String> = []
    var wordsCap: [String: String] = [:]
    var wordsVow: [String: String] = [:]

    func spellchecker(_ wordlist: [String], _ queries: [String]) -> [String] {
        for word in wordlist {
            wordsPerfect.insert(word)
            let wordLow = word.lowercased()
            wordsCap[wordLow, default: word] = word
            let wordLowDV = devowel(wordLow)
            wordsVow[wordLowDV, default: word] = word
        }

        return queries.map { solve($0) }
    }

    func solve(_ query: String) -> String {
        if wordsPerfect.contains(query) {
            return query
        }

        let queryL = query.lowercased()
        if let match = wordsCap[queryL] {
            return match
        }

        let queryLV = devowel(queryL)
        if let match = wordsVow[queryLV] {
            return match
        }

        return ""
    }

    func devowel(_ word: String) -> String {
        let vowels: Set<Character> = ["a", "e", "i", "o", "u"]
        return String(word.map { vowels.contains($0) ? "*" : $0 })
    }
}

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

Задача: 506. Relative Ranks
Сложность: easy

Вам дан целочисленный массив score размером n, где score[i] — это результат i-го спортсмена на соревновании. Все результаты гарантированно уникальны.
Спортсмены размещаются на основе своих результатов: спортсмен, занявший 1-е место, имеет наивысший результат, спортсмен, занявший 2-е место, имеет второй по величине результат и так далее. Размещение каждого спортсмена определяет его ранг:
Ранг спортсмена, занявшего 1-е место, — "Gold Medal".
Ранг спортсмена, занявшего 2-е место, — "Silver Medal".
Ранг спортсмена, занявшего 3-е место, — "Bronze Medal".
Для спортсменов, занявших с 4-го по n-е место, их ранг соответствует их номеру в размещении (т.е. ранг спортсмена, занявшего x-е место, — "x").
Верните массив answer размером n, где answer[i] — это ранг i-го спортсмена.

Пример:

Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].

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

1⃣Инициализация и нахождение максимального значения
Инициализируйте переменную N длиной массива score. Определите функцию findMax, которая находит максимальный балл в массиве score.

2⃣Создание вспомогательных структур
Инициализируйте массив scoreToIndex размером M + 1, где M — это максимальное значение в массиве score. Заполните scoreToIndex таким образом, чтобы для каждого score[i] его индекс сохранялся в scoreToIndex[score[i]].

3⃣Присваивание рангов и формирование ответа
Создайте массив rank для хранения рангов спортсменов. Используйте цикл для присваивания медалей и рангов в зависимости от значений в scoreToIndex, начиная с наибольшего.

😎 Решение:

class Solution {
    func findRelativeRanks(_ score: [Int]) -> [String] {
        let N = score.count
        let maxScore = score.max()!
        var scoreToIndex = [Int](repeating: 0, count: maxScore + 1)
        
        for (i, s) in score.enumerated() {
            scoreToIndex[s] = i + 1
        }
        
        let MEDALS = ["Gold Medal", "Silver Medal", "Bronze Medal"]
        var rank = [String](repeating: "", count: N)
        var place = 1
        
        for i in stride(from: maxScore, through: 0, by: -1) {
            if scoreToIndex[i] != 0 {
                let originalIndex = scoreToIndex[i] - 1
                if place < 4 {
                    rank[originalIndex] = MEDALS[place - 1]
                } else {
                    rank[originalIndex] = String(place)
                }
                place += 1
            }
        }
        
        return rank
    }
}

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

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

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

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

Пример:

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

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

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

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

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

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

😎 Решение:

class CombinationIterator {
    var combinations: [String]

    init(_ characters: String, _ combinationLength: Int) {
        combinations = []
        let n = characters.count
        let k = combinationLength
        for bitmask in 0..<(1 << n) {
            if bitmask.nonzeroBitCount == k {
                var curr = ""
                for j in 0..<n {
                    if bitmask & (1 << (n - j - 1)) != 0 {
                        curr.append(characters[characters.index(characters.startIndex, offsetBy: j)])
                    }
                }
                combinations.append(curr)
            }
        }
    }

    func next() -> String {
        return combinations.removeLast()
    }

    func hasNext() -> Bool {
        return !combinations.isEmpty
    }
}

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

Задача: 249. Group Shifted Strings
Сложность: medium

Выполните следующие операции сдвига на строке:

Правый сдвиг: замените каждую букву следующей буквой английского алфавита, где 'z' заменяется на 'a'. Например, "abc" можно сдвинуть вправо на "bcd" или "xyz" можно сдвинуть вправо на "yza".
Левый сдвиг: замените каждую букву предыдущей буквой английского алфавита, где 'a' заменяется на 'z'. Например, "bcd" можно сдвинуть влево на "abc" или "yza" можно сдвинуть влево на "xyz".
Мы можем продолжать сдвигать строку в обоих направлениях, чтобы сформировать бесконечную последовательность сдвигов.

Например, сдвиньте "abc", чтобы сформировать последовательность: ... <-> "abc" <-> "bcd" <-> ... <-> "xyz" <-> "yza" <-> .... <-> "zab" <-> "abc" <-> ...
Вам дан массив строк strings, сгруппируйте все strings[i], которые принадлежат одной и той же последовательности сдвигов. Ответ можно вернуть в любом порядке.

Пример:

Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"]

Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]

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

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

2⃣Сопоставьте оригинальную строку с найденным хэш-значением в карте mapHashToList, добавляя оригинальную строку в список, соответствующий ее хэш-значению.

3⃣Переберите mapHashToList и сохраните список для каждого ключа в карте в массив ответа groups.

😎 Решение:

class Solution {
    func shiftLetter(_ letter: Character, _ shift: Int) -> Character {
        return Character(UnicodeScalar((letter.asciiValue! - UInt8(shift) + 26) % 26 + 97))
    }
    
    func getHash(_ s: String) -> String {
        let shift = Int(s.first!.asciiValue! - 97)
        var hashKey = ""
        
        for letter in s {
            hashKey.append(shiftLetter(letter, shift))
        }
        
        return hashKey
    }
    
    func groupStrings(_ strings: [String]) -> [[String]] {
        var mapHashToList = [String: [String]]()
        
        for str in strings {
            let hashKey = getHash(str)
            if mapHashToList[hashKey] != nil {
                mapHashToList[hashKey]!.append(str)
            } else {
                mapHashToList[hashKey] = [str]
            }
        }
        
        return Array(mapHashToList.values)
    }
}

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

Задача: 1057. Campus Bikes
Сложность: medium

В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Пример:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]

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

1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список.

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

3⃣Заполни и верни массив назначений.

😎 Решение:

func assignBikes(_ workers: [[Int]], _ bikes: [[Int]]) -> [Int] {
    var pairs = [(Int, Int, Int)]()
    
    for (i, worker) in workers.enumerated() {
        for (j, bike) in bikes.enumerated() {
            let distance = abs(worker[0] - bike[0]) + abs(worker[1] - bike[1])
            pairs.append((distance, i, j))
        }
    }
    
    pairs.sort { $0 < $1 }
    
    var result = [Int](repeating: -1, count: workers.count)
    var bikeTaken = [Bool](repeating: false, count: bikes.count)
    var workerAssigned = [Bool](repeating: false, count: workers.count)
    
    for (distance, workerIdx, bikeIdx) in pairs {
        if !workerAssigned[workerIdx] && !bikeTaken[bikeIdx] {
            result[workerIdx] = bikeIdx
            bikeTaken[bikeIdx] = true
            workerAssigned[workerIdx] = true
        }
    }
    
    return result
}

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

Задача: 1180. Count Substrings with Only One Distinct Letter
Сложность: easy

Дана строка s. Верните количество подстрок, которые содержат только одну уникальную букву.

Пример:

Input: s = "aaaba"
Output: 8
Explanation: The substrings with one distinct letter are "aaa", "aa", "a", "b".
"aaa" occurs 1 time.
"aa" occurs 2 times.
"a" occurs 4 times.
"b" occurs 1 time.
So the answer is 1 + 2 + 4 + 1 = 8.

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

1⃣Инициализируйте целочисленную переменную total для подсчета количества подстрок, а также два указателя left и right, которые отмечают начало и конец подстроки, содержащей только одну уникальную букву.

2⃣Итерируйте по строке S: Если мы не достигли конца и новый символ S[right] такой же, как и начальный символ S[left], увеличьте right на 1 для дальнейшего исследования строки S; в противном случае вычислите длину подстроки как right - left и примените формулу суммы арифметической последовательности; не забудьте установить right в left для начала исследования новой подстроки.

3⃣После завершения итерации добавьте к total количество подстрок для последнего сегмента, если он не был учтен. Верните значение total.

😎 Решение

class Solution {
    func countLetters(_ S: String) -> Int {
        var total = 0
        let chars = Array(S)
        var left = 0

        for right in 0...chars.count {
            if right == chars.count || chars[left] != chars[right] {
                let lenSubstring = right - left
                total += (1 + lenSubstring) * lenSubstring / 2
                left = right
            }
        }
        return total
    }
}

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

Задача: 166. Fraction to Recurring Decimal
Сложность: medium

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

Если дробная часть повторяется, заключите повторяющуюся часть в скобки.

Если возможны несколько ответов, верните любой из них.

Гарантируется, что длина строки ответа будет меньше 10^4 для всех предоставленных входных данных.

Пример:

Input: numerator = 1, denominator = 2
Output: "0.5"

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

1⃣Использование хеш-таблицы для отслеживания остатков:
Создайте хеш-таблицу для хранения соответствия между остатком от деления и его позицией в дробной части. Это поможет определить начало повторяющейся части.
Для каждого нового остатка вычислите следующую цифру результата деления и проверьте, был ли такой остаток уже получен ранее.

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

3⃣Учет особенностей:
Будьте осторожны с крайними случаями, такими как отрицательные дроби или особо сложные случаи, например, деление −1 на −2147483648. В этих случаях следует корректно обрабатывать знаки и возможные переполнения.

😎 Решение:

class Solution {
    func fractionToDecimal(_ numerator: Int, _ denominator: Int) -> String {
        if numerator == 0 {
            return "0"
        }

        var fraction = ""
        if (numerator < 0) != (denominator < 0) {
            fraction += "-"
        }

        let dividend = abs(numerator)
        let divisor = abs(denominator)

        fraction += "\(dividend / divisor)"
        var remainder = dividend % divisor
        if remainder == 0 {
            return fraction
        }

        fraction += "."
        var lookup = [Int: Int]()
        while remainder != 0 {
            if let pos = lookup[remainder] {
                fraction.insert(contentsOf: "(", at: fraction.index(fraction.startIndex, offsetBy: pos))
                fraction += ")"
                break
            }
            lookup[remainder] = fraction.count
            remainder *= 10
            fraction += "\(remainder / divisor)"
            remainder %= divisor
        }

        return fraction
    }
}

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

Задача: 994. Rotting Oranges
Сложность: medium

Дан m x n сетка, где каждая ячейка может иметь одно из трех значений:

0, представляющее пустую ячейку,
1, представляющее свежий апельсин,
2, представляющее гнилой апельсин.
Каждую минуту любой свежий апельсин, который находится в 4-х направленно смежной ячейке с гнилым апельсином, становится гнилым.

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

Пример:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

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

1⃣Инициализация очереди и подсчет апельсинов:
Пройдите по всей сетке, добавьте все гнилые апельсины в очередь и подсчитайте общее количество свежих апельсинов.
Если нет свежих апельсинов, верните 0.

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

3⃣Проверка оставшихся свежих апельсинов:
Если после завершения BFS все еще остаются свежие апельсины, верните -1.

😎 Решение:

class Solution {
    func orangesRotting(_ grid: [[Int]]) -> Int {
        var grid = grid
        var queue: [(Int, Int)] = []
        var freshCount = 0
        let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        var minutes = 0
        
        for i in 0..<grid.count {
            for j in 0..<grid[0].count {
                if grid[i][j] == 2 {
                    queue.append((i, j))
                } else if grid[i][j] == 1 {
                    freshCount += 1
                }
            }
        }
        
        if freshCount == 0 { return 0 }
        
        while !queue.isEmpty {
            var nextQueue: [(Int, Int)] = []
            for (i, j) in queue {
                for dir in directions {
                    let ni = i + dir.0, nj = j + dir.1
                    if ni >= 0, ni < grid.count, nj >= 0, nj < grid[0].count, grid[ni][nj] == 1 {
                        grid[ni][nj] = 2
                        freshCount -= 1
                        nextQueue.append((ni, nj))
                    }
                }
            }
            if !nextQueue.isEmpty {
                minutes += 1
            }
            queue = nextQueue
        }
        
        return freshCount == 0 ? minutes : -1
    }
}

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

Задача: 820. Short Encoding of Words
Сложность: medium

Допустимым кодированием массива слов является любая опорная строка s и массив индексов indices, такие что:

words.length == indices.length
Опорная строка s заканчивается символом '#'.
Для каждого индекса indices[i], подстрока строки s, начинающаяся с indices[i] и заканчивающаяся (но не включительно) следующим символом '#', равна words[i].
Дан массив слов, верните длину самой короткой возможной опорной строки s для любого допустимого кодирования слов.

Пример:

Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"

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

1⃣Поскольку слово имеет не более 6 собственных суффиксов (так как words[i].length <= 7), давайте итерироваться по всем из них. Для каждого собственного суффикса мы попытаемся удалить его из нашего списка слов. Для эффективности сделаем words множеством.

2⃣Затем создадим список оставшихся слов и сформируем опорную строку, объединяя каждое слово с символом '#'.

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

😎 Решение:

class Solution {
    func minimumLengthEncoding(_ words: [String]) -> Int {
        var good = Set(words)
        for word in words {
            for k in 1..<word.count {
                let suffix = String(word.suffix(from: word.index(word.startIndex, offsetBy: k)))
                good.remove(suffix)
            }
        }
        return good.reduce(0) { $0 + $1.count + 1 }
    }
}

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

Задача: 63. Unique Paths II
Сложность: medium

Вам дана матрица размером m на n, содержащая целые числа. Робот находится в начальный момент в верхнем левом углу (то есть в ячейке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть в ячейку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени.

Препятствия и свободные пространства отмечены в матрице как 1 и 0 соответственно. Путь, который проходит робот, не может включать клетки, которые являются препятствиями.

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

Тестовые примеры сгенерированы таким образом, что ответ будет не более 2 * 10^9.

Пример:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

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

1⃣Если первая ячейка, то есть obstacleGrid[0,0], содержит 1, это означает, что в первой ячейке есть препятствие. Следовательно, робот не сможет сделать ни одного хода, и мы должны вернуть количество возможных путей как 0. Если же obstacleGrid[0,0] изначально равно 0, мы устанавливаем его равным 1 и продолжаем.

2⃣Итерация по первой строке. Если ячейка изначально содержит 1, это означает, что текущая ячейка имеет препятствие и не должна учитываться в каком-либо пути. Следовательно, значение этой ячейки устанавливается равным 0. В противном случае, устанавливаем его равным значению предыдущей ячейки, то есть obstacleGrid[i,j] = obstacleGrid[i,j-1]. Повторяем аналогичные действия для первого столбца.

3⃣Далее, итерация по массиву начиная с ячейки obstacleGrid[1,1]. Если ячейка изначально не содержит препятствий, то количество способов добраться до этой ячейки будет равно сумме количества способов добраться до ячейки над ней и количества способов добраться до ячейки слева от неё, то есть obstacleGrid[i,j] = obstacleGrid[i-1,j] + obstacleGrid[i,j-1]. Если в ячейке есть препятствие, устанавливаем её значение равным 0 и продолжаем. Это делается для того, чтобы она не учитывалась в других путях.

😎 Решение:

func uniquePathsWithObstacles(_ obstacleGrid: [[Int]]) -> Int {
    let R = obstacleGrid.count
    let C = obstacleGrid[0].count
    if obstacleGrid[0][0] == 1 {
        return 0
    }
    var grid = obstacleGrid
    grid[0][0] = 1
    for i in 1..<R {
        grid[i][0] = grid[i][0] == 0 && grid[i - 1][0] == 1 ? 1 : 0
    }
    for i in 1..<C {
        grid[0][i] = grid[0][i] == 0 && grid[0][i - 1] == 1 ? 1 : 0
    }
    for i in 1..<R {
        for j in 1..<C {
            if grid[i][j] == 0 {
                grid[i][j] = grid[i - 1][j] + grid[i][j - 1]
            } else {
                grid[i][j] = 0
            }
        }
    }
    return grid[R - 1][C - 1]
}

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

Задача: 275. H-Index II
Сложность: medium

Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью, и массив отсортирован в порядке возрастания. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.
Вы должны написать алгоритм, который работает за логарифмическое время.

Пример:

Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

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

1⃣Найти середину массива:
Определить средний элемент массива, чтобы разделить его на две подмножества: citations[0: mid - 1] и citations[mid + 1: n].

2⃣Сравнить количество статей с цитированиями больше или равными citations[mid]:
Если citations[mid] == n - mid, то найден h-индекс и его можно вернуть.
Если citations[mid] < n - mid, то необходимо искать в правой подмножности citations[mid + 1: n].
Если citations[mid] > n - mid, то необходимо искать в левой подмножности citations[0: mid - 1].

3⃣Возвращение результата:
Продолжать процесс, пока не будет найден h-индекс.
Возвратить n - mid, что является количеством статей с цитированиями больше или равными citations[mid].

😎 Решение:

class Solution {
    func hIndex(_ citations: [Int]) -> Int {
        let n = citations.count
        var left = 0
        var right = n - 1
        
        while left <= right {
            let mid = left + (right - left) / 2
            if citations[mid] == n - mid {
                return n - mid
            } else if citations[mid] < n - mid {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return n - left
    }
}

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

Задача: 528. Random Pick with Weight
Сложность: medium

Вам дан массив положительных целых чисел w, где w[i] описывает вес индекса i.
Вам нужно реализовать функцию pickIndex(), которая случайным образом выбирает индекс в диапазоне [0, w.length - 1] (включительно) и возвращает его. Вероятность выбора индекса i равна w[i] / sum(w).

Например, если w = [1, 3], вероятность выбора индекса 0 составляет 1 / (1 + 3) = 0.25 (т.е. 25%), а вероятность выбора индекса 1 составляет 3 / (1 + 3) = 0.75 (т.е. 75%).

Пример:

Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.

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

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

2⃣ Генерация случайного числа и выбор индекса:
В функции pickIndex() сгенерируйте случайное число в диапазоне от 0 до общей суммы весов totalSum.
Используйте линейный поиск, чтобы найти первый индекс в prefixSums, который больше или равен сгенерированному числу.

3⃣ Возврат результата:
Верните найденный индекс.

😎 Решение:

class Solution {
    private var prefixSums: [Int]
    private var totalSum: Int

    init(_ w: [Int]) {
        prefixSums = [Int](repeating: 0, count: w.count)
        var prefixSum = 0
        for i in 0..<w.count {
            prefixSum += w[i]
            prefixSums[i] = prefixSum
        }
        totalSum = prefixSum
    }

    func pickIndex() -> Int {
        let target = Double(totalSum) * Double.random(in: 0...1)
        for (i, prefixSum) in prefixSums.enumerated() {
            if target < Double(prefixSum) {
                return i
            }
        }
        return prefixSums.count - 1
    }
}

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

⚡ Официальный релиз easyoffer 2.0 состоится уже в течение нескольких дней.

Напоминаю, что в честь релиза запускаем акцию.

Первые 500 покупателей получат:

🚀 Скидку 50% на PRO тариф на 1 год
🎁 Подарок ценностью 5000₽ для тех, кто подписан на этот канал

🔔 Подпишитесь на этот канал: https://t.iss.one/+b2fZN17A9OQ3ZmJi
В нем мы опубликуем сообщение о релизе в первую очередь

Задача: 786. K-th Smallest Prime Fraction
Сложность: medium

Вам дан отсортированный массив целых чисел arr, содержащий 1 и простые числа, где все элементы массива arr уникальны. Также дано целое число k.

Для каждого i и j, где 0 <= i < j < arr.length, мы рассматриваем дробь arr[i] / arr[j].

Верните k-ую наименьшую дробь из рассмотренных. Верните ответ в виде массива из двух целых чисел размера 2, где answer[0] == arr[i] и answer[1] == arr[j].

Пример:

Input: arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.

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

1⃣Создайте пустую приоритетную очередь pq для хранения пар дробей и индексов. Пройдите по массиву arr, вычисляя дробь arr[i] / arr.last для каждого элемента arr[i], и добавьте пары (-1.0 * arr[i] / arr.last, i, arr.count - 1) в pq. Приоритетная очередь pq теперь содержит дроби, образованные делением каждого элемента на последний элемент массива, отсортированные по возрастанию.

2⃣Повторите k - 1 раз: удалите минимальный элемент из pq, уменьшите индекс знаменателя и добавьте новую дробь (-1.0 * arr[числитель] / arr[знаменатель - 1], числитель, знаменатель - 1) в pq, если знаменатель больше числителя. После k - 1 итераций верхний элемент pq будет k-й наименьшей дробью.

3⃣Извлеките индексы числителя и знаменателя из верхнего элемента pq, верните массив [arr[числитель], arr[знаменатель]], соответствующий k-й наименьшей дроби.

😎 Решение:

class Solution {
    func kthSmallestPrimeFraction(_ arr: [Int], _ k: Int) -> [Int] {
        var pq = PriorityQueue<(Double, Int, Int)>()
        
        for i in 0..<arr.count - 1 {
            pq.push((Double(arr[i]) / Double(arr.last!), i, arr.count - 1))
        }
        
        for _ in 0..<k - 1 {
            let cur = pq.pop()!
            if cur.2 > cur.1 {
                pq.push((Double(arr[cur.1]) / Double(arr[cur.2 - 1]), cur.1, cur.2 - 1))
            }
        }
        
        let result = pq.pop()!
        return [arr[result.1], arr[result.2]]
    }
}

struct PriorityQueue<T: Comparable> {
    private var heap: [T] = []
    
    mutating func push(_ element: T) {
        heap.append(element)
        heapify(from: heap.count - 1)
    }
    
    mutating func pop() -> T? {
        guard !heap.isEmpty else { return nil }
        let root = heap[0]
        heap[0] = heap.removeLast()
        heapify(from: 0)
        return root
    }
    
    private mutating func heapify(from index: Int) {
        var idx = index
        let child = heap[idx]
        var parentIdx = (idx - 1) / 2
        
        while idx > 0 && heap[parentIdx] > child {
            heap[idx] = heap[parentIdx]
            idx = parentIdx
            parentIdx = (idx - 1) / 2
        }
        
        heap[idx] = child
        var parentIndex = 0
        
        while true {
            let leftChild = 2 * parentIndex + 1
            let rightChild = 2 * parentIndex + 2
            var swapIndex: Int?
            
            if leftChild < heap.count && heap[leftChild] < heap[parentIndex] {
                swapIndex = leftChild
            }
            if rightChild < heap.count && heap[rightChild] < (swapIndex != nil ? heap[swapIndex!] : heap[parentIndex]) {
                swapIndex = rightChild
            }
            guard let idx = swapIndex else { return }
            
            heap.swapAt(parentIndex, idx)
            parentIndex = idx
        }
    }
}

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

Задача: 495. Teemo Attacking
Сложность: easy

Наш герой Тимо атакует врага Эшу ядовитыми атаками! Когда Тимо атакует Эшу, она оказывается отравленной на ровно duration секунд. Более формально, атака в секунду t означает, что Эша будет отравлена в течение интервала времени [t, t + duration - 1] включительно. Если Тимо атакует снова до окончания эффекта яда, таймер для него сбрасывается, и эффект яда закончится через duration секунд после новой атаки.

Вам дано неубывающее целое число timeSeries, где timeSeries[i] обозначает, что Тимо атакует Эшу во вторую timeSeries[i], и целое число duration.
Верните общее количество секунд, в течение которых Эша была отравлена.

Пример:

Input: timeSeries = [1,4], duration = 2
Output: 4
Explanation: Teemo's attacks on Ashe go as follows:
- At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2.
- At second 4, Teemo attacks, and Ashe is poisoned for seconds 4 and 5.
Ashe is poisoned for seconds 1, 2, 4, and 5, which is 4 seconds in total.

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

1⃣Инициализация
Инициализируйте переменную total для хранения общего времени, в течение которого Эша была отравлена. Проверьте, если массив timeSeries пуст, верните 0.

2⃣Итерация
Пройдите по всем элементам массива timeSeries, кроме последнего. На каждой итерации добавьте к total минимальное значение между длительностью интервала и временем действия яда duration.

3⃣Возврат результата
Верните сумму total и duration, чтобы учесть последнюю атаку.

😎 Решение:

class Solution {
    func findPoisonedDuration(_ timeSeries: [Int], _ duration: Int) -> Int {
        let n = timeSeries.count
        if n == 0 { return 0 }

        var total = 0
        for i in 0..<n-1 {
            total += min(timeSeries[i + 1] - timeSeries[i], duration)
        }
        return total + duration
    }
}

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

Задача: 830. Positions of Large Groups
Сложность: easy

В строке s из строчных букв эти буквы образуют последовательные группы одного и того же символа.
Например, строка s = "abbxxxxzyy" имеет группы "a", "bb", "xxxx", "z" и "yy".
Группа идентифицируется интервалом [start, end], где start и end обозначают начальный и конечный индексы (включительно) группы. В приведенном выше примере "xxxx" имеет интервал [3,6].
Группа считается большой, если в ней 3 или более символов.

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

Пример:

Input: s = "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]
Explanation: The large groups are "ddd", "eeee", and "bbb".

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

1⃣Поддерживайте указатели i и j, где i <= j. Указатель i представляет начало текущей группы, а j будет инкрементироваться вперед, пока не достигнет конца группы.

2⃣Когда j достигнет конца строки или S[j] != S[j+1], у нас будет группа [i, j]. Если длина группы больше или равна 3, добавьте её в результат.

3⃣Обновите i = j + 1 и начните новую группу.

😎 Решение:

class Solution {
    func largeGroupPositions(_ S: String) -> [[Int]] {
        var ans = [[Int]]()
        let N = S.count
        var i = 0
        let chars = Array(S)
        
        for j in 0..<N {
            if j == N-1 || chars[j] != chars[j+1] {
                if j - i + 1 >= 3 {
                    ans.append([i, j])
                }
                i = j + 1
            }
        }
        return ans
    }
}

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

Задача: 1013. Partition Array Into Three Parts With Equal Sum
Сложность: easy

Если задан массив целых чисел arr, верните true, если мы можем разбить массив на три непустые части с равными суммами. Формально, мы можем разбить массив, если можем найти индексы i + 1 < j с (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])

Пример:

Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true

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

1⃣Вычисление общей суммы:
Вычислите общую сумму всех элементов массива. Если эта сумма не делится на 3 без остатка, вернуть false, так как невозможно разбить массив на три части с равной суммой.

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

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

😎 Решение:

class Solution {
    func canThreePartsEqualSum(_ arr: [Int]) -> Bool {
        let totalSum = arr.reduce(0, +)
        if totalSum % 3 != 0 {
            return false
        }
        
        let target = totalSum / 3
        var partSum = 0
        var count = 0
        let n = arr.count
        
        for i in 0..<n {
            partSum += arr[i]
            if partSum == target {
                count += 1
                partSum = 0
                if count == 2 && i < n - 1 {
                    return true
                }
            }
        }
        
        return false
    }
}

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