اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
Swift | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
نمایش بیشتر1 343
مشترکین
-124 ساعت
-67 روز
-1830 روز
آرشیو پست ها
1 343
Задача: 554. Brick Wall
Сложность: medium
Перед вами находится прямоугольная кирпичная стена с n рядами кирпичей. В i-м ряду находится несколько кирпичей одинаковой высоты (то есть один юнит), но они могут быть разной ширины. Общая ширина каждого ряда одинакова.
Нарисуйте вертикальную линию от верха до низа, пересекающую наименьшее количество кирпичей. Если ваша линия проходит по краю кирпича, то кирпич не считается пересеченным. Вы не можете нарисовать линию прямо по одному из двух вертикальных краев стены, так как в этом случае линия очевидно не пересечет ни одного кирпича.
Дан двумерный массив wall, содержащий информацию о стене, верните минимальное количество пересеченных кирпичей после проведения такой вертикальной линии.
Пример:
Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]] Output: 2👨💻 Алгоритм: 1⃣Определите общую ширину стены, сложив ширины кирпичей в первом ряду. Создайте массив pos, где pos[i] указывает на текущую позицию в i-ом ряду. 2⃣Пройдите по каждой возможной позиции для вертикальной линии (от 1 до общей ширины стены - 1). Для каждой позиции обновите массив pos, проверяя, пересекает ли линия границу кирпича. Если пересекает, увеличьте значение pos[i]. 3⃣Подсчитайте количество кирпичей, которые пересечет вертикальная линия для каждой возможной позиции, обновляя счетчик. Выберите минимальное количество пересеченных кирпичей из всех возможных позиций для вертикальной линии. 😎 Решение:
class Solution {
func leastBricks(_ wall: [[Int]]) -> Int {
var pos = [Int](repeating: 0, count: wall.count)
var res = Int.max
var sum = wall[0].reduce(0, +)
while sum != 0 {
var count = 0
for i in 0..<wall.count {
if wall[i][pos[i]] != 0 {
count += 1
} else {
pos[i] += 1
}
wall[i][pos[i]] -= 1
}
sum -= 1
res = min(res, count)
}
return res
}
}1 343
Задача: 536. Construct Binary Tree from String
Сложность: medium
Вам нужно построить бинарное дерево из строки, состоящей из круглых скобок и целых чисел.
Весь ввод представляет собой бинарное дерево. Он содержит целое число, за которым следуют ноль, одна или две пары круглых скобок. Целое число представляет значение корня, а пара круглых скобок содержит дочернее бинарное дерево с той же структурой.
Вы всегда начинаете строить левый дочерний узел родителя сначала, если он существует.
Пример:
Input: s = "4(2(3)(1))(6(5))" Output: [4,2,6,3,1,5]👨💻 Алгоритм: 1⃣ Извлечение числа: Определите функцию getNumber, которая извлекает целое число из текущей строки, начиная с указанного индекса. Учтите знак числа, если он есть. 2⃣ Построение поддерева: Определите рекурсивную функцию str2treeInternal, которая принимает строку и текущий индекс в качестве входных данных и возвращает пару: узел TreeNode и следующий индекс для обработки. Внутри функции извлеките значение для корневого узла текущего поддерева, создайте узел, а затем рекурсивно постройте левое и правое поддеревья, если они существуют. 3⃣ Основная функция: Определите основную функцию str2tree, которая вызывает рекурсивную функцию str2treeInternal и возвращает построенное дерево. 😎 Решение:
class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) { self.val = val; self.left = nil; self.right = nil }
}
class Solution {
func str2tree(_ s: String) -> TreeNode? {
return str2treeInternal(Array(s), 0).node
}
func getNumber(_ s: [Character], _ index: Int) -> (value: Int, index: Int) {
var idx = index
var isNegative = false
if s[idx] == "-" {
isNegative = true
idx += 1
}
var number = 0
while idx < s.count, let digit = s[idx].wholeNumberValue {
number = number * 10 + digit
idx += 1
}
return (isNegative ? -number : number, idx)
}
func str2treeInternal(_ s: [Character], _ index: Int) -> (node: TreeNode?, nextIndex: Int) {
if index >= s.count {
return (nil, index)
}
let numberData = getNumber(s, index)
let value = numberData.value
var idx = numberData.index
let node = TreeNode(value)
if idx < s.count && s[idx] == "(" {
let leftData = str2treeInternal(s, idx + 1)
node.left = leftData.node
idx = leftData.nextIndex
}
if idx < s.count && s[idx] == "(" {
let rightData = str2treeInternal(s, idx + 1)
node.right = rightData.node
idx = rightData.nextIndex
}
return (node, idx < s.count && s[idx] == ")" ? idx + 1 : idx)
}
}1 343
Задача: 1347. Minimum Number of Steps to Make Two Strings Anagram
Сложность: medium
Даны две строки одинаковой длины s и t. За один шаг вы можете выбрать любой символ строки t и заменить его другим символом.
Вернуть минимальное количество шагов, чтобы сделать t анаграммой строки s.
Анаграмма строки — это строка, которая содержит те же символы в другом (или том же) порядке.
Пример:
Input: s = "bab", t = "aba" Output: 1 Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.👨💻 Алгоритм: 1⃣Вычислить разницу частот символов в строках t и s, сохраняя результаты в массиве count. 2⃣Подсчитать количество символов, которые нужно заменить в t, добавляя в ans только положительные значения из массива count. 3⃣Вернуть ans как минимальное количество шагов для превращения t в анаграмму строки s. 😎 Решение:
class Solution {
func minSteps(_ s: String, _ t: String) -> Int {
var count = [Int](repeating: 0, count: 26)
for i in s.indices {
count[Int(t[i].asciiValue! - Character("a").asciiValue!)] += 1
count[Int(s[i].asciiValue! - Character("a").asciiValue!)] -= 1
}
var ans = 0
for i in 0..<26 {
ans += max(0, count[i])
}
return ans
}
}1 343
Задача: 673. Number of Longest Increasing Subsequence
Сложность: medium
Дан массив целых чисел nums, верните количество самых длинных строго возрастающих подпоследовательностей.
Пример:
Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2class Solution {
func findNumberOfLIS(_ nums: [Int]) -> Int {
let n = nums.count
var length = Array(repeating: 1, count: n)
var count = Array(repeating: 1, count: n)
for i in 0..<n {
for j in 0..<i {
if nums[j] < nums[i] {
if length[j] + 1 > length[i] {
length[i] = length[j] + 1
count[i] = 0
}
if length[j] + 1 == length[i] {
count[i] += count[j]
}
}
}
}
let maxLength = length.max() ?? 0
var result = 0
for i in 0..<n {
if length[i] == maxLength {
result += count[i]
}
}
return result
}
}1 343
Задача: 255. Verify Preorder Sequence in Binary Search Tree
Сложность: medium
Дан массив уникальных целых чисел preorder. Верните true, если это правильная последовательность обхода в порядке предварительного (preorder) обхода для бинарного дерева поиска.
Пример:
Input: preorder = [5,2,1,3,6] Output: true👨💻 Алгоритм: 1⃣Объявите целое число minLimit с маленьким значением, например, минус бесконечность, и стек. 2⃣Итерируйте по массиву preorder. Для каждого num: Очистите стек. Пока верх стека меньше num, извлекайте из стека и обновляйте minLimit. Если num <= minLimit, верните false. Добавьте num в стек. 3⃣Верните true, если удалось пройти весь массив. 😎 Решение:
class Solution {
func verifyPreorder(_ preorder: [Int]) -> Bool {
var minLimit = Int.min
var stack: [Int] = []
for num in preorder {
while !stack.isEmpty && stack.last! < num {
minLimit = stack.removeLast()
}
if num <= minLimit {
return false
}
stack.append(num)
}
return true
}
}1 343
Задача: 609. Find Duplicate File in System
Сложность: medium
Получив список paths информации о каталоге, включающий путь к каталогу и все файлы с содержимым в этом каталоге, верните все дубликаты файлов в файловой системе по их путям. Вы можете вернуть ответ в любом порядке. Группа дубликатов состоит как минимум из двух файлов с одинаковым содержимым. Одна строка информации о каталоге во входном списке имеет следующий формат: "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)" Это означает, что в каталоге "root/d1/d2/.../dm" имеется n файлов (f1.txt, f2.txt ... fn.txt) с содержимым (f1_content, f2_content ... fn_content) соответственно. Обратите внимание, что n >= 1 и m >= 0. Если m = 0, это означает, что каталог является только корневым. На выходе получается список групп дублирующихся путей к файлам. Для каждой группы он содержит все пути к файлам, которые имеют одинаковое содержимое. Путь к файлу - это строка, имеющая следующий формат: "каталог_путь/имя_файла.txt".
Пример:
Input: paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)","root 4.txt(efgh)"] Output: [["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]👨💻 Алгоритм: 1⃣Пройдите по списку путей, разберите каждый путь и соберите информацию о содержимом файлов и соответствующих им путях. 2⃣Используйте словарь для хранения списков путей файлов, сгруппированных по их содержимому. 3⃣Пройдите по словарю и соберите группы дубликатов, содержащие как минимум два пути. 😎 Решение:
func findDuplicate(_ paths: [String]) -> [[String]] {
var contentToFilePaths = [String: [String]]()
for path in paths {
let parts = path.split(separator: " ")
let root = parts[0]
for i in 1..<parts.count {
let fileParts = parts[i].split(separator: "(")
let fileName = String(fileParts[0])
let content = String(fileParts[1].dropLast())
let filePath = "\(root)/\(fileName)"
contentToFilePaths[content, default: []].append(filePath)
}
}
return contentToFilePaths.values.filter { $0.count > 1 }
}1 343
Задача: 272. Closest Binary Search Tree Value II
Сложность: hard
Дано корень бинарного дерева поиска, целевое значение и целое число k. Верните k значений в дереве, которые ближе всего к целевому значению. Вы можете вернуть ответ в любом порядке.
Гарантируется, что в дереве есть только один уникальный набор из k значений, которые ближе всего к целевому значению.
Пример:
Input: root = [4,2,5,1,3], target = 3.714286, k = 2 Output: [4,3]👨💻 Алгоритм: 1⃣Выполнить обход дерева в глубину (DFS) и собрать все значения в массив: Пройти по дереву в глубину, добавляя каждое значение узла в массив. 2⃣Отсортировать массив по расстоянию от целевого значения: Использовать пользовательский компаратор, чтобы отсортировать массив по абсолютному значению разности между элементом массива и целевым значением. 3⃣Вернуть первые k значений из отсортированного массива: Извлечь первые k элементов из отсортированного массива и вернуть их. 😎 Решение:
class Solution {
func closestKValues(_ root: TreeNode?, _ target: Double, _ k: Int) -> [Int] {
var arr = [Int]()
dfs(root, &arr)
arr.sort { abs(Double($0) - target) < abs(Double($1) - target) }
return Array(arr.prefix(k))
}
private func dfs(_ node: TreeNode?, _ arr: inout [Int]) {
guard let node = node else { return }
arr.append(node.val)
dfs(node.left, &arr)
dfs(node.right, &arr)
}
}1 343
📺 Уникальная база IT собеседований
456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы.
Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.
🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!
1 343
Задача: 771. Jewels and Stones
Сложность: medium
Вам даны строки jewels, представляющие типы камней, которые являются драгоценностями, и stones, представляющие камни, которые у вас есть. Каждый символ в stones является типом камня, который у вас есть. Вы хотите узнать, сколько из камней, которые у вас есть, также являются драгоценностями.
Буквы чувствительны к регистру, поэтому "a" считается другим типом камня, чем "A".
Пример:
Input: jewels = "aA", stones = "aAAbbbb"
Output: 3class Solution {
func numJewelsInStones(_ J: String, _ S: String) -> Int {
var ans = 0
for s in S {
for j in J {
if j == s {
ans += 1
break
}
}
}
return ans
}
}1 343
Задача: 1086. High Five
Сложность: easy
Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.
Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.
Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.
Пример:
Input: items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]
Output: [[1,100],[7,100]]class Solution {
func highFive(_ items: [[Int]]) -> [[Int]] {
let K = 5
let sortedItems = items.sorted {
if $0[0] != $1[0] {
return $0[0] < $1[0]
}
return $0[1] > $1[1]
}
var solution = [[Int]]()
var i = 0
while i < sortedItems.count {
let id = sortedItems[i][0]
var sum = 0
for k in i..<i+K {
sum += sortedItems[k][1]
}
while i < sortedItems.count && sortedItems[i][0] == id {
i += 1
}
solution.append([id, sum / K])
}
return solution
}
}1 343
Задача: 273. Integer to English Words
Сложность: hard
Преобразуйте неотрицательное целое число num в его словесное представление на английском языке.
Пример:
Input: num = 123 Output: "One Hundred Twenty Three"👨💻 Алгоритм: 1⃣Обработка чисел до 20 и кратных 10 до 90: Создать массивы или словари для чисел от 1 до 19 и для кратных 10 от 20 до 90. Если число попадает в эти диапазоны, сразу вернуть соответствующее словесное представление. 2⃣Обработка сотен, тысяч, миллионов и миллиардов: Разделить число на группы по три цифры (единицы, тысячи, миллионы, миллиарды). Для каждой группы сформировать словесное представление с использованием рекурсивной функции для чисел от 1 до 999. 3⃣Формирование окончательного результата: Собрать словесное представление всех групп, добавив соответствующие суффиксы (тысячи, миллионы, миллиарды). Соединить все части в одну строку, удалив лишние пробелы. 😎 Решение:
class Solution {
private let belowTwenty = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
private let tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
private let thousands = ["", "Thousand", "Million", "Billion"]
func numberToWords(_ num: Int) -> String {
if num == 0 { return "Zero" }
var num = num
var result = ""
var i = 0
while num > 0 {
if num % 1000 != 0 {
result = helper(num % 1000) + thousands[i] + " " + result
}
num /= 1000
i += 1
}
return result.trimmingCharacters(in: .whitespaces)
}
private func helper(_ num: Int) -> String {
if num == 0 { return "" }
else if num < 20 { return belowTwenty[num] + " " }
else if num < 100 { return tens[num / 10] + " " + helper(num % 10) }
else { return belowTwenty[num / 100] + " Hundred " + helper(num % 100) }
}
}1 343
Задача: 478. Generate Random Point in a Circle
Сложность: medium
Дан радиус и положение центра окружности, реализуйте функцию randPoint, которая генерирует равномерно случайную точку внутри окружности.
Реализуйте класс Solution:
- Solution(double radius, double x_center, double y_center) инициализирует объект с радиусом окружности radius и положением центра (x_center, y_center).
- randPoint() возвращает случайную точку внутри окружности. Точка на окружности считается находящейся внутри окружности. Ответ возвращается в виде массива [x, y].
Пример:
Input ["Solution", "randPoint", "randPoint", "randPoint"] [[1.0, 0.0, 0.0], [], [], []] Output [null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]] Explanation Solution solution = new Solution(1.0, 0.0, 0.0); solution.randPoint(); // return [-0.02493, -0.38077] solution.randPoint(); // return [0.82314, 0.38945] solution.randPoint(); // return [0.36572, 0.17248]👨💻 Алгоритм: 1⃣ Генерируем равномерно случайные точки в квадрате S с длиной стороны 2R. 2⃣ Сохраняем все точки, которые находятся на расстоянии не более R от центра, и отклоняем все, которые дальше этого расстояния. 3⃣ Повторяем процесс до получения нужного количества точек, учитывая, что примерно 78.5% от всех сгенерированных точек будут приемлемыми, и ожидаемое число попыток до получения приемлемой точки составляет примерно 1.274 раза. 😎 Решение:
import Foundation
class Solution {
var rad: Double
var xc: Double
var yc: Double
init(_ radius: Double, _ x_center: Double, _ y_center: Double) {
rad = radius
xc = x_center
yc = y_center
}
func randPoint() -> [Double] {
let x0 = xc - rad
let y0 = yc - rad
while true {
let xg = x0 + Double.random(in: 0...(rad * 2))
let yg = y0 + Double.random(in: 0...(rad * 2))
if sqrt(pow(xg - xc, 2) + pow(yg - yc, 2)) <= rad {
return [xg, yg]
}
}
}
}1 343
Задача: 592. Fraction Addition and Subtraction
Сложность: medium
Дана строка, представляющая выражение сложения и вычитания дробей, верните результат вычисления в строковом формате.
Окончательный результат должен быть несократимой дробью. Если ваш окончательный результат является целым числом, преобразуйте его в формат дроби с знаменателем 1. Таким образом, 2 должно быть преобразовано в 2/1.
Пример:
Input: expression = "-1/2+1/2+1/3" Output: "1/3"👨💻 Алгоритм: 1⃣Начните сканирование строки и разделите её на части, содержащие числители и знаменатели, с учетом знаков. 2⃣Выполните операции сложения или вычитания для каждой пары дробей, приводя их к общему знаменателю и сокращая результат. 3⃣Верните результат в виде строки, представляющей несократимую дробь. 😎 Решение:
class Solution {
func fractionAddition(_ expression: String) -> String {
var sign = [Character]()
if expression.first != "-" {
sign.append("+")
}
for char in expression {
if char == "+" || char == "-" {
sign.append(char)
}
}
var prevNum = 0, prevDen = 1
var i = 0
let fractions = expression.split { $0 == "+" || $0 == "-" }
for sub in fractions {
if sub.isEmpty { continue }
let fraction = sub.split(separator: "/").map { Int($0)! }
let num = fraction[0]
let den = fraction[1]
let g = gcd(prevDen, den)
if sign[i] == "+" {
prevNum = prevNum * den / g + num * prevDen / g
} else {
prevNum = prevNum * den / g - num * prevDen / g
}
prevDen = prevDen * den / g
let gcdValue = gcd(abs(prevNum), prevDen)
prevNum /= gcdValue
prevDen /= gcdValue
i += 1
}
return "\(prevNum)/\(prevDen)"
}
private func gcd(_ a: Int, _ b: Int) -> Int {
return b == 0 ? a : gcd(b, a % b)
}
}1 343
Задача: 401. Binary Watch
Сложность: easy
Бинарные часы имеют 4 светодиода сверху для представления часов (0-11) и 6 светодиодов снизу для представления минут (0-59). Каждый светодиод представляет ноль или единицу, при этом младший разряд находится справа.
Пример:
Input: turnedOn = 1 Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]👨💻 Алгоритм: 1⃣Генерация всех возможных комбинаций: Переберите все возможные значения для часов и минут. Используйте битовые операции для подсчета количества единиц в бинарном представлении числа. 2⃣Проверка количества горящих светодиодов: Для каждой комбинации проверьте, соответствует ли сумма единиц в бинарном представлении часов и минут заданному количеству горящих светодиодов. 3⃣Форматирование результата: Если комбинация часов и минут соответствует условию, отформатируйте их в виде строки "часы:минуты" и добавьте в список результатов. 😎 Решение:
class Solution {
func readBinaryWatch(_ turnedOn: Int) -> [String] {
var results = [String]()
for h in 0..<12 {
for m in 0..<60 {
if (h.nonzeroBitCount + m.nonzeroBitCount) == turnedOn {
results.append(String(format: "%d:%02d", h, m))
}
}
}
return results
}
}1 343
Задача: 319. Bulb Switcher
Сложность: medium
Есть n лампочек, которые изначально выключены. Сначала вы включаете все лампочки, затем выключаете каждую вторую лампочку.
На третьем раунде вы переключаете каждую третью лампочку (включаете, если она выключена, или выключаете, если она включена). На i-ом раунде вы переключаете каждую i-ую лампочку. На n-ом раунде вы переключаете только последнюю лампочку.
Верните количество лампочек, которые будут включены после n раундов.
Пример:
Input: n = 3 Output: 1 Explanation: At first, the three bulbs are [off, off, off]. After the first round, the three bulbs are [on, on, on]. After the second round, the three bulbs are [on, off, on]. After the third round, the three bulbs are [on, off, off]. So you should return 1 because there is only one bulb is on. Explanation: The two words can be "abcw", "xtfn".👨💻 Алгоритм: 1⃣Инициализация Лампочка остается включенной, если она переключалась нечетное количество раз. Лампочка будет переключаться на каждом делителе её номера. 2⃣Определение состояния лампочки Лампочка останется включенной только в том случае, если у нее нечетное количество делителей, что возможно только для квадратных чисел. 3⃣Подсчет включенных лампочек Количество лампочек, которые будут включены после n раундов. 😎 Решение:
class Solution {
func bulbSwitch(_ n: Int) -> Int {
return Int(Double(n).squareRoot())
}
}1 343
Задача: 741. Cherry Pickup
Сложность: hard
Вам дана сетка n x n, представляющая поле вишен. Каждая клетка - одно из трех возможных целых чисел. 0 означает, что клетка пуста, и вы можете пройти через нее, 1 означает, что клетка содержит вишню, которую вы можете сорвать и пройти через нее, или -1 означает, что клетка содержит шип, который преграждает вам путь. Верните максимальное количество вишен, которое вы можете собрать, следуя следующим правилам: Начиная с позиции (0, 0) и достигая (n - 1, n - 1) путем перемещения вправо или вниз через допустимые клетки пути (клетки со значением 0 или 1).
После достижения (n - 1, n - 1) вернитесь в (0, 0), двигаясь влево или вверх по клеткам с действительными путями. Проходя через клетку пути, содержащую вишню, вы поднимаете ее, и клетка становится пустой клеткой 0. Если между (0, 0) и (n - 1, n - 1) нет действительного пути, то вишни собрать нельзя.
Пример:
Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]] Output: 5👨💻 Алгоритм: 1⃣Используйте динамическое программирование для подсчета максимального количества вишен, которые можно собрать при движении от (0, 0) до (n - 1, n - 1). 2⃣Примените еще один проход с использованием динамического программирования для движения обратно от (n - 1, n - 1) до (0, 0), чтобы учитывать вишни, собранные на обратном пути. 3⃣Объедините результаты двух проходов, чтобы найти максимальное количество вишен, которые можно собрать. 😎 Решение:
func cherryPickup(_ grid: [[Int]]) -> Int {
let n = grid.count
var dp = Array(repeating: Array(repeating: Array(repeating: Int.min, count: n), count: n), count: n)
dp[0][0][0] = grid[0][0]
for k in 1...(2 * (n - 1)) {
for i1 in max(0, k - n + 1)...min(n - 1, k) {
for i2 in max(0, k - n + 1)...min(n - 1, k) {
let j1 = k - i1
let j2 = k - i2
if j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1 {
var maxCherries = Int.min
if i1 > 0 && i2 > 0 { maxCherries = max(maxCherries, dp[i1 - 1][i2 - 1][k - 1]) }
if i1 > 0 { maxCherries = max(maxCherries, dp[i1 - 1][i2][k - 1]) }
if i2 > 0 { maxCherries = max(maxCherries, dp[i1][i2 - 1][k - 1]) }
maxCherries = max(maxCherries, dp[i1][i2][k - 1])
if maxCherries != Int.min {
dp[i1][i2][k] = maxCherries + grid[i1][j1]
if i1 != i2 { dp[i1][i2][k] += grid[i2][j2] }
}
}
}
}
}
return max(0, dp[n - 1][n - 1][2 * (n - 1)])
}1 343
Задача: 541. Reverse String II
Сложность: easy
Дана строка s и целое число k, переверните первые k символов для каждых 2k символов, начиная с начала строки.
Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть.
Пример:
Input: s = "abcdefg", k = 2 Output: "bacdfeg"👨💻 Алгоритм: 1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее. 2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут. 3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--. 😎 Решение:
class Solution {
func reverseStr(_ s: String, _ k: Int) -> String {
var a = Array(s)
var start = 0
while start < a.count {
var i = start
var j = min(start + k - 1, a.count - 1)
while i < j {
a.swapAt(i, j)
i += 1
j -= 1
}
start += 2 * k
}
return String(a)
}
}1 343
Задача: 58. Length of Last Word
Сложность: easy
Дана строка s, состоящая из слов и пробелов. Верните длину последнего слова в строке.
Слово — это максимальная подстрока, состоящая только из символов, не являющихся пробелами.
Пример:
Input: s = "Hello World" Output: 5 Explanation: The last word is "World" with length 5.👨💻 Алгоритм: 1⃣Поиск последнего слова: Сначала мы пытаемся найти последнее слово, начиная с конца строки. Итерируем строку в обратном порядке, пропуская пробелы. Когда мы встречаем первый непробельный символ, мы знаем, что нашли последний символ последнего слова. 2⃣Определение длины последнего слова: После того как последнее слово найдено, мы подсчитываем его длину, начиная с его последнего символа. Здесь также можно использовать цикл. 3⃣Итог: Используя обратную итерацию и пропуск пробелов, определяется начало и конец последнего слова в строке для вычисления его длины. 😎 Решение:
class Solution {
func lengthOfLastWord(_ s: String) -> Int {
var p = s.count - 1
// Trim the trailing spaces
while p >= 0 && s[s.index(s.startIndex, offsetBy: p)] == ' ' {
p -= 1
}
// Compute the length of the last word
var length = 0
while p >= 0 && s[s.index(s.startIndex, offsetBy: p)] != ' ' {
p -= 1
length += 1
}
return length
}
}1 343
Задача: 648. Replace Words
Сложность: medium
В английском языке есть понятие "корень", за которым может следовать какое-то другое слово, чтобы образовать другое более длинное слово - назовем это слово производным. Например, если за корнем "help" следует слово "ful", мы можем образовать производное "helpful". Дайте словарь, состоящий из множества корней, и предложение, состоящее из слов, разделенных пробелами, замените все производные в предложении на образующий их корень. Если производное может быть заменено более чем одним корнем, замените его корнем, имеющим наименьшую длину. Верните предложение после замены.
Пример:
Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery" Output: "the cat was rat by the bat"👨💻 Алгоритм: 1⃣Преобразуйте словарь корней в набор для быстрого поиска. 2⃣Пройдите по каждому слову в предложении и найдите самый короткий корень, который является префиксом этого слова. 3⃣Замените слово найденным корнем и соберите обновленное предложение. 😎 Решение:
func replaceWords(_ roots: [String], _ sentence: String) -> String {
let rootSet = Set(roots)
func replace(_ word: String) -> String {
for i in 1...word.count {
let prefix = String(word.prefix(i))
if rootSet.contains(prefix) {
return prefix
}
}
return word
}
return sentence.split(separator: " ").map { replace(String($0)) }.joined(separator: " ")
}1 343
Задача: 78. Subsets
Сложность: medium
Дан массив целых чисел nums, содержащий уникальные элементы. Верните все возможные подмножества (степенной набор).
Множество решений не должно содержать дублирующихся подмножеств. Результат может быть возвращен в любом порядке.
Пример:
Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]👨💻 Алгоритм: 1⃣Определяем функцию обратного отслеживания под названием backtrack(first, curr), которая принимает индекс первого элемента, который нужно добавить, и текущую комбинацию в качестве аргументов. 2⃣Если текущая комбинация завершена, мы добавляем её в итоговый вывод. 3⃣В противном случае перебираем индексы i от first до длины всей последовательности n, добавляем элемент nums[i] в текущую комбинацию curr, продолжаем добавлять больше чисел в комбинацию: backtrack(i + 1, curr) и возвращаемся, удаляя nums[i] из curr. 😎 Решение:
func subsets(_ nums: [Int]) -> [[Int]] {
var output = [[Int]]()
let n = nums.count
func backtrack(_ first: Int = 0, _ curr: [Int], _ k: Int) {
if curr.count == k {
output.append(curr)
return
}
for i in first..<n {
backtrack(i + 1, curr + [nums[i]], k)
}
}
for k in 0...n {
backtrack(0, [], k)
}
return output
}