#medium
Задача: 419. Battleships in a Board

Если задана матричная доска размером m x n, где каждая клетка - линкор 'X' или пустая '.', верните количество линкоров на доске. Линкоры могут располагаться на доске только горизонтально или вертикально. Другими словами, они могут быть выполнены только в форме 1 x k (1 строка, k столбцов) или k x 1 (k строк, 1 столбец), где k может быть любого размера. Между двумя линкорами есть хотя бы одна горизонтальная или вертикальная клетка (т. е. нет соседних линкоров).

Пример:

Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
Output: 2

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

1⃣Пройдите по каждой клетке матрицы.

2⃣Если текущая клетка содержит 'X' и она не является продолжением линкора (т.е. не имеет 'X' сверху или слева), увеличьте счетчик линкоров.

3⃣Верните итоговый счетчик.

😎 Решение:

func countBattleships(_ board: [[Character]]) -> Int {
    let m = board.count
    let n = board[0].count
    var count = 0
    
    for i in 0..<m {
        for j in 0..<n {
            if board[i][j] == "X" {
                if (i == 0 || board[i-1][j] != "X") && (j == 0 || board[i][j-1] != "X") {
                    count += 1
                }
            }
        }
    }
    
    return count
}

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

#medium
Задача: 553. Optimal Division

Дано целочисленный массив nums. Соседние целые числа в nums будут выполнять деление с плавающей запятой.

Например, для nums = [2,3,4] мы будем вычислять выражение "2/3/4".
Однако, вы можете добавить любое количество скобок в любое место, чтобы изменить приоритет операций. Вы хотите добавить эти скобки так, чтобы значение выражения после вычисления было максимальным.

Верните соответствующее выражение, которое имеет максимальное значение в строковом формате.

Пример:

