Задача: 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
    }
}

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

Задача: 967. Numbers With Same Consecutive Differences
Сложность: medium

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

Учтите, что целые числа не должны начинаться с нулей. Целые числа, такие как 02 и 043, не допускаются.

Пример:

Input: n = 3, k = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

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

1⃣Если n равно 1, верните массив от 0 до 9, так как все однозначные числа являются допустимыми.

2⃣Инициализируйте список очередей начальными цифрами от 1 до 9.

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

😎 Решение:

class Solution {
    func numsSameConsecDiff(_ N: Int, _ K: Int) -> [Int] {
        if N == 1 { return Array(0...9) }
        
        var queue = Array(1...9)
        for _ in 1..<N {
            var nextQueue = [Int]()
            for num in queue {
                let tailDigit = num % 10
                let nextDigits = [tailDigit + K, tailDigit - K]
                
                for nextDigit in nextDigits where 0 <= nextDigit && nextDigit < 10 {
                    nextQueue.append(num * 10 + nextDigit)
                }
            }
            queue = nextQueue
        }
        
        return queue
    }
}

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

Задача: 944. Delete Columns to Make Sorted
Сложность: easy

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

Пример:

Input: strs = ["cba","daf","ghi"]
Output: 1

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

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

2⃣Пройти по каждому столбцу от 0 до длины строки.
Для каждого столбца проверить, отсортированы ли символы лексикографически.
Если столбец не отсортирован, увеличить count.

3⃣Вернуть count.

😎 Решение:

class Solution {
    func minDeletionSize(_ strs: [String]) -> Int {
        var count = 0
        let strs = strs.map { Array($0) }
        for col in 0..<strs[0].count {
            for row in 1..<strs.count {
                if strs[row][col] < strs[row - 1][col] {
                    count += 1
                    break
                }
            }
        }
        return count
    }
}

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

Задача: №44. Wildcard Matching
Сложность: hard

Учитывая входную строку s и шаблон p, реализуйте сопоставление с поддержкой ? и *, где:
- ? соответствует любому отдельному символу.
- * соответствует любой последовательности символов (включая пустую).
Соответствие должно охватывать всю строку s (не частичное).

Пример:

Input: s = "aa", p = "a*"  
Output: true  

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

1⃣Использовать два указателя sdx и pdx для строки s и шаблона p.

2⃣Если символы совпадают или ?, двигаем оба указателя.

3⃣Если встречаем *, запоминаем позиции в s и p, продолжаем проверку.

😎 Решение:

class Solution {
    typealias C = Character
    
    func isMatch(_ s: String, _ p: String) -> Bool {
        var sArray = Array(s)
        var pArray = Array(p)
        
        var sdx = 0, pdx = 0
        var starPDx = -1, starSDx = -1
        
        while sdx < sArray.count {
            if pdx < pArray.count && (sArray[sdx] == pArray[pdx] || pArray[pdx] == C("?")) {
                sdx += 1
                pdx += 1
            } else if pdx < pArray.count && pArray[pdx] == C("*") {
                starPDx = pdx
                starSDx = sdx
                pdx += 1
            } else if starPDx == -1 {
                return false
            } else {
                sdx = starSDx + 1
                pdx = starPDx + 1
                starSDx = sdx
            }
        }
        
        return pdx < pArray.count ? !pArray[pdx...].contains(where: { $0 != C("*") }) : true
    }
}

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

Задача: 952. Largest Component Size by Common Factor
Сложность: hard

Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае.

Пример:

Input: nums = [4,6,15,35]
Output: 4

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

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

2⃣Использовать алгоритм Union-Find для объединения узлов в связные компоненты.
Для каждого числа в массиве nums найти его простые делители и использовать их для объединения узлов.

3⃣Найти размер наибольшей связной компоненты.

😎 Решение:

class Solution {
    func largestComponentSize(_ nums: [Int]) -> Int {
        var parent = [Int: Int]()
        var rank = [Int: Int]()
        
        for num in nums {
            parent[num] = num
            rank[num] = 0
        }
        
        func find(_ x: Int) -> Int {
            if parent[x] != x {
                parent[x] = find(parent[x]!)
            }
            return parent[x]!
        }
        
        func union(_ x: Int, _ y: Int) {
            let rootX = find(x)
            let rootY = find(y)
            if rootX != rootY {
                if rank[rootX]! > rank[rootY]! {
                    parent[rootY] = rootX
                } else if rank[rootX]! < rank[rootY]! {
                    parent[rootX] = rootY
                } else {
                    parent[rootY] = rootX
                    rank[rootX]! += 1
                }
            }
        }
        
        func primeFactors(_ n: Int) -> Set<Int> {
            var factors = Set<Int>()
            var d = 2
            var n = n
            while d * d <= n {
                while n % d == 0 {
                    factors.insert(d)
                    n /= d
                }
                d += 1
            }
            if n > 1 {
                factors.insert(n)
            }
            return factors
        }
        
        var primeToIndex = [Int: [Int]]()
        for num in nums {
            let primes = primeFactors(num)
            for prime in primes {
                primeToIndex[prime, default: []].append(num)
            }
        }
        
        for primes in primeToIndex.values {
            for i in 1..<primes.count {
                union(primes[0], primes[i])
            }
        }
        
        var size = [Int: Int]()
        for num in nums {
            let root = find(num)
            size[root, default: 0] += 1
        }
        
        return size.values.max()!
    }
}

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