Endi mavjud! Telegram Tadqiqoti 2025 — yilning asosiy insaytlari 
Swift | LeetCode
Kanalga Telegram’da o‘tish
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Ko'proq ko'rsatish1 348
Obunachilar
-224 soatlar
-47 kunlar
-1630 kunlar
Postlar arxiv
1 348
Задача: 415. Add Strings
Сложность: easy
Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.
Пример:
Input: num1 = "11", num2 = "123" Output: "134"👨💻 Алгоритм: 1⃣Инициализируйте три переменные для хранения первого, второго и третьего максимальных чисел. 2⃣Пройдите по массиву nums, обновляя переменные первого, второго и третьего максимальных чисел, избегая дубликатов. 3⃣Верните третье максимальное число, если оно существует, иначе верните первое максимальное число. 😎 Решение:
func thirdMax(_ nums: [Int]) -> Int {
var first: Int? = nil
var second: Int? = nil
var third: Int? = nil
for num in nums {
if num == first || num == second || num == third {
continue
}
if first == nil || num > first! {
third = second
second = first
first = num
} else if second == nil || num > second! {
third = second
second = num
} else if third == nil || num > third! {
third = num
}
}
return third ?? first!
}1 348
Задача: 1037. Valid Boomerang
Сложность: easy
Если задан массив points, где points[i] = [xi, yi] представляет точку на плоскости X-Y, верните true, если эти точки являются бумерангом. Бумеранг - это набор из трех точек, которые отличаются друг от друга и не являются прямой линией.
Пример:
Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2] Output: false👨💻 Алгоритм: 1⃣Проверка уникальности точек: Убедитесь, что все три точки уникальны. Если любые две точки совпадают, то это не бумеранг. 2⃣Проверка на коллинеарность: Используйте определитель (или площадь параллелограмма) для проверки, находятся ли три точки на одной прямой. Если площадь параллелограмма, образованного тремя точками, равна нулю, то точки коллинеарны. 3⃣Результат: Если точки уникальны и не коллинеарны, верните true. В противном случае, верните false. 😎 Решение:
class Solution {
func isBoomerang(_ points: [[Int]]) -> Bool {
let (x1, y1) = (points[0][0], points[0][1])
let (x2, y2) = (points[1][0], points[1][1])
let (x3, y3) = (points[2][0], points[2][1])
return (x1 != x2 || y1 != y2) && (x1 != x3 || y1 != y3) && (x2 != x3 || y2 != y3) && (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) != 0
}
}1 348
Задача: 640. Solve the Equation
Сложность: medium
Решите заданное уравнение и верните значение 'x' в виде строки "x=#value". Уравнение содержит только операции '+', '-', переменную 'x' и ее коэффициент. Вы должны вернуть "No solution", если для уравнения нет решения, или "Infinite solutions", если для уравнения существует бесконечное количество решений. Если для уравнения существует ровно одно решение, мы убеждаемся, что значение 'x' является целым числом.
Пример:
Input: s = "*" Output: 9👨💻 Алгоритм: 1⃣Разделение уравнения: Разделите уравнение на левую и правую части относительно знака равенства '='. 2⃣Парсинг и упрощение: Пройдитесь по каждой части уравнения, упрощая ее до суммы коэффициентов 'x' и числовых значений. 3⃣Решение уравнения: Используйте уравнение вида ax + b = cx + d, чтобы решить для 'x'. Если коэффициенты 'x' равны и числовые значения равны, уравнение имеет бесконечное количество решений. Если коэффициенты 'x' равны, но числовые значения различны, решения нет. В противном случае вычислите значение 'x'. 😎 Решение:
class Solution {
func solveEquation(_ equation: String) -> String {
func parse(_ s: String) -> (Int, Int) {
var coeff = 0
var constPart = 0
var sign = 1
var num = 0
var i = s.startIndex
while i < s.endIndex {
if s[i] == "+" {
sign = 1
i = s.index(after: i)
} else if s[i] == "-" {
sign = -1
i = s.index(after: i)
} else if s[i].isNumber {
num = 0
while i < s.endIndex && s[i].isNumber {
num = num * 10 + s[i].wholeNumberValue!
i = s.index(after: i)
}
if i < s.endIndex && s[i] == "x" {
coeff += sign * num
i = s.index(after: i)
} else {
constPart += sign * num
}
} else if s[i] == "x" {
coeff += sign
i = s.index(after: i)
}
}
return (coeff, constPart)
}
let parts = equation.split(separator: "=")
let (leftCoeff, leftConst) = parse(String(parts[0]))
let (rightCoeff, rightConst) = parse(String(parts[1]))
let coeff = leftCoeff - rightCoeff
let constPart = rightConst - leftConst
if coeff == 0 {
return constPart == 0 ? "Infinite solutions" : "No solution"
}
return "x=\(constPart / coeff)"
}
}1 348
Задача: 814. Binary Tree Pruning
Сложность: medium
Дан корень бинарного дерева. Верните то же дерево, в котором удалены все поддеревья (данного дерева), не содержащие 1.
Поддерево узла node - это сам узел node и все узлы, являющиеся потомками node.
Пример:
Input: root = [1,null,0,0,1] Output: [1,null,0,null,1] Explanation: Only the red nodes satisfy the property "every subtree not containing a 1". The diagram on the right represents the answer.👨💻 Алгоритм: 1⃣Используем функцию containsOne(node), которая сообщает, содержит ли поддерево в данном узле единицу, и обрезает все поддеревья, не содержащие единицу. 2⃣Например, если поддерево node.left не содержит единицу, то мы должны обрезать его через node.left = null. 3⃣Также нужно проверить родительский узел. Например, если дерево состоит из одного узла 0, то ответом будет пустое дерево. 😎 Решение:
class Solution {
func pruneTree(_ root: TreeNode?) -> TreeNode? {
return containsOne(root) ? root : nil
}
func containsOne(_ node: TreeNode?) -> Bool {
guard let node = node else { return false }
let leftContainsOne = containsOne(node.left)
let rightContainsOne = containsOne(node.right)
if !leftContainsOne { node.left = nil }
if !rightContainsOne { node.right = nil }
return node.val == 1 || leftContainsOne || rightContainsOne
}
}1 348
Задача: 1358. Number of Substrings Containing All Three Characters
Сложность: medium
Дана строка s, состоящая только из символов a, b и c.
Верните количество подстрок, содержащих хотя бы одно вхождение всех этих символов a, b и c.
Пример:
Input: s = "abc" Output: 1👨💻 Алгоритм: 1⃣Инициализация указателей и счетчиков: Создайте три указателя i, j, и count для отслеживания текущего положения в строке и подсчета подстрок. Используйте словарь для подсчета вхождений символов a, b, и c. 2⃣Расширение окна: Перемещайте правый указатель j по строке и увеличивайте счетчики символов в словаре. Как только все три символа (a, b, и c) присутствуют в текущем окне, начинайте уменьшать левый указатель i. 3⃣Уменьшение окна и подсчет подстрок: Для каждого сдвига i вправо, проверяйте наличие всех символов в текущем окне. Если все символы присутствуют, добавьте количество подстрок, заканчивающихся в позиции j, к общему счету. Сдвигайте i вправо до тех пор, пока условие выполнения не нарушится. Верните итоговое количество подстрок. 😎 Решение:
class Solution {
func numberOfSubstrings(_ s: String) -> Int {
let chars = Array(s)
var count = 0
var i = 0
var charCount = [Character: Int]()
for j in 0..<chars.count {
charCount[chars[j], default: 0] += 1
while charCount.keys.contains("a") && charCount.keys.contains("b") && charCount.keys.contains("c") {
count += chars.count - j
charCount[chars[i]]! -= 1
if charCount[chars[i]]! == 0 {
charCount.removeValue(forKey: chars[i])
}
i += 1
}
}
return count
}
}1 348
Задача: 722. Remove Comments
Сложность: medium
Дана программа на C++, удалите из нее комментарии. Исходный текст программы представляет собой массив строк source, где source[i] - это i-я строка исходного кода. Это результат разбиения исходной строки исходного кода символом новой строки '\n'. В C++ существует два типа комментариев: строчные и блочные. Строка "//" обозначает строчный комментарий, который означает, что он и остальные символы справа от него в той же строке должны игнорироваться. Строка "/*" обозначает блочный комментарий, который означает, что все символы до следующего (не перекрывающегося) вхождения "*/" должны игнорироваться. (Здесь вхождения происходят в порядке чтения: строка за строкой слева направо.) Чтобы было понятно, строка "/*/" еще не завершает блочный комментарий, так как окончание будет перекрывать начало. Первый эффективный комментарий имеет приоритет над остальными.
Например, если строка "//" встречается в блочном комментарии, она игнорируется. Аналогично, если строка "/*" встречается в строчном или блочном комментарии, она также игнорируется. Если после удаления комментариев определенная строка кода оказывается пустой, вы не должны выводить эту строку: каждая строка в списке ответов будет непустой.
Пример:
Input: source = ["/*Test program */", "int main()", "{ ", " // variable declaration ", "int a, b, c;", "/* This is a test", " multiline ", " comment for ", " testing */", "a = b + c;", "}"]
Output: ["int main()","{ "," ","int a, b, c;","a = b + c;","}"]
👨💻 Алгоритм:
1⃣Создайте строку buffer для хранения текущей строки кода без комментариев и флаг inBlock для отслеживания, находимся ли мы внутри блочного комментария.
2⃣Пройдите по каждой строке source и по каждому символу в этой строке, обрабатывая комментарии: Если встречен блочный комментарий /*, установите флаг inBlock и пропустите символы до */. Если встречен строчный комментарий //, прекратите обработку текущей строки. Если не находимся внутри комментария, добавьте символ в buffer.
3⃣После обработки всех строк добавьте непустые строки из buffer в результат.
😎 Решение:
class Solution {
func removeComments(_ source: [String]) -> [String] {
var inBlock = false
var buffer = [Character]()
var result = [String]()
for line in source {
var i = 0
if !inBlock { buffer = [] }
let chars = Array(line)
while i < chars.count {
if !inBlock && i + 1 < chars.count && chars[i] == "/" && chars[i + 1] == "*" {
inBlock = true
i += 1
} else if inBlock && i + 1 < chars.count && chars[i] == "*" && chars[i + 1] == "/" {
inBlock = false
i += 1
} else if !inBlock && i + 1 < chars.count && chars[i] == "/" && chars[i + 1] == "/" {
break
} else if !inBlock {
buffer.append(chars[i])
}
i += 1
}
if !buffer.isEmpty && !inBlock {
result.append(String(buffer))
}
}
return result
}
}1 348
Задача: 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 348
Задача: 561. Array Partition
Сложность: easy
Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.
Пример:
Input: nums = [1,4,3,2] Output: 4 Explanation: All possible pairings (ignoring the ordering of elements) are: 1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3 2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3 3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4 So the maximum possible sum is 4.👨💻 Алгоритм: 1⃣Отсортируйте массив nums в неубывающем порядке. 2⃣Итерируйте через массив, выбирая каждый второй элемент (начиная с первого). 3⃣Суммируйте выбранные элементы и верните эту сумму. 😎 Решение:
class Solution {
func arrayPairSum(_ nums: [Int]) -> Int {
let sortedNums = nums.sorted()
var sum = 0
for i in stride(from: 0, to: sortedNums.count, by: 2) {
sum += sortedNums[i]
}
return sum
}
}1 348
Задача: 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 348
Задача: 393. UTF-8 Validation
Сложность: medium
Дан целочисленный массив data, представляющий данные, верните, является ли это допустимой UTF-8 кодировкой (т.е. переводится в последовательность допустимых UTF-8 закодированных символов).
Символ в UTF-8 может быть от 1 до 4 байтов в длину, при этом соблюдаются следующие правила:
Для 1-байтового символа первый бит — 0, за которым следует его Unicode код.
Для n-байтового символа первые n битов — все единицы, (n + 1)-й бит — 0, за которыми следуют n - 1 байт с наиболее значимыми 2 битами, равными 10.
Это работает следующим образом:
Количество байтов | UTF-8 Октетная последовательность
| (бинарная)
--------------------+-----------------------------------------
1 | 0xxxxxxx
2 | 110xxxxx 10xxxxxx
3 | 1110xxxx 10xxxxxx 10xxxxxx
4 | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
x обозначает бит в бинарной форме байта, который может быть как 0, так и 1.
Примечание: Вход представляет собой массив целых чисел. Используются только 8 младших значимых битов каждого целого числа. Это означает, что каждое целое число представляет только 1 байт данных.
Пример:
Input: data = [197,130,1] Output: true Explanation: data represents the octet sequence: 11000101 10000010 00000001. It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.👨💻 Алгоритм: 1⃣Начните обработку целых чисел в данном массиве одно за другим. Для каждого целого числа получите его двоичное представление в виде строки. Поскольку целые числа могут быть очень большими, следует учитывать только 8 младших значимых битов данных и отбросить остальные, как указано в условии задачи. После этого шага у вас должно быть 8-битное или 1-байтовое строковое представление целого числа. Назовем эту строку bin_rep. 2⃣Далее нужно рассмотреть два сценария. Первый — мы находимся в процессе обработки некоторого UTF-8 закодированного символа. В этом случае нужно просто проверить первые два бита строки и посмотреть, равны ли они "10", т.е. наиболее значимые два бита целого числа равны 1 и 0. bin_rep[:2] == "10". Второй сценарий — мы уже обработали несколько допустимых UTF-8 символов и должны начать обработку нового UTF-8 символа. В этом случае нужно посмотреть на префикс строкового представления и посчитать количество единиц, которые мы встречаем до первой нули. Это скажет нам, каков размер следующего UTF-8 символа. 3⃣Продолжайте обрабатывать целые числа массива таким образом, пока не обработаете их все или не обнаружите недопустимый сценарий. Теперь давайте перейдем к реализации этого алгоритма. 😎 Решение:
class Solution {
func validUtf8(_ data: [Int]) -> Bool {
var nBytes = 0
for num in data {
let binRep = String(num, radix: 2).suffix(8).padLeft(toLength: 8, withPad: "0")
if nBytes == 0 {
for bit in binRep {
if bit == "0" { break }
nBytes += 1
}
if nBytes == 0 {
continue
}
if nBytes == 1 || nBytes > 4 {
return false
}
} else {
if !(binRep.prefix(2) == "10") {
return false
}
}
nBytes -= 1
}
return nBytes == 0
}
}
extension String {
func padLeft(toLength: Int, withPad: String) -> String {
let newLength = self.count
if newLength < toLength {
return String(repeatElement(withPad, count: toLength - newLength)) + self
} else {
return String(self.suffix(toLength))
}
}
}1 348
Задача: 22. Generate Parentheses
Сложность: medium
Учитывая n пар круглых скобок, напишите функцию для генерации всех комбинаций правильно сформированных круглых скобок.
Пример:
Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]👨💻Алгоритм: 1⃣Используем рекурсию для построения строк, начиная с пустой строки. 2⃣Добавляем открывающую скобку, если их количество меньше n, и вызываем рекурсивную функцию. 3⃣Добавляем закрывающую скобку, если их количество меньше количества открытых, и вызываем рекурсию. 😎Решение:
import Foundation
func generateParenthesis(_ n: Int) -> [String] {
var result = [String]()
generate(current: "", open: 0, close: 0, max: n, result: &result)
return result
}
private func generate(current: String, open: Int, close: Int, max: Int, result: inout [String]) {
if current.count == max * 2 {
result.append(current)
return
}
if open < max {
generate(current: current + "(", open: open + 1, close: close, max: max, result: &result)
}
if close < open {
generate(current: current + ")", open: open, close: close + 1, max: max, result: &result)
}
}1 348
Задача: 763. Partition Labels
Сложность: medium
Вам дана строка s. Мы хотим разбить строку на как можно больше частей так, чтобы каждая буква встречалась не более чем в одной части. Обратите внимание, что разбиение выполняется так, чтобы после конкатенации всех частей по порядку получилась строка s. Верните список целых чисел, представляющих размер этих частей.
Пример:
Input: s = "ababcbacadefegdehijhklij" Output: [9,7,8]👨💻 Алгоритм: 1⃣Создайте словарь для хранения последней позиции каждой буквы в строке. 2⃣Пройдите по строке, отслеживая максимальную позицию текущей части. 3⃣Когда текущая позиция совпадает с максимальной позицией, завершите часть и начните новую. 😎 Решение:
func partitionLabels(_ s: String) -> [Int] {
var lastPos = [Character: Int]()
for (idx, char) in s.enumerated() {
lastPos[char] = idx
}
var partitions = [Int]()
var j = 0, anchor = 0
for (i, char) in s.enumerated() {
j = max(j, lastPos[char]!)
if i == j {
partitions.append(i - anchor + 1)
anchor = i + 1
}
}
return partitions
}1 348
Задача: 725. Split Linked List in Parts
Сложность: medium
Учитывая голову односвязного списка и целое число k, разбейте связный список на k последовательных частей связного списка. Длина каждой части должна быть как можно более одинаковой: никакие две части не должны иметь размер, отличающийся более чем на единицу. Это может привести к тому, что некоторые части будут нулевыми. Части должны располагаться в порядке появления во входном списке, и части, появившиеся раньше, всегда должны иметь размер, больший или равный частям, появившимся позже. Возвращается массив из k частей.
Пример:
Input: head = [1,2,3], k = 5 Output: [[1],[2],[3],[],[]]👨💻 Алгоритм: 1⃣Определите общую длину связного списка. 2⃣Вычислите базовый размер каждой части и количество частей, которые должны быть на одну единицу длиннее. 3⃣Разделите список на части, присваивая каждую часть в массив результатов. 😎 Решение:
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int, _ next: ListNode? = nil) {
self.val = val
self.next = next
}
}
func splitListToParts(_ head: ListNode?, _ k: Int) -> [ListNode?] {
var length = 0
var node = head
while node != nil {
length += 1
node = node?.next
}
let partLength = length / k
let extraParts = length % k
var parts: [ListNode?] = []
node = head
for i in 0..<k {
let partHead = node
let partSize = partLength + (i < extraParts ? 1 : 0)
for _ in 0..<partSize - 1 {
node = node?.next
}
let nextPart = node?.next
node?.next = nil
node = nextPart
parts.append(partHead)
}
return parts
}1 348
Задача: 712. Minimum ASCII Delete Sum for Two Strings
Сложность: medium
Если даны две строки s1 и s2, верните наименьшую ASCII-сумму удаленных символов, чтобы сделать две строки равными.
Пример:
Input: s1 = "sea", s2 = "eat" Output: 231👨💻 Алгоритм: 1⃣Создайте двумерный массив dp размером (len(s1) + 1) x (len(s2) + 1), где dp[i][j] будет хранить наименьшую ASCII-сумму удаленных символов для первых i символов s1 и первых j символов s2. 2⃣Заполните первую строку и первый столбец массива dp суммами ASCII значений символов, которые необходимо удалить для достижения пустой строки. 3⃣Заполните оставшуюся часть массива dp следующим образом: Если символы s1[i-1] и s2[j-1] равны, dp[i][j] = dp[i-1][j-1]. Иначе, dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1])). 😎 Решение:
func minimumDeleteSum(_ s1: String, _ s2: String) -> Int {
let s1Array = Array(s1)
let s2Array = Array(s2)
var dp = Array(repeating: Array(repeating: 0, count: s2Array.count + 1), count: s1Array.count + 1)
for i in 1...s1Array.count {
dp[i][0] = dp[i - 1][0] + Int(s1Array[i - 1].asciiValue!)
}
for j in 1...s2Array.count {
dp[0][j] = dp[0][j - 1] + Int(s2Array[j - 1].asciiValue!)
}
for i in 1...s1Array.count {
for j in 1...s2Array.count {
if s1Array[i - 1] == s2Array[j - 1] {
dp[i][j] = dp[i - 1][j - 1]
} else {
dp[i][j] = min(dp[i - 1][j] + Int(s1Array[i - 1].asciiValue!), dp[i][j - 1] + Int(s2Array[j - 1].asciiValue!))
}
}
}
return dp[s1Array.count][s2Array.count]
}1 348
Задача: 1312. Minimum Insertion Steps to Make a String Palindrome
Сложность: hard
Дана строка s. За один шаг вы можете вставить любой символ в любой индекс строки.
Верните минимальное количество шагов, необходимых для превращения s в палиндром.
Палиндром — это строка, которая читается одинаково как вперед, так и назад.
Пример:
Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we do not need any insertions.class Solution {
private func lcs(_ s1: [Character], _ s2: [Character], _ m: Int, _ n: Int, _ memo: inout [[Int]]) -> Int {
if m == 0 || n == 0 {
return 0
}
if memo[m][n] != -1 {
return memo[m][n]
}
if s1[m - 1] == s2[n - 1] {
return memo[m][n] = 1 + lcs(s1, s2, m - 1, n - 1, &memo)
}
return memo[m][n] = max(lcs(s1, s2, m - 1, n, &memo), lcs(s1, s2, m, n - 1, &memo))
}
func minInsertions(_ s: String) -> Int {
let n = s.count
let sReverse = String(s.reversed())
var memo = Array(repeating: Array(repeating: -1, count: n + 1), count: n + 1)
return n - lcs(Array(s), Array(sReverse), n, n, &memo)
}
}1 348
Задача: 312. Burst Balloons
Сложность: hard
Дано n воздушных шаров, пронумерованных от 0 до n - 1. Каждый шарик окрашен в число, представленное массивом nums. Вам нужно лопнуть все шарики.
Если вы лопаете шарик i, вы получите nums[i - 1] * nums[i] * nums[i + 1] монет. Если i - 1 или i + 1 выходит за границы массива, то считайте, что там находится шарик с числом 1.
Верните максимальное количество монет, которое можно собрать, лопая шарики с умом.
Пример:
Input: nums = [1,5] Output: 10👨💻 Алгоритм: 1⃣Инициализация и подготовка данных Добавьте по одному шару с числом 1 в начало и конец массива nums, чтобы упростить обработку граничных случаев. Определите функцию dp(left, right), которая будет возвращать максимальное количество монет, если лопнуть все шары на интервале [left, right] включительно. 2⃣Вычисление значений для всех интервалов Для каждого интервала [left, right] и каждого индекса i в этом интервале: Вычислите максимальные монеты, которые можно получить, сначала лопая все шары кроме i, а затем лопая i. Обновите dp(left, right) максимальной суммой этих монет. 3⃣Возврат результата Верните значение dp(1, n - 2), которое будет содержать максимальное количество монет, которое можно собрать, лопнув все шары с умом, исключая добавленные нами шары. 😎 Решение:
class Solution {
func maxCoins(_ nums: [Int]) -> Int {
var nums = [1] + nums + [1]
let n = nums.count
var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
for length in 2..<n {
for left in 0..<(n - length) {
let right = left + length
for i in (left + 1)..<right {
dp[left][right] = max(dp[left][right],
nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right])
}
}
}
return dp[0][n - 1]
}
}1 348
Задача: 667. Beautiful Arrangement II
Сложность: medium
Даны два целых числа n и k, составьте список answer, содержащий n различных положительных чисел в диапазоне от 1 до n, который соответствует следующему требованию:
Предположим, что этот список answer = [a1, a2, a3, ... , an], тогда список [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] имеет ровно k различных чисел. Верните список answer. Если существует несколько допустимых ответов, верните любой из них.
Пример:
Input: n = 3, k = 1 Output: [1,2,3] Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1👨💻 Алгоритм: 1⃣Инициализация списка: Начните с создания списка от 1 до n: [1, 2, 3, ..., n]. 2⃣Конструирование шаблона с k различиями: Для обеспечения k различных значений разностей используйте следующий подход: Включайте числа попеременно с конца и начала списка, начиная с n и 1, чтобы создать как можно больше уникальных разностей. Если требуется меньше k, оставшиеся числа просто добавляйте в порядке возрастания, чтобы не увеличивать количество уникальных разностей. 3⃣Заполнение списка: Заполните оставшуюся часть списка последовательными числами, чтобы сохранить уникальные числа в диапазоне от 1 до n. 😎 Решение:
func constructArray(_ n: Int, _ k: Int) -> [Int] {
var answer = [Int]()
var left = 1, right = n
for i in 0...k {
if i % 2 == 0 {
answer.append(left)
left += 1
} else {
answer.append(right)
right -= 1
}
}
if k % 2 == 0 {
answer += left...right
} else {
answer += (left...right).reversed()
}
return answer
}1 348
Задача: 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 348
Задача: 135. Candy
Сложность: hard
В очереди стоят n детей. Каждому ребенку присвоено значение рейтинга, указанное в массиве целых чисел ratings.
Вы раздаете конфеты этим детям с соблюдением следующих требований:
Каждый ребенок должен получить как минимум одну конфету.
Дети с более высоким рейтингом должны получать больше конфет, чем их соседи.
Верните минимальное количество конфет, которое вам нужно иметь, чтобы распределить их среди детей.
Пример:
Input: ratings = [1,0,2] Output: 5 Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.👨💻 Алгоритм: 1⃣Инициализация и первичное заполнение массивов: Создайте два массива: left2right для расчета конфет с учетом только левых соседей и right2left для расчета с учетом только правых соседей. Изначально каждому ученику в обоих массивах присваивается по одной конфете. 2⃣Обход и обновление значений в массивах: Проходите массив ratings слева направо, увеличивая значение в left2right для каждого ученика, чей рейтинг выше рейтинга его левого соседа. Затем проходите массив справа налево, увеличивая значение в right2left для каждого ученика, чей рейтинг выше рейтинга его правого соседа. 3⃣Расчет минимального количества конфет: Для каждого ученика определите максимальное значение конфет между left2right[i] и right2left[i], чтобы соответствовать требованиям к распределению конфет. Суммируйте полученные значения для всех учеников, чтобы найти минимальное количество конфет, необходимое для соблюдения всех правил. 😎 Решение:
func candy(_ ratings: [Int]) -> Int {
let len = ratings.count
var sum = 0
var left2right = Array(repeating: 1, count: len)
var right2left = Array(repeating: 1, count: len)
for i in 1..<len {
if ratings[i] > ratings[i - 1] {
left2right[i] = left2right[i - 1] + 1
}
}
for i in stride(from: len - 2, through: 0, by: -1) {
if ratings[i] > ratings[i + 1] {
right2left[i] = right2left[i + 1] + 1
}
}
for i in 0..<len {
sum += max(left2right[i], right2left[i])
}
return sum
}1 348
Задача: 935. Knight Dialer
Сложность: medium
Шахматный конь обладает уникальным движением: он может перемещаться на две клетки по вертикали и одну клетку по горизонтали, или на две клетки по горизонтали и одну клетку по вертикали (при этом обе клетки образуют форму буквы L). Возможные движения шахматного коня показаны на этой диаграмме: Шахматный конь может двигаться так, как показано на шахматной диаграмме ниже: У нас есть шахматный конь и телефонная панель, как показано ниже, конь может стоять только на числовой клетке (то есть на синей клетке).
Учитывая целое число n, верните, сколько различных телефонных номеров длины n мы можем набрать. Вам разрешается сначала поставить коня на любую цифровую клетку, а затем выполнить n - 1 прыжков, чтобы набрать номер длины n. Все прыжки должны быть правильными прыжками коня. Поскольку ответ может быть очень большим, верните ответ по модулю 10^9 + 7.
Пример:
Input: n = 1 Output: 10👨💻 Алгоритм: 1⃣Определить возможные движения коня с каждой цифровой клетки. Использовать динамическое программирование для хранения количества способов достижения каждой цифровой клетки на каждом шаге. 2⃣Инициализировать массив DP количеством способов набора телефонного номера длины 1 для каждой цифровой клетки (это просто 1). На каждом шаге обновлять массив DP, переходя по всем возможным движениям коня. 3⃣Вернуть сумму всех значений в массиве DP на последнем шаге. 😎 Решение:
var knightDialer = function(n) {
const MOD = 10**9 + 7;
const moves = {
0: [4, 6],
1: [6, 8],
2: [7, 9],
3: [4, 8],
4: [0, 3, 9],
5: [],
6: [0, 1, 7],
7: [2, 6],
8: [1, 3],
9: [2, 4]
};
let dp = new Array(10).fill(1);
for (let step = 1; step < n; step++) {
const newDp = new Array(10).fill(0);
for (let i = 0; i < 10; i++) {
for (const move of moves[i]) {
newDp[move] = (newDp[move] + dp[i]) % MOD;
}
}
dp = newDp;
}
return dp.reduce((acc, val) => (acc + val) % MOD, 0);
};