Input: nums = [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation: 1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant since they do not influence the operation priority.
So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

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

1⃣Разверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры во втором числе: держите переменную переноса, изначально равную 0. Инициализируйте массив (currentResult), начинающийся с некоторых нулей в зависимости от места цифры во втором числе.

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

3⃣После итерации по каждой цифре в первом числе, если перенос не равен нулю, добавьте перенос к массиву currentResult. Добавьте currentResult к массиву ans. Если последняя цифра в ans равна нулю, перед разворотом ans удалите этот ноль, чтобы избежать ведущего нуля в окончательном ответе. Разверните ans и верните его.

😎 Решение:

class Solution {
    private func addStrings(_ num1: [Int], _ num2: [Int]) -> [Int] {
        var ans = [Int]()
        var carry = 0
        let n1 = num1.count
        let n2 = num2.count

        for i in 0..<max(n1, n2) + 1 {
            let digit1 = i < n1 ? num1[i] : 0
            let digit2 = i < n2 ? num2[i] : 0
            let sum = digit1 + digit2 + carry
            carry = sum / 10
            ans.append(sum % 10)
        }
        return ans
    }

    private func multiplyOneDigit(_ firstNumber: String, _ secondNumberDigit: Character, _ numZeros: Int) -> [Int] {
        var currentResult = [Int](repeating: 0, count: numZeros)
        var carry = 0

        for digit in firstNumber {
            let multiplication = (secondNumberDigit.wholeNumberValue! * digit.wholeNumberValue!) + carry
            carry = multiplication / 10
            currentResult.append(multiplication % 10)
        }
        if carry != 0 {
            currentResult.append(carry)
        }
        return currentResult
    }

    func multiply(_ firstNumber: String, _ secondNumber: String) -> String {
        if firstNumber == "0" || secondNumber == "0" {
            return "0"
        }

        let firstNumber = String(firstNumber.reversed())
        let secondNumber = String(secondNumber.reversed())

        var ans = [Int](repeating: 0, count: firstNumber.count + secondNumber.count)

        for (i, digit) in secondNumber.enumerated() {
            ans = addStrings(multiplyOneDigit(firstNumber, digit, i), ans)
        }

        while ans.last == 0 {
            ans.removeLast()
        }

        return ans.reversed().map { String($0) }.joined()
    }
}

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

#hard
Задача: 420. Strong Password Checker

Пароль считается надежным, если выполняются следующие условия: в нем не менее 6 и не более 20 символов. он содержит не менее одной строчной буквы, не менее одной заглавной буквы и не менее одной цифры. он не содержит трех повторяющихся символов подряд (например, "Baaabb0" - слабый, а "Baaba0" - сильный). Учитывая строку пароля, верните минимальное количество шагов, необходимых для того, чтобы сделать пароль сильным. Если пароль уже сильный, верните 0. За один шаг можно: вставить один символ в пароль, удалить один символ из пароля или заменить один символ пароля другим символом.

Пример:

Input: password = "a"
Output: 5

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

1⃣Определите количество недостающих символов до минимума и превышающих символов для ограничения длины пароля. Также определите наличие строчных, заглавных букв и цифр.

2⃣Вычислите количество необходимых замен для устранения трех повторяющихся символов подряд.

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

😎 Решение:

func strongPasswordChecker(_ s: String) -> Int {
    let n = s.count
    var hasLower = false
    var hasUpper = false
    var hasDigit = false
    var repeatCount = 0
    var i = 0
    let sArray = Array(s)
    
    while i < n {
        if sArray[i].isLowercase { hasLower = true }
        if sArray[i].isUppercase { hasUpper = true }
        if sArray[i].isNumber { hasDigit = true }
        
        let start = i
        while i < n && sArray[i] == sArray[start] {
            i += 1
        }
        
        repeatCount += (i - start) / 3
    }
    
    let missingTypes = (hasLower ? 0 : 1) + (hasUpper ? 0 : 1) + (hasDigit ? 0 : 1)
    
    if n < 6 {
        return max(missingTypes, 6 - n)
    } else if n <= 20 {
        return max(missingTypes, repeatCount)
    } else {
        let excessChars = n - 20
        var overLenReduction = 0
        
        i = 2
        while i < n && excessChars > 0 {
            if i % 3 == 2 && sArray[i] == sArray[i - 1] && sArray[i] == sArray[i - 2] {
                overLenReduction += 1
                excessChars -= 1
            }
            i += 1
        }
        
        repeatCount -= overLenReduction
        return (n - 20) + max(missingTypes, repeatCount)
    }
}

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

#medium
Задача: 554. Brick Wall

Перед вами находится прямоугольная кирпичная стена с n рядами кирпичей. В i-м ряду находится несколько кирпичей одинаковой высоты (то есть один юнит), но они могут быть разной ширины. Общая ширина каждого ряда одинакова.

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

Дан двумерный массив wall, содержащий информацию о стене, верните минимальное количество пересеченных кирпичей после проведения такой вертикальной линии.

Пример:

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

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

1⃣Определите общую ширину стены, сложив ширины кирпичей в первом ряду. Создайте массив pos, где pos[i] указывает на текущую позицию в i-ом ряду.

2⃣Пройдите по каждой возможной позиции для вертикальной линии (от 1 до общей ширины стены - 1). Для каждой позиции обновите массив pos, проверяя, пересекает ли линия границу кирпича. Если пересекает, увеличьте значение pos[i].

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

😎 Решение:

class Solution {
    func leastBricks(_ wall: [[Int]]) -> Int {
        var pos = [Int](repeating: 0, count: wall.count)
        var res = Int.max
        var sum = wall[0].reduce(0, +)
        
        while sum != 0 {
            var count = 0
            for i in 0..<wall.count {
                if wall[i][pos[i]] != 0 {
                    count += 1
                } else {
                    pos[i] += 1
                }
                wall[i][pos[i]] -= 1
            }
            sum -= 1
            res = min(res, count)
        }
        
        return res
    }
}

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

#medium
Задача: 556. Next Greater Element III

Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм:

Дано положительное целое число n. Найдите наименьшее целое число, которое имеет точно такие же цифры, как и число n, и больше самого числа n по значению. Если такого положительного целого числа не существует, верните -1.

Учтите, что возвращенное число должно помещаться в 32-битное целое число. Если существует допустимый ответ, но он не помещается в 32-битное целое число, верните -1.

Пример:

Input: n = 12
Output: 21

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

1⃣Нахождение и перестановка цифр
Преобразуйте число n в массив цифр. Найдите первую цифру, которая нарушает убывающий порядок (с конца массива). Назовем её индексом i. Найдите первую цифру, которая больше digits[i-1] (с конца массива). Назовем её индексом j. Поменяйте местами цифры на позициях i-1 и j.

2⃣Обратный порядок оставшихся цифр
Обратный порядок части массива от индекса i до конца, чтобы получить наименьшую перестановку, которая больше исходной.

3⃣Проверка результата и преобразование обратно в число
Преобразуйте массив цифр обратно в число. Если число превышает 32-битный предел, верните -1. В противном случае верните полученное число.

😎 Решение:

class Solution {
    private func swap(_ s: String, _ i0: Int, _ i1: Int) -> String {
        if i0 == i1 {
            return s
        }
        var chars = Array(s)
        chars.swapAt(i0, i1)
        return String(chars)
    }

    private var list = [String]()
    
    private func permute(_ a: String, _ l: Int, _ r: Int) {
        if l == r {
            list.append(a)
        } else {
            var a = a
            for i in l...r {
                a = swap(a, l, i)
                permute(a, l + 1, r)
                a = swap(a, l, i)
            }
        }
    }

    func nextGreaterElement(_ n: Int) -> Int {
        let s = String(n)
        permute(s, 0, s.count - 1)
        list.sort()
        if let index = list.firstIndex(of: s), index < list.count - 1 {
            if let result = Int(list[index + 1]), result <= Int32.max {
                return result
            }
        }
        return -1
    }
}

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

#easy
Задача: 557. Reverse Words in a String III

Дана строка s. Необходимо изменить порядок символов в каждом слове в предложении, сохранив при этом пробелы и начальный порядок слов.

Пример:

Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

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

1⃣Создайте переменную lastSpaceIndex и установите её значение в -1. Пройдите по каждому символу строки s от 0-го до n-го индекса, используя указатель strIndex.

2⃣Когда strIndex указывает на пробел, определите начало (startIndex = lastSpaceIndex + 1) и конец (endIndex = strIndex - 1) текущего слова. Используя два указателя, измените порядок символов в текущем слове.

3⃣Обновите lastSpaceIndex значением strIndex. После окончания цикла измените порядок символов в последнем слове (от lastSpaceIndex + 1 до конца строки).

😎 Решение:

class Solution {
    func reverseWords(_ s: String) -> String {
        var chars = Array(s)
        var lastSpaceIndex = -1
        let len = chars.count
        
        for strIndex in 0...len {
            if strIndex == len || chars[strIndex] == " " {
                var startIndex = lastSpaceIndex + 1
                var endIndex = strIndex - 1
                while startIndex < endIndex {
                    chars.swapAt(startIndex, endIndex)
                    startIndex += 1
                    endIndex -= 1
                }
                lastSpaceIndex = strIndex
            }
        }
        
        return String(chars)
    }
}

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

#easy
Задача: 590. N-ary Tree Postorder Traversal

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

Сериализация входных данных n-арного дерева представлена в обходе уровней. Каждая группа детей разделяется значением null (см. примеры).

Пример:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

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

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

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

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

😎 Решение:

class Node {
    var val: Int
    var children: [Node]
    init(_ val: Int) {
        self.val = val
        self.children = []
    }
}

class Solution {
    func postorder(_ root: Node?) -> [Int] {
        guard let root = root else { return [] }
        var stack: [Node] = [root]
        var output: [Int] = []
        
        while !stack.isEmpty {
            let node = stack.removeLast()
            output.insert(node.val, at: 0)
            for child in node.children {
                stack.append(child)
            }
        }
        return output
    }
}

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

#medium
Задача: 592. Fraction Addition and Subtraction

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

Окончательный результат должен быть несократимой дробью. Если ваш окончательный результат является целым числом, преобразуйте его в формат дроби с знаменателем 1. Таким образом, 2 должно быть преобразовано в 2/1.

Пример:

Input: expression = "-1/2+1/2+1/3"
Output: "1/3"

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

1⃣Начните сканирование строки и разделите её на части, содержащие числители и знаменатели, с учетом знаков.

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

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

😎 Решение:

class Solution {
    func fractionAddition(_ expression: String) -> String {
        var sign = [Character]()
        if expression.first != "-" {
            sign.append("+")
        }
        for char in expression {
            if char == "+" || char == "-" {
                sign.append(char)
            }
        }
        
        var prevNum = 0, prevDen = 1
        var i = 0
        let fractions = expression.split { $0 == "+" || $0 == "-" }
        for sub in fractions {
            if sub.isEmpty { continue }
            let fraction = sub.split(separator: "/").map { Int($0)! }
            let num = fraction[0]
            let den = fraction[1]
            let g = gcd(prevDen, den)
            if sign[i] == "+" {
                prevNum = prevNum * den / g + num * prevDen / g
            } else {
                prevNum = prevNum * den / g - num * prevDen / g
            }
            prevDen = prevDen * den / g
            let gcdValue = gcd(abs(prevNum), prevDen)
            prevNum /= gcdValue
            prevDen /= gcdValue
            i += 1
        }
        
        return "\(prevNum)/\(prevDen)"
    }
    
    private func gcd(_ a: Int, _ b: Int) -> Int {
        return b == 0 ? a : gcd(b, a % b)
    }
}

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

#medium
Задача: 593. Valid Square

Даны координаты четырех точек в 2D-пространстве p1, p2, p3 и p4. Верните true, если эти четыре точки образуют квадрат.

Координата точки pi представлена как [xi, yi]. Ввод не дан в каком-либо определенном порядке.

Корректный квадрат имеет четыре равные стороны с положительной длиной и четыре равных угла (по 90 градусов).

Пример:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: true

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

1⃣Определите функцию для вычисления расстояния между двумя точками.

2⃣Проверьте, равны ли все стороны и диагонали для трех уникальных случаев перестановки точек.

3⃣Верните true, если хотя бы одна из проверок проходит.

😎 Решение:

class Solution {
    func dist(_ p1: [Int], _ p2: [Int]) -> Int {
        return (p2[1] - p1[1]) * (p2[1] - p1[1]) + (p2[0] - p1[0]) * (p2[0] - p1[0])
    }

    func check(_ p1: [Int], _ p2: [Int], _ p3: [Int], _ p4: [Int]) -> Bool {
        return dist(p1, p2) > 0 &&
               dist(p1, p2) == dist(p2, p3) &&
               dist(p2, p3) == dist(p3, p4) &&
               dist(p3, p4) == dist(p4, p1) &&
               dist(p1, p3) == dist(p2, p4)
    }

    func validSquare(_ p1: [Int], _ p2: [Int], _ p3: [Int], _ p4: [Int]) -> Bool {
        return check(p1, p2, p3, p4) ||
               check(p1, p3, p2, p4) ||
               check(p1, p2, p4, p3)
    }
}

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

#Easy
Задача: 598. Range Addition II

Вам дана матрица M размером m x n, инициализированная нулями, и массив операций ops, где ops[i] = [ai, bi] означает, что значение M[x][y] должно быть увеличено на единицу для всех 0 <= x < ai и 0 <= y < bi.

Подсчитайте и верните количество максимальных чисел в матрице после выполнения всех операций.

Пример:

Input: m = 3, n = 3, ops = [[2,2],[3,3]]
Output: 4
Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4.

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

1⃣Все операции выполняются на прямоугольной подматрице изначальной матрицы M, заполненной нулями, с верхним левым углом в точке (0,0) и нижним правым углом для операции [i,j] в точке (i,j).

2⃣Максимальный элемент будет тем, на который выполнены все операции. Максимальные элементы будут находиться в области пересечения прямоугольников, представляющих операции. Для определения этой области нужно найти нижний правый угол пересекающейся области (x,y), который равен (min(op[0]), min(op[1])).

3⃣Количество элементов, находящихся в области пересечения, определяется как произведение координат x и y.

😎 Решение:

public class Solution {
    func maxCount(_ m: Int, _ n: Int, _ ops: [[Int]]) -> Int {
        var minA = m
        var minB = n
        for op in ops {
            minA = min(minA, op[0])
            minB = min(minB, op[1])
        }
        return minA * minB
    }
}

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

#Easy
Задача: 599. Minimum Index Sum of Two Lists

Даны два массива строк list1 и list2, необходимо найти общие строки с наименьшей суммой индексов.

Общая строка - это строка, которая появляется и в list1, и в list2.

Общая строка с наименьшей суммой индексов - это общая строка, такая, что если она появилась в list1[i] и list2[j], то i + j должно быть минимальным значением среди всех других общих строк.

Верните все общие строки с наименьшей суммой индексов. Верните ответ в любом порядке.

Пример:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".

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

1⃣Для каждой строки из list1, сравниваем её с каждой строкой из list2, обходя весь список list2. Используем хэш-таблицу map, которая содержит элементы в виде (сумма: список строк). Здесь сумма относится к сумме индексов совпадающих элементов, а список строк соответствует списку совпадающих строк, чья сумма индексов равна этой сумме.

2⃣Во время сравнений, когда находится совпадение строки на i-м индексе из list1 и j-м индексе из list2, создаём запись в map, соответствующую сумме i + j, если такая запись ещё не существует. Если запись с этой суммой уже существует, добавляем текущую строку в список строк, соответствующих сумме i + j.

3⃣В конце обходим ключи в map и находим список строк, соответствующих ключу с минимальной суммой.

😎 Решение:

class Solution {
    func findRestaurant(_ list1: [String], _ list2: [String]) -> [String] {
        var map = [Int: [String]]()
        for i in 0..<list1.count {
            for j in 0..<list2.count {
                if list1[i] == list2[j] {
                    if map[i + j] == nil {
                        map[i + j] = [String]()
                    }
                    map[i + j]!.append(list1[i])
                }
            }
        }
        let minIndexSum = map.keys.min()!
        return map[minIndexSum]!
    }
}

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

#easy
Задача: 594. Longest Harmonious Subsequence

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

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

Подпоследовательность массива - это последовательность, которую можно получить из массива, удалив некоторые или никакие элементы, не изменяя порядок оставшихся элементов.

Пример:

Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

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

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

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

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

😎 Решение:

class Solution {
    func findLHS(_ nums: [Int]) -> Int {
        var countDict = [Int: Int]()
        var res = 0
        
        for num in nums {
            countDict[num, default: 0] += 1
            if let countPlusOne = countDict[num + 1] {
                res = max(res, countDict[num]! + countPlusOne)
            }
            if let countMinusOne = countDict[num - 1] {
                res = max(res, countDict[num]! + countMinusOne)
            }
        }
        
        return res
    }
}

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

#Hard
Задача: 600. Non-negative Integers without Consecutive Ones

Дано положительное целое число n, верните количество чисел в диапазоне [0, n], бинарные представления которых не содержат последовательных единиц.

Пример:

Input: n = 5
Output: 5
Explanation:
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 

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

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

2⃣Чтобы проверить, существует ли 1 на позиции x (считая от младшего значащего бита), в текущем числе n, поступаем следующим образом. Сдвигаем двоичную 1 x−1 раз влево, чтобы получить число y, которое имеет 1 только на x-й позиции. Логическое И числа n и y даст результат 1 только если n содержит 1 на позиции x.

3⃣В конце подсчитываем и возвращаем количество чисел в диапазоне [0, n], не содержащих последовательных единиц.

😎 Решение:

class Solution {
    func findIntegers(_ num: Int) -> Int {
        var count = 0
        for i in 0...num {
            if check(i) {
                count += 1
            }
        }
        return count
    }
    
    func check(_ n: Int) -> Bool {
        var i = 31
        while i > 0 {
            if (n & (1 << i)) != 0 && (n & (1 << (i - 1))) != 0 {
                return false
            }
            i -= 1
        }
        return true
    }
}

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

#medium
Задача: 309. Best Time to Buy and Sell Stock with Cooldown

Дан массив prices, где prices[i] — цена данной акции в i-й день.

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

После продажи акции вы не можете покупать акции на следующий день (т. е. необходимо один день подождать).

Пример:

Input: prices = [1]
Output: 0

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

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

2⃣Обновление состояний
Итерируйте по каждому дню, обновляя состояния: hold: максимальная прибыль, если у вас есть акция на текущий день. sold: максимальная прибыль, если вы продаете акцию на текущий день. cooldown: максимальная прибыль, если вы находитесь в периоде ожидания на текущий день.

3⃣Определение максимальной прибыли
В конце итерации максимальная прибыль будет максимальным значением между состояниями sold и cooldown, так как hold состояние не может быть конечным состоянием для получения максимальной прибыли.

😎 Решение:

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        guard !prices.isEmpty else { return 0 }
        
        var hold = -prices[0]
        var sold = 0
        var cooldown = 0
        
        for price in prices.dropFirst() {
            let newHold = max(hold, cooldown - price)
            let newSold = hold + price
            let newCooldown = max(cooldown, sold)
            
            hold = newHold
            sold = newSold
            cooldown = newCooldown
        }
        
        return max(sold, cooldown)
    }
}

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

