Задача: 747. Largest Number At Least Twice of Others
Сложность: easy

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

Пример:

Input: nums = [3,6,1,0]
Output: 1

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

1⃣Найдите максимальный элемент в массиве и его индекс.

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

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

😎 Решение:

func dominantIndex(_ nums: [Int]) -> Int {
    guard let maxVal = nums.max() else { return -1 }
    let maxIndex = nums.firstIndex(of: maxVal)!
    for num in nums {
        if num != maxVal && maxVal < 2 * num {
            return -1
        }
    }
    return maxIndex
}

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

Задача: 628. Maximum Product of Three Numbers
Сложность: easy

Задав целочисленный массив nums, найдите три числа, произведение которых максимально, и верните максимальное произведение.

Пример:

Input: nums = [1,2,3]
Output: 6

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

1⃣Отсортируйте массив nums.

2⃣Найдите два возможных максимальных произведения: Произведение трех наибольших элементов массива. Произведение двух наименьших (отрицательных) и одного наибольшего элемента массива.

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

😎 Решение:

func maximumProduct(_ nums: [Int]) -> Int {
    let nums = nums.sorted()
    let n = nums.count
    let max1 = nums[n - 1] * nums[n - 2] * nums[n - 3]
    let max2 = nums[0] * nums[1] * nums[n - 1]
    return max(max1, max2)
}

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

Задача: 989. Add to Array-Form of Integer
Сложность: easy

Массивная форма целого числа num - это массив, представляющий его цифры в порядке слева направо.

Например, для num = 1321, массивная форма - это [1, 3, 2, 1].
Дано num в массивной форме целого числа и целое число k, верните массивную форму числа num + k.

Пример:

Input: num = [1,2,0,0], k = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

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

1⃣Инициализация переменных:
Преобразуйте число k в массив его цифр и переверните оба массива (массив num и массив цифр k).
Завести переменную carry для хранения переноса и инициализировать ее нулем.
Создать пустой массив result для хранения результата.

2⃣Сложение массивов:
Пройдите по элементам массивов num и цифр k, начиная с их конца, сложите соответствующие цифры вместе с переносом (carry).
Если сумма больше 9, сохраните последнюю цифру в текущей позиции результата, а carry установите в 1.
Если сумма меньше 10, установите carry в 0.
Добавьте результат текущего сложения в массив result

3⃣Обработка оставшихся цифр и переноса:
Если один из массивов закончился раньше, продолжайте сложение оставшихся цифр другого массива с переносом.
Если после окончания всех сложений остается перенос (carry), добавьте его в начало массива result.
Переверните массив result обратно и верните его.

😎 Решение:

func addToArrayForm(_ num: [Int], _ k: Int) -> [Int] {
    var num = num.reversed()
    var k = Array(String(k)).map { Int(String($0))! }.reversed()
    var carry = 0
    var result = [Int]()
    var i = 0
    
    while i < num.count || i < k.count || carry > 0 {
        let n = i < num.count ? num[i] : 0
        let m = i < k.count ? k[i] : 0
        let total = n + m + carry
        carry = total / 10
        result.append(total % 10)
        i += 1
    }
    
    return result.reversed()
}

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

Задача: 77. Combinations
Сложность: medium

Даны два целых числа n и k. Верните все возможные комбинации из k чисел, выбранных из диапазона [1, n].

Ответ можно вернуть в любом порядке.

Пример:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

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

1⃣Инициализировать массив ответов ans и массив для построения комбинаций curr.

2⃣Создать функцию обратного вызова backtrack, которая принимает curr в качестве аргумента, а также целое число firstNum:
Если длина curr равна k, добавить копию curr в ans и вернуться.
Вычислить available, количество чисел, которые мы можем рассмотреть в текущем узле.
Итерировать num от firstNum до firstNum + available включительно.
Для каждого num, добавить его в curr, вызвать backtrack(curr, num + 1), а затем удалить num из curr.

3⃣Вызвать backtrack с изначально пустым curr и firstNum = 1.
Вернуть ans.

