Swift | LeetCode
Відкрити в Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Показати більше
Сітка:1 335
Підписники
-124 години
-47 днів
-2330 день
Архів дописів
1 335
Привет, ребята!
У нас для вас отличные новости — на easyoffer вышло сразу несколько крупных обновлений:
1. Автоотклики на HeadHunter
Снова работают в полную силу — можно смело возвращаться к активному поиску.
2. Новый раздел «Резюмейкер»
Теперь вы можете быстро создавать уникальные резюме, адаптированные под каждую вакансию, и сразу добавлять сопроводительное письмо. Это заметно повышает шансы получить приглашение на собеседование.
3. База вопросов стала чище
Мы навели порядок и удалили около 30% дубликатов.
Ориентироваться стало проще.
––––––––––––––––––
🔥 Акция в честь обновления
Пожизненный тариф easyoffer PRO — по цене одного года.
Успейте до 23 июня:
👉 https://easyoffer.ru/pro
––––––––––––––––––
Что дальше?
В ближайшие пару недель добавим ещё два раздела:
1. Сообщество с чатами по всем профессиональным направлениям.
2. Агрегатор вакансий, чтобы поиск работы стал ещё удобнее.
1 335
Задача: 1365. How Many Numbers Are Smaller Than the Current Number
Сложность: easy
Дан массив nums. Для каждого элемента nums[i] определите, сколько чисел в массиве меньше его. То есть, для каждого nums[i] вам нужно посчитать количество допустимых j, таких что j != i и nums[j] < nums[i].
Верните ответ в виде массива.
Пример:
Input: nums = [6,5,4,8] Output: [2,1,0,3]👨💻 Алгоритм: 1⃣Создание копии и сортировка массива: Создайте отсортированную копию массива nums, чтобы легко находить количество элементов, меньших текущего. 2⃣Поиск индекса каждого элемента: Для каждого элемента nums[i] найдите его индекс в отсортированной копии массива. Этот индекс указывает количество элементов, меньших nums[i]. 3⃣Формирование ответа: Сформируйте массив ответов, где каждый элемент будет соответствовать количеству чисел, меньших текущего. 😎 Решение:
class Solution {
func smallerNumbersThanCurrent(_ nums: [Int]) -> [Int] {
let sortedNums = nums.sorted()
var result = [Int]()
for num in nums {
result.append(sortedNums.firstIndex(of: num)!)
}
return result
}
}1 335
Задача: 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
}
}1 335
Задача: 141. Linked List Cycle
Сложность: easy
Дана переменная head, которая является началом связного списка. Определите, содержит ли связный список цикл.
Цикл в связном списке существует, если существует узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла. Обратите внимание, что pos не передается в качестве параметра.
Верните true, если в связном списке есть цикл. В противном случае верните false.
Пример:
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).👨💻 Алгоритм: 1⃣Инициализация структуры данных: Создайте хеш-таблицу (или множество) для хранения ссылок на узлы, чтобы отслеживать уже посещённые узлы. 2⃣Обход списка: Перемещайтесь по связному списку, начиная с головы (head), и проверяйте каждый узел по очереди. 3⃣Проверка на цикл: Если текущий узел равен null, это означает, что вы достигли конца списка, и список не имеет циклов. В этом случае верните false. Если текущий узел уже содержится в хеш-таблице, это означает, что вы вернулись к ранее посещённому узлу, и, следовательно, в списке присутствует цикл. Верните true. Если ни одно из этих условий не выполнено, добавьте текущий узел в хеш-таблицу и продолжите обход списка. 😎 Решение:
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int, _ next: ListNode? = nil) {
self.val = val
self.next = next
}
}
class Solution {
func hasCycle(_ head: ListNode?) -> Bool {
var nodesSeen = Set<ListNode>()
var current = head
while current != nil {
if nodesSeen.contains(current!) {
return true
}
nodesSeen.insert(current!)
current = current?.next
}
return false
}
}1 335
Задача: 275. H-Index II
Сложность: medium
Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью, и массив отсортирован в порядке возрастания. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.
Вы должны написать алгоритм, который работает за логарифмическое время.
Пример:
Input: citations = [0,1,3,5,6] Output: 3 Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 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[0: mid - 1] и citations[mid + 1: n]. 2⃣Сравнить количество статей с цитированиями больше или равными citations[mid]: Если citations[mid] == n - mid, то найден h-индекс и его можно вернуть. Если citations[mid] < n - mid, то необходимо искать в правой подмножности citations[mid + 1: n]. Если citations[mid] > n - mid, то необходимо искать в левой подмножности citations[0: mid - 1]. 3⃣Возвращение результата: Продолжать процесс, пока не будет найден h-индекс. Возвратить n - mid, что является количеством статей с цитированиями больше или равными citations[mid]. 😎 Решение:
class Solution {
func hIndex(_ citations: [Int]) -> Int {
let n = citations.count
var left = 0
var right = n - 1
while left <= right {
let mid = left + (right - left) / 2
if citations[mid] == n - mid {
return n - mid
} else if citations[mid] < n - mid {
left = mid + 1
} else {
right = mid - 1
}
}
return n - left
}
}1 335
Задача: 91. Decode Ways
Сложность: medium
Сообщение, содержащее буквы от A до Z, можно закодировать в числа с использованием следующего соответствия:
- 'A' -> "1"
- 'B' -> "2"
- ...
- 'Z' -> "26"
Для декодирования закодированного сообщения все цифры должны быть сгруппированы и затем отображены обратно в буквы с использованием обратного соответствия (существует несколько способов). Например, "11106" можно представить как:
- "AAJF" с группировкой (1 1 10 6)
- "KJF" с группировкой (11 10 6)
Обратите внимание, что группировка (1 11 06) недопустима, потому что "06" не может быть преобразовано в 'F', так как "6" отличается от "06".
Для данной строки s, содержащей только цифры, верните количество способов декодирования.
Тестовые случаи сформированы таким образом, что ответ укладывается в 32-битное целое число.
Пример:
Input: s = "12" Output: 2 Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).👨💻 Алгоритм: 1⃣Входим в рекурсию с данной строкой, начиная с индекса 0. 2⃣Для окончательного случая рекурсии мы проверяем конец строки. Если мы достигли конца строки, возвращаем 1. Каждый раз, когда мы входим в рекурсию, это для подстроки исходной строки. Если первый символ в подстроке равен 0, то прекращаем этот путь, возвращая 0. Таким образом, этот путь не будет влиять на количество способов. 3⃣Мемоизация помогает снизить сложность, которая иначе была бы экспоненциальной. Мы проверяем словарь memo, чтобы увидеть, существует ли уже результат для данной подстроки. Если результат уже находится в memo, мы возвращаем этот результат. В противном случае количество способов для данной строки определяется путем рекурсивного вызова функции с индексом +1 для следующей подстроки и индексом +2 после проверки на валидность двузначного декодирования. Результат также сохраняется в memo с ключом как текущий индекс, чтобы сохранить его для будущих пересекающихся подзадач. 😎 Решение:
import Foundation
class Solution {
private var memo: [Int: Int] = [:]
private func recursiveWithMemo(_ index: Int, _ s: String) -> Int {
if index == s.count {
return 1
}
let startIndex = s.index(s.startIndex, offsetBy: index)
let firstChar = s[startIndex]
if firstChar == "0" {
return 0
}
if index == s.count - 1 {
return 1
}
if let cachedResult = memo[index] {
return cachedResult
}
let nextIndex = s.index(after: startIndex)
var answer = recursiveWithMemo(index + 1, s)
if index < s.count - 1 {
let secondIndex = s.index(after: nextIndex)
let range = startIndex..<secondIndex
let number = Int(s[range])!
if number <= 26 {
answer += recursiveWithMemo(index + 2, s)
}
}
memo[index] = answer
return answer
}
func numDecodings(_ s: String) -> Int {
return recursiveWithMemo(0, s)
}
}1 335
Задача: 1129. Shortest Path with Alternating Colors
Сложность: medium
Вам дано целое число n, количество узлов в ориентированном графе, где узлы помечены от 0 до n - 1. Каждое ребро в этом графе может быть красным или синим, и могут быть самопетли и параллельные ребра.
Вам даны два массива redEdges и blueEdges, где:
redEdges[i] = [ai, bi] указывает, что в графе существует направленное красное ребро от узла ai к узлу bi, и
blueEdges[j] = [uj, vj] указывает, что в графе существует направленное синее ребро от узла uj к узлу vj.
Верните массив answer длины n, где каждый answer[x] — это длина кратчайшего пути от узла 0 до узла x, такого что цвета ребер чередуются вдоль пути, или -1, если такого пути не существует.
Пример:
Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = [] Output: [0,1,-1]👨💻 Алгоритм: 1⃣Создание структуры данных и инициализация: Создайте список смежности adj, который будет содержать пары (сосед, цвет) для каждого узла. Создайте массив answer длиной n, инициализированный значением -1, чтобы хранить длину кратчайшего пути для каждого узла. Создайте 2D массив visit для отслеживания, были ли узлы посещены с использованием ребра определённого цвета. 2⃣Инициализация очереди и начальных условий: Создайте очередь для хранения трёх значений (узел, количество шагов, цвет предыдущего ребра). Добавьте в очередь начальный узел (0, 0, -1) и установите visit[0][0] и visit[0][1] в true, так как повторное посещение узла 0 бессмысленно. 3⃣Обработка очереди и обновление результата: Пока очередь не пуста, извлекайте элемент из очереди и получайте (узел, количество шагов, цвет предыдущего ребра). Для каждого соседа, если сосед не был посещён с использованием ребра текущего цвета и текущий цвет не равен предыдущему, обновите массив answer и добавьте соседа в очередь. 😎 Решение:
class Solution {
func shortestAlternatingPaths(_ n: Int, _ redEdges: [[Int]], _ blueEdges: [[Int]]) -> [Int] {
var adj = [Int: [[Int]]]()
for redEdge in redEdges {
adj[redEdge[0], default: []].append([redEdge[1], 0])
}
for blueEdge in blueEdges {
adj[blueEdge[0], default: []].append([blueEdge[1], 1])
}
var answer = [Int](repeating: -1, count: n)
var visit = Array(repeating: [false, false], count: n)
var queue = [(0, 0, -1)]
answer[0] = 0
visit[0][0] = true
visit[0][1] = true
while !queue.isEmpty {
let (node, steps, prevColor) = queue.removeFirst()
if let neighbors = adj[node] {
for neighbor in neighbors {
let nextNode = neighbor[0]
let color = neighbor[1]
if !visit[nextNode][color] && color != prevColor {
if answer[nextNode] == -1 {
answer[nextNode] = steps + 1
}
visit[nextNode][color] = true
queue.append((nextNode, steps + 1, color))
}
}
}
}
return answer
}
}1 335
Задача: 1200. Minimum Absolute Difference
Сложность: easy
Дан массив различных целых чисел arr, найдите все пары элементов с минимальной абсолютной разницей между любыми двумя элементами.
Верните список пар в порядке возрастания (по отношению к парам), каждая пара [a, b] следует условиям:
a, b из arr
a < b
b - a равна минимальной абсолютной разнице между любыми двумя элементами в arr
Пример:
Input: arr = [4,2,1,3] Output: [[1,2],[2,3],[3,4]] Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.👨💻 Алгоритм: 1⃣Инициализация вспомогательного массива: Найдите минимальный элемент minElement и максимальный элемент maxElement в массиве arr. Инициализируйте вспомогательный массив line размером maxElement - minElement + 1 и установите смещение shift равным -minElement. Пройдите по массиву arr и для каждого элемента value увеличьте значение в индексе value + shift на 1. 2⃣Поиск минимальной абсолютной разницы: Пройдите по вспомогательному массиву line, начиная с индекса, соответствующего минимальному элементу. Проверьте значения на каждом индексе curr: - если line[curr] равно 0, пропустите этот индекс. - если line[curr] равно 1, сравните абсолютную разницу текущей пары currPairDiff с минимальной найденной разницей minPairDiff. - если currPairDiff больше minPairDiff, продолжайте. - если currPairDiff равно minPairDiff, добавьте эту пару в список ответов. - если currPairDiff меньше minPairDiff, очистите список ответов, добавьте эту пару и обновите minPairDiff. 3⃣Возврат результата: После прохождения всех элементов массива line, список ответов будет содержать все пары с минимальной абсолютной разницей. Верните список ответов. 😎 Решение:
class Solution {
func minimumAbsDifference(_ arr: [Int]) -> [[Int]] {
let sortedArr = arr.sorted()
var minDiff = Int.max
var result = [[Int]]()
for i in 1..<sortedArr.count {
let diff = sortedArr[i] - sortedArr[i - 1]
if diff < minDiff {
minDiff = diff
result = [[sortedArr[i - 1], sortedArr[i]]]
} else if diff == minDiff {
result.append([sortedArr[i - 1], sortedArr[i]])
}
}
return result
}
}1 335
Задача: 239. Sliding Window Maximum
Сложность: hard
Вам дан массив целых чисел nums. Существует скользящее окно размера k, которое перемещается с самого левого конца массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.
Верните максимальные значения скользящего окна.
Пример:
Input: nums = [1], k = 1 Output: [1]👨💻 Алгоритм: 1⃣Инициализация и заполнение первой части окна: Создайте двустороннюю очередь dq для хранения индексов элементов и список res для хранения результатов. Пройдите по первым k элементам массива nums (от i = 0 до k - 1). Для каждого элемента: Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i]. Добавьте текущий индекс i в конец dq. Добавьте в res максимальный элемент первого окна, который находится в nums[dq[0]]. 2⃣Сканирование оставшейся части массива: Пройдите по оставшимся элементам массива nums (от i = k до n - 1). Для каждого элемента: Если индекс элемента на передней части dq равен i - k, удалите этот элемент из dq, так как он выходит за пределы текущего окна. Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i]. Добавьте текущий индекс i в конец dq. Добавьте в res максимальный элемент текущего окна, который находится в nums[dq[0]]. 3⃣Возвращение результата: Верните список res, содержащий максимальные элементы для каждого скользящего окна. 😎 Решение:
class Solution {
func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
var dq = [Int]()
var res = [Int]()
for i in 0..<k {
while !dq.isEmpty && nums[i] >= nums[dq.last!] {
dq.removeLast()
}
dq.append(i)
}
res.append(nums[dq.first!])
for i in k..<nums.count {
if dq.first == i - k {
dq.removeFirst()
}
while !dq.isEmpty && nums[i] >= nums[dq.last!] {
dq.removeLast()
}
dq.append(i)
res.append(nums[dq.first!])
}
return res
}
}1 335
Задача: 965. Univalued Binary Tree
Сложность: easy
Бинарное дерево является одноценным, если каждый узел в дереве имеет одинаковое значение.
Дан корень бинарного дерева, верните true, если данное дерево является одноценным, или false в противном случае.
Пример:
Input: root = [1,1,1,1,1,null,1] Output: true👨💻 Алгоритм: 1⃣Выполните обход дерева в глубину (DFS), чтобы собрать все значения узлов в список. 2⃣Проверьте, что все значения в списке одинаковы. 3⃣Если все значения одинаковы, верните true, иначе верните false. 😎 Решение:
class Solution {
var vals: [Int] = []
func isUnivalTree(_ root: TreeNode?) -> Bool {
dfs(root)
for v in vals {
if v != vals[0] {
return false
}
}
return true
}
func dfs(_ node: TreeNode?) {
if let node = node {
vals.append(node.val)
dfs(node.left)
dfs(node.right)
}
}
}1 335
Задача: 1318. Minimum Flips to Make a OR b Equal to c
Сложность: medium
Даны три положительных числа a, b и c. Верните минимальное количество переворотов, необходимых в некоторых битах a и b, чтобы сделать (a OR b == c) (побитовая операция OR). Операция переворота состоит из изменения любого отдельного бита с 1 на 0 или с 0 на 1 в их двоичном представлении.
Пример:
Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)class Solution {
func minFlips(_ a: Int, _ b: Int, _ c: Int) -> Int {
var a = a, b = b, c = c
var answer = 0
while a != 0 || b != 0 || c != 0 {
if (c & 1) == 1 {
if (a & 1) == 0 && (b & 1) == 0 {
answer += 1
}
} else {
answer += (a & 1) + (b & 1)
}
a >>= 1
b >>= 1
c >>= 1
}
return answer
}
}1 335
Задача: 252. Meeting Rooms
Сложность: easy
Дан массив интервалов времени встреч, где intervals[i] = [starti, endi]. Определите, может ли человек посетить все встречи.
Пример:
Input: intervals = [[0,30],[5,10],[15,20]] Output: false👨💻 Алгоритм: 1⃣Создайте функцию для проверки перекрытия двух интервалов: Возвращайте true, если начало одного интервала находится внутри другого интервала. 2⃣Проверьте каждый интервал с каждым другим интервалом: Если найдено перекрытие, верните false. 3⃣Если все интервалы проверены и перекрытий не найдено, верните true. 😎 Решение:
class Solution {
func overlap(_ interval1: [Int], _ interval2: [Int]) -> Bool {
return (interval1[0] >= interval2[0] && interval1[0] < interval2[1]) ||
(interval2[0] >= interval1[0] && interval2[0] < interval1[1])
}
func canAttendMeetings(_ intervals: [[Int]]) -> Bool {
for i in 0..<intervals.count {
for j in i + 1..<intervals.count {
if overlap(intervals[i], intervals[j]) {
return false
}
}
}
return true
}
}1 335
Задача: 719. Find K-th Smallest Pair Distance
Сложность: hard
Расстояние между парой целых чисел a и b определяется как абсолютная разность между a и b. Учитывая целочисленный массив nums и целое число k, верните k-е наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 <= i < j < nums.length.
Пример:
Input: nums = [1,3,1], k = 1 Output: 0👨💻 Алгоритм: 1⃣Отсортируйте массив nums. 2⃣Определите минимальное и максимальное возможные расстояния. 3⃣Используйте бинарный поиск, чтобы найти k-е наименьшее расстояние, проверяя количество пар с расстоянием меньше или равно текущему среднему значению. 😎 Решение:
func smallestDistancePair(_ nums: [Int], _ k: Int) -> Int {
let nums = nums.sorted()
func countPairs(_ mid: Int) -> Int {
var count = 0, j = 0
for i in 0..<nums.count {
while j < nums.count && nums[j] - nums[i] <= mid {
j += 1
}
count += j - i - 1
}
return count
}
var left = 0, right = nums.last! - nums.first!
while left < right {
let mid = (left + right) / 2
if countPairs(mid) < k {
left = mid + 1
} else {
right = mid
}
}
return left
}1 335
Задача: 1182. Shortest Distance to Target Color
Сложность: medium
Дан массив colors, содержащий три цвета: 1, 2 и 3.
Также даны несколько запросов. Каждый запрос состоит из двух целых чисел i и c. Верните наименьшее расстояние между заданным индексом i и целевым цветом c. Если решения нет, верните -1.
Пример:
Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation:
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).class Solution {
func shortestDistanceColor(_ colors: [Int], _ queries: [[Int]]) -> [Int] {
var queryResults = [Int]()
var hashmap = [Int: [Int]]()
for i in 0..<colors.count {
hashmap[colors[i], default: [Int]()].append(i)
}
for query in queries {
let target = query[0]
let color = query[1]
guard let indexList = hashmap[color] else {
queryResults.append(-1)
continue
}
let insert = indexList.binarySearch(target)
if insert < 0 {
let insertPos = -(insert + 1)
if insertPos == 0 {
queryResults.append(indexList[insertPos] - target)
} else if insertPos == indexList.count {
queryResults.append(target - indexList[insertPos - 1])
} else {
let leftNearest = target - indexList[insertPos - 1]
let rightNearest = indexList[insertPos] - target
queryResults.append(min(leftNearest, rightNearest))
}
} else {
queryResults.append(0)
}
}
return queryResults
}
}
extension Array where Element: Comparable {
func binarySearch(_ value: Element) -> Int {
var left = 0
var right = self.count - 1
while left <= right {
let mid = (left + right) / 2
if self[mid] == value {
return mid
} else if self[mid] < value {
left = mid + 1
} else {
right = mid - 1
}
}
return -(left + 1)
}
}1 335
Главный навык на ближайшие годы — ВАЙБ-КОДИНГ
ИИ уже пишет код, чинит баги, генерирует тесты, документацию и помогает запускать продукты быстрее, чем это делали классические команды разработки. И это уже не "будущее когда-нибудь", а реальность, которая меняет рынок уже сегодня
И те, кто научится вайбкодить сейчас, будут увереннее конкурировать на рынке и зарабатывать больше тех, кто по-прежнему делает всё вручную.
Стартовать с нуля поможет канал Вайб-кодинг. Там ребята круглосуточно мониторят более 320 российских и зарубежных источников и публикуют только главное: релизы, инструменты, гайды, курсы и практические кейсы.
Подписывайтесь, нас уже 30 тысяч: @vibecoding_tg
1 335
Задача: 968. Binary Tree Cameras
Сложность: hard
Вам дан корень бинарного дерева. Мы устанавливаем камеры на узлы дерева, где каждая камера на узле может наблюдать за своим родителем, собой и своими непосредственными детьми.
Верните минимальное количество камер, необходимых для наблюдения за всеми узлами дерева.
Пример:
Input: root = [0,0,null,0,null,0,null,null,0] Output: 2 Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.👨💻 Алгоритм: 1⃣Рекурсивное решение (solve): Для каждого узла определите три состояния: - [State 0] Строгое поддерево: все узлы ниже этого узла покрыты, но не сам узел. - [State 1] Нормальное поддерево: все узлы ниже и включая этот узел покрыты, но на этом узле нет камеры. - [State 2] Установленная камера: все узлы ниже и включая этот узел покрыты, и на этом узле установлена камера. Рассчитайте эти состояния для левого и правого поддеревьев. 2⃣Рассчёт состояний: Чтобы покрыть строгое поддерево, дети этого узла должны находиться в состоянии 1. Чтобы покрыть нормальное поддерево без установки камеры на этом узле, дети этого узла должны находиться в состояниях 1 или 2, и по крайней мере один из этих детей должен быть в состоянии 2. Чтобы покрыть поддерево при установке камеры на этом узле, дети могут находиться в любом состоянии. 3⃣Минимальное количество камер: Запустите функцию solve на корневом узле и верните минимальное значение между состояниями 1 и 2. 😎 Решение:
class Solution {
func minCameraCover(_ root: TreeNode?) -> Int {
let ans = solve(root)
return min(ans[1], ans[2])
}
func solve(_ node: TreeNode?) -> [Int] {
if node == nil {
return [0, 0, 99999]
}
let L = solve(node?.left)
let R = solve(node?.right)
let mL12 = min(L[1], L[2])
let mR12 = min(R[1], R[2])
let d0 = L[1] + R[1]
let d1 = min(L[2] + mR12, R[2] + mL12)
let d2 = 1 + min(L[0], mL12) + min(R[0], mR12)
return [d0, d1, d2]
}
}1 335
Задача: 1134. Armstrong Number
Сложность: easy
Дано целое число n, верните true, если и только если оно является числом Армстронга.
k-значное число n является числом Армстронга, если сумма k-й степени каждой его цифры равна n.
Пример:
Input: n = 153 Output: true Explanation: 153 is a 3-digit number, and 153 = 1^3 + 5^3 + 3^3.👨💻 Алгоритм: 1⃣Получите количество цифр в n, преобразовав его в строку и найдя длину. 2⃣Создайте функцию getSumOfKthPowerOfDigits(n, k), которая возвращает сумму k-й степени каждой цифры числа n. Инициализируйте переменную result для хранения результата. Пока n не равно 0, добавляйте k-ю степень последней цифры n к result и удаляйте последнюю цифру. 3⃣Верните true, если результат равен исходному числу n. 😎 Решение:
class Solution {
func getSumOfKthPowerOfDigits(_ n: Int, _ k: Int) -> Int {
var result = 0
var number = n
while number != 0 {
let digit = number % 10
result += Int(pow(Double(digit), Double(k)))
number /= 10
}
return result
}
func isArmstrong(_ n: Int) -> Bool {
let length = String(n).count
return getSumOfKthPowerOfDigits(n, length) == n
}
}1 335
Задача: 1056. Confusing Number
Сложность: easy
Запутанное число - это число, которое при повороте на 180 градусов становится другим числом, каждая цифра которого действительна. Мы можем повернуть цифры числа на 180 градусов, чтобы получить новые цифры. Когда 0, 1, 6, 8 и 9 поворачиваются на 180 градусов, они становятся 0, 1, 9, 8 и 6 соответственно.
При повороте на 180 градусов 2, 3, 4, 5 и 7 становятся недействительными. Обратите внимание, что после поворота числа мы можем игнорировать ведущие нули. Например, после поворота 8000 мы получим 0008, которое считается просто 8. Если задано целое число n, верните true, если это запутанное число, или false в противном случае.
Пример:
Input: n = 6 Output: true👨💻 Алгоритм: 1⃣Преобразуй число в строку для удобства работы с его цифрами. Используй словарь для хранения соответствий цифр при повороте на 180 градусов. 2⃣Пройди по цифрам числа, проверяя, что все цифры действительны и заменяя их на соответствующие при повороте. 3⃣Проверь, что перевернутая строка отличается от исходной. 😎 Решение:
func isConfusingNumber(_ n: Int) -> Bool {
let rotationMap: [Character: Character] = ["0": "0", "1": "1", "6": "9", "8": "8", "9": "6"]
let nStr = String(n)
var rotatedStr = ""
for char in nStr {
guard let rotatedChar = rotationMap[char] else {
return false
}
rotatedStr = String(rotatedChar) + rotatedStr
}
return rotatedStr != nStr
}1 335
Задача: 290. Word Pattern
Сложность: easy
Дан шаблон и строка s, необходимо определить, следует ли строка s этому шаблону.
Здесь "следует" означает полное соответствие, такое что существует биекция между буквой в шаблоне и непустым словом в строке s.
Пример:
Input: pattern = "abba", s = "dog cat cat dog" Output: true👨💻 Алгоритм: 1⃣Разделение строки на слова: Разделите строку s на отдельные слова. Если количество слов не равно длине шаблона, возвращаем false. 2⃣Создание отображений: Создайте два словаря: один для отображения букв шаблона на слова, другой для слов на буквы шаблона. 3⃣Проверка биекции: Пройдите по каждому символу шаблона и соответствующему слову. Если символ уже в словаре и не соответствует текущему слову или слово уже в словаре и не соответствует текущему символу, возвращаем false. Иначе добавляем символ и слово в словари и продолжаем проверку. Если все проверки пройдены, возвращаем true. 😎 Решение:
class Solution {
func wordPattern(_ pattern: String, _ s: String) -> Bool {
var mapChar = [Character: String]()
var mapWord = [String: Character]()
let words = s.split(separator: " ")
if words.count != pattern.count {
return false
}
for (i, word) in words.enumerated() {
let c = pattern[pattern.index(pattern.startIndex, offsetBy: i)]
let w = String(word)
if mapChar[c] == nil {
if mapWord[w] != nil {
return false
} else {
mapChar[c] = w
mapWord[w] = c
}
} else {
if mapChar[c] != w {
return false
}
}
}
return true
}
}1 335
Задача: 940. Distinct Subsequences II
Сложность: hard
Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (Например, "ace" является подпоследовательностью "abcde", а "aec" - нет.
Пример:
Input: s = "abc" Output: 7👨💻 Алгоритм: 1⃣Определить матрицу DP, где dp[i][j] будет хранить количество подпоследовательностей строки s с длиной i, оканчивающихся символом j. 2⃣Инициализировать матрицу DP нулями. Пройти по каждому символу строки: Если символ еще не был встречен, все подпоследовательности до текущего символа + текущий символ. Если символ уже был встречен, учет всех подпоследовательностей, включающих текущий символ, с учетом предыдущих вхождений. 3⃣Вернуть сумму всех значений в DP по модулю 10^9 + 7. 😎 Решение:
class Solution {
func countSubsequences(_ s: String) -> Int {
let MOD = 1000000007
var dp = [Int](repeating: 0, count: 26)
for c in s {
let index = Int(c.asciiValue! - Character("a").asciiValue!)
dp[index] = (dp.reduce(0, +) + 1) % MOD
}
return dp.reduce(0, +) % MOD
}
}