#medium
Задача: 640. Solve the Equation

Решите заданное уравнение и верните значение 'x' в виде строки "x=#value". Уравнение содержит только операции '+', '-', переменную 'x' и ее коэффициент. Вы должны вернуть "No solution", если для уравнения нет решения, или "Infinite solutions", если для уравнения существует бесконечное количество решений. Если для уравнения существует ровно одно решение, мы убеждаемся, что значение 'x' является целым числом.

Пример:

Input: s = "*"
Output: 9

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

1⃣Разделение уравнения: Разделите уравнение на левую и правую части относительно знака равенства '='.

2⃣Парсинг и упрощение: Пройдитесь по каждой части уравнения, упрощая ее до суммы коэффициентов 'x' и числовых значений.

3⃣Решение уравнения: Используйте уравнение вида ax + b = cx + d, чтобы решить для 'x'. Если коэффициенты 'x' равны и числовые значения равны, уравнение имеет бесконечное количество решений. Если коэффициенты 'x' равны, но числовые значения различны, решения нет. В противном случае вычислите значение 'x'.

😎 Решение:

class Solution {
    func solveEquation(_ equation: String) -> String {
        func parse(_ s: String) -> (Int, Int) {
            var coeff = 0
            var constPart = 0
            var sign = 1
            var num = 0
            var i = s.startIndex
            
            while i < s.endIndex {
                if s[i] == "+" {
                    sign = 1
                    i = s.index(after: i)
                } else if s[i] == "-" {
                    sign = -1
                    i = s.index(after: i)
                } else if s[i].isNumber {
                    num = 0
                    while i < s.endIndex && s[i].isNumber {
                        num = num * 10 + s[i].wholeNumberValue!
                        i = s.index(after: i)
                    }
                    if i < s.endIndex && s[i] == "x" {
                        coeff += sign * num
                        i = s.index(after: i)
                    } else {
                        constPart += sign * num
                    }
                } else if s[i] == "x" {
                    coeff += sign
                    i = s.index(after: i)
                }
            }
            return (coeff, constPart)
        }
        
        let parts = equation.split(separator: "=")
        let (leftCoeff, leftConst) = parse(String(parts[0]))
        let (rightCoeff, rightConst) = parse(String(parts[1]))
        
        let coeff = leftCoeff - rightCoeff
        let constPart = rightConst - leftConst
        
        if coeff == 0 {
            return constPart == 0 ? "Infinite solutions" : "No solution"
        }
        return "x=\(constPart / coeff)"
    }
}

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

#easy
Задача: 566. Reshape the Matrix

В MATLAB есть удобная функция под названием reshape, которая может преобразовать матрицу размером m x n в новую матрицу с другим размером r x c, сохраняя исходные данные.

Вам дана матрица m x n mat и два целых числа r и c, представляющие количество строк и столбцов желаемой преобразованной матрицы.

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

Если операция преобразования с заданными параметрами возможна и допустима, выведите новую преобразованную матрицу; в противном случае выведите исходную матрицу.

Пример:

Input: mat = [[1,2],[3,4]], r = 1, c = 4
Output: [[1,2,3,4]]

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

1⃣Проверить, можно ли преобразовать матрицу с заданными параметрами r и c. Это возможно, если произведение m * n равно произведению r * c. Если преобразование невозможно, вернуть исходную матрицу.

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

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

😎 Решение:

class Solution {
    func matrixReshape(_ mat: [[Int]], _ r: Int, _ c: Int) -> [[Int]] {
        let m = mat.count
        let n = mat[0].count
        if m * n != r * c {
            return mat
        }
        var reshapedMatrix = Array(repeating: Array(repeating: 0, count: c), count: r)
        var row = 0
        var col = 0
        for i in 0..<m {
            for j in 0..<n {
                reshapedMatrix[row][col] = mat[i][j]
                col += 1
                if col == c {
                    col = 0
                    row += 1
                }
            }
        }
        return reshapedMatrix
    }
}

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

#medium
Задача: 567. Permutation in String

Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае.

Другими словами, верните true, если одна из перестановок s1 является подстрокой s2.

Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

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

1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2.
2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1.
3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false.

😎 Решение:

