Задача: 670. Maximum Swap
Сложность: medium

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

Верните число с наибольшим значением, которое можно получить.

Пример:

Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

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

1⃣Сохраняем кандидатов как списки длины len(num). Для каждой пары позиций (i, j) выполняем обмен цифр, записываем кандидата, если он больше текущего ответа, затем возвращаем цифры обратно.

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

3⃣Возвращаем максимальное значение из всех кандидатов.

😎 Решение:

class Solution {
    func maximumSwap(_ num: Int) -> Int {
        var A = Array(String(num))
        var ans = A
        for i in 0..<A.count {
            for j in i+1..<A.count {
                A.swapAt(i, j)
                for k in 0..<A.count {
                    if A[k] != ans[k] {
                        if A[k] > ans[k] {
                            ans = A
                        }
                        break
                    }
                }
                A.swapAt(i, j)
            }
        }
        return Int(String(ans)) ?? num
    }
}

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

Задача: 867. Transpose Matrix
Сложность: easy

Дан двумерный целочисленный массив matrix, верните его транспонированную матрицу.

Транспонированная матрица — это матрица, перевернутая относительно своей главной диагонали, при этом строки и столбцы меняются местами.

Пример:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]

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

1⃣Инициализируйте новую матрицу ans с размерами C x R, где C — количество столбцов в исходной матрице, а R — количество строк.

2⃣Скопируйте каждую запись исходной матрицы в новую матрицу так, чтобы ans[c][r] = matrix[r][c].

3⃣Верните матрицу ans.

😎 Решение:

class Solution {
    func transpose(_ A: [[Int]]) -> [[Int]] {
        let R = A.count, C = A[0].count
        var ans = Array(repeating: Array(repeating: 0, count: R), count: C)
        for r in 0..<R {
            for c in 0..<C {
                ans[c][r] = A[r][c]
            }
        }
        return ans
    }
}

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

Задача: 402. Remove K Digits
Сложность: medium

Если задана строка num, представляющая неотрицательное целое число num, и целое число k, верните наименьшее возможное целое число после удаления k цифр из num.

Пример:

Input: num = "1432219", k = 3
Output: "1219"

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

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

2⃣Обработка каждой цифры
Перебирайте каждую цифру в строке num.
Если текущая цифра меньше верхней цифры в стеке и у вас есть еще возможность удалить цифры (k > 0), удалите верхнюю цифру из стека.
Добавьте текущую цифру в стек.
Удаление оставшихся цифр:
Если после прохождения всей строки k еще больше нуля, удалите оставшиеся цифры из конца стека

3⃣Формирование результата
Постройте итоговое число из цифр в стеке и удалите ведущие нули.

😎 Решение:

class Solution {
    func removeKdigits(_ num: String, _ k: Int) -> String {
        var stack = [Character]()
        var k = k
        for digit in num {
            while k > 0 && !stack.isEmpty && stack.last! > digit {
                stack.removeLast()
                k -= 1
            }
            stack.append(digit)
        }
        stack = Array(stack[0..<stack.count-k])
        let result = String(stack).trimmingCharacters(in: CharacterSet(charactersIn: "0"))
        return result.isEmpty ? "0" : result
    }
}

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

Задача: 191. Number of 1 Bits
Сложность: easy

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

Пример:

Input: n = 11

Output: 3

Explanation:

The input binary string 1011 has a total of three set bits.

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

1⃣Решение простое: проверяем каждый из 32 битов числа. Если бит равен 1, увеличиваем количество 1-битов на единицу.

2⃣Для проверки i-го бита числа используем битовую маску. Начинаем с маски m=1, так как двоичное представление 1 это 0000 0000 0000 0000 0000 0000 0000 0001. Логическое И между любым числом и маской 1 дает нам младший бит этого числа.

3⃣Для проверки следующего бита сдвигаем маску влево на один:
0000 0000 0000 0000 0000 0000 0000 0010 и так далее.

😎 Решение:

public func hammingWeight(_ n: Int) -> Int {
    var bits = 0
    var mask = 1
    for _ in 0..<32 {
        if (n & mask) != 0 {
            bits += 1
        }
        mask <<= 1
    }
    return bits
}

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

Задача: 1119. Remove Vowels from a String
Сложность: easy

Дана строка s, удалите из нее гласные 'a', 'e', 'i', 'o' и 'u' и верните новую строку.

Пример:

Input: s = "leetcodeisacommunityforcoders"
Output: "ltcdscmmntyfrcdrs"

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

1⃣Создайте метод isVowel(), который возвращает true, если переданный символ является одной из гласных [a, e, i, o, u], и false в противном случае.

