Задача: 137. Single Number II
Сложность: medium

Дан массив целых чисел nums, в котором каждый элемент встречается три раза, кроме одного, который встречается ровно один раз. Найдите этот единственный элемент и верните его.

Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.

Пример:

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

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

1⃣Сортировка массива:
Отсортируйте массив nums. Это упорядочит все элементы так, чтобы одинаковые числа находились рядом.

2⃣Итерация с проверкой:
Используйте цикл for для перебора элементов массива от начала до nums.size() - 2 с шагом 3. Таким образом, каждый проверяемый индекс будет иметь следующий за ним индекс в пределах массива.
Если элемент на текущем индексе совпадает с элементом на следующем индексе (проверка nums[i] == nums[i + 1]), продолжайте следующую итерацию цикла.

3⃣Возврат уникального элемента:
Если элемент на текущем индексе не совпадает с следующим, значит, это искомый уникальный элемент, который встречается только один раз. В этом случае возвращайте элемент на текущем индексе.
Если до последнего элемента цикл не нашёл уникального элемента, возвращайте последний элемент массива nums[nums.size() - 1], поскольку он, очевидно, будет уникальным, если предыдущие проверки не выявили уникального элемента раньше.

😎 Решение:

func singleNumber(_ nums: [Int]) -> Int {
    let sortedNums = nums.sorted()
    var i = 0
    while i < sortedNums.count - 1 {
        if sortedNums[i] == sortedNums[i + 1] {
            i += 3
        } else {
            return sortedNums[i]
        }
    }
    return sortedNums.last ?? 0
}

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

Задача: 61. Rotate List
Сложность: medium

Дан указатель на начало связного списка, поверните список вправо на k позиций.

Пример:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

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

1⃣Найдите старый хвост и соедините его с головой (old_tail.next = head), чтобы замкнуть кольцо. Одновременно вычислите длину списка n.

2⃣Найдите новый хвост, который находится на позиции (n - k % n - 1) от головы, и новую голову, которая находится на позиции (n - k % n).

3⃣Разорвите кольцо (new_tail.next = None) и верните new_head.

😎 Решение:

func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
    if head == nil { return nil }
    if head?.next == nil { return head }

    var oldTail = head
    var n = 1
    while oldTail?.next != nil {
        oldTail = oldTail?.next
        n += 1
    }
    oldTail?.next = head

    var newTail = head
    for _ in 0..<(n - k % n - 1) {
        newTail = newTail?.next
    }
    let newHead = newTail?.next

    newTail?.next = nil
    return newHead
}

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

Задача: 190. Reverse Bits
Сложность: easy

Переверните биты заданного 32-битного беззнакового целого числа.

Пример:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:

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

1⃣Итерируем по байтам целого числа, используя побитовую операцию И (n & 0xff) с маской 11111111, чтобы извлечь крайний правый байт числа.

2⃣Для каждого байта сначала переворачиваем биты внутри байта с помощью функции reverseByte(byte). Затем сдвигаем перевернутые биты на их окончательные позиции.

3⃣В функции reverseByte(byte) используем технику мемоизации, которая сохраняет результат функции и возвращает его непосредственно при последующих вызовах с тем же входным значением. Мемоизация — это компромисс между использованием памяти и объемом вычислений.

😎 Решение:

class Solution {
    var cache = [UInt32: UInt32]()

    func reverseByte(_ byte: UInt32) -> UInt32 {
        if let cachedValue = cache[byte] {
            return cachedValue
        }
        let value = ((byte * 0x0202020202) & 0x010884422010) % 1023
        cache[byte] = value
        return value
    }

    func reverseBits(_ n: UInt32) -> UInt32 {
        var ret: UInt32 = 0
        var power: UInt32 = 24
        var n = n
        while n != 0 {
            ret += reverseByte(n & 0xff) << power
            n = n >> 8
            power -= 8
        }
        return ret
    }
}

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

Задача: 1248. Count Number of Nice Subarrays
Сложность: medium

Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.

Пример:

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

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

1⃣Преобразуйте массив чисел nums, заменив все чётные числа на 0, а все нечётные числа на 1.

2⃣Используя технику скользящего окна (или двух указателей), найдите все подмассивы, содержащие ровно k единиц.

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

