Задача: 501. Find Mode in Binary Search Tree
Сложность: easy

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

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

Пример:

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

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

1⃣Обход дерева
Выполните обход дерева (inorder DFS) с использованием рекурсивной функции dfs, чтобы пройти по всем узлам дерева. На каждом узле добавьте node.val в список values.

2⃣Поиск мод
Инициализируйте переменные maxStreak, currStreak, currNum как 0 и пустой список ans. Пройдите по списку values. Для каждого числа num: если num равно currNum, увеличьте currStreak. Иначе, установите currStreak равным 1, а currNum равным num. Если currStreak больше maxStreak, обновите maxStreak и сбросьте ans. Если currStreak равен maxStreak, добавьте num в ans.

3⃣Возврат результата
Верните список ans.

😎 Решение:

class Solution {
    func findMode(_ root: TreeNode?) -> [Int] {
        var values = [Int]()
        dfs(root, &values)
        
        var maxStreak = 0, currStreak = 0, currNum = 0
        var ans = [Int]()
        
        for num in values {
            if num == currNum {
                currStreak += 1
            } else {
                currStreak = 1
                currNum = num
            }
            
            if currStreak > maxStreak {
                ans = [num]
                maxStreak = currStreak
            } else if currStreak == maxStreak {
                ans.append(num)
            }
        }
        
        return ans
    }
    
    func dfs(_ node: TreeNode?, _ values: inout [Int]) {
        guard let node = node else { return }
        dfs(node.left, &values)
        values.append(node.val)
        dfs(node.right, &values)
    }
}

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

Задача: 537. Complex Number Multiplication
Сложность: medium

Комплексное число можно представить в виде строки в формате "real+imaginaryi", где:
real — это действительная часть и является целым числом в диапазоне [-100, 100].
imaginary — это мнимая часть и является целым числом в диапазоне [-100, 100].
i^2 == -1.
Даны два комплексных числа num1 и num2 в виде строк, верните строку комплексного числа, представляющую их произведение.

Пример:

Input: num1 = "1+1i", num2 = "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

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

1⃣ Извлечение реальной и мнимой частей:
Разделите строки a и b на реальные и мнимые части, используя символы '+' и 'i'.

2⃣ Вычисление произведения:
Переведите извлечённые части в целые числа.
Используйте формулу для умножения комплексных чисел: (a+ib)×(x+iy)=ax−by+i(bx+ay).

3⃣ Формирование строки результата:
Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её.

😎 Решение:

class Solution {
    func complexNumberMultiply(_ a: String, _ b: String) -> String {
        let x = a.split(separator: "+")
        let y = b.split(separator: "+")
        let a_real = Int(x[0])!
        let a_img = Int(x[1].dropLast())!
        let b_real = Int(y[0])!
        let b_img = Int(y[1].dropLast())!
        let realPart = a_real * b_real - a_img * b_img
        let imaginaryPart = a_real * b_img + a_img * b_real
        return "\(realPart)+\(imaginaryPart)i"
    }
}

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

Задача: 636. Exclusive Time of Functions
Сложность: medium

На однопоточном процессоре выполняется программа, содержащая n функций. Каждая функция имеет уникальный ID от 0 до n-1. Вызовы функций хранятся в стеке вызовов: когда начинается вызов функции, ее ID заталкивается в стек, а когда вызов функции заканчивается, ее ID выгружается из стека. Функция, чей идентификатор находится в верхней части стека, является текущей выполняемой функцией. Каждый раз, когда функция запускается или завершается, мы пишем лог с идентификатором, началом или завершением и меткой времени. Вам предоставляется список logs, где logs[i] представляет собой i-е сообщение лога, отформатированное как строка "{function_id}:{"start" | "end"}:{timestamp}". Например, "0:start:3" означает, что вызов функции с идентификатором 0 начался в начале временной метки 3, а "1:end:2" означает, что вызов функции с идентификатором 1 завершился в конце временной метки 2. Обратите внимание, что функция может быть вызвана несколько раз, возможно, рекурсивно. Исключительное время функции - это сумма времен выполнения всех вызовов функции в программе. Например, если функция вызывается дважды, причем один вызов выполняется за 2 единицы времени, а другой - за 1 единицу, то эксклюзивное время равно 2 + 1 = 3. Верните эксклюзивное время каждой функции в массив, где значение по i-му индексу представляет собой эксклюзивное время для функции с идентификатором i.