😎 Решение:

func combine(_ n: Int, _ k: Int) -> [[Int]] {
    var ans = [[Int]]()
    func backtrack(_ curr: inout [Int], _ firstNum: Int) {
        if curr.count == k {
            ans.append(curr)
            return
        }
        let need = k - curr.count
        let remain = n - firstNum + 1
        let available = remain - need
        for num in firstNum...(firstNum + available) {
            curr.append(num)
            backtrack(&curr, num + 1)
            curr.removeLast()
        }
    }
    var initial = [Int]()
    backtrack(&initial, 1)
    return ans
}

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

Задача: 737. Sentence Similarity II
Сложность: medium

Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].

Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c похожи.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
Output: true

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

1⃣Проверить, одинаковой ли длины предложения sentence1 и sentence2. Если нет, вернуть false.

2⃣Построить граф схожести слов с использованием словаря.

3⃣Использовать поиск в глубину (DFS) для проверки транзитивной схожести слов в предложениях.

😎 Решение:

func areSentencesSimilar(_ sentence1: [String], _ sentence2: [String], _ similarPairs: [[String]]) -> Bool {
    if sentence1.count != sentence2.count {
        return false
    }
    
    var graph = [String: [String]]()
    for pair in similarPairs {
        let (x, y) = (pair[0], pair[1])
        graph[x, default: []].append(y)
        graph[y, default: []].append(x)
    }
    
    func dfs(_ word1: String, _ word2: String, _ visited: inout Set<String>) -> Bool {
        if word1 == word2 {
            return true
        }
        visited.insert(word1)
        for neighbor in graph[word1, default: []] {
            if !visited.contains(neighbor) && dfs(neighbor, word2, &visited) {
                return true
            }
        }
        return false
    }
    
    for (w1, w2) in zip(sentence1, sentence2) {
        if w1 != w2 {
            var visited = Set<String>()
            if !dfs(w1, w2, &visited) {
                return false
            }
        }
    }
    
    return true
}

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

Задача: 1802. Maximum Value at a Given Index in a Bounded Array
Сложность: medium

Даны три положительных целых числа: n, index и maxSum. Вам нужно построить массив nums (индексация с нуля), который удовлетворяет следующим условиям:

- nums.length == n
- nums[i] является положительным целым числом, где 0 <= i < n.
- abs(nums[i] - nums[i+1]) <= 1, где 0 <= i < n-1.
- Сумма всех элементов массива nums не превышает maxSum.
- nums[index] максимально возможен.

Верните значение nums[index] в построенном массиве.

Обратите внимание, что abs(x) равно x, если x >= 0, и -x в противном случае.

Пример:

Input: n = 4, index = 2,  maxSum = 6
Output: 2

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

1⃣Определите функцию getSum(index, value) для вычисления минимальной суммы массива при условии, что nums[index] = value.

2⃣Инициализируйте диапазон поиска [left, right] значениями left = 1 и right = maxSum. Выполните бинарный поиск: вычислите mid = (left + right + 1) / 2 и проверьте, если getSum(index, mid) <= maxSum. Если условие выполняется, установите left = mid, иначе установите right = mid - 1.

3⃣Верните left по завершении бинарного поиска.

😎 Решение:

class Solution {
    private func getSum(_ index: Int, _ value: Int, _ n: Int) -> Int64 {
        var count: Int64 = 0
        if value > index {
            count += Int64(value + value - index) * Int64(index + 1) / 2
        } else {
            count += Int64(value + 1) * Int64(value) / 2 + Int64(index - value + 1)
        }
        if value >= n - index {
            count += Int64(value + value - n + 1 + index) * Int64(n - index) / 2
        } else {
            count += Int64(value + 1) * Int64(value) / 2 + Int64(n - index - value)
        }
        return count - Int64(value)
    }

    func maxValue(_ n: Int, _ index: Int, _ maxSum: Int) -> Int {
        var left = 1, right = maxSum
        while left < right {
            let mid = (left + right + 1) / 2
            if getSum(index, mid, n) <= maxSum {
                left = mid
            } else {
                right = mid - 1
            }
        }
        return left
    }
}

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

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

