现已上线！2025 年 Telegram 研究 — 年度关键洞察 
Swift | LeetCode
前往频道在 Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
显示更多1 349
订阅者
-224 小时
-47 天
-1630 天
帖子存档
1 348
Задача: 188. Best Time to Buy and Sell Stock IV
Сложность: hard
Дан массив целых чисел prices, где prices[i] - это цена данной акции в i-й день, и целое число k.
Найдите максимальную прибыль, которую вы можете получить. Вы можете завершить не более чем k транзакций, т.е. вы можете купить не более k раз и продать не более k раз.
Обратите внимание: Вы не можете участвовать в нескольких транзакциях одновременно (т.е., вы должны продать акцию, прежде чем снова купить).
Пример:
Input: k = 2, prices = [2,4,1] Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.👨💻 Алгоритм: 1⃣Инициализация DP массива: Инициализируйте трехмерный массив dp, где dp[i][j][l] представляет максимальную прибыль на конец i-го дня с j оставшимися транзакциями и l акциями в портфеле. Начните с dp[0][0][0] = 0 (нет прибыли без акций и транзакций) и dp[0][1][1] = -prices[0] (покупка первой акции). 2⃣Вычисление переходов: Для каждого дня и каждого возможного количества транзакций вычислите возможные действия: держать акцию, не держать акцию, купить акцию, если j > 0, или продать акцию. Обновляйте dp с использованием: dp[i][j][1] = max(dp[i−1][j][1], dp[i−1][j−1][0] - prices[i]) (максимум между удержанием акции и покупкой новой). dp[i][j][0] = max(dp[i−1][j][0], dp[i−1][j][1] + prices[i]) (максимум между неудержанием акции и продажей). 3⃣Расчет результатов: По завершении всех дней, возвращайте максимальное значение dp[n-1][j][0] для всех j от 0 до k, что представляет максимальную прибыль без удержания акций на последний день. Обработайте специальный случай, когда 𝑘×2≥𝑛, чтобы избежать лишних расчетов. 😎 Решение:
class Solution {
func maxProfit(_ k: Int, _ prices: [Int]) -> Int {
let n = prices.count
if n <= 0 || k <= 0 { return 0 }
if k * 2 >= n {
return prices.dropFirst().enumerated().reduce(0) { $0 + max(0, prices[$1.offset + 1] - prices[$1.offset]) }
}
var dp = Array(repeating: Array(repeating: [Int.min / 2, Int.min / 2], count: k + 1), count: n)
dp[0][0][0] = 0
dp[0][1][1] = -prices[0]
for i in 1..<n {
for j in 0...k {
dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])
if j > 0 {
dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])
}
}
}
return dp[n - 1].map { $0[0] }.max() ?? 0
}
}1 348
Задача: №18. 4Sum
Сложность: medium
Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что:
- 0 <= a, b, c, d < n
- a, b, c и d различны.
- nums[a] + nums[b] + nums[c] + nums[d] == target
Вы можете вернуть ответ в любом порядке.
Пример:
Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]👨💻 Алгоритм: 1⃣Отсортировать массив для удобного пропуска дубликатов и эффективного поиска. 2⃣Использовать два вложенных цикла для выбора первых двух чисел и два указателя для поиска оставшихся двух чисел. 3⃣Обрабатывать дубликаты, чтобы избежать повторяющихся четверок. 😎 Решение:
class Solution {
func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
let len = nums.count
guard len >= 4 else { return [] }
var result = [[Int]]()
let sort = nums.sorted()
for a in 0..<(len - 3) {
if a > 0, sort[a] == sort[a - 1] { continue }
for b in (a + 1)..<(len - 2) {
if b > a + 1, sort[b] == sort[b - 1] { continue }
var c = b + 1, d = len - 1
while c < d {
let sum = sort[a] + sort[b] + sort[c] + sort[d]
if sum == target {
result.append([sort[a], sort[b], sort[c], sort[d]])
repeat { c += 1 } while c < d && sort[c] == sort[c - 1]
repeat { d -= 1 } while c < d && sort[d] == sort[d + 1]
} else if sum < target {
c += 1
} else {
d -= 1
}
}
}
}
return result
}
}1 348
Задача: 315. Count of Smaller Numbers After Self
Сложность: hard
Дан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i].
Пример:
Input: nums = [5,2,6,1] Output: [2,1,1,0] Explanation: To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.👨💻 Алгоритм: 1⃣Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4. 2⃣Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия: Смещайте число на num + offset. Запросите количество элементов в дереве отрезков, которые меньше текущего числа. Обновите счетчик текущего числа в дереве отрезков. 3⃣Верните результат. 😎 Решение:
class Solution {
func countSmaller(_ nums: [Int]) -> [Int] {
let offset = 10000
let size = 2 * 10000 + 1
var tree = [Int](repeating: 0, count: size * 2)
var result = [Int]()
for num in nums.reversed() {
let smallerCount = query(0, num + offset, tree, size)
result.append(smallerCount)
update(num + offset, 1, tree, size)
}
return result.reversed()
}
private func update(_ index: Int, _ value: Int, _ tree: inout [Int], _ size: Int) {
var idx = index + size
tree[idx] += value
while idx > 1 {
idx /= 2
tree[idx] = tree[idx * 2] + tree[idx * 2 + 1]
}
}
private func query(_ left: Int, _ right: Int, _ tree: [Int], _ size: Int) -> Int {
var result = 0
var l = left + size
var r = right + size
while l < r {
if l % 2 == 1 {
result += tree[l]
l += 1
}
l /= 2
if r % 2 == 1 {
r -= 1
result += tree[r]
}
r /= 2
}
return result
}
}1 348
Задача: 634. Find the Derangement of An Array
Сложность: medium
В комбинаторной математике отклонение - это перестановка элементов множества таким образом, что ни один элемент не оказывается на прежнем месте. Вам дано целое число n. Изначально имеется массив, состоящий из n целых чисел от 1 до n в порядке возрастания, верните количество отклонений, которые он может породить. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.
Пример:
Input: n = 3 Output: 2👨💻 Алгоритм: 1⃣Инициализация массива для хранения результатов Создайте массив dp для хранения количества отклонений для каждого значения от 0 до n. Установите начальные значения: dp[0] = 1 и dp[1] = 0. 2⃣Вычисление количества отклонений Используйте динамическое программирование для вычисления количества отклонений для каждого значения от 2 до n. Формула для вычисления: dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD. 3⃣Возвращение результата Верните значение dp[n], которое будет количеством отклонений для n элементов, по модулю 10^9 + 7. 😎 Решение:
import Foundation
func countDerangements(_ n: Int) -> Int {
let MOD = 1_000_000_007
if n == 0 {
return 1
}
if n == 1 {
return 0
}
var dp = [Int](repeating: 0, count: n + 1)
dp[0] = 1
dp[1] = 0
for i in 2...n {
dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD
}
return dp[n]
}1 348
Задача: 201. Bitwise AND of Numbers Range
Сложность: medium
Даны два целых числа left и right, которые представляют диапазон [left, right], верните побитовое И всех чисел в этом диапазоне включительно.
Пример:
Input: left = 5, right = 7 Output: 4👨💻 Алгоритм: 1⃣Сдвигать left и right вправо, пока они не станут равными. 2⃣Подсчитать количество сдвигов. 3⃣Сдвинуть left влево на количество сдвигов и вернуть результат. 😎 Решение:
class Solution {
func rangeBitwiseAnd(_ left: Int, _ right: Int) -> Int {
var left = left
var right = right
var shift = 0
while left < right {
left >>= 1
right >>= 1
shift += 1
}
return left << shift
}
}1 348
Задача: 1137. N-th Tribonacci Number
Сложность: easy
Трибоначчи последовательность Tn определяется следующим образом:
T0 = 0, T1 = 1, T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 для n >= 0.
Дано n, вернуть значение Tn.
Пример:
Input: n = 4 Output: 4 Explanation: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4👨💻 Алгоритм: 1⃣Если n < 3, вернуть значение n-го терма, как указано в описании задачи. 2⃣Инициализировать a, b и c как базовые случаи. Установить a = 0, b = 1, c = 1. 3⃣Для следующих n - 2 шагов обновлять a, b, c следующим образом: a = b, b = c, c = a + b + c. Вернуть c. 😎 Решение:
class Solution {
func tribonacci(_ n: Int) -> Int {
if n < 3 {
return n > 0 ? 1 : 0
}
var a = 0, b = 1, c = 1
for _ in 0..<n-2 {
let tmp = a + b + c
a = b
b = c
c = tmp
}
return c
}
}1 348
Задача: 491. Non-decreasing Subsequences
Сложность: medium
Дан массив целых чисел nums. Верните все возможные различные неубывающие подпоследовательности данного массива, содержащие как минимум два элемента. Вы можете вернуть ответ в любом порядке.
Пример:
Input: nums = [4,6,7,7] Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]👨💻 Алгоритм: 1⃣Инициализация и запуск функции обратного отслеживания Создайте множество для хранения результатов. Создайте список для хранения текущей последовательности. Запустите рекурсивную функцию обратного отслеживания с начальным индексом 0. 2⃣Функция обратного отслеживания Если текущий индекс равен длине массива, проверьте длину текущей последовательности и добавьте её в результат, если она содержит не менее двух элементов. Если текущая последовательность остаётся неубывающей после добавления текущего элемента массива, добавьте этот элемент, вызовите рекурсивную функцию для следующего индекса и удалите элемент из последовательности (обратное отслеживание). Всегда вызывайте рекурсивную функцию для следующего индекса без добавления текущего элемента. 3⃣Возврат результата После завершения всех рекурсивных вызовов преобразуйте множество результатов в список и верните его. 😎 Решение:
class Solution {
func findSubsequences(_ nums: [Int]) -> [[Int]] {
var result = Set<[Int]>()
var sequence = [Int]()
backtrack(nums, 0, &sequence, &result)
return Array(result)
}
func backtrack(_ nums: [Int], _ index: Int, _ sequence: inout [Int], _ result: inout Set<[Int]>) {
if index == nums.count {
if sequence.count >= 2 {
result.insert(sequence)
}
return
}
if sequence.isEmpty || sequence.last! <= nums[index] {
sequence.append(nums[index])
backtrack(nums, index + 1, &sequence, &result)
sequence.removeLast()
}
backtrack(nums, index + 1, &sequence, &result)
}
}1 348
Задача: 815. Bus Routes
Сложность: hard
Дан массив routes, представляющий автобусные маршруты, где routes[i] - это автобусный маршрут, который i-й автобус повторяет бесконечно.
Например, если routes[0] = [1, 5, 7], это означает, что 0-й автобус путешествует в последовательности 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... бесконечно.
Вы начинаете на автобусной остановке source (вы изначально не находитесь в автобусе) и хотите добраться до автобусной остановки target. Перемещаться между автобусными остановками можно только на автобусах.
Верните наименьшее количество автобусов, которые вам нужно взять, чтобы доехать от source до target. Верните -1, если это невозможно.
Пример:
Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.class Solution {
func numBusesToDestination(_ routes: [[Int]], _ source: Int, _ target: Int) -> Int {
if source == target { return 0 }
var adjList = [Int: [Int]]()
for route in 0..<routes.count {
for stop in routes[route] {
adjList[stop, default: []].append(route)
}
}
var q = [Int]()
var vis = Set<Int>()
for route in adjList[source] ?? [] {
q.append(route)
vis.insert(route)
}
var busCount = 1
while !q.isEmpty {
for _ in 0..<q.count {
let route = q.removeFirst()
for stop in routes[route] {
if stop == target { return busCount }
for nextRoute in adjList[stop] ?? [] {
if !vis.contains(nextRoute) {
vis.insert(nextRoute)
q.append(nextRoute)
}
}
}
}
busCount += 1
}
return -1
}
}1 348
Задача: 1422. Maximum Score After Splitting a String
Сложность: easy
Дана строка s из нулей и единиц. Верните максимальное количество очков после разбиения строки на две непустые подстроки (т.е. левую подстроку и правую подстроку).
Количество очков после разбиения строки - это количество нулей в левой подстроке плюс количество единиц в правой подстроке.
Пример:
Input: s = "011101" Output: 5 Explanation: All possible ways of splitting s into two non-empty substrings are: left = "0" and right = "11101", score = 1 + 4 = 5 left = "01" and right = "1101", score = 1 + 3 = 4 left = "011" and right = "101", score = 1 + 2 = 3 left = "0111" and right = "01", score = 1 + 1 = 2 left = "01110" and right = "1", score = 2 + 1 = 3👨💻 Алгоритм: 1⃣Посчитайте количество единиц в строке и инициализируйте счётчики нулей и максимального значения. 2⃣Перебирайте символы строки до предпоследнего символа, обновляя счётчики нулей и единиц. 3⃣Обновляйте максимальное значение, если текущая сумма нулей и единиц больше предыдущего максимума. 😎 Решение:
class Solution {
func maxScore(_ s: String) -> Int {
let ones = s.filter { $0 == "1" }.count
var zeros = 0, ans = 0, countOnes = ones
for i in 0..<s.count - 1 {
let char = s[s.index(s.startIndex, offsetBy: i)]
if char == "1" {
countOnes -= 1
} else {
zeros += 1
}
ans = max(ans, zeros + countOnes)
}
return ans
}
}1 348
Задача: 412. Fizz Buzz
Сложность: easy
Учитывая целое число n, верните строковый массив answer (с индексом 1), где: answer[i] == "FizzBuzz", если i делится на 3 и 5. answer[i] == "Fizz", если i делится на 3. answer[i] == "Buzz", если i делится на 5. answer[i] == i (как строка), если ни одно из перечисленных условий не верно.
Пример:
Input: n = 3
Output: ["1","2","Fizz"]func fizzBuzz(_ n: Int) -> [String] {
var answer = [String]()
for i in 1...n {
if i % 3 == 0 && i % 5 == 0 {
answer.append("FizzBuzz")
} else if i % 3 == 0 {
answer.append("Fizz")
} else if i % 5 == 0 {
answer.append("Buzz")
} else {
answer.append(String(i))
}
}
return answer
}1 348
Задача: 1243. Array Transformation
Сложность: easy
Если задан исходный массив arr, то каждый день вы создаете новый массив, используя массив предыдущего дня. В i-й день вы выполняете следующие операции над массивом дня i-1, чтобы получить массив дня i: если элемент меньше своего левого и правого соседа, то этот элемент увеличивается. Если элемент больше своего левого и правого соседа, то этот элемент уменьшается. Первый и последний элементы никогда не меняются. Через несколько дней массив не меняется. Верните этот окончательный массив.
Пример:
Input: arr = [6,2,3,4] Output: [6,3,3,4]👨💻 Алгоритм: 1⃣Инициализация нового массива с такими же значениями, как у исходного массива. Циклически изменяем массив в соответствии с правилами, пока он не перестанет меняться. 2⃣Для каждого элемента массива проверяем, изменяется ли он в зависимости от его левого и правого соседей. Если элемент меньше своего левого и правого соседей, увеличиваем его. Если элемент больше своего левого и правого соседей, уменьшаем его. 3⃣Первый и последний элементы массива остаются неизменными. 😎 Решение:
class Solution {
func transformArray(_ arr: [Int]) -> [Int] {
var arr = arr
var changed = false
repeat {
changed = false
var newArr = arr
for i in 1..<arr.count - 1 {
if arr[i] < arr[i - 1] && arr[i] < arr[i + 1] {
newArr[i] += 1
changed = true
} else if arr[i] > arr[i - 1] && arr[i] > arr[i + 1] {
newArr[i] -= 1
changed = true
}
}
arr = newArr
} while changed
return arr
}
}1 348
Задача: 1278. Palindrome Partitioning III
Сложность: hard
Вам дана строка s, содержащая строчные буквы, и целое число k. Вам нужно: Сначала заменить некоторые символы s на другие строчные английские буквы. Затем разделить s на k непустых непересекающихся подстрок так, чтобы каждая подстрока была палиндромом. Верните минимальное количество символов, которое нужно изменить, чтобы разделить строку.
Пример:
Input: s = "abc", k = 2 Output: 1👨💻 Алгоритм: 1⃣Используйте динамическое программирование для вычисления количества изменений, необходимых для превращения любой подстроки в палиндром. 2⃣Используйте еще одно динамическое программирование для разбиения строки на k палиндромических подстрок с минимальным количеством изменений. 3⃣Верните минимальное количество изменений, найденное во втором шаге. 😎 Решение:
class Solution {
func minChangesToMakePalindrome(_ s: String, _ k: Int) -> Int {
let n = s.count
let sArray = Array(s)
func minChangeToPalindrome(_ i: Int, _ j: Int) -> Int {
var changes = 0
var i = i
var j = j
while i < j {
if sArray[i] != sArray[j] {
changes += 1
}
i += 1
j -= 1
}
return changes
}
var dp1 = Array(repeating: Array(repeating: 0, count: n), count: n)
for length in 1...n {
for i in 0...(n - length) {
let j = i + length - 1
dp1[i][j] = minChangeToPalindrome(i, j)
}
}
var dp2 = Array(repeating: Array(repeating: Int.max, count: k + 1), count: n + 1)
dp2[0][0] = 0
for i in 1...n {
for kk in 1...k {
for j in 0..<i {
dp2[i][kk] = min(dp2[i][kk], dp2[j][kk - 1] + dp1[j][i - 1])
}
}
}
return dp2[n][k]
}
}1 348
Задача: 1663. Smallest String With A Given Numeric Value
Сложность: medium
Числовое значение строчной буквы определяется ее позицией (начиная с 1) в алфавите, поэтому числовое значение a равно 1, числовое значение b равно 2, числовое значение c равно 3 и так далее.
Числовое значение строки, состоящей из строчных букв, определяется как сумма числовых значений ее символов. Например, числовое значение строки "abe" равно 1 + 2 + 5 = 8.
Вам даны два целых числа n и k. Верните лексикографически наименьшую строку длиной n с числовым значением, равным k.
Обратите внимание, что строка x лексикографически меньше строки y, если x идет перед y в словарном порядке, то есть либо x является префиксом y, либо, если i - первая позиция, где x[i] != y[i], то x[i] идет перед y[i] в алфавитном порядке.
Пример:
Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.class Solution {
func getSmallestString(_ n: Int, _ k: Int) -> String {
var result = Array(repeating: "a", count: n)
var k = k
for position in 0..<n {
let positionsLeft = (n - position - 1)
if k > positionsLeft * 26 {
let add = k - (positionsLeft * 26)
result[position] = String(UnicodeScalar(97 + add - 1)!)
k -= add
} else {
k -= 1
}
}
return result.joined()
}
}1 348
Задача: 27. Remove Element
Сложность: easy
Учитывая целочисленный массив
nums и целочисленное значение val, удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов, которые не равны val.
Пример:
Input: nums = [3,2,2,3], val = 3 Output: 2👨💻Алгоритм: 1⃣Используем указатель
k для отслеживания позиции, куда вставлять элементы, не равные val.
2⃣Проходим по массиву и при нахождении элемента, отличного от val, записываем его на позицию k, затем увеличиваем k.
3⃣В конце k будет содержать количество элементов, которые не равны val.
😎Решение:
func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
var k = 0
for i in 0..<nums.count {
if nums[i] != val {
nums[k] = nums[i]
k += 1
}
}
return k
}1 348
Задача: 716. Max Stack
Сложность: hard
Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова.
Пример:
Input ["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"] [[], [5], [1], [5], [], [], [], [], [], []] Output [null, null, null, null, 5, 5, 1, 5, 1, 5]👨💻 Алгоритм: 1⃣Инициализируйте MaxStack с двумя стеками: один для хранения всех элементов, другой для отслеживания максимальных элементов. 2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека. 3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно. 😎 Решение:
class MaxStack {
private var stack: [Int]
private var maxStack: [Int]
init() {
stack = []
maxStack = []
}
func push(_ x: Int) {
stack.append(x)
if maxStack.isEmpty || x >= maxStack.last! {
maxStack.append(x)
}
}
func pop() -> Int {
let x = stack.removeLast()
if x == maxStack.last! {
maxStack.removeLast()
}
return x
}
func top() -> Int {
return stack.last!
}
func peekMax() -> Int {
return maxStack.last!
}
func popMax() -> Int {
let maxVal = maxStack.removeLast()
var buffer: [Int] = []
while stack.last! != maxVal {
buffer.append(stack.removeLast())
}
stack.removeLast()
while !buffer.isEmpty {
push(buffer.removeLast())
}
return maxVal
}
}1 348
Задача: 1319. Number of Operations to Make Network Connected
Сложность: medium
Дано n компьютеров, пронумерованных от 0 до n - 1, соединённых Ethernet-кабелями connections, образующими сеть, где connections[i] = [ai, bi] представляет собой соединение между компьютерами ai и bi. Любой компьютер может достичь любого другого компьютера напрямую или косвенно через сеть.
Вам даны начальные соединения сети. Вы можете извлекать определённые кабели между двумя напрямую соединёнными компьютерами и размещать их между любыми парами несоединённых компьютеров, чтобы сделать их напрямую соединёнными.
Верните минимальное количество раз, которое необходимо сделать это, чтобы соединить все компьютеры. Если это невозможно, верните -1.
Пример:
Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.class Solution {
func dfs(_ node: Int, _ adj: [Int: [Int]], _ visit: inout [Bool]) {
visit[node] = true
guard let neighbors = adj[node] else { return }
for neighbor in neighbors {
if !visit[neighbor] {
visit[neighbor] = true
dfs(neighbor, adj, &visit)
}
}
}
func makeConnected(_ n: Int, _ connections: [[Int]]) -> Int {
if connections.count < n - 1 {
return -1
}
var adj = [Int: [Int]]()
for connection in connections {
adj[connection[0], default: []].append(connection[1])
adj[connection[1], default: []].append(connection[0])
}
var numberOfConnectedComponents = 0
var visit = [Bool](repeating: false, count: n)
for i in 0..<n {
if !visit[i] {
numberOfConnectedComponents += 1
dfs(i, adj, &visit)
}
}
return numberOfConnectedComponents - 1
}
}1 348
Задача: 1427. Perform String Shifts
Сложность: easy
Вам дана строка s, содержащая строчные английские буквы, и матрица shift, где shift[i] = [directioni, amounti]:
directioni может быть 0 (для сдвига влево) или 1 (для сдвига вправо).
amounti - это количество, на которое строка s должна быть сдвинута.
Сдвиг влево на 1 означает удаление первого символа строки s и добавление его в конец.
Аналогично, сдвиг вправо на 1 означает удаление последнего символа строки s и добавление его в начало.
Верните итоговую строку после всех операций.
Пример:
Input: s = "abc", shift = [[0,1],[1,2]] Output: "cab" Explanation: [0,1] means shift to left by 1. "abc" -> "bca" [1,2] means shift to right by 2. "bca" -> "cab"👨💻 Алгоритм: 1⃣Пройдите по списку сдвигов, суммируя все сдвиги вправо и влево в два отдельных значения. 2⃣Определите, какое из значений больше, и частично компенсируйте его другим. Затем выполните соответствующий сдвиг с оставшимся значением. Если оба значения равны, строка останется неизменной. 3⃣Выполните сдвиг строки на основе вычисленного значения и верните итоговую строку. 😎 Решение:
class Solution {
func stringShift(_ s: String, _ shift: [[Int]]) -> String {
var leftShifts = 0
var rightShifts = 0
for move in shift {
if move[0] == 0 {
leftShifts += move[1]
} else {
rightShifts += move[1]
}
}
let netShifts = (rightShifts - leftShifts) % s.count
let netShift = netShifts < 0 ? s.count + netShifts : netShifts
if netShift == 0 {
return s
}
let splitIndex = s.index(s.startIndex, offsetBy: s.count - netShift)
return String(s[splitIndex...]) + String(s[..<splitIndex])
}
}1 348
Задача: 720. Longest Word in Dictionary
Сложность: medium
Если задан массив строк words, представляющих английский словарь, верните самое длинное слово из words, которое может быть построено по одному символу из других слов из words. Если существует более одного возможного ответа, верните самое длинное слово с наименьшим лексикографическим порядком. Если ответа нет, верните пустую строку. Обратите внимание, что слово должно строиться слева направо, причем каждый дополнительный символ добавляется в конец предыдущего слова.
Пример:
Input: words = ["w","wo","wor","worl","world"] Output: "world"👨💻 Алгоритм: 1⃣Отсортируйте массив слов по длине и лексикографическому порядку. 2⃣Используйте множество для отслеживания слов, которые можно построить. 3⃣Пройдите по каждому слову в отсортированном массиве и добавьте его в множество, если все его префиксы уже существуют в множестве. 😎 Решение:
func longestWord(_ words: [String]) -> String {
let sortedWords = words.sorted()
var validWords: Set<String> = [""]
var longest = ""
for word in sortedWords {
if validWords.contains(String(word.dropLast())) {
validWords.insert(word)
if word.count > longest.count {
longest = word
}
}
}
return longest
}1 348
Задача: 784. Letter Case Permutation
Сложность: medium
Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве.
Пример:
Input: s = "a1b2" Output: ["a1b2","a1B2","A1b2","A1B2"]👨💻 Алгоритм: 1⃣Если следующий символ c является буквой, то мы удвоим все слова в нашем текущем ответе, и добавим lowercase(c) к каждому слову в первой половине, и uppercase(c) к каждому слову во второй половине. 2⃣Если c является цифрой, мы добавим его к каждому слову. 3⃣Продолжайте процесс для всех символов в строке, чтобы получить все возможные комбинации. 😎 Решение:
class Solution {
func letterCasePermutation(_ S: String) -> [String] {
var ans: [[Character]] = [[]]
for char in S {
let n = ans.count
if char.isLetter {
for i in 0..<n {
ans.append(ans[i])
ans[i].append(char.lowercased().first!)
ans[n+i].append(char.uppercased().first!)
}
} else {
for i in 0..<n {
ans[i].append(char)
}
}
}
return ans.map { String($0) }
}
}1 348
Задача: 130. Surrounded Regions
Сложность: Medium
Вам дана матрица размером m на n, которая содержит буквы 'X' и 'O'. Захватите регионы, которые окружены:
Соединение: Ячейка соединена с соседними ячейками по горизонтали или вертикали.
Регион: Для формирования региона соедините каждую ячейку 'O'.
Окружение: Регион окружён ячейками 'X', если можно соединить регион с ячейками 'X', и ни одна из ячеек региона не находится на краю доски.
Окруженный регион захватывается путём замены всех 'O' на 'X' в исходной матрице.
Пример:
Input: board = [["X"]] Output: [["X"]]👨💻 Алгоритм: 1⃣Выбор начальных ячеек и инициация DFS: Начинаем с выбора всех ячеек, расположенных на границах доски. Затем, начиная с каждой выбранной ячейки на границе, выполняем обход в глубину (DFS). 2⃣Логика и выполнение DFS: Если ячейка на границе оказывается 'O', это означает, что эта ячейка "жива", вместе с другими ячейками 'O', соединёнными с этой граничной ячейкой. Две ячейки считаются соединёнными, если между ними существует путь, состоящий только из букв 'O'. Цель нашего обхода DFS будет заключаться в том, чтобы отметить все такие связанные ячейки 'O', которые исходят из границы, каким-либо отличительным символом, например, 'E'. 3⃣Классификация и финальная обработка ячеек: После обхода всех граничных ячеек мы получаем три типа ячеек: Ячейки с буквой 'X': эти ячейки можно считать стеной. Ячейки с буквой 'O': эти ячейки не затрагиваются в нашем обходе DFS, то есть они не имеют соединения с границей, следовательно, они захвачены. Эти ячейки следует заменить на букву 'X'. Ячейки с буквой 'E': это ячейки, отмеченные в ходе нашего обхода DFS, то есть ячейки, имеющие хотя бы одно соединение с границами, следовательно, они не захвачены. В результате мы должны вернуть этим ячейкам их исходную букву 'O'. 😎 Решение:
class Solution {
private var rows: Int = 0
private var cols: Int = 0
func solve(_ board: inout [[Character]]) {
rows = board.count
guard rows > 0 else { return }
cols = board[0].count
guard cols > 0 else { return }
for i in 0..<rows {
for j in 0..<cols {
if i == 0 || j == 0 || i == rows - 1 || j == cols - 1 {
dfs(&board, i, j)
}
}
}
for i in 0..<rows {
for j in 0..<cols {
if board[i][j] == "O" {
board[i][j] = "X"
} else if board[i][j] == "E" {
board[i][j] = "O"
}
}
}
}
private func dfs(_ board: inout [[Character]], _ i: Int, _ j: Int) {
if board[i][j] != "O" { return }
board[i][j] = "E"
if j < cols - 1 { dfs(&board, i, j + 1) }
if i < rows - 1 { dfs(&board, i + 1, j) }
if j > 0 { dfs(&board, i, j - 1) }
if i > 0 { dfs(&board, i - 1, j) }
}
}