#medium
Задача: 513. Find Bottom Left Tree Value

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

Пример:

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

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

1⃣Инициализируйте переменную maxDepth для хранения глубины нижнего уровня дерева. Инициализируйте переменную bottomLeftValue для хранения самого левого значения в последней строке дерева.

2⃣Реализуйте рекурсивную функцию dfs, которая обходит дерево и находит самое левое значение в последней строке дерева. Параметры функции: current (текущий узел) и depth (его глубина). Проверьте, пуст ли текущий узел. Если да, то вернитесь.

3⃣Проверьте, превышает ли текущая глубина глобальную переменную maxDepth. Если да, это значит, что мы нашли новый уровень. Установите maxDepth в значение текущей глубины. Установите bottomLeftValue в значение текущего узла. Рекурсивно вызовите dfs для левого поддерева текущего узла, увеличив глубину на один. Рекурсивно вызовите dfs для правого поддерева текущего узла, увеличив глубину на один. Вызовите dfs с корнем и начальной глубиной 0. Верните bottomLeftValue.

😎 Решение:

class Solution {
    var maxDepth = -1
    var bottomLeftValue = 0
    
    func findBottomLeftValue(_ root: TreeNode?) -> Int {
        dfs(root, 0)
        return bottomLeftValue
    }
    