Даны корни двух бинарных деревьев p и q. Напишите функцию, чтобы проверить, одинаковы ли они. Два бинарных дерева считаются одинаковыми, если они структурно идентичны, и узлы имеют одинаковые значения.
Пример:
Input: p = [1,2,3], q = [1,2,3] Output: true

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

1⃣Если оба узла — nil, возвращаем true

2⃣Если один из них — nil, или значения не совпадают, возвращаем false

3⃣Рекурсивно проверяем левое и правое поддерево

😎 Решение:

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

class Solution {
    func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        if p == nil && q == nil {
            return true
        }
        if p == nil || q == nil {
            return false
        }
        if p!.val != q!.val {
            return false
        }
        return isSameTree(p!.left, q!.left) && isSameTree(p!.right, q!.right)
    }
}

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

Задача: 198. House Robber
Сложность: medium

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

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

Пример:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

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

1⃣Определите функцию robFrom(), которая принимает индекс дома, который грабитель должен осмотреть, и массив nums, необходимый для вычислений. На каждом шаге рекурсивного вызова у грабителя есть два варианта: ограбить текущий дом или нет.

2⃣Если грабитель выбирает ограбить текущий дом, он должен пропустить следующий, т.е. вызвать robFrom(i + 2, nums). Ответ будет равен значению robFrom(i + 2, nums) плюс сумма, которую грабитель получит, ограбив текущий дом, т.е. nums[i]. В противном случае он может перейти к следующему дому и вернуть прибыль, которую он получит в подзадаче, т.е. robFrom(i + 1, nums).

3⃣Нужно найти, сохранить в кэше и вернуть максимум из этих двух вариантов на каждом шаге. robFrom(0, nums) даст ответ на всю задачу.

😎 Решение:

class Solution {
    var memo: [Int]

    init() {
        memo = Array(repeating: -1, count: 100)
    }

    func rob(_ nums: [Int]) -> Int {
        return robFrom(0, nums)
    }

    private func robFrom(_ i: Int, _ nums: [Int]) -> Int {
        if i >= nums.count {
            return 0
        }

        if memo[i] > -1 {
            return memo[i]
        }

        let ans = max(robFrom(i + 1, nums), robFrom(i + 2, nums) + nums[i])

        memo[i] = ans
        return ans
    }
}

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

Задача: 110. Balanced Binary Tree
Сложность: easy

Дано бинарное дерево, определите, является ли оно
сбалансированным по высоте.

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: true

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

1⃣Сначала мы определяем функцию height, которая для любого узла p в дереве T возвращает:
-1, если p является пустым поддеревом, т.е. null;
1 + max(height(p.left), height(p.right)) в противном случае.

2⃣Теперь, когда у нас есть метод для определения высоты дерева, остается только сравнить высоты детей каждого узла. Дерево T с корнем r является сбалансированным тогда и только тогда, когда высоты его двух детей отличаются не более чем на 1 и поддеревья каждого ребенка также сбалансированы.

3⃣Следовательно, мы можем сравнить высоты двух дочерних поддеревьев, а затем рекурсивно проверить каждое из них:
Если root == NULL, возвращаем true.
Если abs(height(root.left) - height(root.right)) > 1, возвращаем false.
В противном случае возвращаем isBalanced(root.left) && isBalanced(root.right).

😎 Решение:

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

class Solution {
    func height(_ root: TreeNode?) -> Int {
        guard let root = root else {
            return -1
        }
        return 1 + max(height(root.left), height(root.right))
    }

    func isBalanced(_ root: TreeNode?) -> Bool {
        guard let root = root else {
            return true
        }
        return abs(height(root.left) - height(root.right)) < 2 &&
               isBalanced(root.left) && isBalanced(root.right)
    }
}

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

Задача: 850. Rectangle Area II
Сложность: hard