2⃣Инициализируйте пустую строку ans.

3⃣Пройдитесь по каждому символу в строке s, и для каждого символа c проверьте, является ли он гласной, используя isVowel(c). Если нет, добавьте символ в строку ans. В конце верните строку ans.

😎 Решение:

class Solution {
    func removeVowels(_ s: String) -> String {
        var ans = ""
        for char in s {
            if !isVowel(char) {
                ans.append(char)
            }
        }
        return ans
    }
    
    private func isVowel(_ c: Character) -> Bool {
        return "aeiou".contains(c)
    }
}

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

Задача: 726. Number of Atoms
Сложность: hard

Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество элементов. Например, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. Например, "H2O2He3Mg4" также является формулой.
Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. Например, "(H2O2)" и "(H2O2)3" являются формулами.
Возвращает количество всех элементов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые примеры генерируются таким образом, чтобы все значения в выводе помещались в 32-битное целое число.

Пример:

Input: formula = "H2O"
Output: "H2O"

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

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

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

3⃣После завершения обработки строки, объедините все словари из стека и отсортируйте результат.

😎 Решение:

import Foundation

func countOfAtoms(_ formula: String) -> String {
    var stack = [Dictionary<String, Int>]()
    stack.append(Dictionary<String, Int>())
    let formula = Array(formula)
    var i = 0
    let n = formula.count
    
    while i < n {
        if formula[i] == "(" {
            stack.append(Dictionary<String, Int>())
            i += 1
        } else if formula[i] == ")" {
            let top = stack.removeLast()
            i += 1
            var multiplicity = 0
            while i < n && formula[i].isNumber {
                multiplicity = multiplicity * 10 + Int(String(formula[i]))!
                i += 1
            }
            multiplicity = multiplicity == 0 ? 1 : multiplicity
            for (name, count) in top {
                stack[stack.count - 1][name, default: 0] += count * multiplicity
            }
        } else {
            var start = i
            i += 1
            while i < n && formula[i].isLowercase {
                i += 1
            }
            let name = String(formula[start..<i])
            start = i
            var multiplicity = 0
            while i < n && formula[i].isNumber {
                multiplicity = multiplicity * 10 + Int(String(formula[i]))!
                i += 1
            }
            multiplicity = multiplicity == 0 ? 1 : multiplicity
            stack[stack.count - 1][name, default: 0] += multiplicity
        }
    }
    
    let last = stack.removeLast()
    var result = ""
    for key in last.keys.sorted() {
        result += key
        if last[key]! > 1 {
            result += "\(last[key]!)"
        }
    }
    return result
}

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

Задача: 1053. Previous Permutation With One Swap
Сложность: medium

Учитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j].

Пример:

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

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

1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив.

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

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

😎 Решение:

func prevPermOpt1(_ arr: [Int]) -> [Int] {
    var arr = arr
    let n = arr.count
    var i = n - 2
    while i >= 0 && arr[i] <= arr[i + 1] {
        i -= 1
    }
    if i == -1 {
        return arr
    }
    
    var j = n - 1
    while arr[j] >= arr[i] || (j < n - 1 && arr[j] == arr[j + 1]) {
        j -= 1
    }
    
    arr.swapAt(i, j)
    
    return arr
}

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

Задача: 913. Cat and Mouse
Сложность: hard

В игру на неориентированном графе играют два игрока, Мышь и Кот, которые чередуются по очереди. Граф задан следующим образом: graph[a] - это список всех вершин b, таких, что ab является ребром графа. Мышь начинает в вершине 1 и идет первой, Кот начинает в вершине 2 и идет второй, а в вершине 0 находится дыра. Во время хода каждого игрока он должен пройти по одному ребру графа, которое встречает его местоположение.Например, если Мышь находится в узле 1, она должна добраться до любого узла графа[1]. Кроме того, Кошке запрещено добираться до Дыры (узел 0). Затем игра может закончиться тремя способами: если Кошка занимает тот же узел, что и Мышь, Кошка побеждает. Если Мышь достигает Дыры, Мышь побеждает. Если позиция повторяется (т.е, игроки находятся в той же позиции, что и в предыдущий ход, и сейчас очередь того же игрока двигаться), то игра считается ничейной. Учитывая граф и предполагая, что оба игрока играют оптимально, верните 1, если в игре победила мышь, 2, если в игре победила кошка, или 0, если в игре ничья.

Пример:

Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0

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

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

2⃣Проверить три условия окончания игры:
Мышь достигает дырки (победа мыши).
Кот достигает мыши (победа кота).
Позиция повторяется (ничья).