Пример:

Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output: [3,4]

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

1⃣Парсинг логов: Пройдитесь по каждому логу, чтобы распознать действие (start или end) и идентификатор функции вместе с временной меткой.

2⃣Использование стека: Используйте стек для отслеживания текущих вызовов функций. Если лог содержит start, добавьте функцию в стек и начните отсчет времени. Если лог содержит end, снимите функцию со стека и обновите эксклюзивное время.

3⃣Обновление времени выполнения: Когда функция завершает выполнение, обновите ее эксклюзивное время и также учитывайте время выполнения вложенных функций.

😎 Решение:

class Solution {
    func exclusiveTime(_ n: Int, _ logs: [String]) -> [Int] {
        var stack = [Int]()
        var times = [Int](repeating: 0, count: n)
        var prevTime = 0
        
        for log in logs {
            let parts = log.split(separator: ":")
            let fid = Int(parts[0])!
            let type = String(parts[1])
            let time = Int(parts[2])!
            
            if type == "start" {
                if let last = stack.last {
                    times[last] += time - prevTime
                }
                stack.append(fid)
                prevTime = time
            } else {
                times[stack.removeLast()] += time - prevTime + 1
                prevTime = time + 1
            }
        }
        
        return times
    }
}

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

Задача: 433. Minimum Genetic Mutation
Сложность: medium

Генетическая строка может быть представлена строкой длиной 8 символов, содержащей символы 'A', 'C', 'G' и 'T'.

Предположим, нам нужно исследовать мутацию от генетической строки startGene до генетической строки endGene, где одна мутация определяется как изменение одного символа в генетической строке.

Например, "AACCGGTT" --> "AACCGGTA" является одной мутацией.
Также существует генетический банк bank, который содержит все допустимые генетические мутации. Генетическая строка должна быть в банке, чтобы считаться допустимой.

Даны две генетические строки startGene и endGene и генетический банк bank, верните минимальное количество мутаций, необходимых для мутации от startGene до endGene. Если такой мутации не существует, верните -1.

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

Пример:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

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

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

2⃣Выполняйте BFS. На каждом узле, если node == endGene, верните количество шагов, пройденных до этого момента. В противном случае, итеративно заменяйте каждый символ в строке на один из "A", "C", "G", "T" для нахождения соседей. Для каждого соседа, если он еще не был посещен и находится в bank, добавьте его в очередь и в множество seen.

3⃣Если BFS завершился и endGene не был найден, задача невыполнима. Верните -1.

😎 Решение:

class Solution {
    func minMutation(_ start: String, _ end: String, _ bank: [String]) -> Int {
        var queue: [String] = [start]
        var seen: Set<String> = [start]
        var steps = 0
        
        while !queue.isEmpty {
            for _ in 0..<queue.count {
                let node = queue.removeFirst()
                
                if node == end {
                    return steps
                }
                
                for c in "ACGT" {
                    for i in node.indices {
                        var neighbor = Array(node)
                        neighbor[i] = c
                        let neighborStr = String(neighbor)
                        if !seen.contains(neighborStr) && bank.contains(neighborStr) {
                            queue.append(neighborStr)
                            seen.insert(neighborStr)
                        }
                    }
                }
            }
            steps += 1
        }
        
        return -1
    }
}

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

Задача: 813. Largest Sum of Averages
Сложность: medium

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

Обратите внимание, что при разбиении должны быть использованы все целые числа из nums, и что оценка не обязательно является целым числом.

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

Пример:

Input: nums = [9,1,2,3,9], k = 3
Output: 20.00000
Explanation: 
The best choice is to partition nums into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned nums into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.

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

1⃣Пусть dp(i, k) будет лучшей оценкой для разбиения массива A[i:] на не более чем k частей. Если первая группа, в которую мы разбиваем A[i:], заканчивается перед j, тогда наше разбиение-кандидат имеет оценку average(i, j) + dp(j, k-1), где average(i, j) = (A[i] + A[i+1] + ... + A[j-1]) / (j - i) (деление с плавающей запятой). Мы берем наивысшую оценку из этих вариантов, помня, что разбиение необязательно - dp(i, k) также может быть просто average(i, N).

2⃣В общем случае наша рекурсия выглядит так: dp(i, k) = max(average(i, N), max_{j > i}(average(i, j) + dp(j, k-1))). Мы можем рассчитывать average немного быстрее, используя префиксные суммы. Если P[x+1] = A[0] + A[1] + ... + A[x], тогда average(i, j) = (P[j] - P[i]) / (j - i).

3⃣Наша реализация демонстрирует подход "снизу вверх" для динамического программирования. На шаге k во внешнем цикле, dp[i] представляет собой dp(i, k) из обсуждения выше, и мы рассчитываем следующий слой dp(i, k+1). Завершение второго цикла для i = 0..N-1 означает завершение расчета правильного значения для dp(i, t), а внутренний цикл выполняет расчет max_{j > i}(average(i, j) + dp(j, k)).

😎 Решение:

class Solution {
    func largestSumOfAverages(_ A: [Int], _ K: Int) -> Double {
        var P = [0]
        for x in A { P.append(P.last! + x) }
        
        func average(_ i: Int, _ j: Int) -> Double {
            return Double(P[j] - P[i]) / Double(j - i)
        }
        
        let N = A.count
        var dp = (0..<N).map { average($0, N) }
        for _ in 0..<(K-1) {
            for i in 0..<N {
                for j in i+1..<N {
                    dp[i] = max(dp[i], average(i, j) + dp[j])
                }
            }
        }
        
        return dp[0]
    }
}

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

Задача: 474. Ones and Zeroes
Сложность: medium

Дан массив двоичных строк strs и два целых числа m и n.

Верните размер наибольшего подмножества strs, такого что в подмножестве содержится не более m нулей и n единиц.

Множество x является подмножеством множества y, если все элементы множества x также являются элементами множества y.

Пример:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

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

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

2⃣Считаем количество нулей и единиц в каждом подмножестве.

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

😎 Решение:

class Solution {
    func findMaxForm(_ strs: [String], _ m: Int, _ n: Int) -> Int {
        var maxlen = 0
        for i in 0..<(1 << strs.count) {
            var zeroes = 0, ones = 0, len = 0
            for j in 0..<32 {
                if (i & (1 << j)) != 0 {
                    let count = countZeroesOnes(strs[j])
                    zeroes += count[0]
                    ones += count[1]
                    if zeroes > m || ones > n {
                        break
                    }
                    len += 1
                }
            }
            if zeroes <= m && ones <= n {
                maxlen = max(maxlen, len)
            }
        }
        return maxlen
    }

    func countZeroesOnes(_ s: String) -> [Int] {
        var c = [0, 0]
        for char in s {
            c[Int(char.asciiValue! - Character("0").asciiValue!)] += 1
        }
        return c
    }
}

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

Задача: 209. Minimum Size Subarray Sum
Сложность: medium

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

Пример:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

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

1⃣Инициализация переменных:
Создайте три целочисленные переменные left, right и sumOfCurrentWindow. Переменные left и right формируют подмассив, указывая на начальные и конечные индексы текущего подмассива (или окна), а sumOfCurrentWindow хранит сумму этого окна. Инициализируйте все их значением 0.
Создайте еще одну переменную res для хранения ответа на задачу. Инициализируйте ее большим целым значением.