😎 Решение:

class Solution {
    func numberOfSubarrays(_ nums: [Int], _ k: Int) -> Int {
        return atMost(nums, k) - atMost(nums, k - 1)
    }

    private func atMost(_ nums: [Int], _ k: Int) -> Int {
        var res = 0, left = 0, count = 0
        for right in 0..<nums.count {
            if nums[right] % 2 == 1 {
                count += 1
            }
            while count > k {
                if nums[left] % 2 == 1 {
                    count -= 1
                }
                left += 1
            }
            res += right - left + 1
        }
        return res
    }
}

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

Задача: 143. Reorder List
Сложность: medium

Вам дана голова односвязного списка. Список можно представить в следующем виде:

L0 → L1 → … → Ln - 1 → Ln

Переупорядочите список так, чтобы он принял следующую форму:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

Вы не можете изменять значения в узлах списка. Можно изменять только сами узлы.

Пример:

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

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

1⃣Нахождение середины списка и разделение его на две части:
Используйте два указателя, slow и fast, для нахождения середины списка. Указатель slow движется на один узел за шаг, а fast — на два узла. Когда fast достигает конца списка, slow окажется в середине.
Разделите список на две части. Первая часть начинается от головы списка до slow, вторая — с узла после slow до конца списка.

2⃣Реверс второй половины списка:
Инициализируйте указатели prev как NULL и curr как slow. Перемещайтесь по второй половине списка и меняйте направление ссылок между узлами для реверсирования списка.
Продолжайте, пока не перестроите весь второй сегмент, теперь последний элемент первой части списка будет указывать на NULL, а prev станет новой головой второй половины списка.

3⃣Слияние двух частей списка в заданном порядке:
Начните с головы первой части списка (first) и головы реверсированной второй части (second).
Перекрестно связывайте узлы из первой и второй части, вставляя узлы из второй части между узлами первой части. Передвигайте указатели first и second соответственно после каждой вставки.
Продолжайте этот процесс до тех пор, пока узлы второй части не закончатся.

😎 Решение:

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

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

func reorderList(_ head: ListNode?) {
    guard var slow = head, var fast = head else { return }

    while let nextFast = fast.next?.next {
        slow = slow.next!
        fast = nextFast
    }

    var prev: ListNode? = nil
    var curr: ListNode? = slow
    while let current = curr {
        let tmp = current.next
        current.next = prev
        prev = current
        curr = tmp
    }

    var first = head
    var second = prev
    while second?.next != nil {
        let tmp = first?.next
        first?.next = second
        first = tmp
        let tmp2 = second?.next
        second?.next = first
        second = tmp2
    }
}

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

Задача: 37. Sudoku Solver
Сложность: hard

Напишите программу для решения головоломки Судоку, заполнив пустые ячейки.

Решение Судоку должно удовлетворять всем следующим правилам:

Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждой строке.
Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждом столбце.
Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждом из 9 подблоков 3x3 сетки.
Символ '.' обозначает пустые ячейки.

Пример:

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

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

1⃣Теперь все готово для написания функции обратного поиска backtrack(row = 0, col = 0). Начните с верхней левой ячейки row = 0, col = 0. Продолжайте, пока не дойдете до первой свободной ячейки.

2⃣Итерируйте по числам от 1 до 9 и попробуйте поставить каждое число d в ячейку (row, col).
Если число d еще не в текущей строке, столбце и блоке:
Поместите d в ячейку (row, col).
Запишите, что d теперь присутствует в текущей строке, столбце и блоке.

3⃣Если вы на последней ячейке row == 8, col == 8:
Это означает, что судоку решено.
В противном случае продолжайте размещать дальнейшие числа.
Откат, если решение еще не найдено: удалите последнее число из ячейки (row, col).

😎 Решение:

import Foundation