    func dfs(_ current: TreeNode?, _ depth: Int) {
        guard let current = current else { return }
        
        if depth > maxDepth {
            maxDepth = depth
            bottomLeftValue = current.val
        }
        
        dfs(current.left, depth + 1)
        dfs(current.right, depth + 1)
    }
}

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

#easy
Задача: 1287. Element Appearing More Than 25% In Sorted Array

Дан массив целых чисел, отсортированный в неубывающем порядке. В этом массиве есть ровно одно число, которое встречается более чем в 25% случаев. Верните это число.

Пример:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

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

1⃣Инициализируйте хеш-таблицу counts и перебирайте каждый элемент в массиве arr, увеличивая counts[num] для каждого элемента num.

2⃣Установите target = arr.length / 4.

3⃣Перебирайте каждую пару ключ-значение в counts и, если значение > target, верните ключ. Код никогда не достигнет этой точки, так как гарантируется, что ответ существует; верните любое значение.

😎 Решение:

class Solution {
    func findSpecialInteger(_ arr: [Int]) -> Int {
        var counts = [Int: Int]()
        let target = arr.count / 4
        for num in arr {
            counts[num, default: 0] += 1
            if counts[num]! > target {
                return num
            }
        }
        return -1
    }
}

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

#medium
Задача: 1286. Iterator for Combination