Вам дан двумерный массив прямоугольников, выровненных по осям. Каждый прямоугольник[i] = [xi1, yi1, xi2, yi2] обозначает i-й прямоугольник, где (xi1, yi1) — координаты нижнего левого угла, а (xi2, yi2) — координаты верхнего правого угла.

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

Верните общую площадь. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.

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

1⃣Переназначьте каждую x координату на 0, 1, 2, .... Аналогично, переназначьте все y координаты.

2⃣Теперь мы имеем задачу, которую можно решить методом грубой силы: для каждого прямоугольника с переназначенными координатами (rx1, ry1, rx2, ry2) заполним сетку grid[x][y] = True для rx1 <= x < rx2 и ry1 <= y < ry2.

3⃣Затем каждая ячейка grid[rx][ry] будет представлять площадь (imapx(rx+1) - imapx(rx)) * (imapy(ry+1) - imapy(ry)), где если x был переназначен на rx, то imapx(rx) = x ("обратная карта x для переназначенного x равна x"), аналогично для imapy.

😎 Решение:

class Solution {
    func rectangleArea(_ rectangles: [[Int]]) -> Int {
        let N = rectangles.count
        var Xvals = Set<Int>()
        var Yvals = Set<Int>()

        for rec in rectangles {
            Xvals.insert(rec[0])
            Xvals.insert(rec[2])
            Yvals.insert(rec[1])
            Yvals.insert(rec[3])
        }

        let imapx = Array(Xvals).sorted()
        let imapy = Array(Yvals).sorted()

        var mapx = [Int: Int]()
        var mapy = [Int: Int]()
        for i in 0..<imapx.count {
            mapx[imapx[i]] = i
        }
        for i in 0..<imapy.count {
            mapy[imapy[i]] = i
        }

        var grid = Array(repeating: Array(repeating: false, count: imapy.count), count: imapx.count)
        for rec in rectangles {
            for x in mapx[rec[0]]!..<mapx[rec[2]]! {
                for y in mapy[rec[1]]!..<mapy[rec[3]]! {
                    grid[x][y] = true
                }
            }
        }

        var ans: Int64 = 0
        for x in 0..<grid.count {
            for y in 0..<grid[0].count {
                if grid[x][y] {
                    ans += Int64(imapx[x+1] - imapx[x]) * Int64(imapy[y+1] - imapy[y])
                }
            }
        }

        ans %= 1_000_000_007
        return Int(ans)
    }
}

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

Задача: 1014. Best Sightseeing Pair
Сложность: medium

Вам дан целочисленный массив values, в котором values[i] представляет собой значение i-й достопримечательности. Две достопримечательности i и j имеют расстояние j - i между собой. Оценка пары (i < j) достопримечательностей равна values[i] + values[j] + i - j: сумма значений достопримечательностей минус расстояние между ними. Возвращается максимальная оценка пары достопримечательностей.

Пример:

Input: values = [8,1,5,2,6]
Output: 11

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

1⃣Инициализация переменных:
Инициализируйте переменную max_score для хранения максимальной оценки пары.
Инициализируйте переменную max_i_plus_value для хранения максимального значения выражения values[i] + i при проходе по массиву.

2⃣Проход по массиву:
Пройдитесь по массиву начиная с первого элемента и для каждого элемента values[j] вычислите текущую оценку пары как values[j] - j + max_i_plus_value.
Обновите значение max_score, если текущая оценка больше.
Обновите значение max_i_plus_value, если текущий элемент values[j] + j больше предыдущего max_i_plus_value.

3⃣Возврат результата:
Верните значение max_score как максимальную оценку пары достопримечательностей.

😎 Решение:

class Solution {
    func maxScoreSightseeingPair(_ values: [Int]) -> Int {
        var max_score = 0
        var max_i_plus_value = values[0]
        
        for j in 1..<values.count {
            max_score = max(max_score, max_i_plus_value + values[j] - j)
            max_i_plus_value = max(max_i_plus_value, values[j] + j)
        }
        
        return max_score
    }
}

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