class Solution {
    func solveSudoku(_ board: inout [[Character]]) {
        let n = 3
        let N = n * n
        var tracking = Array(repeating: [Character: Int](), count: N * 3)

        func index(_ type: Int, _ i: Int) -> Int { type * N + i }
        func boxIndex(_ r: Int, _ c: Int) -> Int { (r / n) * n + c / n }

        func canPlace(_ num: Character, _ r: Int, _ c: Int) -> Bool {
            let bIdx = boxIndex(r, c)
            return tracking[index(0, r)][num] == nil &&
                   tracking[index(1, c)][num] == nil &&
                   tracking[index(2, bIdx)][num] == nil
        }

        func placeOrRemove(_ num: Character, _ r: Int, _ c: Int, place: Bool) {
            let bIdx = boxIndex(r, c)
            let adjustment = place ? 1 : -1
            tracking[index(0, r)][num, default: 0] += adjustment
            tracking[index(1, c)][num, default: 0] += adjustment
            tracking[index(2, bIdx)][num, default: 0] += adjustment
            board[r][c] = place ? num : "."
        }

        func backtrack(_ r: Int = 0, _ c: Int = 0) {
            if c == N && r == N - 1 { return }
            let nextR = c == N - 1 ? r + 1 : r
            let nextC = c == N - 1 ? 0 : c + 1

            if board[r][c] == "." {
                for num in "123456789" {
                    if canPlace(num, r, c) {
                        placeOrRemove(num, r, c, place: true)
                        backtrack(nextR, nextC)
                        placeOrRemove(num, r, c, place: false)
                    }
                }
            } else {
                backtrack(nextR, nextC)
            }
        }

        for r in 0..<N {
            for c in 0..<N where board[r][c] != "." {
                placeOrRemove(board[r][c], r, c, place: true)
            }
        }

        backtrack()
    }
}

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

Задача: 1032. Stream of Characters
Сложность: hard

Разработайте алгоритм, который принимает поток символов и проверяет, является ли суффикс этих символов строкой заданного массива строк words. Например, если words = ["abc", "xyz"] и в поток добавлены четыре символа (один за другим) 'a', 'x', 'y' и 'z', ваш алгоритм должен определить, что суффикс "xyz" символов "axyz" соответствует "xyz" из words.

Реализуйте класс StreamChecker: StreamChecker(String[] words) Инициализирует объект с массивом строк words. boolean query(char letter) Принимает новый символ из потока и возвращает true, если любой непустой суффикс из потока образует слово, которое есть в words.

Пример:

Input
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
Output
[null, false, false, false, true, false, true, false, false, false, false, false, true]

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

1⃣Построение суффиксного Trie:
Создайте суффиксный Trie (префиксное дерево) для хранения всех слов из массива words в обратном порядке. Это позволяет эффективно искать слова, которые являются суффиксами потока символов.

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

3⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.

😎 Решение:

class TrieNode {
    var children: [Character: TrieNode] = [:]
    var isEndOfWord: Bool = false
}

class StreamChecker {
    private var root: TrieNode = TrieNode()
    private var stream: [Character] = []

    init(_ words: [String]) {
        for word in words {
            var node = root
            for char in word.reversed() {
                if node.children[char] == nil {
                    node.children[char] = TrieNode()
                }
                node = node.children[char]!
            }
            node.isEndOfWord = true
        }
    }

    func query(_ letter: Character) -> Bool {
        stream.insert(letter, at: 0)
        var node = root
        for char in stream {
            if let nextNode = node.children[char] {
                node = nextNode
                if node.isEndOfWord {
                    return true
                }
            } else {
                break
            }
        }
        return false
    }
}

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

Задача: 1044. Longest Duplicate Substring
Сложность: hard

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

Пример:

Input: s = "banana"
Output: "ana"

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

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

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

3⃣Хеширование с помощью функции rolling hash:
Rolling hash позволяет быстро вычислять хеши подстрок фиксированной длины и сравнивать их для поиска дубликатов.

😎 Решение:

func longestDupSubstring(_ s: String) -> String {
    let arr = Array(s)
    
    func search(_ length: Int) -> String? {
        var seen = Set<String>()
        for i in 0...(arr.count - length) {
            let sub = String(arr[i..<i+length])
            if seen.contains(sub) {
                return sub
            }
            seen.insert(sub)
        }
        return nil
    }

    var left = 1, right = arr.count
    var result = ""
    while left < right {
        let mid = (left + right) / 2
        if let dup = search(mid) {
            result = dup
            left = mid + 1
        } else {
            right = mid
        }
    }
    return result
}

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

Задача: 900. RLE Iterator
Сложность: hard