3⃣Использовать BFS (поиск в ширину) для определения результатов игры, начиная с конечных состояний и работая назад.

😎 Решение:

class Solution {
    func catMouseGame(_ graph: [[Int]]) -> Int {
        let n = graph.count
        let DRAW = 0, MOUSE = 1, CAT = 2
        var dp = Array(repeating: Array(repeating: Array(repeating: DRAW, count: 2), count: n), count: n)
        var queue = [(Int, Int, Int, Int)]()
        
        for i in 1..<n {
            dp[0][i][0] = MOUSE
            dp[0][i][1] = MOUSE
            dp[i][i][0] = CAT
            dp[i][i][1] = CAT
            queue.append((0, i, 0, MOUSE))
            queue.append((0, i, 1, MOUSE))
            queue.append((i, i, 0, CAT))
            queue.append((i, i, 1, CAT))
        }
        
        func parents(_ mouse: Int, _ cat: Int, _ turn: Int) -> [(Int, Int, Int)] {
            if turn == 1 {
                return graph[mouse].map { ($0, cat, 0) }
            } else {
                return graph[cat].compactMap { $0 > 0 ? (mouse, $0, 1) : nil }
            }
        }
        
        while !queue.isEmpty {
            let (mouse, cat, turn, winner) = queue.removeFirst()
            for (m, c, t) in parents(mouse, cat, turn) {
                if dp[m][c][t] == DRAW {
                    if (t == 0 && winner == MOUSE) || (t == 1 && winner == CAT) {
                        dp[m][c][t] = winner
                        queue.append((m, c, t, winner))
                    } else {
                        let degrees = parents(m, c, t).count
                        if degrees == 0 {
                            dp[m][c][t] = winner
                            queue.append((m, c, t, winner))
                        }
                    }
                }
            }
        }
        
        return dp[1][2][0]
    }
}

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

Задача: 1523. Count Odd Numbers in an Interval Range
Сложность: easy

Даны два неотрицательных целых числа low и high. Верните количество нечётных чисел между low и high (включительно).

Пример:

Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].

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

1⃣Проверьте, является ли число low нечётным. Это можно легко сделать с помощью оператора %, но мы используем побитовый оператор &, так как он более эффективен.

2⃣Если low нечётное, увеличьте его на 1.

3⃣Верните (high - low) / 2 + 1. Важный момент здесь - проверить, не стало ли low больше, чем high после увеличения. Это произойдёт, если low = high, и в этом случае следует вернуть 0.

😎 Решение:

class Solution {
    func countOdds(_ low: Int, _ high: Int) -> Int {
        var low = low
        if (low & 1) == 0 {
            low += 1
        }
        return low > high ? 0 : (high - low) / 2 + 1
    }
}

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

Задача: 647. Palindromic Substrings
Сложность: medium

Если задана строка 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
}

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

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

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

Лист — это узел без детей.

Пример:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

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

1⃣Если текущий узел не является null, добавьте его значение к текущему пути.
Если текущий узел является листом (не имеет дочерних узлов), добавьте текущий путь в список путей.
Если текущий узел не является листом, добавьте "->" к текущему пути и рекурсивно вызовите функцию для левого и правого дочерних узлов.

2⃣Начните с корневого узла, пустого пути и пустого списка путей.

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

😎 Решение:

class Solution {
    func construct_paths(_ root: TreeNode?, _ path: String, _ paths: inout [String]) {
        if let root = root {
            var path = path + "\(root.val)"
            if root.left == nil && root.right == nil {
                paths.append(path)
            } else {
                path += "->"
                construct_paths(root.left, path, &paths)
                construct_paths(root.right, path, &paths)
            }
        }
    }

    func binaryTreePaths(_ root: TreeNode?) -> [String] {
        var paths = [String]()
        construct_paths(root, "", &paths)
        return paths
    }
}

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

Задача: 1351. Count Negative Numbers in a Sorted Matrix
Сложность: easy

Дана матрица m x n grid, которая отсортирована по убыванию как по строкам, так и по столбцам. Вернуть количество отрицательных чисел в grid.

Пример:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

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

1⃣Инициализировать переменную count = 0 для подсчета общего числа отрицательных элементов в матрице.

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

3⃣Вернуть count.

😎 Решение:

class Solution {
    func countNegatives(_ grid: [[Int]]) -> Int {
        var count = 0
        for row in grid {
            for element in row {
                if element < 0 {
                    count += 1
                }
            }
        }
        return count
    }
}

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

Задача: 79. Word Search
Сложность: medium

Дана сетка символов размером m на n, называемая board, и строка word. Верните true, если слово word существует в сетке.

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

Пример:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

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