Создайте класс 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
    }
}

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

#medium
Задача: 515. Find Largest Value in Each Tree Row

Дан корень двоичного дерева, верните массив наибольших значений в каждой строке дерева (индексация с 0).

Пример:

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

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

1⃣Если корень дерева равен null (пустое дерево), верните пустой список. Инициализируйте список ans для хранения результатов и очередь с корнем дерева для выполнения поиска в ширину (BFS).

2⃣Выполните BFS, пока очередь не пуста: инициализируйте currMax минимальным значением и сохраните длину очереди в currentLength. Повторите currentLength раз: удалите узел из очереди, обновите currMax, если значение узла больше. Для каждого дочернего узла, если он не равен null, добавьте его в очередь.

3⃣Добавьте currMax в ans. Верните ans.

😎 Решение:

class Solution {
    func largestValues(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return [] }
        
        var ans = [Int]()
        var queue = [root]
        
        while !queue.isEmpty {
            var currentLength = queue.count
            var currMax = Int.min
            
            for _ in 0..<currentLength {
                let node = queue.removeFirst()
                currMax = max(currMax, node.val)
                if let left = node.left {
                    queue.append(left)
                }
                if let right = node.right {
                    queue.append(right)
                }
            }
            
            ans.append(currMax)
        }
        
        return ans
    }
}

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