class Solution {
    func checkInclusion(_ s1: String, _ s2: String) -> Bool {
        let s1Len = s1.count, s2Len = s2.count
        if s1Len > s2Len { return false }
        
        let s1Arr = Array(s1), s2Arr = Array(s2)
        var s1Count = [Int](repeating: 0, count: 26)
        var s2Count = [Int](repeating: 0, count: 26)
        
        for i in 0..<s1Len {
            s1Count[Int(s1Arr[i].asciiValue! - Character("a").asciiValue!)] += 1
            s2Count[Int(s2Arr[i].asciiValue! - Character("a").asciiValue!)] += 1
        }
        
        for i in 0..<(s2Len - s1Len) {
            if s1Count == s2Count { return true }
            s2Count[Int(s2Arr[i].asciiValue! - Character("a").asciiValue!)] -= 1
            s2Count[Int(s2Arr[i + s1Len].asciiValue! - Character("a").asciiValue!)] += 1
        }
        
        return s1Count == s2Count
    }
}

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

#medium
Задача: 641. Design Circular Deque

Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае.

Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

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

1⃣Инициализация и проверка состояний: Реализуйте конструктор для инициализации кольцевой двусторонней очереди заданного размера и методы для проверки пустоты и полноты очереди.
2⃣Операции вставки: Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры.
3⃣Операции удаления: Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди.

😎 Решение:

class MyCircularDeque {
    private var deque: [Int]
    private var front: Int
    private var rear: Int
    private var size: Int
    private var capacity: Int

    init(_ k: Int) {
        self.capacity = k
        self.deque = [Int](repeating: 0, count: k)
        self.front = 0
        self.rear = 0
        self.size = 0
    }

    func insertFront(_ value: Int) -> Bool {
        if isFull() {
            return false
        }
        front = (front - 1 + capacity) % capacity
        deque[front] = value
        size += 1
        return true
    }

    func insertLast(_ value: Int) -> Bool {
        if isFull() {
            return false
        }
        deque[rear] = value
        rear = (rear + 1) % capacity
        size += 1
        return true
    }

    func deleteFront() -> Bool {
        if isEmpty() {
            return false
        }
        front = (front + 1) % capacity
        size -= 1
        return true
    }

    func deleteLast() -> Bool {
        if isEmpty() {
            return false
        }
        rear = (rear - 1 + capacity) % capacity
        size -= 1
        return true
    }

    func getFront() -> Int {
        if isEmpty() {
            return -1
        }
        return deque[front]
    }

    func getRear() -> Int {
        if isEmpty() {
            return -1
        }
        return deque[(rear - 1 + capacity) % capacity]
    }

    func isEmpty() -> Bool {
        return size == 0
    }

    func isFull() -> Bool {
        return size == capacity
    }
}

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

#hard
Задача: 568. Maximum Vacation Days

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

Правила и ограничения:
Вы можете путешествовать только между n городами, обозначенными индексами от 0 до n-1. Изначально вы находитесь в городе с индексом 0 в понедельник.
Города связаны рейсами. Рейсы представлены матрицей n x n, называемой flights, представляющей статус авиалинии от города i до города j. Если рейса из города i в город j нет, flights[i][j] == 0; иначе flights[i][j] == 1. Также для всех i выполняется flights[i][i] == 0.
У вас есть k недель (каждая неделя состоит из семи дней) для путешествий. Вы можете летать не более одного раза в день и можете летать только утром каждого понедельника. Время полета настолько короткое, что его влияние не учитывается.
Для каждого города у вас есть ограниченные дни отпуска в разные недели, заданные матрицей n x k, называемой days. Значение days[i][j] представляет максимальное количество дней отпуска, которые вы можете взять в городе i на неделе j.
Вы можете оставаться в городе большее количество дней, чем количество дней отпуска, но вы должны работать в дополнительные дни, которые не будут учитываться как дни отпуска.
Даны две матрицы flights и days, верните максимальное количество дней отпуска, которые вы можете взять в течение k недель.

Пример:

Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation:
One of the best strategies is:
1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day.
(Although you start at city 0, we could also fly to and start at other cities since it is Monday.)
2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
3rd week : stay at city 2, and play 3 days and work 4 days.
Ans = 6 + 3 + 3 = 12.

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