Для кодирования последовательности целых чисел мы можем использовать кодирование по длине строки (т. е. RLE). В кодированном по длине пробега массиве четной длины (с индексацией 0) для всех четных i значение encoding[i] говорит нам о том, сколько раз неотрицательное целое значение encoding[i + 1] повторяется в последовательности.

Например, последовательность arr = [8,8,8,5,5] может быть закодирована как encoding = [3,8,2,5]. encoding = [3,8,0,9,2,5] и encoding = [2,8,1,8,2,5] также являются допустимыми RLE для arr.
Задав кодированный по длине пробега массив, разработайте итератор для его итерации. Реализуйте класс RLEIterator: RLEIterator(int[] encoded) Инициализирует объект с кодированным массивом encoded. int next(int n) Исчерпывает следующие n элементов и возвращает последний исчерпанный таким образом элемент. Если не осталось элементов для исчерпания, возвращает -1.

Пример:

Input
["RLEIterator", "next", "next", "next", "next"]
[[[3, 8, 0, 9, 2, 5]], [2], [1], [1], [2]]
Output
[null, 8, 8, 5, -1]

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

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

2⃣При вызове метода next(n), уменьшить текущий счетчик на n или перейти к следующему числу, если текущий счетчик равен нулю.

3⃣Возвращать текущий элемент или -1, если все элементы исчерпаны.

😎 Решение:

class RLEIterator {
    private var encoding: [Int]
    private var index: Int

    init(_ encoding: [Int]) {
        self.encoding = encoding
        self.index = 0
    }

    func next(_ n: Int) -> Int {
        var n = n
        while index < encoding.count {
            if n > encoding[index] {
                n -= encoding[index]
                index += 2
            } else {
                encoding[index] -= n
                return encoding[index + 1]
            }
        }
        return -1
    }
}

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

Задача: 43. Multiply Strings
Сложность: hard

Даны два неотрицательных целых числа num1 и num2, представленные в виде строк. Верните произведение num1 и num2, также представленное в виде строки.

Примечание: Вы не должны использовать встроенную библиотеку BigInteger или прямо преобразовывать входные данные в целые числа.

Пример:

Input: num1 = "2", num2 = "3"
Output: "6"

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

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

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

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

😎 Решение:

func addStrings(_ num1: [Int], _ num2: [Int]) -> [Int] {
    var ans = [Int]()
    var carry = 0
    let maxLength = max(num1.count, num2.count)

    for i in 0..<maxLength {
        let digit1 = i < num1.count ? num1[i] : 0
        let digit2 = i < num2.count ? num2[i] : 0

        let sum = digit1 + digit2 + carry
        carry = sum / 10
        ans.append(sum % 10)
    }

    if carry > 0 {
        ans.append(carry)
    }
    return ans
}

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

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

    if carry > 0 {
        currentResult.append(carry)
    }
    return currentResult
}

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

    let firstNumber = Array(num1).reversed().map { Int(String($0))! }
    let secondNumber = Array(num2).reversed().map { Int(String($0))! }

    var ans = Array(repeating: 0, count: firstNumber.count + secondNumber.count)

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

    while ans.last == 0 && ans.count > 1 {
        ans.removeLast()
    }

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

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

Задача: 38. Count and Say
Сложность: medium

Последовательность "считай и скажи" — это последовательность строк цифр, определяемая с помощью рекурсивной формулы:

countAndSay(1) = "1"
countAndSay(n) — это кодирование длин серий из countAndSay(n - 1).
Кодирование длин серий (RLE) — это метод сжатия строк, который работает путём замены последовательных идентичных символов (повторяющихся 2 или более раз) на конкатенацию символа и числа, обозначающего количество символов (длину серии). Например, чтобы сжать строку "3322251", мы заменяем "33" на "23", "222" на "32", "5" на "15" и "1" на "11". Таким образом, сжатая строка становится "23321511".

Для заданного положительного целого числа n верните n-й элемент последовательности "считай и скажи".

Пример:

Input: n = 4

Output: "1211"

Explanation:

countAndSay(1) = "1"
countAndSay(2) = RLE of "1" = "11"
countAndSay(3) = RLE of "11" = "21"
countAndSay(4) = RLE of "21" = "1211"

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

