¡Ya disponible! Investigación de Telegram 2025 — los principales insights del año 
Swift | LeetCode
Ir al canal en Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+bn3i_aLL0-A2ZGMy Вопросы собесов t.me/+wtkjBoN6OI5hNGEy Вакансии t.me/+3o9-Ytdiv_E5OGIy
Mostrar más1 360
Suscriptores
-224 horas
-47 días
-1030 días
Archivo de publicaciones
1 360
Задача: 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
}
}1 360
Задача: 73. Set Matrix Zeroes
Сложность: medium
Дана матрица размером m×n, состоящая из целых чисел. Если элемент матрицы равен 0, установите в 0 все элементы его строки и столбца.
Необходимо выполнить это действие на месте, не используя дополнительное пространство для другой матрицы.
Пример:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]]👨💻 Алгоритм: 1⃣Мы перебираем матрицу и отмечаем первую ячейку строки i и первую ячейку столбца j, если условие в приведенном выше псевдокоде выполняется, т.е. если cell[i][j] == 0. 2⃣Первая ячейка строки и столбца для первой строки и первого столбца совпадают, т.е. cell[0][0]. Поэтому мы используем дополнительную переменную, чтобы узнать, был ли отмечен первый столбец, а cell[0][0] используется для того же для первой строки. 3⃣Теперь мы перебираем исходную матрицу, начиная со второй строки и второго столбца, т.е. с matrix[1][1]. Для каждой ячейки мы проверяем, были ли ранее отмечены строка r или столбец c, проверяя соответствующую первую ячейку строки или первую ячейку столбца. Если любая из них была отмечена, мы устанавливаем значение в ячейке на 0. Обратите внимание, что первая строка и первый столбец служат как row_set и column_set, которые мы использовали в первом подходе. Затем мы проверяем, равна ли cell[0][0] нулю, если это так, мы отмечаем первую строку как ноль. И, наконец, если первый столбец был отмечен, мы делаем все записи в нем нулевыми. 😎 Решение:
func setZeroes(_ matrix: inout [[Int]]) {
var isCol = false
let R = matrix.count
let C = matrix[0].count
for i in 0..<R {
if matrix[i][0] == 0 {
isCol = true
}
for j in 1..<C {
if matrix[i][j] == 0 {
matrix[0][j] = 0
matrix[i][0] = 0
}
}
}
for i in 1..<R {
for j in 1..<C {
if matrix[i][0] == 0 || matrix[0][j] == 0 {
matrix[i][j] = 0
}
}
}
if matrix[0][0] == 0 {
for j in 0..<C {
matrix[0][j] = 0
}
}
if isCol {
for i in 0..<R {
matrix[i][0] = 0
}
}
}1 360
Задача: 294. Flip Game II
Сложность: medium
Вы играете в игру Flip со своим другом.
Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда игрок больше не может сделать ход, и, следовательно, другой игрок становится победителем.
Верните true, если начальный игрок может гарантировать победу, и false в противном случае.
Пример:
Input: currentState = "++++" Output: true Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".👨💻 Алгоритм: 1⃣Генерация всех возможных следующих ходов: Для текущего состояния currentState, создайте все возможные новые состояния, заменяя каждую пару "++" на "--". 2⃣Рекурсивная проверка выигрыша: Для каждого нового состояния вызовите функцию рекурсивно, чтобы проверить, может ли противник проиграть в этом новом состоянии. Если противник не может сделать ход, верните true, так как начальный игрок гарантирует победу. 3⃣Проверка всех возможных ходов: Если для всех возможных ходов начальный игрок не может гарантировать победу, верните false. Иначе, если есть хотя бы один ход, при котором противник проигрывает, верните true. 😎 Решение:
class Solution {
func canWin(_ currentState: String) -> Bool {
var stateArray = Array(currentState)
for i in 0..<(stateArray.count - 1) {
if stateArray[i] == "+" && stateArray[i + 1] == "+" {
stateArray[i] = "-"
stateArray[i + 1] = "-"
let newState = String(stateArray)
if !canWin(newState) {
stateArray[i] = "+"
stateArray[i + 1] = "+"
return true
}
stateArray[i] = "+"
stateArray[i + 1] = "+"
}
}
return false
}
}1 360
Задача: 1357. Apply Discount Every n Orders
Сложность: medium
В супермаркете, который посещает множество покупателей, товары представлены двумя параллельными массивами целых чисел products и prices, где i-й товар имеет идентификатор products[i] и цену prices[i].
Когда покупатель оплачивает товар, его счет представлен двумя параллельными массивами целых чисел product и amount, где j-й приобретенный товар имеет идентификатор product[j], а amount[j] - количество купленного товара. Их промежуточный итог рассчитывается как сумма каждого amount[j] * (цена j-го товара).
Супермаркет решил провести распродажу. Каждому n-му покупателю, оплачивающему свои покупки, будет предоставлена скидка в процентах. Сумма скидки задается параметром discount, и покупатель получит скидку в discount процентов от своего промежуточного итога. Формально, если их промежуточный итог составляет bill, то они фактически заплатят bill * ((100 - discount) / 100).
Реализуйте класс Cashier:
Cashier(int n, int discount, int[] products, int[] prices): инициализирует объект с параметрами n, discount, а также массивами товаров и их цен.
double getBill(int[] product, int[] amount): возвращает итоговую сумму счета с примененной скидкой (если применима). Ответы, отличающиеся от фактического значения не более чем на 10^-5, будут приняты.
Пример:
Input ["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"] [[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]] Output [null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]👨💻 Алгоритм: 1⃣Инициализация объекта: Создайте класс Cashier с конструктором, который принимает параметры n, discount, products и prices. В конструкторе инициализируйте необходимые переменные и создайте словарь для сопоставления идентификаторов продуктов с их ценами. 2⃣Обработка каждого счета: Создайте метод getBill, который принимает массивы product и amount. Вычислите промежуточный итог счета, умножая количество каждого продукта на его цену и суммируя результаты. Увеличьте счетчик клиентов. Если клиент является n-м по счету, примените скидку к промежуточному итогу. 3⃣Верните итоговую сумму счета. 😎 Решение:
class Cashier {
private let n: Int
private let discount: Int
private var productsPrices: [Int: Int]
private var customerCount: Int
init(_ n: Int, _ discount: Int, _ products: [Int], _ prices: [Int]) {
self.n = n
self.discount = discount
self.customerCount = 0
self.productsPrices = Dictionary(uniqueKeysWithValues: zip(products, prices))
}
func getBill(_ product: [Int], _ amount: [Int]) -> Double {
customerCount += 1
var bill = 0.0
for (index, prod) in product.enumerated() {
bill += Double(productsPrices[prod]! * amount[index])
}
if customerCount % n == 0 {
bill *= Double(100 - discount) / 100.0
}
return bill
}
}1 360
Задача: 128. Longest Consecutive Sequence
Сложность: Medium
Дан несортированный массив целых чисел nums. Верните длину самой длинной последовательности последовательных элементов.
Необходимо написать алгоритм, который работает за время O(n).
Пример:
Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.👨💻 Алгоритм: 1⃣Проверка базового случая: Перед началом работы проверяем базовый случай с пустым массивом. Самая длинная последовательность в пустом массиве, очевидно, равна 0, поэтому мы можем просто вернуть это значение. 2⃣Обработка чисел в массиве: Для всех других случаев мы сортируем массив nums и рассматриваем каждое число, начиная со второго (поскольку нам нужно сравнивать каждое число с предыдущим). Если текущее число и предыдущее равны, то текущая последовательность не удлиняется и не прерывается, поэтому мы просто переходим к следующему числу. Если числа не равны, то нужно проверить, удлиняет ли текущее число последовательность (т.е. nums[i] == nums[i-1] + 1). Если удлиняет, то мы увеличиваем наш текущий счёт и продолжаем. 3⃣Завершение обработки и возврат результата: В противном случае последовательность прерывается, и мы записываем нашу текущую последовательность и сбрасываем её до 1 (чтобы включить число, которое прервало последовательность). Возможно, что последний элемент массива nums является частью самой длинной последовательности, поэтому мы возвращаем максимум из текущей последовательности и самой длинной. 😎 Решение:
func longestConsecutive(_ nums: [Int]) -> Int {
var longestStreak = 0
let numSet = Set(nums)
for num in numSet {
if !numSet.contains(num - 1) {
var currentNum = num
var currentStreak = 1
while numSet.contains(currentNum + 1) {
currentNum += 1
currentStreak += 1
}
longestStreak = max(longestStreak, currentStreak)
}
}
return longestStreak
}1 360
Задача: 684. Redundant Connection
Сложность: medium
В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов.
Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе.
Верните ребро, которое можно удалить, чтобы результирующий граф стал деревом из n узлов. Если существует несколько ответов, верните тот, который встречается последним в исходных данных.
Пример:
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]class Solution {
var seen = Set<Int>()
let MAX_EDGE_VAL = 1000
func findRedundantConnection(_ edges: [[Int]]) -> [Int] {
var graph = Array(repeating: [Int](), count: MAX_EDGE_VAL + 1)
for edge in edges {
seen.removeAll()
if !graph[edge[0]].isEmpty && !graph[edge[1]].isEmpty && dfs(graph, edge[0], edge[1]) {
return edge
}
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
}
return []
}
func dfs(_ graph: [[Int]], _ source: Int, _ target: Int) -> Bool {
if !seen.contains(source) {
seen.insert(source)
if source == target { return true }
for nei in graph[source] {
if dfs(graph, nei, target) { return true }
}
}
return false
}
}1 360
Задача: 263. Ugly Number
Сложность: easy
Уродливое число — это положительное целое число, простые множители которого ограничены числами 2, 3 и 5.
Дано целое число n, верните true, если n является уродливым числом.
Пример:
Input: n = 6 Output: true Explanation: 6 = 2 × 3👨💻 Алгоритм: 1⃣Если данное целое число n неположительное, верните false, так как неположительное число не может быть уродливым. 2⃣Определите функцию keepDividingWhenDivisible, которая принимает два аргумента: делимое и делитель. Эта функция будет делить делимое на делитель до тех пор, пока оно делится без остатка. Функция возвращает измененное делимое. Последовательно примените эту функцию к n с делителями 2, 3 и 5. 3⃣Если после всех делений n равно 1, верните true, иначе верните false. 😎 Решение:
class Solution {
func isUgly(_ n: Int) -> Bool {
if n <= 0 {
return false
}
var n = n
for factor in [2, 3, 5] {
n = keepDividingWhenDivisible(n, factor)
}
return n == 1
}
private func keepDividingWhenDivisible(_ dividend: Int, _ divisor: Int) -> Int {
var dividend = dividend
while dividend % divisor == 0 {
dividend /= divisor
}
return dividend
}
}1 360
Задача: 931. Minimum Falling Path Sum
Сложность: medium
Если задан массив целых чисел n x n, верните минимальную сумму любого падающего пути через матрицу. Падающий путь начинается с любого элемента в первой строке и выбирает элемент в следующей строке, который находится либо прямо под ним, либо по диагонали слева/справа. В частности, следующим элементом из позиции (row, col) будет (row + 1, col - 1), (row + 1, col) или (row + 1, col + 1).
Пример:
Input: matrix = [[2,1,3],[6,5,4],[7,8,9]] Output: 13👨💻 Алгоритм: 1⃣Использовать динамическое программирование для хранения минимальных сумм падающих путей для каждой позиции. 2⃣Инициализировать dp массив копией первой строки исходной матрицы. Пройти по каждой строке, обновляя dp массив на основе значений из предыдущей строки. 3⃣Вернуть минимальное значение в последней строке dp массива. 😎 Решение:
class Solution {
func minFallingPathSum(_ matrix: [[Int]]) -> Int {
let n = matrix.count
var dp = matrix[0]
for i in 1..<n {
var newDp = [Int](repeating: 0, count: n)
for j in 0..<n {
newDp[j] = matrix[i][j] + min(dp[j], dp[j-1] ?? Int.max, dp[j+1] ?? Int.max)
}
dp = newDp
}
return dp.min()!
}
}1 360
Задача: 844. Backspace String Compare
Сложность: easy
Даны две строки s и t, верните true, если они равны после ввода в пустые текстовые редакторы. Символ '#' означает клавишу backspace.
Обратите внимание, что после нажатия backspace на пустом тексте, текст останется пустым.
Пример:
Input: s = "ab#c", t = "ad#c" Output: true Explanation: Both s and t become "ac".👨💻 Алгоритм: 1⃣Пройдите по строкам s и t с конца, учитывая символы '#' как backspace и пропуская соответствующие символы. 2⃣Сравнивайте текущие символы из обеих строк, пропуская символы, которые должны быть удалены. 3⃣Если все соответствующие символы совпадают и строки эквивалентны после всех backspace операций, верните true; в противном случае верните false. 😎 Решение:
class Solution {
func backspaceCompare(_ S: String, _ T: String) -> Bool {
var i = S.count - 1, j = T.count - 1
var skipS = 0, skipT = 0
let sArray = Array(S), tArray = Array(T)
while i >= 0 || j >= 0 {
while i >= 0 {
if sArray[i] == "#" {
skipS += 1
i -= 1
} else if skipS > 0 {
skipS -= 1
i -= 1
} else {
break
}
}
while j >= 0 {
if tArray[j] == "#" {
skipT += 1
j -= 1
} else if skipT > 0 {
skipT -= 1
j -= 1
} else {
break
}
}
if i >= 0 && j >= 0 && sArray[i] != tArray[j] {
return false
}
if (i >= 0) != (j >= 0) {
return false
}
i -= 1
j -= 1
}
return true
}
}1 360
Задача: 438. Find All Anagrams in a String
Сложность: medium
Даны две строки s и p, вернуть массив всех начальных индексов анаграмм строки p в строке s. Ответ можно вернуть в любом порядке.
Анаграмма - это слово или фраза, образованные перестановкой букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.
Пример:
Input: s = "cbaebabacd", p = "abc" Output: [0,6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".👨💻 Алгоритм: 1⃣Построить эталонный счетчик pCount для строки p. 2⃣Передвигать скользящее окно по строке s: Пересчитывать счетчик скользящего окна sCount на каждом шаге, добавляя одну букву справа и удаляя одну букву слева. 3⃣Если sCount == pCount, обновить выходной список. Вернуть выходной список. 😎 Решение:
class Solution {
func findAnagrams(_ s: String, _ p: String) -> [Int] {
let ns = s.count, np = p.count
if ns < np { return [] }
var pCount = [Character: Int]()
var sCount = [Character: Int]()
for ch in p {
pCount[ch, default: 0] += 1
}
var output = [Int]()
let sArray = Array(s)
for i in 0..<ns {
let ch = sArray[i]
sCount[ch, default: 0] += 1
if i >= np {
let leftChar = sArray[i - np]
if sCount[leftChar] == 1 {
sCount.removeValue(forKey: leftChar)
} else {
sCount[leftChar]! -= 1
}
}
if pCount == sCount {
output.append(i - np + 1)
}
}
return output
}
}1 360
Задача: 677. Map Sum Pairs
Сложность: medium
Создайте карту, которая позволяет выполнять следующие действия:
Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:
MapSum() Инициализирует объект MapSum.
void insert(String key, int val) Вставляет пару ключ-значение в карту. Если ключ уже существовал, исходная пара ключ-значение будет заменена на новую.
int sum(string prefix) Возвращает сумму всех значений пар, у которых ключ начинается с данного префикса.
Пример:
Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]
Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);
mapSum.sum("ap"); // return 3 (apple = 3)
mapSum.insert("app", 2);
mapSum.sum("ap"); // return 5 (apple + app = 3 + 2 = 5)
👨💻 Алгоритм:
1⃣Для каждого ключа в карте проверить, начинается ли этот ключ с данного префикса.
2⃣Если ключ начинается с префикса, добавить его значение к ответу.
3⃣Вернуть полученную сумму как результат.
😎 Решение:
class MapSum {
private var mapData: [String: Int]
init() {
self.mapData = [:]
}
func insert(_ key: String, _ val: Int) {
mapData[key] = val
}
func sum(_ prefix: String) -> Int {
var ans = 0
for (key, val) in mapData {
if key.hasPrefix(prefix) {
ans += val
}
}
return ans
}
}1 360
Задача: 1380. Lucky Numbers in a Matrix
Сложность: easy
Дана матрица m x n из различных чисел, верните все счастливые числа в матрице в любом порядке.
Счастливое число — это элемент матрицы, который является минимальным элементом в своей строке и максимальным в своем столбце.
Пример:
Input: matrix = [[3,7,8],[9,11,13],[15,16,17]] Output: [15] Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column.👨💻 Алгоритм: 1⃣Сохраните минимум каждой строки в список rowMin и максимум каждого столбца в список colMax. 2⃣Итерируйте по каждому числу в матрице и проверяйте, равно ли оно rowMin[i] и colMax[j]. 3⃣Если число удовлетворяет условию, добавьте его в список luckyNumbers и верните luckyNumbers. 😎 Решение:
class Solution {
func luckyNumbers (_ matrix: [[Int]]) -> [Int] {
let N = matrix.count
let M = matrix[0].count
var rowMin = [Int]()
for i in 0..<N {
var rMin = Int.max
for j in 0..<M {
rMin = min(rMin, matrix[i][j])
}
rowMin.append(rMin)
}
var colMax = [Int]()
for i in 0..<M {
var cMax = Int.min
for j in 0..<N {
cMax = max(cMax, matrix[j][i])
}
colMax.append(cMax)
}
var luckyNumbers = [Int]()
for i in 0..<N {
for j in 0..<M {
if matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j] {
luckyNumbers.append(matrix[i][j])
}
}
}
return luckyNumbers
}
}1 360
Задача: 1315. Sum of Nodes with Even-Valued Grandparent
Сложность: medium
Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.
A grandparent of a node is the parent of its parent if it exists.
Пример:
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.class Solution {
private func solve(_ root: TreeNode?, _ parent: Int, _ gParent: Int) -> Int {
guard let root = root else {
return 0
}
return solve(root.left, root.val, parent)
+ solve(root.right, root.val, parent)
+ (gParent % 2 == 0 ? root.val : 0)
}
func sumEvenGrandparent(_ root: TreeNode?) -> Int {
return solve(root, -1, -1)
}
}1 360
📱 Стажировки и вакансии для SWIFT разработчиков.
- Вакансии которых нет на джоб-агрегаторах
- Только прямые контакты HR в Telegram
👉 @jobs_swift
🤖 ML & DS 👩💻 DevOps
👨✈️ ИБ & OSINT 👣 Go
👩💻 Mobile 👩💻 C#
👩💻 Node.js 👩💻 Python
🔎 QA 👩💻 Java
👩💻 UX/UI 👩💻 Frontend
🖼️ PHP 📋 Analyst
💼 1C 🖥 SQL
👩💻 IT HR
Пока другие листают джоб-сайты — ты уже пишешь HR в Telegram.
1 360
Задача: 1066. Campus Bikes II
Сложность: medium
На кампусе, представленном в виде двумерной сетки, есть n рабочих и m велосипедов, где n <= m. Каждый рабочий и велосипед имеют координаты на этой сетке.
Мы назначаем каждому рабочему уникальный велосипед таким образом, чтобы сумма Манхэттенских расстояний между каждым рабочим и назначенным ему велосипедом была минимальной.
Верните минимально возможную сумму Манхэттенских расстояний между каждым рабочим и назначенным ему велосипедом.
Манхэттенское расстояние между двумя точками p1 и p2 вычисляется как Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
Пример:
Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]class Solution {
var smallestDistanceSum = Int.max
var visited = [Bool](repeating: false, count: 10)
func findDistance(_ worker: [Int], _ bike: [Int]) -> Int {
return abs(worker[0] - bike[0]) + abs(worker[1] - bike[1])
}
func minimumDistanceSum(_ workers: [[Int]], _ workerIndex: Int,
_ bikes: [[Int]], _ currDistanceSum: Int) {
if workerIndex >= workers.count {
smallestDistanceSum = min(smallestDistanceSum, currDistanceSum)
return
}
if currDistanceSum >= smallestDistanceSum {
return
}
for bikeIndex in 0..<bikes.count {
if !visited[bikeIndex] {
visited[bikeIndex] = true
minimumDistanceSum(workers, workerIndex + 1, bikes,
currDistanceSum + findDistance(workers[workerIndex], bikes[bikeIndex]))
visited[bikeIndex] = false
}
}
}
func assignBikes(_ workers: [[Int]], _ bikes: [[Int]]) -> Int {
minimumDistanceSum(workers, 0, bikes, 0)
return smallestDistanceSum
}
}1 360
Задача: 354. Russian Doll Envelopes
Сложность: hard
Вам дан двумерный массив целых чисел envelopes, где envelopes[i] = [wi, hi] представляет ширину и высоту конверта.
Один конверт может поместиться в другой, если и только если ширина и высота одного конверта больше ширины и высоты другого конверта.
Верните максимальное количество конвертов, которые вы можете вложить друг в друга (т.е. поместить один в другой).
Примечание: Вы не можете поворачивать конверт.
Пример:
Input: envelopes = [[5,4],[6,4],[6,7],[2,3]] Output: 3 Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).👨💻 Алгоритм: 1⃣Отсортируйте массив конвертов по возрастанию по первой размерности (ширине) и по убыванию по второй размерности (высоте). 2⃣Извлеките вторую размерность (высоты) отсортированного массива. 3⃣Найдите длину наибольшей возрастающей подпоследовательности в массиве высот. 😎 Решение:
class Solution {
func lengthOfLIS(_ nums: [Int]) -> Int {
var dp = [Int](repeating: 0, count: nums.count)
var len = 0
for num in nums {
var i = dp.binarySearch(0..<len, num)
if i < 0 { i = -(i + 1) }
dp[i] = num
if i == len { len += 1 }
}
return len
}
func maxEnvelopes(_ envelopes: [[Int]]) -> Int {
let sortedEnvelopes = envelopes.sorted {
if $0[0] == $1[0] { return $0[1] > $1[1] }
return $0[0] < $1[0]
}
let secondDim = sortedEnvelopes.map { $0[1] }
return lengthOfLIS(secondDim)
}
}
extension Array where Element == Int {
func binarySearch(_ range: Range<Int>, _ target: Int) -> Int {
var left = range.lowerBound
var right = range.upperBound
while left < right {
let mid = left + (right - left) / 2
if self[mid] < target {
left = mid + 1
} else {
right = mid
}
}
return left < range.upperBound && self[left] == target ? left : -(left + 1)
}
}1 360
Задача: 1262. Greatest Sum Divisible by Three
Сложность: medium
Если задан целочисленный массив nums, верните максимально возможную сумму элементов массива, которая делится на три.
Пример:
Input: nums = [3,6,5,1,8] Output: 18👨💻 Алгоритм: 1⃣Найдите сумму всех элементов массива. 2⃣Если сумма делится на 3, то она и есть ответ. 3⃣Если сумма при делении на 3 дает остаток 1, удалите один элемент с остатком 1 или два элемента с остатком 2 (если их сумма равна 2). Если сумма при делении на 3 дает остаток 2, удалите один элемент с остатком 2 или два элемента с остатком 1 (если их сумма равна 2). 😎 Решение:
class Solution {
func maxSumDivThree(_ nums: [Int]) -> Int {
let totalSum = nums.reduce(0, +)
if totalSum % 3 == 0 {
return totalSum
}
var mod1 = [Int]()
var mod2 = [Int]()
for num in nums {
if num % 3 == 1 {
mod1.append(num)
} else if num % 3 == 2 {
mod2.append(num)
}
}
mod1.sort()
mod2.sort()
if totalSum % 3 == 1 {
let remove1 = mod1.isEmpty ? Int.max : mod1[0]
let remove2 = mod2.count < 2 ? Int.max : mod2[0] + mod2[1]
return totalSum - min(remove1, remove2)
} else {
let remove2 = mod2.isEmpty ? Int.max : mod2[0]
let remove1 = mod1.count < 2 ? Int.max : mod1[0] + mod1[1]
return totalSum - min(remove2, remove1)
}
}
}1 360
Задача: 1662. Check If Two String Arrays are Equivalent
Сложность: easy
Даны два массива строк
word1 и word2. Верните true, если два массива представляют одну и ту же строку, и false в противном случае.
Строка представлена массивом, если элементы массива, соединенные в порядке, образуют строку.
Пример:
Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.class Solution {
func arrayStringsAreEqual(_ word1: [String], _ word2: [String]) -> Bool {
let list2 = word2.joined()
var index = list2.startIndex
for word in word1 {
for char in word {
if index == list2.endIndex || char != list2[index] {
return false
}
index = list2.index(after: index)
}
}
return index == list2.endIndex
}
}1 360
Задача: 851. Loud and Rich
Сложность: medium
Есть группа из n человек, пронумерованных от 0 до n - 1, где у каждого человека разное количество денег и разный уровень спокойствия.
Вам дан массив richer, где richer[i] = [ai, bi] указывает на то, что ai имеет больше денег, чем bi, и целочисленный массив quiet, где quiet[i] — это уровень спокойствия i-го человека. Все данные в richer логически корректны (т.е. данные не приведут к ситуации, где x богаче y и y богаче x одновременно).
Верните целочисленный массив answer, где answer[x] = y, если y — это самый спокойный человек (то есть человек y с наименьшим значением quiet[y]) среди всех людей, которые однозначно имеют столько же или больше денег, чем человек x.
Пример:
Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output: [5,5,2,5,4,5,6,7]
Explanation:
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but it is not clear if they have more money than person 0.
answer[7] = 7.
Among all people that definitely have equal to or more money than person 7 (which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x]) is person 7.
The other answers can be filled out with similar reasoning.class Solution {
var graph: [[Int]] = []
var answer: [Int] = []
var quiet: [Int] = []
func loudAndRich(_ richer: [[Int]], _ quiet: [Int]) -> [Int] {
let N = quiet.count
graph = Array(repeating: [], count: N)
answer = Array(repeating: -1, count: N)
self.quiet = quiet
for edge in richer {
graph[edge[1]].append(edge[0])
}
for node in 0..<N {
_ = dfs(node)
}
return answer
}
func dfs(_ node: Int) -> Int {
if answer[node] == -1 {
answer[node] = node
for child in graph[node] {
let cand = dfs(child)
if quiet[cand] < quiet[answer[node]] {
answer[node] = cand
}
}
}
return answer[node]
}
}1 360
Задача: 287. Find the Duplicate Number
Сложность: medium
Дан массив целых чисел nums, содержащий n + 1 целых чисел, где каждое число находится в диапазоне [1, n] включительно.
В массиве есть только одно повторяющееся число, верните это повторяющееся число.
Вы должны решить задачу, не изменяя массив nums и используя только постоянное дополнительное пространство.
Пример:
Input: nums = [1,3,4,2,2] Output: 2👨💻 Алгоритм: 1⃣Определение дубликата: Итерируйте по массиву, оценивая каждый элемент (назовем его cur). Используйте абсолютное значение текущего элемента, чтобы получить индекс. Если элемент по индексу cur отрицательный, значит, мы уже встречали этот элемент ранее, и cur является дубликатом. Сохраните cur как дубликат и выйдите из цикла. Если элемент по индексу cur положительный, инвертируйте знак этого элемента, чтобы пометить его как встреченный, и перейдите к следующему элементу. 2⃣Восстановление массива: Пройдите по массиву и измените все отрицательные элементы обратно на положительные, чтобы восстановить исходное состояние массива. 3⃣Возврат результата: Верните найденный дубликат. 😎 Решение:
class Solution {
func findDuplicate(_ nums: [Int]) -> Int {
var nums = nums
var duplicate = -1
for i in 0..<nums.count {
let cur = abs(nums[i])
if nums[cur] < 0 {
duplicate = cur
break
}
nums[cur] *= -1
}
for i in 0..<nums.count {
nums[i] = abs(nums[i])
}
return duplicate
}
}