1⃣Использовать функцию dfs (поиск в глубину), которая возвращает количество отпускных дней, которые можно взять, начиная с текущего города cur_city и текущей недели weekno. В каждом вызове функции проходить по всем городам и находить все города, которые связаны с текущим городом. Такой город обозначен 1 в соответствующей позиции flights[cur_city][i].

2⃣Для текущего города можно либо остаться в нем, либо поехать в связанный город. Обозначим город, в который меняется расположение, как j. После смены города нужно найти количество отпускных дней, которые можно взять, начиная с нового города и с новой недели. Это количество отпускных дней можно представить как: days[j][weekno] + dfs(flights, days, j, weekno + 1).

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

😎 Решение:

class Solution {
    func maxVacationDays(_ flights: [[Int]], _ days: [[Int]]) -> Int {
        let n = flights.count
        let k = days[0].count
        var memo = Array(repeating: Array(repeating: -1, count: k), count: n)
        
        func dfs(_ cur_city: Int, _ weekno: Int) -> Int {
            if weekno == k {
                return 0
            }
            if memo[cur_city][weekno] != -1 {
                return memo[cur_city][weekno]
            }
            var max_vac = 0
            for next_city in 0..<n {
                if cur_city == next_city || flights[cur_city][next_city] == 1 {
                    max_vac = max(max_vac, days[next_city][weekno] + dfs(next_city, weekno + 1))
                }
            }
            memo[cur_city][weekno] = max_vac
            return max_vac
        }
        
        return dfs(0, 0)
    }
}

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

#hard
Задача: 642. Design Search Autocomplete System

Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае.

Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

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

1⃣Инициализация и проверка состояний: Реализуйте конструктор для инициализации кольцевой двусторонней очереди заданного размера и методы для проверки пустоты и полноты очереди.
2⃣Операции вставки: Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры.
3⃣Операции удаления: Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди.

😎 Решение:

class TrieNode {
    var children = [Character: TrieNode]()
    var count = [String: Int]()
}

class AutocompleteSystem {
    private var root = TrieNode()
    private var prefix = ""

    init(_ sentences: [String], _ times: [Int]) {
        for i in 0..<sentences.count {
            add(sentences[i], times[i])
        }
    }

    private func add(_ sentence: String, _ count: Int) {
        var node = root
        for char in sentence {
            if node.children[char] == nil {
                node.children[char] = TrieNode()
            }
            node = node.children[char]!
            node.count[sentence, default: 0] += count
        }
    }

    func input(_ c: Character) -> [String] {
        if c == "#" {
            add(prefix, 1)
            prefix = ""
            return []
        }

        prefix.append(c)
        var node = root
        for char in prefix {
            if node.children[char] == nil {
                return []
            }
            node = node.children[char]!
        }

        let pq = node.count.sorted { lhs, rhs in
            if lhs.value == rhs.value {
                return lhs.key < rhs.key
            }
            return lhs.value > rhs.value
        }

        return Array(pq.prefix(3)).map { $0.key }
    }
}

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

#easy
Задача: 643. Maximum Average Subarray I

Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.

Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000

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

1⃣Инициализация скользящего окна: Вычислите сумму первых k элементов массива nums. Это будет начальное значение максимальной суммы.
2⃣Перемещение окна: Перемещайте окно длиной k по массиву, добавляя следующий элемент и убирая предыдущий, чтобы поддерживать сумму текущего окна.
3⃣Обновление максимальной суммы: На каждом шаге обновляйте максимальную сумму, если текущая сумма больше, и в конце верните среднее значение этой суммы.

😎 Решение:

class Solution {
    func findMaxAverage(_ nums: [Int], _ k: Int) -> Double {
        var currentSum = nums.prefix(k).reduce(0, +)
        var maxSum = currentSum
        
        for i in k..<nums.count {
            currentSum += nums[i] - nums[i - k]
            maxSum = max(maxSum, currentSum)
        }
        
        return Double(maxSum) / Double(k)
    }
}

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

#hard
Задача: 644. Maximum Average Subarray II

Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого больше или равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.

Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000

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

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

😎 Решение:

func findMaxAverage(_ nums: [Int], _ k: Int) -> Double {
    var currSum = nums[0..<k].reduce(0, +)
    var maxSum = currSum
    for i in k..<nums.count {
        currSum += nums[i] - nums[i - k]
        if currSum > maxSum {
            maxSum = currSum
        }
    }
    return Double(maxSum) / Double(k)
}

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