1⃣Общий подход к алгоритмам обратной трассировки: В каждом алгоритме обратной трассировки существует определенный шаблон кода. Например, один из таких шаблонов можно найти в нашем разделе "Рекурсия II". Скелет алгоритма представляет собой цикл, который проходит через каждую ячейку в сетке. Для каждой ячейки вызывается функция обратной трассировки (backtrack()), чтобы проверить, можно ли найти решение, начиная с этой ячейки.

2⃣Функция обратной трассировки: Эта функция, реализуемая как алгоритм поиска в глубину (DFS), часто представляет собой рекурсивную функцию. Первым делом проверяется, достигнут ли базовый случай рекурсии, когда слово для сопоставления пусто, то есть для каждого префикса слова уже найдено совпадение. Затем проверяется, не является ли текущее состояние недопустимым: либо позиция ячейки выходит за границы доски, либо буква в текущей ячейке не совпадает с первой буквой слова.

3⃣Исследование и завершение: Если текущий шаг допустим, начинается исследование с использованием стратегии DFS. Сначала текущая ячейка помечается как посещенная, например, любой неалфавитный символ подойдет. Затем осуществляется итерация через четыре возможных направления: вверх, вправо, вниз и влево. Порядок направлений может быть изменен по предпочтениям пользователя. В конце исследования ячейка возвращается к своему исходному состоянию, и возвращается результат исследования.

😎 Решение:

func exist(_ board: inout [[Character]], _ word: String) -> Bool {
    let rows = board.count
    let cols = board[0].count

    func backtrack(_ row: Int, _ col: Int, _ index: Int) -> Bool {
        if index == word.count { return true }
        if row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] != word[word.index(word.startIndex, offsetBy: index)] {
            return false
        }
        
        board[row][col] = "#"  
        let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        var result = false
        
        for (rowOffset, colOffset) in directions {
            result = backtrack(row + rowOffset, col + colOffset, index + 1)
            if result { break }
        }
        
        board[row][col] = word[word.index(word.startIndex, offsetBy: index)]  
        return result
    }

    for row in 0..<rows {
        for col in 0..<cols {
            if backtrack(row, col, 0) { return true }
        }
    }
    return false
}

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

Задача: 1256. Encode Number
Сложность: medium

Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно.

Пример:

Input: num = 23
Output: "1000"

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

1⃣На основе предоставленной таблицы можно выявить закономерность для преобразования целого числа n в строку f(n)

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

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

😎 Решение:

class Solution {
    func encode(_ num: Int) -> String {
        if num == 0 { return "" }
        return String(num - 1, radix: 2)
    }
}

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

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

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

Пример:

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

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

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

2⃣Найти наибольшее значение i, для которого citations[i] > i:
Пройтись по отсортированному массиву и найти наибольшее значение i, для которого выполняется условие citations[i] > i.
Это значение будет индексом, при котором количество цитирований статьи больше индекса.

3⃣Рассчитать h-индекс:
h-индекс будет равен i + 1, где i - наибольшее значение, найденное на предыдущем шаге.

😎 Решение:

class Solution {
    func hIndex(_ citations: [Int]) -> Int {
        let n = citations.count
        var papers = [Int](repeating: 0, count: n + 1)
        for c in citations {
            papers[min(n, c)] += 1
        }
        var k = n
        var s = papers[n]
        while k > s {
            k -= 1
            s += papers[k]
        }
        return k
    }
}

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

Задача: 622. Design Circular Queue
Сложность: medium

Разработайте свою реализацию круговой очереди. Круговая очередь - это линейная структура данных, в которой операции выполняются по принципу FIFO (First In First Out), а последняя позиция соединяется с первой, образуя круг. Одно из преимуществ круговой очереди заключается в том, что мы можем использовать пространство перед очередью. В обычной очереди, когда очередь становится полной, мы не можем вставить следующий элемент, даже если перед очередью есть свободное место. Но с помощью круговой очереди мы можем использовать пространство для хранения новых значений. Реализация класса MyCircularQueue: MyCircularQueue(k) Инициализирует объект с размером очереди k. int Front() Получает первый элемент из очереди. Если очередь пуста, возвращается -1. int Rear() Получает последний элемент из очереди. Если очередь пуста, возвращается -1. boolean enQueue(int value) Вставляет элемент в циклическую очередь. Возвращает true, если операция прошла успешно. boolean deQueue() Удаляет элемент из круговой очереди. Возвращает true, если операция выполнена успешно. boolean isEmpty() Проверяет, пуста ли круговая очередь. boolean isFull() Проверяет, заполнена ли круговая очередь. Вы должны решить проблему без использования встроенной структуры данных очереди в вашем языке программирования.