Задача: 898. Bitwise ORs of Subarrays
Сложность: medium

Если задан целочисленный массив arr, верните количество различных побитовых ИЛИ всех непустых подмассивов arr. Побитовое ИЛИ подмассива - это побитовое ИЛИ каждого целого числа в подмассиве. Побитовым ИЛИ подмассива одного целого числа является это целое число. Подмассив - это непрерывная непустая последовательность элементов в массиве.

Пример:

Input: arr = [0]
Output: 1

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

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

2⃣Для каждого элемента массива, вычислить побитовое ИЛИ всех подмассивов, начинающихся с этого элемента.
Добавить результат каждого вычисления в множество.

3⃣Вернуть размер множества.

😎 Решение:

func subarrayBitwiseORs(_ arr: [Int]) -> Int {
    var result = Set<Int>()
    var current = Set<Int>()
    for num in arr {
        current = Set(current.map { $0 | num }) + [num]
        result.formUnion(current)
    }
    return result.count
}

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

Задача: 258. Add Digits
Сложность: easy

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

Пример:

Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

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

1⃣Инициализируйте переменную digital_root значением 0.

2⃣В цикле, пока num больше 0:
Добавьте к digital_root последнюю цифру num.
Уменьшите num, удалив последнюю цифру.
Если num равно 0 и digital_root больше 9, присвойте num значение digital_root и сбросьте digital_root в 0.

3⃣Верните значение digital_root.

😎 Решение:

class Solution {
    func addDigits(_ num: Int) -> Int {
        var num = num
        var digital_root = 0
        while num > 0 {
            digital_root += num % 10
            num /= 10
            if num == 0 && digital_root > 9 {
                num = digital_root
                digital_root = 0
            }
        }
        return digital_root
    }
}

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

#medium
Задача: 161. One Edit Distance

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

Строка s считается отличающейся на одну операцию редактирования от строки t, если можно:
- Вставить ровно один символ в строку s, чтобы получить t.
- Удалить ровно один символ из строки s, чтобы получить t.
- Заменить ровно один символ в строке s на другой символ, чтобы получить t.

Пример:

Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.

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

1⃣Проверка длины строк:
Убедитесь, что строка s короче строки t. Если это не так, поменяйте их местами и повторите проверку.
Если разница в длине между s и t больше 1, то строки невозможно привести к равенству одной операцией редактирования, верните false.

2⃣Сравнение строк посимвольно:
Проходите по строке s и сравнивайте каждый символ с соответствующим символом в строке t.
Если находите различающийся символ:
Если длины строк равны (ns == nt), проверьте, равны ли подстроки после текущего символа для обеих строк (s.substr(i + 1) == t.substr(i + 1)). Если равны, возвращайте true, иначе false.
Если длины строк различаются, проверьте, равна ли подстрока s начиная с текущего символа подстроке t начиная с следующего символа (s.substr(i) == t.substr(i + 1)). Если равны, возвращайте true, иначе false

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

😎 Решение:

class Solution {
    func isOneEditDistance(_ s: String, _ t: String) -> Bool {
        let ns = s.count
        let nt = t.count
        let sChars = Array(s)
        let tChars = Array(t)
        if ns > nt { return isOneEditDistance(t, s) }
        if nt - ns > 1 { return false }

        for i in 0..<ns {
            if sChars[i] != tChars[i] {
                if ns == nt { return String(sChars[(i + 1)...]) == String(tChars[(i + 1)...]) }
                else { return String(sChars[i...]) == String(tChars[(i + 1)...]) }
            }
        }
        return ns + 1 == nt
    }
}

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

Задача: 1189. Maximum Number of Balloons
Сложность: easy

Дана строка text. Вы хотите использовать символы строки text, чтобы сформировать как можно больше экземпляров слова "balloon".

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

Пример:

Input: text = "nlaebolko"
Output: 1

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

1⃣Подсчитайте количество появлений каждого символа 'b', 'a', 'l', 'o', 'n' в строке text.