#easy
Задача: 645. Set Mismatch

У вас есть набор целых чисел s, который изначально содержит все числа от 1 до n. К сожалению, из-за какой-то ошибки одно из чисел в s продублировалось в другое число в наборе, что привело к повторению одного числа и потере другого. Вам дан целочисленный массив nums, представляющий состояние данных в этом наборе после ошибки. Найдите число, которое встречается дважды, и число, которое отсутствует, и верните их в виде массива.

Пример:

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

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

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

😎 Решение:

func findErrorNums(_ nums: [Int]) -> [Int] {
    var numSet = Set<Int>()
    var duplicate = -1
    let n = nums.count
    for num in nums {
        if numSet.contains(num) {
            duplicate = num
        }
        numSet.insert(num)
    }
    let missing = (n * (n + 1)) / 2 - numSet.reduce(0, +)
    return [duplicate, missing]
}

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

#hard
Задача: 656. Coin Path

Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y.

Пример:

Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]

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

1⃣Используйте динамическое программирование для нахождения минимальной стоимости до каждого индекса, начиная с первого.
2⃣Храните путь до каждого индекса для отслеживания наименьшего лексикографического пути.
3⃣Используя полученную информацию, восстановите путь с минимальной стоимостью до последнего индекса.

😎 Решение:

import Foundation

func minCostPath(_ coins: [Int], _ maxJump: Int) -> [Int] {
    let n = coins.count
    if coins[0] == -1 { return [] }
    
    var dp = [Int](repeating: Int.max, count: n)
    dp[0] = coins[0]
    var path = Array(repeating: [Int](), count: n)
    path[0] = [1]
    
    var heap = [(cost: Int, index: Int)]()
    heap.append((coins[0], 0))
    
    while !heap.isEmpty {
        heap.sort(by: { $0.cost < $1.cost })
        let (current_cost, i) = heap.removeFirst()
        if current_cost > dp[i] { continue }
        for k in 1...maxJump {
            if i + k < n && coins[i + k] != -1 {
                let new_cost = current_cost + coins[i + k]
                if new_cost < dp[i + k] || (new_cost == dp[i + k] && path[i] + [i + k + 1] < path[i + k]) {
                    dp[i + k] = new_cost
                    path[i + k] = path[i] + [i + k + 1]
                    heap.append((new_cost, i + k))
                }
            }
        }
    }
    
    return dp[n - 1] == Int.max ? [] : path[n - 1]
}

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

#medium
Задача: 655. Print Binary Tree

Учитывая корень двоичного дерева, постройте строковую матрицу res с индексом 0 размером m x n, которая представляет собой форматированную раскладку дерева. Форматированная матрица должна быть построена по следующим правилам: высота дерева равна height, количество строк m должно быть равно height + 1. Количество столбцов n должно быть равно 2height+1 - 1. Поместите корневой узел в середину верхней строки (более формально, в позицию res[0][(n-1)/2]).
Для каждого узла, который был помещен в матрицу в позицию res[r][c], поместите его левого ребенка в res[r+1][c-2height-r-1], а правого - в res[r+1][c+2height-r-1]. Продолжайте этот процесс, пока не будут размещены все узлы дерева. Любые пустые ячейки должны содержать пустую строку "". Верните построенную матрицу res.

Пример:

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

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

1⃣Найдите высоту дерева и определите размер матрицы (m x n).

2⃣Рекурсивно разместите узлы в матрице, начиная с корневого узла.

3⃣Верните заполненную матрицу.

😎 Решение:

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

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

func fill(_ res: inout [[String]], _ root: TreeNode?, _ r: Int, _ c: Int, _ height: Int) {
    guard let root = root else { return }
    res[r][c] = String(root.val)
    if let left = root.left {
        fill(&res, left, r + 1, c - (1 << (height - r - 1)), height)
    }
    if let right = root.right {
        fill(&res, right, r + 1, c + (1 << (height - r - 1)), height)
    }
}

func printTree(_ root: TreeNode?) -> [[String]] {
    let height = findHeight(root)
    let m = height + 1
    let n = (1 << (height + 1)) - 1
    var res = Array(repeating: Array(repeating: "", count: n), count: m)
    fill(&res, root, 0, (n - 1) / 2, height)
    return res
}

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

#medium
Задача: 654. Maximum Binary Tree

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