Пример:

Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

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

1⃣Используйте массив фиксированного размера для хранения элементов очереди и два указателя: front для отслеживания начала очереди и rear для отслеживания конца очереди.

2⃣Реализуйте методы enQueue и deQueue для вставки и удаления элементов, обновляя указатели по круговому принципу.

3⃣Реализуйте методы Front, Rear, isEmpty и isFull для доступа к элементам и проверки состояния очереди.

😎 Решение:

class MyCircularQueue {
    private var queue: [Int]
    private var front: Int
    private var rear: Int
    private var size: Int
    private var capacity: Int

    init(_ k: Int) {
        self.queue = Array(repeating: -1, count: k)
        self.front = 0
        self.rear = -1
        self.size = 0
        self.capacity = k
    }
    
    func enQueue(_ value: Int) -> Bool {
        if isFull() {
            return false
        }
        rear = (rear + 1) % capacity
        queue[rear] = value
        size += 1
        return true
    }
    
    func deQueue() -> Bool {
        if isEmpty() {
            return false
        }
        front = (front + 1) % capacity
        size -= 1
        return true
    }
    
    func Front() -> Int {
        return isEmpty() ? -1 : queue[front]
    }
    
    func Rear() -> Int {
        return isEmpty() ? -1 : queue[rear]
    }
    
    func isEmpty() -> Bool {
        return size == 0
    }
    
    func isFull() -> Bool {
        return size == capacity
    }
}

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

Задача: 738. Monotone Increasing Digits
Сложность: medium

Целое число имеет монотонно возрастающие цифры тогда и только тогда, когда каждая пара соседних цифр x и y удовлетворяет x <= y. Задав целое число n, верните наибольшее число, которое меньше или равно n с монотонно возрастающими цифрами.

Пример:

Input: n = 10
Output: 9

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

1⃣Преобразуйте число в строку для удобства обработки.

2⃣Найдите позицию, где последовательность перестает быть монотонной.

3⃣Уменьшите соответствующую цифру и установите все последующие цифры в 9.

😎 Решение:

func monotoneIncreasingDigits(_ n: Int) -> Int {
    var digits = Array(String(n))
    var mark = digits.count
    
    for i in stride(from: digits.count - 1, to: 0, by: -1) {
        if digits[i] < digits[i - 1] {
            mark = i
            digits[i - 1] = Character(String(digits[i - 1].wholeNumberValue! - 1))
        }
    }
    
    for i in mark..<digits.count {
        digits[i] = "9"
    }
    
    return Int(String(digits))!
}

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

Задача: 367. Valid Perfect Square
Сложность: hard

Дано положительное целое число num, вернуть true, если num является идеальным квадратом, или false в противном случае.

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

Вы не должны использовать какие-либо встроенные библиотечные функции, такие как sqrt.

Пример:

Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.

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

1⃣Если num < 2, вернуть True. Установить левую границу в 2, а правую границу в num / 2.

2⃣Пока left <= right, взять x = (left + right) / 2, вычислить guess_squared = x * x и сравнить его с num:
Если guess_squared == num, вернуть True.
Если guess_squared > num, сдвинуть правую границу right = x - 1.
В противном случае сдвинуть левую границу left = x + 1.

3⃣Если вышли из цикла, вернуть False.

😎 Решение:

class Solution {
    func isPerfectSquare(_ num: Int) -> Bool {
        if num < 2 { return true }

        var x = num / 2
        while x * x > num {
            x = (x + num / x) / 2
        }
        return x * x == num
    }
}

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

Задача: 759. Employee Free Time
Сложность: hard

Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.

Пример:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]

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

1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам.

2⃣Объедините пересекающиеся интервалы в один.

3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.

😎 Решение:

class Interval {
    var start: Int
    var end: Int
    init(_ start: Int, _ end: Int) {
        self.start = start
        self.end = end
    }
}

func employeeFreeTime(_ schedule: [[Interval]]) -> [Interval] {
    var intervals = [Interval]()
    for employee in schedule {
        intervals.append(contentsOf: employee)
    }
    
    intervals.sort { $0.start < $1.start }
    
    var merged = [Interval]()
    for interval in intervals {
        if merged.isEmpty || merged.last!.end < interval.start {
            merged.append(interval)
        } else {
            merged.last!.end = max(merged.last!.end, interval.end)
        }
    }
    
    var freeTime = [Interval]()
    for i in 1..<merged.count {
        if merged[i].start > merged[i-1].end {
            freeTime.append(Interval(merged[i-1].end, merged[i].start))
        }
    }
    
    return freeTime
}

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