2⃣Вычислите потенциал для каждого символа: для 'b' и 'a' потенциал равен количеству их появлений, для 'l' и 'o' потенциал равен количеству их появлений, деленному на 2, а для 'n' потенциал равен количеству его появлений.

3⃣Найдите символ с наименьшим потенциалом среди 'b', 'a', 'l', 'o', 'n', который ограничивает количество возможных слов "balloon", и верните это значение.

😎 Решение

class Solution {
    func maxNumberOfBalloons(_ text: String) -> Int {
        var bCount = 0, aCount = 0, lCount = 0, oCount = 0, nCount = 0

        for char in text {
            if char == "b" {
                bCount += 1
            } else if char == "a" {
                aCount += 1
            } else if char == "l" {
                lCount += 1
            } else if char == "o" {
                oCount += 1
            } else if char == "n" {
                nCount += 1
            }
        }

        lCount = lCount / 2
        oCount = oCount / 2

        return min(bCount, min(aCount, min(lCount, min(oCount, nCount))))
    }
}

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

Задача: 972. Equal Rational Numbers
Сложность: hard

Даны две строки s и t, каждая из которых представляет собой неотрицательное рациональное число. Вернуть true тогда и только тогда, когда они представляют одно и то же число. Строки могут использовать скобки для обозначения повторяющейся части рационального числа.

Рациональное число может быть представлено с использованием до трех частей: <ЦелаяЧасть>, <НеповторяющаясяЧасть> и <ПовторяющаясяЧасть>. Число будет представлено одним из следующих трех способов:

<ЦелаяЧасть>
Например, 12, 0 и 123.
<ЦелаяЧасть><.><НеповторяющаясяЧасть>
Например, 0.5, 1., 2.12 и 123.0001.
<ЦелаяЧасть><.><НеповторяющаясяЧасть><(><ПовторяющаясяЧасть><)>
Например, 0.1(6), 1.(9), 123.00(1212).
Повторяющаяся часть десятичного разложения обозначается в круглых скобках. Например:

1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66).

Пример:

Input: s = "0.(52)", t = "0.5(25)"
Output: true
Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

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

1⃣Преобразование дроби. Определите и изолируйте повторяющуюся часть дроби. Преобразуйте строку, представляющую число, в выражение вида S=x/(10^k-1), где x — повторяющаяся часть, а k — её длина.

2⃣Вычисление геометрической суммы. Преобразуйте повторяющуюся часть в сумму вида S=x*(r/(1-r)), где r = 10^(-k). Найдите значение дроби для повторяющейся части, используя формулу геометрической прогрессии.

3⃣Обработка неповторяющейся части. Определите значение неповторяющейся части дроби как обычное число. Объедините результаты для повторяющейся и неповторяющейся частей для получения итогового значения.

😎 Решение:

class Solution {
    func isRationalEqual(_ S: String, _ T: String) -> Bool {
        let f1 = convert(S)
        let f2 = convert(T)
        return f1.n == f2.n && f1.d == f2.d
    }

    func convert(_ S: String) -> Fraction {
        var state = 0
        var ans = Fraction(0, 1)
        var decimal_size = 0

        for part in S.split(whereSeparator: { ".()".contains($0) }) {
            state += 1
            if part.isEmpty { continue }
            let x = Int64(part) ?? 0
            let sz = part.count

            if state == 1 {
                ans.iadd(Fraction(x, 1))
            } else if state == 2 {
                ans.iadd(Fraction(x, Int64(pow(10.0, Double(sz)))))
                decimal_size = sz
            } else {
                var denom = Int64(pow(10.0, Double(decimal_size)))
                denom *= Int64(pow(10.0, Double(sz))) - 1
                ans.iadd(Fraction(x, denom))
            }
        }
        return ans
    }
}

class Fraction {
    var n: Int64
    var d: Int64

    init(_ n: Int64, _ d: Int64) {
        let g = Fraction.gcd(n, d)
        self.n = n / g
        self.d = d / g
    }