2⃣Итерация по массиву:
Итерируйте по массиву nums с помощью right, начиная с right = 0 до nums.length - 1, увеличивая right на 1 после каждой итерации. Выполняйте следующее внутри этой итерации:
Добавьте элемент с индексом right к текущему окну, увеличив sumOfCurrentWindow на nums[right].
Проверьте, если sumOfCurrentWindow >= target. Если да, у нас есть подмассив, который удовлетворяет условию. В результате, попытайтесь обновить переменную ответа res длиной этого подмассива. Выполните res = min(res, right - left + 1). Затем удалите первый элемент из этого окна, уменьшив sumOfCurrentWindow на nums[left] и увеличив left на 1. Этот шаг повторяется во внутреннем цикле, пока sumOfCurrentWindow >= target.

3⃣Возврат результата:
Текущая сумма окна теперь меньше target. Нужно добавить больше элементов в окно. В результате, увеличивается right на 1.
Верните res.

😎 Решение:

class Solution {
    func minSubArrayLen(_ target: Int, _ nums: [Int]) -> Int {
        var left = 0, right = 0, sumOfCurrentWindow = 0
        var res = Int.max

        while right < nums.count {
            sumOfCurrentWindow += nums[right]
            right += 1

            while sumOfCurrentWindow >= target {
                res = min(res, right - left)
                sumOfCurrentWindow -= nums[left]
                left += 1
            }
        }

        return res == Int.max ? 0 : res
    }
}

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

Задача: 147. Insertion Sort List
Сложность: medium

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

Шаги алгоритма сортировки вставками:

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

Пример:

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

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

1⃣Создание вспомогательного узла (pseudo_head):
В качестве первого шага создайте вспомогательный узел, который называется pseudo_head. Этот узел будет использоваться как указатель на начало результирующего списка. Этот узел облегчает доступ к результирующему списку, особенно когда необходимо вставить новый элемент в начало списка. Этот прием значительно упрощает логику работы с односвязным списком.

2⃣Механизм вставки узла:
В односвязном списке каждый узел содержит только один указатель, который указывает на следующий узел. Чтобы вставить новый узел (например, B) перед определенным узлом (например, A), необходимо знать узел (например, C), который находится перед узлом A (т.е. C -> A). Имея ссылку на узел C, можно вставить новый узел так, чтобы получилось C -> B -> A.

3⃣Использование пары указателей для вставки:
Используя пару указателей (prev и next), которые служат местом для вставки нового элемента между ними, вставьте новый элемент в список. Это делается путем установки prev -> new_node -> next. Этот метод позволяет точно и безопасно вставлять новые элементы в список, сохраняя при этом правильный порядок элементов без необходимости перемещения других узлов списка.

😎 Решение:

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

class Solution {
    func insertionSortList(_ head: ListNode?) -> ListNode? {
        let dummy = ListNode()
        var curr = head
        
        while let current = curr {
            var prev = dummy
            while let nextNode = prev.next, nextNode.val <= current.val {
                prev = nextNode
            }
            let next = current.next
            current.next = prev.next
            prev.next = current
            curr = next
        }
        
        return dummy.next
    }
}

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

Задача: 303. Range Sum Query - Immutable
Сложность: easy

Дан целочисленный массив nums. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right.
Реализуйте класс NumArray:
- NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums.
- int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]).

Пример:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

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

1⃣Инициализация:
Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums.

2⃣Предварительное вычисление сумм:
Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно.

3⃣Вычисление диапазонной суммы:
Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат.

😎 Решение:

class NumArray {
    private var sum: [Int]

    init(_ nums: [Int]) {
        sum = [Int](repeating: 0, count: nums.count + 1)
        for i in 0..<nums.count {
            sum[i + 1] = sum[i] + nums[i]
        }
    }

    func sumRange(_ i: Int, _ j: Int) -> Int {
        return sum[j + 1] - sum[i]
    }
}

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

Задача: 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
    }
}

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