#medium
Задача: 516. Longest Palindromic Subsequence

Дана строка s, найдите длину самой длинной палиндромной подпоследовательности в s.

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

Пример:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

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

1⃣Создайте целочисленную переменную n и инициализируйте её размером строки s. Создайте двумерный массив memo размером n на n, где memo[i][j] содержит длину самой длинной палиндромной подпоследовательности подстроки, сформированной от индекса i до j в s.

2⃣Верните lps(s, 0, n - 1, memo), где lps — это рекурсивный метод с четырьмя параметрами: s, начальный индекс подстроки как i, конечный индекс подстроки как j и memo. Если memo[i][j] != 0, это означает, что мы уже решили эту подзадачу, поэтому возвращаем memo[i][j]. Если i > j, строка пуста, возвращаем 0. Если i == j, это подстрока, содержащая один символ, возвращаем 1.

3⃣Если первый и последний символы совпадают, т.е. s[i] == s[j], включаем эти два символа в палиндромную подпоследовательность и добавляем её к самой длинной палиндромной подпоследовательности, сформированной с использованием подстроки от индекса i + 1 до j - 1. Выполняем memo[i][j] = lps(s, i + 1, j - 1, memo) + 2. Если первый и последний символы не совпадают, рекурсивно ищем самую длинную палиндромную подпоследовательность в обеих подстроках, сформированных после игнорирования первого и последнего символов. Выбираем максимум из этих двух и выполняем memo[i][j] = max(lps(s, i + 1, j, memo), lps(s, i, j - 1, memo)). Возвращаем memo[i][j].