1⃣Мы хотим использовать шаблон, который соответствует строкам из одинаковых символов, таких как "4", "7777", "2222222".
Если у вас есть опыт работы с регулярными выражениями, вы можете обнаружить, что шаблон (.)\1* работает.

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

3⃣*: этот квалификатор, следующий за ссылкой на группу \1, указывает, что мы хотели бы видеть повторение группы ноль или более раз.
Таким образом, шаблон соответствует строкам, которые состоят из некоторого символа, а затем ноль или более повторений этого символа после его первого появления. Это то, что нам нужно.
Мы находим все совпадения с регулярным выражением, а затем конкатенируем результаты.

😎 Решение:

func countAndSay(_ n: Int) -> String {
    var s = "1"
    for _ in 2...n {
        var t = ""
        var matches = Array(s.matchingStrings(regex: "(.)\\1*"))
        for match in matches {
            t += "\(match[0].count)\(match[1])"
        }
        s = t
    }
    return s
}

extension String {
    func matchingStrings(regex: String) -> [[String]] {
        do {
            let regex = try NSRegularExpression(pattern: regex)
            let results = regex.matches(in: self, range: NSRange(self.startIndex..., in: self))
            return results.map { result in
                (0..<result.numberOfRanges).map {
                    String(self[Range(result.range(at: $0), in: self)!])
                }
            }
        } catch let error {
            print("invalid regex: \(error.localizedDescription)")
            return []
        }
    }
}

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

Задача: 1404. Number of Steps to Reduce a Number in Binary Representation to One
Сложность: medium

Дано бинарное представление целого числа в виде строки s. Верните количество шагов, необходимых для его сокращения до 1 по следующим правилам:
Если текущее число четное, его нужно разделить на 2.
Если текущее число нечетное, нужно прибавить к нему 1.
Гарантируется, что для всех тестовых случаев всегда можно достичь единицы.

Пример:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.  

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

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

2⃣Повторяйте операции, пока длина строки s больше 1:
Если последний бит строки s равен 0, это означает, что число четное; примените операцию деления на 2, удалив последний бит.
В противном случае это означает, что число, представленное строкой, нечетное; добавьте 1 к числу, изменив строку, чтобы выполнить эту операцию.

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

😎 Решение:

class Solution {
    func numSteps(_ s: String) -> Int {
        var str = Array(s)
        var operations = 0

        while str.count > 1 {
            if str.last == "0" {
                str.removeLast()
            } else {
                var i = str.count - 1
                while i >= 0 && str[i] == "1" {
                    str[i] = "0"
                    i -= 1
                }
                if i < 0 {
                    str.insert("1", at: 0)
                } else {
                    str[i] = "1"
                }
            }
            operations += 1
        }

        return operations
    }
}

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

Задача: 1261. Find Elements in a Contaminated Binary Tree
Сложность: medium

Дано двоичное дерево со следующими правилами: root.val == 0 Если treeNode.val == x и treeNode.left != null, то treeNode.left.val == 2 * x + 1 Если treeNode.val == x и treeNode.right != null, то treeNode.right.val == 2 * x + 2 Теперь двоичное дерево загрязнено, то есть все treeNode.val были изменены на -1. Реализация класса FindElements: FindElements(TreeNode* root) Инициализирует объект с загрязненным двоичным деревом и восстанавливает его. bool find(int target) Возвращает true, если целевое значение существует в восстановленном двоичном дереве.

Пример:

Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output
[null,false,true]

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

1⃣Восстановление дерева: Начните с корневого узла, установите его значение на 0. Затем рекурсивно восстановите значения для всех узлов, используя правила left.val = 2 * parent.val + 1 и right.val = 2 * parent.val + 2.

2⃣Сохранение значений: Используйте структуру данных, такую как множество (set), для хранения всех восстановленных значений узлов.

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

😎 Решение:

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

class FindElements {
    private var root: TreeNode?
    private var values: Set<Int>
    
    init(_ root: TreeNode?) {
        self.root = root
        self.values = Set<Int>()
        if let root = root {
            root.val = 0
            values.insert(0)
            recover(root)
        }
    }
    
