اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
Swift | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
نمایش بیشتر1 349
مشترکین
-224 ساعت
-47 روز
-1630 روز
آرشیو پست ها
1 348
Задача: 1062. Longest Repeating Substring
Сложность: medium
Дана строка s. Вернуть длину самой длинной повторяющейся подстроки. Если повторяющаяся подстрока отсутствует, вернуть 0.
Пример:
Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.class Solution {
func search(_ L: Int, _ n: Int, _ S: String) -> Int {
var seen = Set<String>()
for start in 0...(n - L) {
let tmp = String(S[S.index(S.startIndex, offsetBy: start)..<S.index(S.startIndex, offsetBy: start + L)])
if seen.contains(tmp) { return start }
seen.insert(tmp)
}
return -1
}
func longestRepeatingSubstring(_ S: String) -> Int {
let n = S.count
var left = 1, right = n
while left <= right {
let L = left + (right - left) / 2
if search(L, n, S) != -1 {
left = L + 1
} else {
right = L - 1
}
}
return left - 1
}
}1 348
Задача: 714. Best Time to Buy and Sell Stock with Transaction Fee
Сложность: medium
Вам дан массив prices, где prices[i] - это цена данной акции в i-й день, и целое число fee, представляющее собой комиссию за сделку. Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить сколько угодно сделок, но за каждую сделку вам придется заплатить комиссию. Примечание: Вы не можете совершать несколько сделок одновременно (то есть вы должны продать акции, прежде чем купить их снова). Комиссия за сделку взимается только один раз за каждую покупку и продажу акций.
Пример:
Input: prices = [1,3,2,8,4,9], fee = 2 Output: 8👨💻 Алгоритм: 1⃣Инициализируйте две переменные: cash, представляющую максимальную прибыль без наличия акций, и hold, представляющую максимальную прибыль с наличием акций. 2⃣Пройдите по каждому элементу массива prices и обновите значения cash и hold, используя текущую цену и комиссию. 3⃣Верните значение cash, которое будет максимальной прибылью без наличия акций. 😎 Решение:
func maxProfit(_ prices: [Int], _ fee: Int) -> Int {
var cash = 0
var hold = -prices[0]
for price in prices {
cash = max(cash, hold + price - fee)
hold = max(hold, cash - price)
}
return cash
}1 348
Задача: 31. Next Permutation
Сложность: medium
Перестановка массива целых чисел — это упорядочивание его элементов в последовательность или линейный порядок.
Следующая перестановка массива целых чисел — это следующая лексикографически большая перестановка его чисел. Если такое упорядочивание невозможно, массив должен быть переупорядочен в наименьший возможный порядок (отсортирован по возрастанию).
Пример:
Input: nums = [1,2,3] Output: [1,3,2]👨💻Алгоритм: 1⃣Найти первое число
nums[i], которое меньше nums[i+1], двигаясь справа налево.
2⃣Найти наименьшее число справа от nums[i], которое больше него, и поменять их местами.
3⃣Перевернуть все элементы после i, чтобы получить наименьшую возможную лексикографическую перестановку.
😎Решение:
func nextPermutation(_ nums: inout [Int]) {
var i = nums.count - 2
while i >= 0 && nums[i + 1] <= nums[i] {
i -= 1
}
if i >= 0 {
var j = nums.count - 1
while nums[j] <= nums[i] {
j -= 1
}
nums.swapAt(i, j)
}
reverse(nums: &nums, start: i + 1)
}
func reverse(nums: inout [Int], start: Int) {
var i = start
var j = nums.count - 1
while i < j {
nums.swapAt(i, j)
i += 1
j -= 1
}
}1 348
Задача: 1428. Leftmost Column with at Least a One
Сложность: medium
Строково-отсортированная бинарная матрица означает, что все элементы равны 0 или 1, и каждая строка матрицы отсортирована в неубывающем порядке.
Дана строково-отсортированная бинарная матрица binaryMatrix, верните индекс (начиная с 0) самого левого столбца, содержащего 1. Если такого индекса не существует, верните -1.
Вы не можете напрямую обращаться к бинарной матрице. Вы можете получить доступ к матрице только через интерфейс BinaryMatrix:
- BinaryMatrix.get(row, col) возвращает элемент матрицы с индексом (row, col) (начиная с 0).
- BinaryMatrix.dimensions() возвращает размеры матрицы в виде списка из 2 элементов [rows, cols], что означает, что матрица имеет размер rows x cols.
Отправки, делающие более 1000 вызовов к BinaryMatrix.get, будут оценены как неправильный ответ. Кроме того, любые решения, пытающиеся обойти проверку, будут дисквалифицированы.
Для пользовательского тестирования вводом будет вся бинарная матрица mat. Вы не будете иметь прямого доступа к бинарной матрице.
Пример:
Input: mat = [[0,0],[0,1]] Output: 1👨💻 Алгоритм: 1⃣Инициализируйте указатели на текущую строку и столбец, начиная с верхнего правого угла матрицы. 2⃣Повторяйте поиск до тех пор, пока указатели не выйдут за границы матрицы: Если текущий элемент равен 0, сдвигайте указатель строки вниз. Если текущий элемент равен 1, сдвигайте указатель столбца влево. 3⃣Если указатель столбца остается на последнем столбце, значит, все элементы матрицы равны 0, и верните -1. В противном случае верните индекс самого левого столбца с 1. 😎 Решение:
class Solution {
func leftMostColumnWithOne(_ binaryMatrix: BinaryMatrix) -> Int {
let dimensions = binaryMatrix.dimensions()
let rows = dimensions[0]
let cols = dimensions[1]
var currentRow = 0
var currentCol = cols - 1
while currentRow < rows && currentCol >= 0 {
if binaryMatrix.get(currentRow, currentCol) == 0 {
currentRow += 1
} else {
currentCol -= 1
}
}
return (currentCol == cols - 1) ? -1 : currentCol + 1
}
}1 348
Задача: 59. Spiral Matrix II
Сложность: medium
Дано положительное целое число n. Сгенерируйте матрицу n на n, заполненную элементами от 1 до n^2 в спиральном порядке.
Пример:
Input: n = 3 Output: [[1,2,3],[8,9,4],[7,6,5]]👨💻 Алгоритм: 1⃣Определение направлений движения: Для обхода матрицы используются четыре направления, формирующие слои. Создается массив dir, который хранит изменения координат x и y для каждого направления. Например, при движении слева направо (направление №1) координата x остается неизменной, а y увеличивается (x=0, y=1). При движении справа налево (направление №3) x остается неизменным, а y уменьшается (x=0, y=-1). 2⃣Перемещение по матрице: Переменные row и col представляют текущие координаты x и y соответственно. Они обновляются в зависимости от направления движения. Применяется предварительно определенный массив dir с изменениями координат x и y для каждого из четырех направлений. 3⃣Изменение направления: Направление изменяется, когда следующая строка или столбец в определенном направлении имеют ненулевое значение, что указывает на то, что они уже были пройдены. Переменная d представляет текущий индекс направления. Переход к следующему направлению в массиве dir осуществляется с использованием формулы (d+1)%4. Это позволяет вернуться к направлению 1 после завершения одного полного круга от направления 1 до направления 4. 😎 Решение:
class Solution {
func floorMod(_ x: Int, _ y: Int) -> Int {
return ((x % y) + y) % y
}
func generateMatrix(_ n: Int) -> [[Int]] {
var result = Array(repeating: Array(repeating: 0, count: n), count: n)
var cnt = 1
let dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]
var d = 0
var row = 0
var col = 0
while cnt <= n * n {
result[row][col] = cnt
cnt += 1
let r = floorMod(row + dir[d].0, n)
let c = floorMod(col + dir[d].1, n)
if result[r][c] != 0 {
d = (d + 1) % 4
}
row += dir[d].0
col += dir[d].1
}
return result
}
}1 348
Задача: 638. Shopping Offers
Сложность: medium
В магазине LeetCode Store есть n предметов для продажи. Каждый товар имеет свою цену. Однако существуют специальные предложения, и специальное предложение состоит из одного или нескольких различных видов товаров с распродажной ценой. Вам дан целочисленный массив price, где price[i] - цена i-го товара, и целочисленный массив needs, где needs[i] - количество штук i-го товара, который вы хотите купить. Вам также дан массив special, где special[i] имеет размер n + 1, где special[i][j] - количество штук j-го товара в i-м предложении, а special[i][n] (т.е., Возвращает наименьшую цену, которую вы можете заплатить за определенный товар из заданных, где вы могли бы оптимально использовать специальные предложения. Вам не разрешается покупать больше товаров, чем вы хотите, даже если это снизит общую цену. Вы можете использовать любое из специальных предложений столько раз, сколько захотите.
Пример:
Input: price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2] Output: 14👨💻 Алгоритм: 1⃣Рекурсивное вычисление стоимости: Определите функцию, которая рекурсивно вычисляет минимальную стоимость для оставшихся нужд, используя динамическое программирование для запоминания уже вычисленных значений. 2⃣Использование специальных предложений: Для каждой комбинации товаров в специальных предложениях, определите, можно ли использовать это предложение без превышения нужд. Если можно, вычислите новую стоимость, учитывая это предложение. 3⃣Выбор минимальной стоимости: Сравните стоимость при использовании специальных предложений и стоимость при покупке товаров по индивидуальным ценам, выбирая минимальную стоимость. 😎 Решение:
class Solution {
func shoppingOffers(_ price: [Int], _ special: [[Int]], _ needs: [Int]) -> Int {
var memo = [String: Int]()
return dfs(price, special, needs, &memo)
}
private func dfs(_ price: [Int], _ special: [[Int]], _ needs: [Int], _ memo: inout [String: Int]) -> Int {
let key = needs.map(String.init).joined(separator: ",")
if let cached = memo[key] {
return cached
}
var minPrice = zip(price, needs).map(*).reduce(0, +)
for offer in special {
var newNeeds = [Int]()
var valid = true
for i in 0..<needs.count {
if needs[i] < offer[i] {
valid = false
break
}
newNeeds.append(needs[i] - offer[i])
}
if valid {
minPrice = min(minPrice, offer.last! + dfs(price, special, newNeeds, &memo))
}
}
memo[key] = minPrice
return minPrice
}
}1 348
Задача: 348. Design Tic-Tac-Toe
Сложность: medium
Предположим, что следующие правила относятся к игре в крестики-нолики на доске размером n x n между двумя игроками:
Ход гарантированно является допустимым и делается на пустом поле.
Как только достигается выигрышное условие, дальнейшие ходы запрещены.
Игрок, который успешно размещает n своих меток в горизонтальном, вертикальном или диагональном ряду, выигрывает игру.
Реализуйте класс TicTacToe:
TicTacToe(int n) Инициализирует объект с размером доски n.
int move(int row, int col, int player) Указывает, что игрок с идентификатором player делает ход в ячейке (row, col) на доске. Ход гарантированно является допустимым, и два игрока ходят по очереди. Возвращает:
0, если после хода победителя нет.
1, если после хода игрок 1 является победителем.
2, если после хода игрок 2 является победителем.
Пример:
Input ["TicTacToe", "move", "move", "move", "move", "move", "move", "move"] [[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]] Output [null, 0, 0, 0, 0, 0, 0, 1]👨💻 Алгоритм: 1⃣Инициализация: Создайте массивы rows и cols для отслеживания количества маркеров в каждой строке и столбце соответственно. Создайте переменные diagonal и antiDiagonal для отслеживания количества маркеров на главной и побочной диагоналях соответственно. Инициализируйте размер доски n. 2⃣Выполнение хода: Увеличьте счетчики в rows, cols, diagonal и antiDiagonal в зависимости от текущего хода. Если текущий ход игрока попадает на диагонали, обновите соответствующие переменные diagonal и antiDiagonal. 3⃣Проверка победы: Проверьте, достиг ли один из счетчиков в rows, cols, diagonal или antiDiagonal значения n (размер доски). Если да, верните идентификатор игрока как победителя. Если ни одно из условий победы не выполнено, верните 0, что означает отсутствие победителя после текущего хода. 😎 Решение:
class TicTacToe {
private var rows: [Int]
private var cols: [Int]
private var diagonal: Int
private var antiDiagonal: Int
private var n: Int
init(_ n: Int) {
self.n = n
rows = [Int](repeating: 0, count: n)
cols = [Int](repeating: 0, count: n)
diagonal = 0
antiDiagonal = 0
}
func move(_ row: Int, _ col: Int, _ player: Int) -> Int {
let add = player == 1 ? 1 : -1
rows[row] += add
cols[col] += add
if row == col {
diagonal += add
}
if row + col == n - 1 {
antiDiagonal += add
}
if abs(rows[row]) == n || abs(cols[col]) == n || abs(diagonal) == n || abs(antiDiagonal) == n {
return player
}
return 0
}
}1 348
Задача: 187. Repeated DNA Sequences
Сложность: medium
ДНК состоит из серии нуклеотидов, обозначаемых как 'A', 'C', 'G' и 'T'.
Например, "ACGAATTCCG" — это последовательность ДНК.
При изучении ДНК полезно определять повторяющиеся последовательности внутри молекулы ДНК.
Дана строка s, представляющая последовательность ДНК. Верните все последовательности длиной 10 букв (подстроки), которые встречаются более одного раза в молекуле ДНК. Ответ можно возвращать в любом порядке.
Пример:
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" Output: ["AAAAACCCCC","CCCCCAAAAA"]👨💻 Алгоритм: 1⃣Перебираем начальные позиции последовательности от 1 до 𝑁−𝐿, где 𝑁 — длина строки, а 𝐿 — длина подстроки (в данном случае 10): Если начальная позиция 𝑠𝑡𝑎𝑟𝑡==0, вычисляем хеш первой последовательности 𝑠[0:𝐿]. В противном случае вычисляем скользящий хеш из предыдущего значения хеша. 2⃣Проверяем хеш в хешсете: Если хеш уже существует в хешсете, значит, мы нашли повторяющуюся последовательность, и пора обновить вывод. В противном случае добавляем хеш в хешсет. 3⃣Возвращаем список вывода, содержащий все повторяющиеся последовательности. 😎 Решение:
class Solution {
func findRepeatedDnaSequences(_ s: String) -> [String] {
let L = 10, n = s.count
if n <= L { return [] }
let a = 4, aL = Int(pow(Double(a), Double(L)))
var toInt = ["A": 0, "C": 1, "G": 2, "T": 3]
var nums = s.map { toInt[String($0)]! }
var h = 0
var seen = Set<Int>()
var output = Set<String>()
for start in 0..<(n - L + 1) {
if start != 0 {
h = h * a - nums[start - 1] * aL + nums[start + L - 1]
} else {
for i in 0..<L {
h = h * a + nums[i]
}
}
if seen.contains(h) {
output.insert(String(s.dropFirst(start).prefix(L)))
}
seen.insert(h)
}
return Array(output)
}
}1 348
Задача: 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 348
Задача: 834. Sum of Distances in Tree
Сложность: hard
Есть неориентированное связное дерево с n узлами, пронумерованными от 0 до n - 1, и n - 1 ребрами.
Вам даны целое число n и массив edges, где edges[i] = [ai, bi] указывает, что существует ребро между узлами ai и bi в дереве.
Верните массив answer длиной n, где answer[i] — это сумма расстояний между i-м узлом в дереве и всеми другими узлами.
Пример:
Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]] Output: [8,12,6,10,10,10] Explanation: The tree is shown above. We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) equals 1 + 1 + 2 + 2 + 2 = 8. Hence, answer[0] = 8, and so on.👨💻 Алгоритм: 1⃣Постройте дерево и выполните обход в глубину (DFS) для расчета количества узлов в поддереве и суммы расстояний до всех узлов поддерева. 2⃣На основе полученных данных рассчитайте сумму расстояний для корня дерева. 3⃣Выполните второй обход в глубину (DFS) для корректировки суммы расстояний для каждого узла на основе суммы расстояний его родительского узла. 😎 Решение:
class Solution {
var ans: [Int] = []
var count: [Int] = []
var graph: [[Int]] = []
var N: Int = 0
func sumOfDistancesInTree(_ N: Int, _ edges: [[Int]]) -> [Int] {
self.N = N
graph = Array(repeating: [], count: N)
ans = Array(repeating: 0, count: N)
count = Array(repeating: 1, count: N)
for edge in edges {
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
}
dfs(0, -1)
dfs2(0, -1)
return ans
}
func dfs(_ node: Int, _ parent: Int) {
for child in graph[node] {
if child != parent {
dfs(child, node)
count[node] += count[child]
ans[node] += ans[child] + count[child]
}
}
}
func dfs2(_ node: Int, _ parent: Int) {
for child in graph[node] {
if child != parent {
ans[child] = ans[node] - count[child] + N - count[child]
dfs2(child, node)
}
}
}
}1 348
Сегодня последний день, когда можно приобрести пожизненный PRO тариф easyoffer
Акция до 20 февраля 00:00
Покупаешь сейчас один раз — пользуешься всю жизнь без лимита, включая все будущие функции.
👉 Смотри подробности тарифа и покупай на https://easyoffer.ru/
1 348
Задача: 378. Kth Smallest Element in a Sorted Matrix
Сложность: medium
Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице.
Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент.
Вы должны найти решение с использованием памяти лучше, чем O(n²).
Пример:
Input: matrix = [[-5]], k = 1 Output: -5👨💻 Алгоритм: 1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список. 2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку. 3⃣Мин-куча будет содержать тройки информации (значение, строка, столбец). Куча будет упорядочена по значениям, и мы будем использовать номера строк и столбцов для добавления следующего элемента, если текущий элемент будет удален из кучи. 😎 Решение:
class MyHeapNode {
var row: Int
var column: Int
var value: Int
init(_ value: Int, _ row: Int, _ column: Int) {
self.value = value
self.row = row
self.column = column
}
}
class Solution {
func kthSmallest(_ matrix: [[Int]], _ k: Int) -> Int {
let N = matrix.count
var minHeap = PriorityQueue<MyHeapNode> { $0.value < $1.value }
for r in 0..<min(N, k) {
minHeap.enqueue(MyHeapNode(matrix[r][0], r, 0))
}
var element: MyHeapNode = minHeap.peek()!
var k = k
while k > 0 {
element = minHeap.dequeue()!
let r = element.row, c = element.column
if c < N - 1 {
minHeap.enqueue(MyHeapNode(matrix[r][c + 1], r, c + 1))
}
k -= 1
}
return element.value
}
}
struct PriorityQueue<Element: Equatable> {
private var elements: [Element]
private let priorityFunction: (Element, Element) -> Bool
init(priorityFunction: @escaping (Element, Element) -> Bool) {
self.elements = []
self.priorityFunction = priorityFunction
}
var isEmpty: Bool {
return elements.isEmpty
}
func peek() -> Element? {
return elements.first
}
mutating func enqueue(_ element: Element) {
elements.append(element)
siftUp(elementAtIndex: elements.count - 1)
}
mutating func dequeue() -> Element? {
guard !isEmpty else { return nil }
if elements.count == 1 {
return elements.removeLast()
} else {
let value = elements[0]
elements[0] = elements.removeLast()
siftDown(elementAtIndex: 0)
return value
}
}
private mutating func siftUp(elementAtIndex index: Int) {
let parent = parentIndex(of: index)
guard !isRoot(index), isHigherPriority(at: index, than: parent) else { return }
swapElement(at: index, with: parent)
siftUp(elementAtIndex: parent)
}
private mutating func siftDown(elementAtIndex index: Int) {
let childIndex = highestPriorityIndex(for: index)
if index == childIndex { return }
swapElement(at: index, with: childIndex)
siftDown(elementAtIndex: childIndex)
}
private func isRoot(_ index: Int) -> Bool {
return index == 0
}
private func leftChildIndex(of index: Int) -> Int {
return 2 * index + 1
}
private func rightChildIndex(of index: Int) -> Int {
return 2 * index + 2
}
private func parentIndex(of index: Int) -> Int {
return (index - 1) / 2
}
private func isHigherPriority(at firstIndex: Int, than secondIndex: Int) -> Bool {
return priorityFunction(elements[firstIndex], elements[secondIndex])
}1 348
Задача: 920. Number of Music Playlists
Сложность: hard
В вашем плеере есть n разных песен. Во время путешествия вы хотите прослушать goal песен (не обязательно разных). Чтобы избежать скуки, вы создадите плейлист таким образом, чтобы: каждая песня играла хотя бы один раз. Песня может быть проиграна снова только в том случае, если было проиграно k других песен. Учитывая n, цель и k, верните количество возможных плейлистов, которые вы можете создать. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.
Пример:
Input: n = 3, goal = 3, k = 1 Output: 6👨💻 Алгоритм: 1⃣Создать двумерный массив dp, где dp[i][j] представляет количество возможных плейлистов длины i, содержащих j различных песен. 2⃣Инициализировать dp[0][0] = 1, что означает, что существует один способ создать плейлист длины 0 с 0 песнями. Заполнить массив dp, используя два случая: Добавление новой песни, которая не была проиграна раньше: dp[i][j] += dp[i-1][j-1] * (n - j + 1) Повторное проигрывание песни, если было проиграно k других песен: dp[i][j] += dp[i-1][j] * max(j - k, 0) 3⃣Ответ находится в dp[goal][n]. 😎 Решение:
class Solution {
func numMusicPlaylists(_ n: Int, _ goal: Int, _ k: Int) -> Int {
let MOD = 1_000_000_007
var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: goal + 1)
dp[0][0] = 1
for i in 1...goal {
for j in 1...n {
dp[i][j] = dp[i-1][j-1] * (n - j + 1) % MOD
if j > k {
dp[i][j] = (dp[i][j] + dp[i-1][j] * (j - k) % MOD) % MOD
}
}
}
return dp[goal][n]
}
}1 348
Завтра конец акции на возможность приобрести PRO тариф по цене одного года
Доступный функционал включает базы вопросов с собеседований, задач для live-coding, реальных интервью и тестовых заданий от топ-компаний, а также аналитику требований для резюме и тренажеры с режимом симуляции собеседования под конкретную компанию.
Акция до 20 февраля (включительно) на PRO-тариф. Покупаешь сейчас один раз — пользуешься всю жизнь без лимита, включая все будущие функции.
👉 Смотри подробности тарифа и покупай на https://easyoffer.ru/
1 348
Задача: 713. Subarray Product Less Than K
Сложность: medium
Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k.
Пример:
Input: nums = [10,5,2,6], k = 100 Output: 8👨💻 Алгоритм: 1⃣Инициализируйте переменные для отслеживания текущего произведения и количества допустимых подмассивов. Используйте два указателя для границ подмассива. 2⃣Перемещайте правый указатель по массиву и умножайте текущий элемент на текущее произведение. Если произведение становится больше или равно k, перемещайте левый указатель, уменьшая произведение до тех пор, пока оно снова не станет меньше k. 3⃣Подсчитайте количество подмассивов с текущим правым указателем, добавив к общему количеству допустимых подмассивов разницу между правым и левым указателями. 😎 Решение:
func numSubarrayProductLessThanK(_ nums: [Int], _ k: Int) -> Int {
if k <= 1 {
return 0
}
var product = 1
var count = 0
var left = 0
for right in 0..<nums.count {
product *= nums[right]
while product >= k {
product /= nums[left]
left += 1
}
count += right - left + 1
}
return count
}1 348
Задача: 969. Pancake Sorting
Сложность: medium
Дан массив целых чисел arr, отсортируйте массив, выполняя серию переворотов блинов.
При одном перевороте блина мы выполняем следующие шаги:
Выбираем целое число k, где 1 <= k <= arr.length.
Переворачиваем подмассив arr[0...k-1] (индексация с 0).
Например, если arr = [3,2,1,4] и мы выполнили переворот блина, выбрав k = 3, мы переворачиваем подмассив [3,2,1], так что arr = [1,2,3,4] после переворота блина при k = 3.
Верните массив значений k, соответствующих последовательности переворотов блинов, которая сортирует arr. Любой допустимый ответ, который сортирует массив за количество переворотов не более чем 10 * arr.length, будет считаться правильным.
Пример:
Input: arr = [3,2,4,1] Output: [4,2,4,3] Explanation: We perform 4 pancake flips, with k values 4, 2, 4, and 3. Starting state: arr = [3, 2, 4, 1] After 1st flip (k = 4): arr = [1, 4, 2, 3] After 2nd flip (k = 2): arr = [4, 1, 2, 3] After 3rd flip (k = 4): arr = [3, 2, 1, 4] After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.👨💻 Алгоритм: 1⃣Вдохновляясь пузырьковой сортировкой, начнем с реализации функции flip(list, k), которая выполняет переворот блина на префиксе list[0 ] (в Python). 2⃣Основной алгоритм выполняет цикл по значениям списка, начиная с наибольшего. 3⃣На каждом этапе определяем значение для сортировки (назовем его value_to_sort), которое является числом, которое мы будем ставить на место на этом этапе. Затем находим индекс value_to_sort. Если value_to_sort еще не на своем месте, выполняем максимум два переворота блинов, как объяснено в интуиции. В конце этапа value_to_sort будет на своем месте. 😎 Решение:
class Solution {
func pancakeSort(_ A: [Int]) -> [Int] {
var A = A
var ans = [Int]()
for valueToSort in stride(from: A.count, to: 0, by: -1) {
let index = find(A, valueToSort)
if index == valueToSort - 1 { continue }
if index != 0 {
ans.append(index + 1)
flip(&A, index + 1)
}
ans.append(valueToSort)
flip(&A, valueToSort)
}
return ans
}
private func flip(_ sublist: inout [Int], _ k: Int) {
var i = 0
while i < k / 2 {
let temp = sublist[i]
sublist[i] = sublist[k - i - 1]
sublist[k - i - 1] = temp
i += 1
}
}
private func find(_ a: [Int], _ target: Int) -> Int {
for i in 0..<a.count {
if a[i] == target {
return i
}
}
return -1
}
}1 348
Задача: 860. Lemonade Change
Сложность: easy
На лимонадной стойке каждый лимонад стоит $5. Покупатели стоят в очереди, чтобы купить лимонад, и заказывают по одному (в порядке, указанном в массиве bills). Каждый покупатель покупает только один лимонад и платит либо $5, $10, либо $20. Вы должны предоставить правильную сдачу каждому покупателю, чтобы чистая сделка была такой, что покупатель платит $5.
Обратите внимание, что изначально у вас нет никакой сдачи.
Дан целочисленный массив bills, где bills[i] — купюра, которой платит i-й покупатель. Верните true, если вы можете предоставить каждому покупателю правильную сдачу, или false в противном случае.
Пример:
Input: bills = [5,5,5,10,20]
Output: true
Explanation:
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.class Solution {
func lemonadeChange(_ bills: [Int]) -> Bool {
var five = 0, ten = 0
for bill in bills {
if bill == 5 {
five += 1
} else if bill == 10 {
if five == 0 { return false }
five -= 1
ten += 1
} else {
if five > 0 && ten > 0 {
five -= 1
ten -= 1
} else if five >= 3 {
five -= 3
} else {
return false
}
}
}
return true
}
}1 348
Задача: 424. Longest Repeating Character Replacement
Сложность: medium
Вам дана строка s и целое число k. Вы можете выбрать любой символ строки и заменить его на любой другой заглавный английский символ. Вы можете выполнить эту операцию не более k раз.
Верните длину самой длинной подстроки, содержащей одну и ту же букву, которую можно получить после выполнения вышеуказанных операций.
Пример:
Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa.👨💻 Алгоритм: 1⃣Определите диапазон поиска. Минимальная длина подстроки с одинаковыми символами всегда равна 1 (назовем ее min), а максимальная длина подстроки может быть равна длине данной строки (назовем ее max). Ответ будет лежать в диапазоне [min, max] (включительно). 2⃣Инициализируйте две переменные lo и hi для бинарного поиска. lo всегда указывает на длину допустимой строки, а hi - на недопустимую длину. Изначально lo равно 1, а hi равно max+1. 3⃣Выполните бинарный поиск, чтобы найти максимальное значение lo, которое представляет самую длинную допустимую подстроку. В конце lo будет содержать ответ, а hi будет на единицу больше lo. 😎 Решение:
class Solution {
func characterReplacement(_ s: String, _ k: Int) -> Int {
var lo = 1
var hi = s.count + 1
while lo + 1 < hi {
let mid = lo + (hi - lo) / 2
if canMakeValidSubstring(s, mid, k) {
lo = mid
} else {
hi = mid
}
}
return lo
}
private func canMakeValidSubstring(_ s: String, _ substringLength: Int, _ k: Int) -> Bool {
var freqMap = [Int](repeating: 0, count: 26)
var maxFrequency = 0
let sArray = Array(s)
var start = 0
for end in 0..<sArray.count {
freqMap[Int(sArray[end].asciiValue! - Character("A").asciiValue!)] += 1
if end + 1 - start > substringLength {
freqMap[Int(sArray[start].asciiValue! - Character("A").asciiValue!)] -= 1
start += 1
}
maxFrequency = max(maxFrequency, freqMap[Int(sArray[end].asciiValue! - Character("A").asciiValue!)])
if substringLength - maxFrequency <= k {
return true
}
}
return false
}
}1 348
Пожизненная PRO подписка на easyoffer по цене одного года.
Акция до 20 февраля. Покупаешь сейчас один раз – пользуешься всю жизнь без лимита, включая все будущие функции.
Запланированные новые фичи на ближайшие пол года:
1. Агрегатор вакансий
2. Улучшение резюме, чтобы проходить ATS системы
3. Генерация уникального резюме и сопроводительного письма под вакансию
Покупай на https://easyoffer.ru/
1 348
Задача: 1167. Minimum Cost to Connect Sticks
Сложность: medium
У вас есть несколько палочек с положительными целыми длинами. Эти длины даны в виде массива sticks, где sticks[i] — длина i-й палочки.
Вы можете соединить любые две палочки длиной x и y в одну палочку, заплатив стоимость x + y. Вы должны соединить все палочки, пока не останется только одна палочка.
Верните минимальную стоимость соединения всех данных палочек в одну палочку таким образом.
Пример:
Input: sticks = [5]
Output: 0
Explanation: There is only one stick, so you don't need to do anything. The total cost is 0.class Solution {
func connectSticks(_ sticks: [Int]) -> Int {
var totalCost = 0
var pq = PriorityQueue(sticks)
while pq.count > 1 {
let cost = pq.dequeue()! + pq.dequeue()!
totalCost += cost
pq.enqueue(cost)
}
return totalCost
}
}
struct PriorityQueue<T: Comparable> {
private var heap: [T]
init(_ elements: [T] = []) {
self.heap = elements
heapify()
}
var count: Int { heap.count }
mutating func enqueue(_ element: T) {
heap.append(element)
siftUp(heap.count - 1)
}
mutating func dequeue() -> T? {
guard !heap.isEmpty else { return nil }
if heap.count == 1 { return heap.removeFirst() }
heap.swapAt(0, heap.count - 1)
let removed = heap.removeLast()
siftDown(0)
return removed
}
private mutating func heapify() {
for index in (0..<(heap.count / 2)).reversed() {
siftDown(index)
}
}
private mutating func siftUp(_ index: Int) {
var childIndex = index
let child = heap[childIndex]
var parentIndex = (childIndex - 1) / 2
while childIndex > 0 && child < heap[parentIndex] {
heap[childIndex] = heap[parentIndex]
childIndex = parentIndex
parentIndex = (childIndex - 1) / 2
}
heap[childIndex] = child
}
private mutating func siftDown(_ index: Int) {
var parentIndex = index
while true {
let leftChildIndex = 2 * parentIndex + 1
let rightChildIndex = 2 * parentIndex + 2
var optionalParentIndex = parentIndex
if leftChildIndex < heap.count && heap[leftChildIndex] < heap[optionalParentIndex] {
optionalParentIndex = leftChildIndex
}
if rightChildIndex < heap.count && heap[rightChildIndex] < heap[optionalParentIndex] {
optionalParentIndex = rightChildIndex
}
if optionalParentIndex == parentIndex { return }
heap.swapAt(parentIndex, optionalParentIndex)
parentIndex = optionalParentIndex
}
}
}