Пример:

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

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

1⃣Найдите максимальное значение в текущем подмассиве и создайте узел с этим значением.

2⃣Рекурсивно постройте левое поддерево для подмассива слева от максимального значения.

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

😎 Решение:

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

func constructMaximumBinaryTree(_ nums: [Int]) -> TreeNode? {
    guard !nums.isEmpty else { return nil }
    let maxIndex = nums.firstIndex(of: nums.max()!)!
    let root = TreeNode(nums[maxIndex])
    root.left = constructMaximumBinaryTree(Array(nums[..<maxIndex]))
    root.right = constructMaximumBinaryTree(Array(nums[(maxIndex + 1)...]))
    return root
}

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

#easy
Задача: 653. Two Sum IV - Input is a BST

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

Пример:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

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

1⃣Выполните обход BST и сохраните все значения узлов в набор.

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

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

😎 Решение:

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

func findTarget(_ root: TreeNode?, _ k: Int) -> Bool {
    var seen = Set<Int>()
    func find(_ node: TreeNode?) -> Bool {
        guard let node = node else { return false }
        if seen.contains(k - node.val) {
            return true
        }
        seen.insert(node.val)
        return find(node.left) || find(node.right)
    }
    return find(root)
}

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

#medium
Задача: 652. Find Duplicate Subtrees

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

Пример:

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

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

1⃣Выполните обход дерева и используйте сериализацию для представления каждого поддерева.

2⃣Храните все сериализованные представления поддеревьев в хэш-таблице и отслеживайте частоту их появления.

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

😎 Решение:

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

func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {
    var count = [String: Int]()
    var result = [TreeNode?]()
    
    @discardableResult
    func serialize(_ node: TreeNode?) -> String {
        guard let node = node else { return "#" }
        let serial = "\(node.val),\(serialize(node.left)),\(serialize(node.right))"
        count[serial, default: 0] += 1
        if count[serial] == 2 {
            result.append(node)
        }
        return serial
    }
    
    serialize(root)
    return result
}

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

#medium
Задача: 651. 4 Keys Keyboard

Представьте, что у вас есть специальная клавиатура со следующими клавишами: A: Напечатать одну букву "A" на экране. Ctrl-A: Выделить весь экран. Ctrl-C: Скопировать выделение в буфер. Ctrl-V: Печать буфера на экране с добавлением его после того, что уже было напечатано. Учитывая целое число n, верните максимальное количество букв 'A', которые можно напечатать на экране при нажатии не более n клавиш.

Пример:

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

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

1⃣Используйте динамическое программирование для отслеживания максимального количества букв 'A' на экране после каждого числа нажатий клавиш.

2⃣Итерируйтесь от 1 до n, вычисляя максимальное количество 'A' для каждой позиции, учитывая возможность вставки скопированного текста.

3⃣Возвращайте значение из таблицы динамического программирования для n нажатий клавиш.

😎 Решение:

func maxA(_ n: Int) -> Int {
    var dp = [Int](repeating: 0, count: n + 1)
    for i in 1...n {
        dp[i] = dp[i - 1] + 1
        for j in 2..<i {
            dp[i] = max(dp[i], dp[j - 2] * (i - j + 1))
        }
    }
    return dp[n]
}

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

#medium
Задача: 650. 2 Keys Keyboard

На экране блокнота есть только один символ 'A'. Для каждого шага можно выполнить одну из двух операций над этим блокнотом: Copy All: скопировать все символы, присутствующие на экране (частичное копирование не допускается). Paste: Вы можете вставить символы, которые были скопированы в прошлый раз. Учитывая целое число n, верните минимальное количество операций, чтобы символ 'A' появился на экране ровно n раз.

Пример:

Input: n = 3
Output: 3

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

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

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

3⃣Возвращайте значение из таблицы динамического программирования для n.

😎 Решение:

func minSteps(_ n: Int) -> Int {
    if n == 1 { return 0 }
    var dp = [Int](repeating: 0, count: n + 1)
    for i in 2...n {
        dp[i] = i
        for j in 1...(i / 2) {
            if i % j == 0 {
                dp[i] = min(dp[i], dp[j] + i / j)
            }
        }
    }
    return dp[n]
}

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

#medium
Задача: 649. Dota2 Senate