    private func recover(_ node: TreeNode) {
        if let left = node.left {
            left.val = 2 * node.val + 1
            values.insert(left.val)
            recover(left)
        }
        if let right = node.right {
            right.val = 2 * node.val + 2
            values.insert(right.val)
            recover(right)
        }
    }
    
    func find(_ target: Int) -> Bool {
        return values.contains(target)
    }
}

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

Задача: 785. Is Graph Bipartite?
Сложность: medium

Есть неориентированный граф с n узлами, где каждый узел пронумерован от 0 до n - 1. Вам дан двумерный массив graph, где graph[u] — это массив узлов, смежных с узлом u. Более формально, для каждого v в graph[u] существует неориентированное ребро между узлом u и узлом v. Граф обладает следующими свойствами:

Нет петель (graph[u] не содержит u).
Нет параллельных ребер (graph[u] не содержит дублирующихся значений).
Если v есть в graph[u], то u есть в graph[v] (граф неориентированный).
Граф может быть несвязным, то есть могут существовать два узла u и v, между которыми нет пути.
Граф является двудольным, если узлы можно разделить на два независимых множества A и B так, что каждое ребро в графе соединяет узел из множества A с узлом из множества B.

Верните true, если и только если граф является двудольным.

Пример:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

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

1⃣Мы будем хранить массив (или hashmap) для поиска цвета каждого узла: color[node]. Цвета могут быть 0, 1 или неокрашенные (-1 или null).

2⃣Мы должны быть внимательны к рассмотрению несвязных компонентов графа, выполняя поиск для каждого узла. Для каждого неокрашенного узла мы начнем процесс окрашивания, выполняя поиск в глубину (DFS) для этого узла. Каждый соседний узел получает цвет, противоположный цвету текущего узла. Если мы обнаруживаем, что соседний узел окрашен в тот же цвет, что и текущий узел, значит, наше окрашивание невозможно.

3⃣Для выполнения поиска в глубину мы используем стек. Для каждого неокрашенного соседа в graph[node] мы будем его окрашивать и добавлять в наш стек, который действует как своего рода "список дел" для узлов, которые нужно посетить дальше. Наш внешний цикл для start... гарантирует, что мы окрасим каждый узел.

😎 Решение:

class Solution {
    func isBipartite(_ graph: [[Int]]) -> Bool {
        var color = [Int: Int]()
        for node in 0..<graph.count {
            if color[node] == nil {
                var stack = [node]
                color[node] = 0
                while !stack.isEmpty {
                    let node = stack.removeLast()
                    for nei in graph[node] {
                        if color[nei] == nil {
                            stack.append(nei)
                            color[nei] = color[node]! ^ 1
                        } else if color[nei] == color[node] {
                            return false
                        }
                    }
                }
            }
        }
        return true
    }
}

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

Задача: 1673. Find the Most Competitive Subsequence
Сложность: medium

Дан целочисленный массив nums и положительное целое число k. Верните наиболее конкурентоспособную подпоследовательность массива nums размера k.

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

Мы определяем, что подпоследовательность a более конкурентоспособна, чем подпоследовательность b (одинаковой длины), если в первой позиции, где они различаются, подпоследовательность a имеет число меньше, чем соответствующее число в b. Например, [1,3,4] более конкурентоспособна, чем [1,3,5], потому что первая позиция, где они различаются, это последнее число, и 4 меньше, чем 5.

Пример:

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.

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

1⃣Создайте двустороннюю очередь (deque), которая будет хранить выбранную подпоследовательность.

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

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

😎 Решение:

class Solution {
    func mostCompetitive(_ nums: [Int], _ k: Int) -> [Int] {
        var queue = [Int]()
        var additionalCount = nums.count - k
        
        for num in nums {
            while !queue.isEmpty && queue.last! > num && additionalCount > 0 {
                queue.removeLast()
                additionalCount -= 1
            }
            queue.append(num)
        }
        
        return Array(queue.prefix(k))
    }
}

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

Задача: 1258. Synonymous Sentences
Сложность: medium

Вам дан список эквивалентных пар строк synonyms, где synonyms[i] = [si, ti] означает, что si и ti являются эквивалентными строками. Вам также дан текст предложения. Верните все возможные синонимичные предложения, отсортированные лексикографически.

