Swift | LeetCode
Open in Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Show more
1 273
Subscribers
-224 hours
-77 days
-2530 days
Posts Archive
1 273
Задача: 1267. Count Servers that Communicate
Сложность: medium
На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение.
Пример:
Input: grid = [[1,0],[0,1]] Output: 0👨💻 Алгоритм: 1⃣Подсчитайте количество серверов в каждой строке и каждом столбце. 2⃣Пройдите по каждой ячейке и определите, взаимодействует ли сервер с другими серверами в той же строке или столбце. 3⃣Подсчитайте и верните количество взаимодействующих серверов. 😎 Решение:
class Solution {
func countServers(_ grid: [[Int]]) -> Int {
var rows = [Int](repeating: 0, count: grid.count)
var cols = [Int](repeating: 0, count: grid[0].count)
for i in 0..<grid.count {
for j in 0..<grid[0].count {
if grid[i][j] == 1 {
rows[i] += 1
cols[j] += 1
}
}
}
var count = 0
for i in 0..<grid.count {
for j in 0..<grid[0].count {
if grid[i][j] == 1 && (rows[i] > 1 || cols[j] > 1) {
count += 1
}
}
}
return count
}
}1 273
Задача: 943. Find the Shortest Superstring
Сложность: hard
Учитывая массив строк words, верните наименьшую строку, которая содержит каждую строку в words в качестве подстроки. Если существует несколько допустимых строк наименьшей длины, верните любую из них. Вы можете предположить, что ни одна строка в words не является подстрокой другой строки в words.
Пример:
Input: words = ["alex","loves","leetcode"] Output: "alexlovesleetcode"👨💻 Алгоритм: 1⃣Реализовать функцию overlap для вычисления максимального перекрытия двух строк, где одна строка заканчивается, а другая начинается. 2⃣Реализовать функцию merge для объединения двух строк с максимальным перекрытием. Использовать жадный алгоритм для нахождения двух строк с максимальным перекрытием и объединить их, повторяя до тех пор, пока не останется одна строка. 3⃣Вернуть результат. 😎 Решение:
class Solution {
func shortestSuperstring(_ words: [String]) -> String {
func overlap(_ a: String, _ b: String) -> Int {
let aArr = Array(a), bArr = Array(b)
var maxOverlap = 0
for i in 1...min(aArr.count, bArr.count) {
if aArr.suffix(i) == bArr.prefix(i) {
maxOverlap = i
}
}
return maxOverlap
}
func merge(_ a: String, _ b: String, _ overlapLen: Int) -> String {
return a + String(b.dropFirst(overlapLen))
}
var words = words
while words.count > 1 {
var maxOverlap = -1
var l = 0, r = 0
for i in 0..<words.count {
for j in 0..<words.count {
if i != j {
let ovlp = overlap(words[i], words[j])
if ovlp > maxOverlap {
maxOverlap = ovlp
l = i
r = j
}
}
}
}
words.append(merge(words[l], words[r], maxOverlap))
words.remove(at: r)
words.remove(at: l)
}
return words[0]
}
}1 273
Задача: 278. First Bad Version
Сложность: easy
Вы являетесь менеджером продукта и в настоящее время возглавляете команду по разработке нового продукта. К сожалению, последняя версия вашего продукта не прошла проверку качества. Поскольку каждая версия разрабатывается на основе предыдущей версии, все версии, вышедшие после плохой версии, также оказываются плохими.
Предположим, у вас есть n версий [1, 2, ..., n], и вы хотите выяснить первую плохую версию, которая вызывает все последующие версии быть плохими.
Вам предоставлен API bool isBadVersion(version), который возвращает, является ли версия плохой. Реализуйте функцию для нахождения первой плохой версии. Вы должны минимизировать количество вызовов API.
Пример:
Input: n = 5, bad = 4 Output: 4 Explanation: call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true Then 4 is the first bad version.👨💻 Алгоритм: 1⃣Инициализация границ поиска: Устанавливаем начальные значения левой и правой границ поиска: left = 1 и right = n. 2⃣Бинарный поиск: Пока левая граница меньше правой, находим среднюю точку mid и проверяем, является ли она плохой версией с помощью isBadVersion(mid). Если текущая версия mid плохая, смещаем правую границу к mid, иначе смещаем левую границу на mid + 1. 3⃣Возврат результата: Когда левая граница станет равной правой, возвращаем left как индекс первой плохой версии. 😎 Решение:
class Solution {
func firstBadVersion(_ n: Int) -> Int {
var left = 1
var right = n
while left < right {
let mid = left + (right - left) / 2
if isBadVersion(mid) {
right = mid
} else {
left = mid + 1
}
}
return left
}
}1 273
Задача: 383. Ransom Note
Сложность: easy
Даны две строки ransomNote и magazine, верните true, если ransomNote можно составить, используя буквы из magazine, и false в противном случае.
Каждая буква из magazine может быть использована в ransomNote только один раз.
Пример:
Input: ransomNote = "a", magazine = "b" Output: false👨💻 Алгоритм: 1⃣Поскольку строки являются неизменяемым типом, их нельзя изменять, поэтому у них нет операций "вставки" и "удаления". 2⃣По этой причине необходимо заменять строку magazine новой строкой, в которой отсутствует символ, который мы хотели удалить. 3⃣Повторяйте этот процесс, пока не будут удалены все необходимые символы. 😎 Решение:
func canConstruct(_ ransomNote: String, _ magazine: String) -> Bool {
var magazine = magazine
for char in ransomNote {
if let index = magazine.firstIndex(of: char) {
magazine.remove(at: index)
} else {
return false
}
}
return true
}1 273
Задача: 1091. Shortest Path in Binary Matrix
Сложность: medium
Дан бинарный матричный массив grid размером n x n. Верните длину самого короткого чистого пути в матрице. Если чистого пути не существует, верните -1.
Чистый путь в бинарной матрице — это путь из верхнего левого угла (т.е. (0, 0)) в нижний правый угол (т.е. (n - 1, n - 1)), такой что:
Все посещенные клетки пути равны 0.
Все соседние клетки пути соединены по 8 направлениям (т.е. они различны и имеют общую сторону или угол).
Длина чистого пути — это количество посещенных клеток этого пути.
Пример:
Input: grid = [[0,1],[1,0]] Output: 2👨💻 Алгоритм: 1⃣Проверить, что начальная и конечная клетки открыты (равны 0). Если нет, вернуть -1. 2⃣Выполнить поиск в ширину (BFS) из начальной клетки, добавляя в очередь соседние клетки, если они открыты и еще не посещены. Обновлять длину пути для каждой клетки. 3⃣Если достигнута конечная клетка, вернуть длину пути. Если очередь пуста и конечная клетка не достигнута, вернуть -1. 😎 Решение:
class Solution {
private let directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
func shortestPathBinaryMatrix(_ grid: [[Int]]) -> Int {
if grid[0][0] != 0 || grid[grid.count - 1][grid[0].count - 1] != 0 {
return -1
}
var grid = grid
var queue: [(Int, Int)] = [(0, 0)]
grid[0][0] = 1
while !queue.isEmpty {
let (row, col) = queue.removeFirst()
let distance = grid[row][col]
if row == grid.count - 1 && col == grid[0].count - 1 {
return distance
}
for direction in directions {
let newRow = row + direction.0
let newCol = col + direction.1
if newRow >= 0 && newCol >= 0 && newRow < grid.count && newCol < grid[0].count && grid[newRow][newCol] == 0 {
queue.append((newRow, newCol))
grid[newRow][newCol] = distance + 1
}
}
}
return -1
}
}1 273
Задача: 986. Interval List Intersections
Сложность: medium
Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.
Верните пересечение этих двух списков интервалов.
Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.
Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].
Пример:
Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]👨💻 Алгоритм: 1⃣Инициализация указателей: Завести два указателя i и j, указывающие на начало firstList и secondList соответственно. 2⃣Поиск пересечений: Пока оба указателя находятся в пределах своих списков, выполнить следующие действия: Найти максимальное начало и минимальный конец текущих интервалов. Если начало меньше или равно концу, добавить пересечение в результат. Сдвинуть указатель списка, у которого текущий интервал заканчивается раньше. 3⃣Возврат результата: Вернуть список пересечений. 😎 Решение:
func intervalIntersection(_ firstList: [[Int]], _ secondList: [[Int]]) -> [[Int]] {
var i = 0, j = 0
var result = [[Int]]()
while i < firstList.count && j < secondList.count {
let start = max(firstList[i][0], secondList[j][0])
let end = min(firstList[i][1], secondList[j][1])
if start <= end {
result.append([start, end])
}
if firstList[i][1] < secondList[j][1] {
i += 1
} else {
j += 1
}
}
return result
}1 273
Задача: 394. Decode String
Сложность: medium
Дана закодированная строка, вернуть её декодированную версию.
Правило кодирования следующее: k[закодированная_строка], где закодированная_строка внутри квадратных скобок повторяется ровно k раз. Обратите внимание, что k гарантированно является положительным целым числом.
Можно предположить, что входная строка всегда допустима; нет лишних пробелов, квадратные скобки корректно сформированы и т.д. Более того, можно предположить, что исходные данные не содержат никаких цифр, и что цифры используются только для обозначения количества повторений, k. Например, не будет таких входных данных, как 3a или 2[4].
Тестовые случаи сгенерированы так, что длина выходной строки никогда не превысит 105.
Пример:
Input: s = "3[a]2[bc]" Output: "aaabcbc"👨💻 Алгоритм: 1⃣Проходите по строке s и обрабатывайте каждый символ. Если текущий символ не является закрывающей скобкой ], поместите его в стек. 2⃣Если текущий символ является закрывающей скобкой ], начните декодировать последнюю пройденную строку. Извлекайте из стека символы, пока следующий символ не станет открывающей скобкой [, и добавляйте каждый символ (a-z) к decodedString. Затем извлеките открывающую скобку [ из стека и извлекайте символы, пока следующий символ является цифрой (0-9), чтобы собрать число k. 3⃣Декодируйте шаблон k[decodedString], помещая decodedString в стек k раз. После того как вся строка будет пройдена, извлеките результат из стека и верните его. 😎 Решение:
class Solution {
func decodeString(_ s: String) -> String {
var stack = [Character]()
for char in s {
if char == "]" {
var decodedString = ""
while let last = stack.last, last != "[" {
decodedString = String(stack.removeLast()) + decodedString
}
stack.removeLast()
var k = 0
var base = 1
while let last = stack.last, let digit = last.wholeNumberValue {
k += digit * base
base *= 10
stack.removeLast()
}
for _ in 0..<k {
for c in decodedString {
stack.append(c)
}
}
} else {
stack.append(char)
}
}
return String(stack)
}
}1 273
Задача: 1219. Path with Maximum Gold
Сложность: medium
В золотом руднике размером m x n каждая ячейка содержит целое число, представляющее количество золота в этой ячейке, или 0, если она пуста.
Верните максимальное количество золота, которое вы можете собрать при следующих условиях:
- Каждый раз, когда вы находитесь в ячейке, вы собираете всё золото из этой ячейки.
- Из вашей позиции вы можете сделать один шаг влево, вправо, вверх или вниз.
- Вы не можете посещать одну и ту же ячейку более одного раза.
- Никогда не посещайте ячейку с 0 золотом.
- Вы можете начинать и прекращать сбор золота с любой позиции в сетке, которая содержит золото.
Пример:
Input: grid = [[0,6,0],[5,8,7],[0,9,0]] Output: 24 Explanation: [[0,6,0], [5,8,7], [0,9,0]] Path to get the maximum gold, 9 -> 8 -> 7.👨💻 Алгоритм: 1⃣Инициализация и подготовка: Инициализируйте константный массив DIRECTIONS для направления перемещений. Определите количество строк и столбцов в сетке. Инициализируйте переменную maxGold для хранения максимального количества собранного золота. 2⃣Функция DFS и обратный трек: Реализуйте функцию dfsBacktrack для поиска пути с максимальным золотом с помощью DFS и обратного трека. Обрабатывайте базовый случай, проверяя выход за пределы сетки или ячейки без золота. Пометьте текущую ячейку как посещённую и сохраните её значение. Исследуйте каждую из четырёх смежных ячеек и обновите максимальное количество золота, если найден лучший путь. Сбросьте текущую ячейку до её исходного значения для дальнейших исследований. 3⃣Поиск максимального золота: Используйте вложенные циклы для каждой ячейки в сетке, чтобы найти максимальное количество золота, начиная с этой ячейки, с помощью функции dfsBacktrack. Обновите maxGold при нахождении лучшего пути. Верните maxGold. 😎 Решение:
class Solution {
let directions = [0, 1, 0, -1, 0]
func getMaximumGold(_ grid: [[Int]]) -> Int {
var grid = grid
let rows = grid.count
let cols = grid[0].count
var maxGold = 0
for row in 0..<rows {
for col in 0..<cols {
maxGold = max(maxGold, dfsBacktrack(&grid, rows, cols, row, col))
}
}
return maxGold
}
func dfsBacktrack(_ grid: inout [[Int]], _ rows: Int, _ cols: Int, _ row: Int, _ col: Int) -> Int {
if row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] == 0 {
return 0
}
let originalVal = grid[row][col]
grid[row][col] = 0
var maxGold = 0
for i in 0..<4 {
maxGold = max(maxGold, dfsBacktrack(&grid, rows, cols, row + directions[i], col + directions[i + 1]))
}
grid[row][col] = originalVal
return maxGold + originalVal
}
}1 273
Задача: 228. Summary Ranges
Сложность: easy
Вам дан отсортированный массив уникальных целых чисел nums.
Диапазон [a,b] - это множество всех целых чисел от a до b (включительно).
Верните наименьший отсортированный список диапазонов, которые покрывают все числа в массиве точно. То есть, каждый элемент nums покрывается ровно одним из диапазонов, и не существует такого целого числа x, чтобы x находился в одном из диапазонов, но не находился в nums.
Каждый диапазон [a,b] в списке должен быть представлен в формате:
"a->b" если a != b
"a" если a == b
Пример:
Input: nums = [0,1,2,4,5,7] Output: ["0->2","4->5","7"] Explanation: The ranges are: [0,2] --> "0->2" [4,5] --> "4->5" [7,7] --> "7"👨💻 Алгоритм: 1⃣Создайте список строк ranges, который будет содержать решение задачи, и начните итерацию по всем элементам nums с указателем i = 0. Каждая итерация внешнего цикла представляет собой поиск одного диапазона. Для начала сохраните начало текущего диапазона в start = nums[i]. 2⃣Проверьте, отличается ли следующий элемент в nums на индексе i + 1 от nums[i] на 1 или больше. Если следующий элемент отличается на 1, увеличьте i на 1, чтобы включить (i+1)-й элемент в этот диапазон и продолжайте проверку следующего элемента. Продолжайте добавлять элементы в этот диапазон, пока последовательные элементы отличаются на 1, используя цикл while для выполнения этой логики. 3⃣Если следующий элемент отличается более чем на 1 или если все элементы в nums уже обработаны, проверьте, равен ли start значению nums[i]. Если start == nums[i], добавьте только start как строку в ranges, так как у нас есть только один элемент в этом диапазоне. Если start != nums[i], добавьте строку start->nums[i] в ranges. Увеличьте i на 1, чтобы начать новый диапазон. 😎 Решение:
class Solution {
func summaryRanges(_ nums: [Int]) -> [String] {
var ranges: [String] = []
var i = 0
while i < nums.count {
let start = nums[i]
while i + 1 < nums.count && nums[i] + 1 == nums[i + 1] {
i += 1
}
if start != nums[i] {
ranges.append("\(start)->\(nums[i])")
} else {
ranges.append("\(start)")
}
i += 1
}
return ranges
}
}1 273
Задача: 998. Maximum Binary Tree II
Сложность: medium
Максимальное дерево - это дерево, в котором каждый узел имеет значение большее, чем любое другое значение в его поддереве. Вам дан корень максимального двоичного дерева и целое число val. Как и в предыдущей задаче, данное дерево было построено из списка a (root = Construct(a)) рекурсивно с помощью следующей процедуры Construct(a): Если a пусто, верните null.
В противном случае пусть a[i] - наибольший элемент a. Создайте корневой узел со значением a[i]. Левым ребенком root будет Construct([a[0], a[1], ..., a[i - 1]]). Правым ребенком root будет Construct([a[i + 1], a[i + 2], ..., a[a.length])...., a[a.length - 1]]). Возвращаем root. Обратите внимание, что нам не было дано непосредственно a, а только корневой узел root = Construct(a). Предположим, что b - это копия a с добавленным к ней значением val. Гарантируется, что b имеет уникальные значения. Возвращаем Construct(b).
Пример:
Input: n = 2, trust = [[1,2]] Output: 2👨💻 Алгоритм: 1⃣Поиск места вставки: Итерируйте через дерево, начиная с корня. Найдите место для вставки нового значения val так, чтобы дерево оставалось максимальным деревом. Если значение val больше, чем значение текущего узла, создайте новый узел с val и сделайте текущий узел его левым ребенком. 2⃣Вставка нового узла: Если значение val меньше, чем значение текущего узла, продолжайте спускаться по правому поддереву, пока не найдете место для вставки. 3⃣Создание нового дерева: После вставки нового узла убедитесь, что дерево сохраняет свои свойства максимального дерева. 😎 Решение:
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init() { self.val = 0; self.left = nil; self.right = nil; }
public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
self.val = val
self.left = left
self.right = right
}
}
class Solution {
func insertIntoMaxTree(_ root: TreeNode?, _ val: Int) -> TreeNode? {
guard let root = root else { return TreeNode(val) }
if val > root.val {
return TreeNode(val, root, nil)
}
root.right = insertIntoMaxTree(root.right, val)
return root
}
}1 273
Задача: 338. Counting Bits
Сложность: easy
Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i.
Пример:
Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101👨💻 Алгоритм: 1⃣ Инициализация массива: Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n. 2⃣ Итерация и вычисление: Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x. 3⃣ Возврат результата: Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n. 😎 Решение:
class Solution {
func countBits(_ num: Int) -> [Int] {
var ans = [Int](repeating: 0, count: num + 1)
for x in 1...num {
ans[x] = ans[x & (x - 1)] + 1
}
return ans
}
}1 273
Задача: 98. Validate Binary Search Tree
Сложность: medium
Дан корень бинарного дерева. Определите, является ли это дерево допустимым бинарным деревом поиска (BST).
Допустимое BST определяется следующим образом:
Левое поддерево узла содержит только узлы с ключами, меньшими, чем ключ узла.
Правое поддерево узла содержит только узлы с ключами, большими, чем ключ узла.
Оба поддерева — левое и правое — также должны быть бинарными деревьями поиска.
Пример:
Input: root = [2,1,3] Output: true👨💻 Алгоритм: 1⃣Давайте воспользуемся порядком узлов при симметричном обходе (inorder traversal): Левый -> Узел -> Правый. Постордер: Здесь узлы перечисляются в порядке их посещения, и вы можете следовать последовательности 1-2-3-4-5 для сравнения различных стратегий. Порядок "Левый -> Узел -> Правый" при симметричном обходе означает, что для BST каждый элемент должен быть меньше следующего. 2⃣Следовательно, алгоритм с временной сложностью O(N) и пространственной сложностью O(N) может быть простым: Вычислить список симметричного обхода inorder. Проверить, меньше ли каждый элемент в списке inorder следующего за ним. Постордер: 3⃣Нужно ли сохранять весь список симметричного обхода? На самом деле, нет. Достаточно последнего добавленного элемента inorder, чтобы на каждом шаге убедиться, что дерево является BST (или нет). Следовательно, можно объединить оба шага в один и уменьшить используемое пространство. 😎 Решение:
class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {
self.val = val
self.left = left
self.right = right
}
}
class Solution {
private var prev: Int?
private func inorder(_ root: TreeNode?) -> Bool {
guard let root = root else {
return true
}
if !inorder(root.left) {
return false
}
if let prev = prev, root.val <= prev {
return false
}
prev = root.val
return inorder(root.right)
}
func isValidBST(_ root: TreeNode?) -> Bool {
prev = nil // Reset previous value
return inorder(root)
}
}1 273
Задача: 524. Longest Word in Dictionary through Deleting
Сложность: medium
Даны строка s и массив строк dictionary. Верните самую длинную строку из dictionary, которую можно сформировать, удаляя некоторые символы из данной строки s. Если возможных результатов несколько, верните самое длинное слово с наименьшим лексикографическим порядком. Если возможного результата нет, верните пустую строку.
Пример:
Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"] Output: "apple"👨💻 Алгоритм: 1⃣Инициализируйте переменную для хранения самой длинной строки, соответствующей критериям. Пройдите по каждой строке x в неотсортированном массиве dictionary и проверьте, является ли x подпоследовательностью строки s. 2⃣Если строка x является подпоследовательностью, сравните её с текущей самой длинной строкой по длине. Если длина x больше или равна длине текущей самой длинной строки и она меньше текущей строки в лексикографическом порядке (если равны по длине), обновите текущую самую длинную строку. 3⃣После рассмотрения всех строк в dictionary, верните найденную строку. Если ни одна строка не подошла, верните пустую строку. 😎 Решение:
class Solution {
func isSubsequence(_ x: String, _ y: String) -> Bool {
var j = x.startIndex
for i in y.indices where j < x.endIndex {
if x[j] == y[i] {
j = x.index(after: j)
}
}
return j == x.endIndex
}
func findLongestWord(_ s: String, _ d: [String]) -> String {
var maxStr = ""
for str in d {
if isSubsequence(str, s) {
if str.count > maxStr.count || (str.count == maxStr.count && str < maxStr) {
maxStr = str
}
}
}
return maxStr
}
}1 273
Задача: 1802. Maximum Value at a Given Index in a Bounded Array
Сложность: medium
Даны три положительных целых числа:
n, index и maxSum. Вам нужно построить массив nums (индексация с нуля), который удовлетворяет следующим условиям:
- nums.length == n
- nums[i] является положительным целым числом, где 0 <= i < n.
- abs(nums[i] - nums[i+1]) <= 1, где 0 <= i < n-1.
- Сумма всех элементов массива nums не превышает maxSum.
- nums[index] максимально возможен.
Верните значение nums[index] в построенном массиве.
Обратите внимание, что abs(x) равно x, если x >= 0, и -x в противном случае.
Пример:
Input: n = 4, index = 2, maxSum = 6 Output: 2👨💻 Алгоритм: 1⃣Определите функцию getSum(index, value) для вычисления минимальной суммы массива при условии, что nums[index] = value. 2⃣Инициализируйте диапазон поиска [left, right] значениями left = 1 и right = maxSum. Выполните бинарный поиск: вычислите mid = (left + right + 1) / 2 и проверьте, если getSum(index, mid) <= maxSum. Если условие выполняется, установите left = mid, иначе установите right = mid - 1. 3⃣Верните left по завершении бинарного поиска. 😎 Решение:
class Solution {
private func getSum(_ index: Int, _ value: Int, _ n: Int) -> Int64 {
var count: Int64 = 0
if value > index {
count += Int64(value + value - index) * Int64(index + 1) / 2
} else {
count += Int64(value + 1) * Int64(value) / 2 + Int64(index - value + 1)
}
if value >= n - index {
count += Int64(value + value - n + 1 + index) * Int64(n - index) / 2
} else {
count += Int64(value + 1) * Int64(value) / 2 + Int64(n - index - value)
}
return count - Int64(value)
}
func maxValue(_ n: Int, _ index: Int, _ maxSum: Int) -> Int {
var left = 1, right = maxSum
while left < right {
let mid = (left + right + 1) / 2
if getSum(index, mid, n) <= maxSum {
left = mid
} else {
right = mid - 1
}
}
return left
}
}1 273
🔥 Скрытые вакансии с удаленной работой для iOS разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.
🔹 iOS Jobs | Вакансии
🔹 Flutter Dart Jobs | Вакансии
🔹 Android Jobs | Вакансии
🔸 Все каналы с вакансиями
1 273
Задача: 494. Target Sum
Сложность: medium
Вам дан массив целых чисел nums и целое число target.
Вы хотите создать выражение из nums, добавляя один из символов '+' или '-' перед каждым числом в nums, а затем объединяя все числа.
Например, если nums = [2, 1], вы можете добавить '+' перед 2 и '-' перед 1, а затем объединить их, чтобы получить выражение "+2-1".
Верните количество различных выражений, которые можно построить и которые оцениваются в target.
Пример:
Input: nums = [1,1,1,1,1], target = 3 Output: 5 Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3. -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3👨💻 Алгоритм: 1⃣Инициализация и вызов рекурсивной функции Создайте переменную для хранения количества решений (count). Вызовите рекурсивную функцию calculate с начальными параметрами (nums, начальный индекс 0, начальная сумма 0, и target). 2⃣Рекурсивная функция calculate Если текущий индекс равен длине массива, проверьте, равна ли текущая сумма значению target. Если да, увеличьте счетчик решений. В противном случае, вызовите функцию рекурсивно дважды: добавляя и вычитая текущее значение из суммы. 3⃣Возврат результата После завершения всех рекурсивных вызовов верните значение счетчика решений. 😎 Решение:
class Solution {
var count = 0
func findTargetSumWays(_ nums: [Int], _ S: Int) -> Int {
calculate(nums, 0, 0, S)
return count
}
func calculate(_ nums: [Int], _ i: Int, _ sum: Int, _ S: Int) {
if i == nums.count {
if sum == S {
count += 1
}
} else {
calculate(nums, i + 1, sum + nums[i], S)
calculate(nums, i + 1, sum - nums[i], S)
}
}
}1 273
Задача: 208. Implement Trie (Prefix Tree)
Сложность: medium
Trie (произносится как "трай") или префиксное дерево — это древовидная структура данных, используемая для эффективного хранения и поиска ключей в наборе строк. Существует множество применений этой структуры данных, таких как автозаполнение и проверка орфографии.
Реализуйте класс Trie:
Trie() инициализирует объект trie.
void insert(String word) вставляет строку word в trie.
boolean search(String word) возвращает true, если строка word есть в trie (то есть была вставлена ранее), и false в противном случае.
boolean startsWith(String prefix) возвращает true, если есть ранее вставленная строка word, которая имеет префикс prefix, и false в противном случае.
Пример:
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]
Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // return True
trie.search("app"); // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app"); // return True
👨💻 Алгоритм:
1⃣Инициализация и вставка в Trie:
Создайте класс Trie, который включает в себя метод insert(String word) для добавления строк в Trie.
Метод insert инициализирует текущий узел как корень и проходит по каждому символу строки. Если текущий узел не содержит символа, создайте новый узел. В конце отметьте последний узел как конец слова.
2⃣Поиск строки в Trie:
Создайте метод search(String word), который использует вспомогательный метод searchPrefix(String word) для поиска строки или префикса в Trie.
В методе searchPrefix начните с корневого узла и для каждого символа строки перемещайтесь к следующему узлу. Если на каком-то этапе узел не содержит текущего символа, верните null. В противном случае, в конце строки верните текущий узел.
3⃣Проверка наличия префикса в Trie:
Создайте метод startsWith(String prefix), который также использует метод searchPrefix(String prefix).
Метод startsWith вызывает searchPrefix и возвращает true, если возвращаемый узел не равен null, что указывает на наличие префикса в Trie.
😎 Решение:
class TrieNode {
var links = [TrieNode?](repeating: nil, count: 26)
var isEnd = false
func containsKey(_ ch: Character) -> Bool {
return links[Int(ch.asciiValue! - Character("a").asciiValue!)] != nil
}
func get(_ ch: Character) -> TrieNode? {
return links[Int(ch.asciiValue! - Character("a").asciiValue!)]
}
func put(_ ch: Character, _ node: TrieNode) {
links[Int(ch.asciiValue! - Character("a").asciiValue!)] = node
}
func setEnd() {
isEnd = true
}
}
class Trie {
private var root = TrieNode()
func insert(_ word: String) {
var node = root
for ch in word {
if !node.containsKey(ch) {
node.put(ch, TrieNode())
}
node = node.get(ch)!
}
node.setEnd()
}
private func searchPrefix(_ word: String) -> TrieNode? {
var node = root
for ch in word {
if node.containsKey(ch) {
node = node.get(ch)!
} else {
return nil
}
}
return node
}
func search(_ word: String) -> Bool {
if let node = searchPrefix(word) {
return node.isEnd
}
return false
}
func startsWith(_ prefix: String) -> Bool {
return searchPrefix(prefix) != nil
}
}1 273
Задача: 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 273
Задача: 260. Single Number III
Сложность: medium
Дан целочисленный массив nums, в котором ровно два элемента встречаются только один раз, а все остальные элементы встречаются ровно дважды. Найдите два элемента, которые встречаются только один раз. Вы можете вернуть ответ в любом порядке.
Вы должны написать алгоритм, который работает за линейное время и использует только постоянное дополнительное пространство..
Пример:
Input: nums = [1,2,1,3,2,5] Output: [3,5] Explanation: [5, 3] is also a valid answer.👨💻 Алгоритм: 1⃣Выполните XOR для всех элементов массива nums. Это даст результат, который является XOR двух уникальных чисел. 2⃣Найдите бит, который отличается в этих двух числах, чтобы разделить все числа в массиве на две группы. 3⃣Выполните XOR для каждой группы, чтобы найти два уникальных числа. 😎 Решение:
class Solution {
func singleNumber(_ nums: [Int]) -> [Int] {
let xor = nums.reduce(0, ^)
let diff = xor & -xor
var res = [0, 0]
for num in nums {
if (num & diff) == 0 {
res[0] ^= num
} else {
res[1] ^= num
}
}
return res
}
}1 273
🚨 40 минут
Пожизненный PRO по цене года закрывается прямо сейчас. Это последнее напоминание.
👉 https://easyoffer.ru/pro