В мире Dota2 есть две партии: Radiant и Dire. Сенат Dota2 состоит из сенаторов, представляющих две партии. Теперь сенат хочет принять решение об изменении игры Dota2. Голосование за это изменение проходит в несколько раундов. В каждом раунде каждый сенатор может воспользоваться одним из двух прав: Запретить право одного сенатора: Сенатор может заставить другого сенатора потерять все свои права в этом и всех последующих раундах. Объявить о победе: Если этот сенатор обнаружил, что все сенаторы, у которых еще есть право голоса, принадлежат к одной партии, он может объявить о победе и принять решение об изменении игры. Дана строка senate, представляющая партийную принадлежность каждого сенатора. Символы "R" и "D" обозначают партию Лучезарных и партию Ужасных. Если сенаторов n, то размер данной строки будет равен n. Процедура голосования по кругу начинается от первого сенатора к последнему в заданном порядке. Эта процедура длится до конца голосования. Все сенаторы, потерявшие свои права, будут пропущены во время процедуры. Предположим, что каждый сенатор достаточно умен и будет играть по лучшей стратегии для своей партии. Предскажите, какая партия в итоге объявит о победе и изменит игру в Dota2. На выходе должно получиться "Radiant" или "Dire".

Пример:

Input: senate = "RD"
Output: "Radiant"

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

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

2⃣Выполните цикл, пока обе очереди не станут пустыми: Сравните индексы первых сенаторов из обеих очередей. Удалите сенатора с меньшим индексом из очереди и добавьте его с индексом, увеличенным на длину строки. Удалите сенатора с большим индексом из очереди.

3⃣Если одна из очередей опустела, объявите победу партии, чья очередь еще содержит сенаторов.

😎 Решение:

func predictPartyVictory(_ senate: String) -> String {
    var radiant = [Int]()
    var dire = [Int]()
    
    for (i, s) in senate.enumerated() {
        if s == "R" {
            radiant.append(i)
        } else {
            dire.append(i)
        }
    }
    
    while !radiant.isEmpty && !dire.isEmpty {
        let r = radiant.removeFirst()
        let d = dire.removeFirst()
        if r < d {
            radiant.append(r + senate.count)
        } else {
            dire.append(d + senate.count)
        }
    }
    
    return radiant.isEmpty ? "Dire" : "Radiant"
}

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

#medium
Задача: 648. Replace Words

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

Пример:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

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

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

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

3⃣Замените слово найденным корнем и соберите обновленное предложение.

😎 Решение:

func replaceWords(_ roots: [String], _ sentence: String) -> String {
    let rootSet = Set(roots)
    
    func replace(_ word: String) -> String {
        for i in 1...word.count {
            let prefix = String(word.prefix(i))
            if rootSet.contains(prefix) {
                return prefix
            }
        }
        return word
    }
    
    return sentence.split(separator: " ").map { replace(String($0)) }.joined(separator: " ")
}

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

#medium
Задача: 647. Palindromic Substrings

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

Пример:

Input: s = "abc"
Output: 3

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

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

2⃣Для каждой позиции в строке используйте два метода расширения: один для палиндромов нечетной длины и один для палиндромов четной длины.

3⃣Расширяйте от центра, проверяя, является ли подстрока палиндромом, и увеличивайте счетчик, если условие выполняется.

😎 Решение:

func countSubstrings(_ s: String) -> Int {
    let sArray = Array(s)
    var totalCount = 0
    
    func expandAroundCenter(_ left: Int, _ right: Int) -> Int {
        var left = left
        var right = right
        var count = 0
        while left >= 0 && right < sArray.count && sArray[left] == sArray[right] {
            count += 1
            left -= 1
            right += 1
        }
        return count
    }
    
    for i in 0..<sArray.count {
        totalCount += expandAroundCenter(i, i)
        totalCount += expandAroundCenter(i, i + 1)
    }
    return totalCount
}

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

#medium
Задача: 677. Map Sum Pairs

Создайте карту, которая позволяет выполнять следующие действия:

Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:

MapSum() Инициализирует объект MapSum.
void insert(String key, int val) Вставляет пару ключ-значение в карту. Если ключ уже существовал, исходная пара ключ-значение будет заменена на новую.
int sum(string prefix) Возвращает сумму всех значений пар, у которых ключ начинается с данного префикса.