😎 Решение:

class Solution {
    func longestPalindromeSubseq(_ s: String) -> Int {
        let n = s.count
        var memo = [[Int]: Int]()
        
        func lps(_ l: Int, _ r: Int) -> Int {
            if let res = memo[[l, r]] {
                return res
            }
            if l > r {
                return 0
            }
            if l == r {
                return 1
            }
            
            let start = s.index(s.startIndex, offsetBy: l)
            let end = s.index(s.startIndex, offsetBy: r)
            
            if s[start] == s[end] {
                memo[[l, r]] = lps(l + 1, r - 1) + 2
            } else {
                memo[[l, r]] = max(lps(l, r - 1), lps(l + 1, r))
            }
            return memo[[l, r]]!
        }
        
        return lps(0, n - 1)
    }
}

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

#hard
Задача: 517. Super Washing Machines

У вас есть n супер стиральных машин, расположенных в одну линию. Изначально каждая стиральная машина содержит некоторое количество платьев или пуста.

За один ход вы можете выбрать любые m (1 <= m <= n) стиральные машины и одновременно передать одно платье из каждой выбранной машины в одну из её соседних стиральных машин.

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

Пример:

Input: machines = [1,0,5]
Output: 3
Explanation:
1st move:    1     0 <-- 5    =>    1     1     4
2nd move:    1 <-- 1 <-- 4    =>    2     1     3
3rd move:    2     1 <-- 3    =>    2     2     2

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

1⃣Проверьте, можно ли решить задачу: длина массива machines должна быть делителем суммы элементов массива machines. Если нет, верните -1. Вычислите количество платьев, которое должно быть в каждой машине: dresses_per_machine = sum(machines) / len(machines). Нормализуйте задачу, заменив количество платьев в каждой машине на количество платьев, которые нужно удалить из этой машины (может быть отрицательное значение).

2⃣Инициализируйте переменные curr_sum, max_sum и res нулем. Итеративно пройдитесь по всем машинам m в массиве machines, обновляя curr_sum и max_sum на каждом шагу: curr_sum += m, max_sum = max(max_sum, abs(curr_sum)).

3⃣Обновляйте результат res на каждом шагу: res = max(res, max_sum, m). Верните res.

😎 Решение:

class Solution {
    func findMinMoves(_ machines: [Int]) -> Int {
        let n = machines.count
        let dressTotal = machines.reduce(0, +)
        if dressTotal % n != 0 { return -1 }

        let dressPerMachine = dressTotal / n
        var machines = machines.map { $0 - dressPerMachine }

        var currSum = 0
        var maxSum = 0
        var res = 0

        for m in machines {
            currSum += m
            maxSum = max(maxSum, abs(currSum))
            res = max(res, max(maxSum, m))
        }
        return res
    }
}

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