Пример:

Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"
Output: ["I am cheerful today but was sad yesterday","I am cheerful today but was sorrow yesterday","I am happy today but was sad yesterday","I am happy today but was sorrow yesterday","I am joy today but was sad yesterday","I am joy today but was sorrow yesterday"]

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

1⃣Построить граф синонимов, используя структуру данных, такую как Union-Find или просто с использованием DFS/BFS.

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

3⃣Отсортировать полученные предложения лексикографически.

😎 Решение:

class Solution {
    func generateSentences(_ synonyms: [[String]], _ text: String) -> [String] {
        var graph = [String: Set<String>]()

        for pair in synonyms {
            graph[pair[0], default: Set()].insert(pair[1])
            graph[pair[1], default: Set()].insert(pair[0])
        }

        let words = text.split(separator: " ").map { String($0) }
        var synonymGroups = [[String]]()
        for word in words {
            synonymGroups.append(findSynonyms(graph, word))
        }

        var sentences = [String]()
        var sentence = ""
        generate(&sentences, synonymGroups, &sentence, 0)
        return sentences.sorted()
    }

    private func findSynonyms(_ graph: [String: Set<String>], _ word: String) -> [String] {
        var synonyms = Set<String>()
        var stack = [word]
        while !stack.isEmpty {
            let w = stack.removeLast()
            if synonyms.insert(w).inserted {
                for neighbor in graph[w] ?? [] {
                    stack.append(neighbor)
                }
            }
        }
        return Array(synonyms).sorted()
    }

    private func generate(_ sentences: inout [String], _ groups: [[String]], _ sentence: inout String, _ index: Int) {
        if index == groups.count {
            sentences.append(sentence.trimmingCharacters(in: .whitespaces))
            return
        }
        for word in groups[index] {
            let original = sentence
            sentence += " " + word
            generate(&sentences, groups, &sentence, index + 1)
            sentence = original
        }
    }
}

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

Задача: 665. Non-decreasing Array
Сложность: medium

Дан массив nums из n целых чисел. Ваша задача - проверить, можно ли сделать его неубывающим, изменив не более одного элемента.

Мы определяем массив как неубывающий, если для каждого i (индексация с 0), такого что 0 <= i <= n - 2, выполняется условие nums[i] <= nums[i + 1].

Пример:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

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

1⃣Инициализация переменных:
Завести переменную count для подсчета числа изменений.
Проверить последовательность чисел в массиве nums.

2⃣Проверка условий:
Если nums[i] > nums[i + 1], то увеличиваем count.
Если count превышает 1, возвращаем false, так как больше одного изменения недопустимо.
Если nums[i - 1] > nums[i + 1] и nums[i] > nums[i + 2], то возвращаем false.

3⃣Возврат результата:
Если количество изменений не превышает 1, вернуть true.

😎 Решение:

class Solution {
    func checkPossibility(_ nums: [Int]) -> Bool {
        var nums = nums
        var count = 0
        
        for i in 1..<nums.count {
            if nums[i] < nums[i - 1] {
                if count > 0 {
                    return false
                }
                count += 1
                if i == 1 || nums[i] >= nums[i - 2] {
                    nums[i - 1] = nums[i]
                } else {
                    nums[i] = nums[i - 1]
                }
            }
        }
        
        return true
    }
}

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

Задача: 1305. All Elements in Two Binary Search Trees
Сложность: medium

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

Пример:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

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

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

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; }
}

class Solution {
    func getAllElements(_ root1: TreeNode?, _ root2: TreeNode?) -> [Int] {
        var stack1 = [TreeNode](), stack2 = [TreeNode]()
        var output = [Int]()
        var root1 = root1
        var root2 = root2

        while root1 != nil || root2 != nil || !stack1.isEmpty || !stack2.isEmpty {
            while root1 != nil {
                stack1.append(root1!)
                root1 = root1!.left
            }
            while root2 != nil {
                stack2.append(root2!)
                root2 = root2!.left
            }
            if stack2.isEmpty || (!stack1.isEmpty && stack1.last!.val <= stack2.last!.val) {
                root1 = stack1.removeLast()
                output.append(root1!.val)
                root1 = root1!.right
            } else {
                root2 = stack2.removeLast()
                output.append(root2!.val)
                root2 = root2!.right
            }
        }
        return output
    }
}

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