    func iadd(_ other: Fraction) {
        let numerator = self.n * other.d + self.d * other.n
        let denominator = self.d * other.d
        let g = Fraction.gcd(numerator, denominator)
        self.n = numerator / g
        self.d = denominator / g
    }

    static func gcd(_ x: Int64, _ y: Int64) -> Int64 {
        return x != 0 ? gcd(y % x, x) : y
    }
}

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

Задача: 755. Pour Water
Сложность: medium

Вам дана карта высот, представленная в виде целочисленного массива heights, где heights[i] - высота местности в точке i. Ширина в каждой точке равна 1. Вам также даны два целых числа volume и k. Единицы объема воды будут падать в точке k. Вода сначала падает в точке k и упирается в самую высокую местность или воду в этой точке. Затем она течет по следующим правилам: если капля в конечном итоге упадет, двигаясь влево, то двигайтесь влево. Иначе, если капля в конечном итоге упадет, двигаясь вправо, то двигайтесь вправо. Иначе поднимайтесь в текущее положение. Здесь "в конечном итоге упадет" означает, что капля в конечном итоге окажется на более низком уровне, если она будет двигаться в этом направлении. Кроме того, уровень означает высоту местности плюс вода в этом столбе. Мы можем предположить, что на двух сторонах, выходящих за пределы массива, есть бесконечно высокая местность. Также не может быть частичного равномерного распределения воды более чем на один блок сетки, и каждая единица воды должна находиться ровно в одном блоке.

Пример:

Input: heights = [2,1,1,2,1,2,2], volume = 4, k = 3
Output: [2,2,2,3,2,2,2]

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

1⃣Инициализируйте цикл для добавления объема воды.

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

3⃣Повторите шаг 2, пока не будет добавлен весь объем воды.

😎 Решение:

func pourWater(_ heights: inout [Int], _ volume: Int, _ k: Int) -> [Int] {
    for _ in 0..<volume {
        var dropIndex = k
        for d in [-1, 1] {
            var i = k
            while i + d >= 0 && i + d < heights.count && heights[i + d] <= heights[i] {
                if heights[i + d] < heights[i] {
                    dropIndex = i + d
                }
                i += d
            }
            if dropIndex != k {
                break
            }
        }
        heights[dropIndex] += 1
    }
    return heights
}

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

Задача: 1102. Path With Maximum Minimum Value
Сложность: medium

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

Значение пути определяется минимальным числом на этом пути.

Пример:

Input: grid = [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
Explanation: The path with the maximum score is highlighted in yellow. 

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

1⃣Начните с оценки curScore = min(grid[0][0], grid[m-1][n-1]), где m и n - общее количество строк и столбцов входной матрицы.

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

3⃣Если пути не существует, что означает, что curScore слишком велик, уменьшите его на 1 и повторите шаг 2.
В противном случае, верните curScore как ответ.

😎 Решение:

class Solution {
    let dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]

    func maximumMinimumPath(_ grid: [[Int]]) -> Int {
        var curScore = min(grid[0][0], grid[grid.count - 1][grid[0].count - 1])

        while curScore >= 0 {
            if pathExists(grid, curScore) {
                return curScore
            } else {
                curScore -= 1
            }
        }
        return -1
    }

    func pathExists(_ grid: [[Int]], _ curScore: Int) -> Bool {
        let R = grid.count, C = grid[0].count
        var visited = Array(repeating: Array(repeating: false, count: C), count: R)
        var dq: [(Int, Int)] = [(0, 0)]
        visited[0][0] = true

        func push(_ row: Int, _ col: Int) {
            if row >= 0 && col >= 0 && row < R && col < C && !visited[row][col] && grid[row][col] >= curScore {
                dq.append((row, col))
                visited[row][col] = true
            }
        }

        while !dq.isEmpty {
            let (curRow, curCol) = dq.removeFirst()
            if curRow == R - 1 && curCol == C - 1 {
                return true
            }

            for dir in dirs {
                push(curRow + dir[0], curCol + dir[1])
            }
        }
        return false
    }
}

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