Пример:

Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]

Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

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

1⃣Для каждого ключа в карте проверить, начинается ли этот ключ с данного префикса.

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

3⃣Вернуть полученную сумму как результат.

😎 Решение:

class MapSum {
    private var mapData: [String: Int]

    init() {
        self.mapData = [:]
    }

    func insert(_ key: String, _ val: Int) {
        mapData[key] = val
    }

    func sum(_ prefix: String) -> Int {
        var ans = 0
        for (key, val) in mapData {
            if key.hasPrefix(prefix) {
                ans += val
            }
        }
        return ans
    }
}

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

#medium
Задача: 678. Valid Parenthesis String

Создайте карту, которая позволяет выполнять следующие действия:

Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:

Дана строка s, содержащая только три типа символов: '(', ')' и '*'. Вернуть true, если s является допустимой.

Следующие правила определяют допустимую строку:

Любая открывающая скобка '(' должна иметь соответствующую закрывающую скобку ')'.
Любая закрывающая скобка ')' должна иметь соответствующую открывающую скобку '('.
Открывающая скобка '(' должна идти перед соответствующей закрывающей скобкой ')'.
'*' может рассматриваться как одна закрывающая скобка ')', одна открывающая скобка '(' или пустая строка "".

Пример:

Input: s = "()"
Output: true
Example 2:

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

1⃣Инициализировать 2D вектор memo размером s.size() x s.size() - 1, представляющий неинициализированное состояние. Вызвать вспомогательную функцию isValidString с начальными параметрами index = 0, openCount = 0 и строкой s. Вернуть результат isValidString.

2⃣Вспомогательная функция isValidString. Базовый случай: если index достиг конца строки (index == s.size.), вернуть true, если openCount равен 0 (все скобки сбалансированы), и false в противном случае. Проверить, был ли результат для текущего index и openCount уже вычислен (мемоизирован) в memo. Если да, вернуть мемоизированный результат. Инициализировать isValid как false. Если текущий символ s[index] равен '*': Попробовать трактовать '*' как '(' и вызвать isValidString рекурсивно с index + 1 и openCount + 1. Если рекурсивный вызов вернет true, обновить isValid на true. Если openCount не равен нулю, попробовать трактовать '*' как ')' и вызвать isValidString рекурсивно с index + 1 и openCount - 1. Если рекурсивный вызов вернет true, обновить isValid на true. Попробовать трактовать '*' как пустой символ и вызвать isValidString рекурсивно с index + 1 и тем же openCount. Если рекурсивный вызов вернет true, обновить isValid на true.

3⃣Продолжение функции isValidString. Если текущий символ s[index] равен '(': Вызвать isValidString рекурсивно с index + 1 и openCount + 1. Обновить isValid с результатом рекурсивного вызова. Если текущий символ s[index] равен ')': Если openCount не равен нулю (есть открытые скобки), вызвать isValidString рекурсивно с index + 1 и openCount - 1. Обновить isValid с результатом рекурсивного вызова. Мемоизировать результат isValid в memo[index][openCount]. Вернуть isValid.

😎 Решение:

class Solution {
    func checkValidString(_ s: String) -> Bool {
        var memo = Array(repeating: Array(repeating: -1, count: s.count), count: s.count)
        return isValidString(0, 0, s, &memo)
    }
    
    private func isValidString(_ index: Int, _ openCount: Int, _ str: String, _ memo: inout [[Int]]) -> Bool {
        if index == str.count {
            return openCount == 0
        }
        
        if memo[index][openCount] != -1 {
            return memo[index][openCount] == 1
        }
        
        var isValid = false
        let currentIndex = str.index(str.startIndex, offsetBy: index)
        
        if str[currentIndex] == "*" {
            isValid = isValidString(index + 1, openCount + 1, str, &memo)
            if openCount > 0 {
                isValid = isValid || isValidString(index + 1, openCount - 1, str, &memo)
            }
            isValid = isValid || isValidString(index + 1, openCount, str, &memo)
        } else if str[currentIndex] == "(" {
            isValid = isValidString(index + 1, openCount + 1, str, &memo)
        } else if openCount > 0 {
            isValid = isValidString(index + 1, openCount - 1, str, &memo)
        }
        
        memo[index][openCount] = isValid ? 1 : 0
        return isValid
    }
}

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