Задача: 92. Reverse Linked List II
Сложность: medium

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

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

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

1⃣Определяем рекурсивную функцию, которая будет отвечать за переворачивание части односвязного списка. Назовем эту функцию recurse. Функция принимает три параметра: m, начальную точку переворота, n, конечную точку переворота, и указатель right, который начинается с узла n в связанном списке и движется назад вместе с откатом рекурсии. Если это пока не ясно, следующие диаграммы помогут.

2⃣Также у нас есть указатель left, который начинается с узла m в связанном списке и движется вперед. В Python мы должны использовать глобальную переменную для этого, которая изменяется с каждым вызовом рекурсии. В других языках, где изменения, сделанные в вызовах функций, сохраняются, мы можем рассматривать этот указатель как дополнительную переменную для функции recurse.
В рекурсивном вызове, учитывая m, n и right, мы проверяем, равно ли n единице. Если это так, дальше двигаться не нужно.

3⃣До тех пор, пока мы не достигнем n = 1, мы продолжаем двигать указатель right на один шаг вперед, после чего делаем рекурсивный вызов с уменьшенным на один значением n. В то же время мы продолжаем двигать указатель left вперед до тех пор, пока m не станет равным 1. Когда мы говорим, что указатель движется вперед, мы имеем в виду pointer.next.
Таким образом, мы откатываемся, как только n достигает 1. В этот момент указатель right находится на последнем узле подсписка, который мы хотим перевернуть, и left уже достиг первого узла этого подсписка. Тогда мы меняем данные и перемещаем указатель left на один шаг вперед с помощью left = left.next. Нам нужно, чтобы это изменение сохранялось в процессе отката.
Оттуда при каждом откате указатель right движется на один шаг назад. Это и есть та симуляция, о которой мы всё время говорили. Обратное движение симулируется откатом.
Мы прекращаем обмены, когда right == left, что происходит, если размер подсписка нечетный, или right.next == left, что происходит в процессе отката для четного подсписка, когда указатель right пересекает left. Мы используем глобальный булевый флаг для остановки обменов, как только эти условия выполнены.

😎 Решение:

class ListNode {
    var val: Int
    var next: ListNode?

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

class Solution {
    private var left: ListNode?
    private var stop = false

    func reverseBetween(_ head: ListNode?, _ m: Int, _ n: Int) -> ListNode? {
        if head == nil { return nil }

        left = head
        var right = head
        stop = false

        recurseAndReverse(right, m, n)
        return head
    }

    private func recurseAndReverse(_ right: ListNode?, _ m: Int, _ n: Int) {
        if n == 1 { return }

        if let next = right?.next {
            recurseAndReverse(next, m - 1, n - 1)
        }

        if left === right || right?.next === left {
            stop = true
        }

        if !stop {
            let temp = left?.val
            left?.val = right?.val
            right?.val = temp

            left = left?.next
        }
    }
}
class ListNode {
    var val: Int
    var next: ListNode?

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

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

Задача: 270. Closest Binary Search Tree Value
Сложность: easy

Дано корень бинарного дерева поиска и целевое значение. Верните значение в дереве, которое ближе всего к целевому. Если существует несколько ответов, выведите наименьшее.

Пример:

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

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

1⃣Построить массив с помощью inorder обхода:
Выполнить inorder обход дерева и собрать элементы в отсортированный массив.

2⃣Найти ближайший элемент:
Пройти по массиву и определить элемент, наиболее близкий к целевому значению.

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

😎 Решение:

class Solution {
    func closestValue(_ root: TreeNode?, _ target: Double) -> Int {
        var closest = root!.val
        var node = root
        while node != nil {
            if abs(Double(node!.val) - target) < abs(Double(closest) - target) {
                closest = node!.val
            } else if abs(Double(node!.val) - target) == abs(Double(closest) - target) {
                closest = min(node!.val, closest)
            }
            node = target < Double(node!.val) ? node!.left : node!.right
        }
        return closest
    }
}

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