¡Ya disponible! Investigación de Telegram 2025 — los principales insights del año 
Swift | LeetCode
Ir al canal en Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Mostrar más1 349
Suscriptores
-224 horas
-47 días
-1630 días
Archivo de publicaciones
1 349
Пожизненный PRO доступ на easyoffer — по цене одного года!
До 31 марта вы можете купить PRO навсегда. Запускаем акцию, чтобы ускорить развитие сервиса.
Что добавим в PRO в ближайшие полгода:
– Автоотклики
– Агрегатор вакансий
– Проход ATS без отсева
– Уникальные резюме и письма под каждую вакансию
Покупаешь один раз — пользуешься всю жизнь.
👉 Купить PRO со скидкой 70%: https://easyoffer.ru/pro
1 349
Задача: 895. Maximum Frequency Stack
Сложность: hard
Разработайте структуру данных, похожую на стек, чтобы заталкивать элементы в стек и вытаскивать из него самый частый элемент. Реализуйте класс FreqStack: FreqStack() строит пустой стек частот. void push(int val) заталкивает целое число val на вершину стека. int pop() удаляет и возвращает самый частый элемент в стеке. Если есть равенство в выборе самого частого элемента, то удаляется и возвращается элемент, который ближе всего к вершине стека.
Пример:
Input ["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"] [[], [5], [7], [5], [7], [4], [5], [], [], [], []] Output [null, null, null, null, null, null, null, 5, 7, 5, 4]👨💻 Алгоритм: 1⃣Создать два словаря: freq для хранения частоты каждого элемента и group для хранения стека элементов для каждой частоты. 2⃣При добавлении элемента увеличивать его частоту в freq и добавлять его в стек соответствующей частоты в group. 3⃣При извлечении элемента найти максимальную частоту, удалить элемент из стека соответствующей частоты и уменьшить его частоту в freq. Если стек для данной частоты становится пустым, удалить его. 😎 Решение:
class FreqStack {
private var freq: [Int: Int]
private var group: [Int: [Int]]
private var maxfreq: Int
init() {
freq = [:]
group = [:]
maxfreq = 0
}
func push(_ val: Int) {
let f = (freq[val] ?? 0) + 1
freq[val] = f
if f > maxfreq {
maxfreq = f
group[f] = []
}
group[f]?.append(val)
}
func pop() -> Int {
guard let val = group[maxfreq]?.popLast() else { return -1 }
freq[val, default: 0] -= 1
if group[maxfreq]?.isEmpty ?? false {
maxfreq -= 1
}
return val
}
}1 349
Задача: 1230. Toss Strange Coins
Сложность: medium
У вас есть несколько монет. Вероятность выпадения орла для i-й монеты равна prob[i].
Верните вероятность того, что количество монет, на которых выпал орел, равно target, если вы подбросите каждую монету ровно один раз.
Пример:
Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0 Output: 0.03125👨💻 Алгоритм: 1⃣Инициализация: Создайте переменную n и инициализируйте её размером массива prob. Создайте 2D массив dp размером n + 1 строк и target + 1 столбцов, где dp[i][j] хранит вероятность получить j орлов, используя первые i монет. Установите базовый случай dp[0][0] = 1. 2⃣Итерация: Используйте два вложенных цикла для заполнения массива dp. Внешний цикл итерируется от i = 1 до n. Для каждого i установите dp[i][0], что обозначает вероятность получить 0 орлов при использовании i монет: dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1]). Внутренний цикл итерируется от j = 1 до target. Для каждого j вычислите dp[i][j] по формуле: dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1]). 3⃣Возврат результата: Верните значение dp[n][target], которое содержит искомую вероятность. 😎 Решение:
class Solution {
func probabilityOfHeads(_ prob: [Double], _ target: Int) -> Double {
let n = prob.count
var dp = Array(repeating: Array(repeating: 0.0, count: target + 1), count: n + 1)
dp[0][0] = 1.0
for i in 1...n {
dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1])
for j in 1...target {
if j <= i {
dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1])
}
}
}
return dp[n][target]
}
}1 349
Задача: 259. 3Sum Smaller
Сложность: medium
Дан массив из n целых чисел nums и целое число target. Найдите количество троек индексов i, j, k, удовлетворяющих условию 0 <= i < j < k < n и nums[i] + nums[j] + nums[k] < target.
Пример:
Input: nums = [-2,0,1,3], target = 2 Output: 2 Explanation: Because there are two triplets which sums are less than 2: [-2,0,1] [-2,0,3]👨💻 Алгоритм: 1⃣Отсортируйте массив nums. 2⃣Для каждого элемента nums[i] от 0 до n-3 найдите количество пар индексов j и k (где i < j < k), таких что nums[i] + nums[j] + nums[k] < target. Используйте функцию twoSumSmaller, которая ищет количество пар с суммой меньше заданного значения. 3⃣В функции twoSumSmaller используйте бинарный поиск для поиска верхней границы индекса k и подсчета количества подходящих пар. 😎 Решение:
class Solution {
func threeSumSmaller(_ nums: [Int], _ target: Int) -> Int {
let nums = nums.sorted()
var sum = 0
for i in 0..<nums.count - 2 {
sum += twoSumSmaller(nums, i + 1, target - nums[i])
}
return sum
}
private func twoSumSmaller(_ nums: [Int], _ startIndex: Int, _ target: Int) -> Int {
var sum = 0
for i in startIndex..<nums.count - 1 {
let j = binarySearch(nums, i, target - nums[i])
sum += j - i
}
return sum
}
private func binarySearch(_ nums: [Int], _ startIndex: Int, _ target: Int) -> Int {
var left = startIndex
var right = nums.count - 1
while left < right {
let mid = (left + right + 1) / 2
if nums[mid] < target {
left = mid
} else {
right = mid - 1
}
}
return left
}
}1 349
Задача: 1255. Maximum Score Words Formed by Letters
Сложность: hard
Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно.
Пример:
Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0] Output: 23👨💻 Алгоритм: 1⃣Создайте функцию для вычисления оценки слова. 2⃣Используйте метод перебора подмножеств (или битовое представление всех подмножеств) для нахождения всех возможных комбинаций слов. Для каждой комбинации проверяйте, можно ли составить каждое слово из доступных букв. 3⃣Вычислите суммарную оценку для каждой допустимой комбинации слов и сохраните максимальную оценку. 😎 Решение:
class Solution {
func maxScoreWords(_ words: [String], _ letters: [Character], _ score: [Int]) -> Int {
var letterCount = [Character: Int]()
for ch in letters {
letterCount[ch, default: 0] += 1
}
func wordScore(_ word: String) -> Int {
var total = 0
for ch in word {
total += score[Int(ch.asciiValue! - Character("a").asciiValue!)]
}
return total
}
func canFormWord(_ word: String, _ letterCount: [Character: Int]) -> Bool {
var count = [Character: Int]()
for ch in word {
count[ch, default: 0] += 1
if count[ch]! > letterCount[ch, default: 0] {
return false
}
}
return true
}
var maxScore = 0
let n = words.count
for i in 1..<1<<n {
var currScore = 0
var usedLetters = [Character: Int]()
var valid = true
for j in 0..<n {
if (i & 1<<j) != 0 {
let word = words[j]
if canFormWord(word, letterCount) {
currScore += wordScore(word)
for ch in word {
usedLetters[ch, default: 0] += 1
}
} else {
valid = false
break
}
}
}
if valid {
maxScore = max(maxScore, currScore)
}
}
return maxScore
}
}1 349
Задача: 832. Flipping an Image
Сложность: easy
Дано бинарное изображение размером n x n, необходимо перевернуть изображение по горизонтали, затем инвертировать его и вернуть результат.
Перевернуть изображение по горизонтали означает, что каждая строка изображения будет развернута.
Например, переворот строки [1,1,0] по горизонтали дает [0,1,1].
Инвертировать изображение означает, что каждый 0 заменяется на 1, а каждый 1 заменяется на 0.
Например, инверсия строки [0,1,1] дает [1,0,0].
Пример:
Input: image = [[1,1,0],[1,0,1],[0,0,0]] Output: [[1,0,0],[0,1,0],[1,1,1]] Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]]. Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]👨💻 Алгоритм: 1⃣Переверните каждую строку по горизонтали, обменяв элементы слева направо и наоборот. 2⃣Инвертируйте каждую строку, заменив каждый 0 на 1 и каждый 1 на 0. 3⃣Верните преобразованное изображение. 😎 Решение:
class Solution {
func flipAndInvertImage(_ A: [[Int]]) -> [[Int]] {
var A = A
let C = A[0].count
for i in 0..<A.count {
for j in 0..<(C + 1) / 2 {
let temp = A[i][j] ^ 1
A[i][j] = A[i][C - 1 - j] ^ 1
A[i][C - 1 - j] = temp
}
}
return A
}
}1 349
Задача: 268. Missing Number
Сложность: easy
Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.
Пример:
Input: nums = [3,0,1] Output: 2 Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.👨💻 Алгоритм: 1⃣Сначала отсортируйте массив nums. 2⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце. 3⃣Пройдитесь по отсортированному массиву и для каждого индекса проверьте, что число на этом индексе соответствует ожидаемому (предыдущее число плюс один). Как только вы обнаружите несоответствие, верните ожидаемое число. 😎 Решение:
class Solution {
func missingNumber(_ nums: [Int]) -> Int {
let sortedNums = nums.sorted()
if sortedNums.last != sortedNums.count {
return sortedNums.count
} else if sortedNums.first != 0 {
return 0
}
for i in 1..<sortedNums.count {
let expectedNum = sortedNums[i - 1] + 1
if sortedNums[i] != expectedNum {
return expectedNum
}
}
return -1
}
}1 349
Задача: 1017. Convert to Base -2
Сложность: medium
Если задано целое число n, верните двоичную строку, представляющую его в базе -2. Обратите внимание, что возвращаемая строка не должна содержать ведущих нулей, за исключением случаев, когда строка равна "0".
Пример:
Input: n = 2 Output: "110"👨💻 Алгоритм: 1⃣Инициализация переменных: Создайте пустую строку для хранения двоичного представления числа. Используйте цикл для вычисления каждой цифры числа в базе -2. 2⃣Вычисление цифр: В цикле, пока число не равно 0, вычисляйте остаток от деления числа на -2. Если остаток отрицательный, корректируйте его, добавляя 2, и увеличивайте число на 1. Добавляйте остаток в начало строки. 3⃣Возврат результата: Верните строку, представляющую число в базе -2. Если строка пустая, верните "0". 😎 Решение:
class Solution {
func baseNeg2(_ n: Int) -> String {
if n == 0 {
return "0"
}
var n = n
var res = ""
while n != 0 {
var remainder = n % -2
n /= -2
if remainder < 0 {
remainder += 2
n += 1
}
res = String(remainder) + res
}
return res
}
}1 349
Задача: 1538. Guess the Majority in a Hidden Array
Сложность: medium
У нас есть целочисленный массив
nums, где все числа в nums равны 0 или 1. Вам не будет предоставлен прямой доступ к массиву, вместо этого у вас будет API ArrayReader, который имеет следующие функции:
int query(int a, int b, int c, int d): где 0 <= a < b < c < d < ArrayReader.length(). Функция возвращает распределение значений 4 элементов и возвращает:
4: если значения всех 4 элементов одинаковы (0 или 1).
2: если три элемента имеют значение 0 и один элемент имеет значение 1 или наоборот.
0: если два элемента имеют значение 0 и два элемента имеют значение 1.
int length(): Возвращает размер массива.
Вам разрешено вызывать query() не более 2 * n раз, где n равно ArrayReader.length().
Верните любой индекс самого частого значения в nums, в случае ничьей верните -1.
Пример:
Input: nums = [0,0,1,0,1,1,1,1]
Output: 5
Explanation: The following calls to the API
reader.length() // returns 8 because there are 8 elements in the hidden array.
reader.query(0,1,2,3) // returns 2 this is a query that compares the elements nums[0], nums[1], nums[2], nums[3]
// Three elements have a value equal to 0 and one element has value equal to 1 or viceversa.
reader.query(4,5,6,7) // returns 4 because nums[4], nums[5], nums[6], nums[7] have the same value.
we can infer that the most frequent value is found in the last 4 elements.
Index 2, 4, 6, 7 is also a correct answer.class Solution {
var cntEqual = 1, cntDiffer = 0, indexDiffer = -1
private func f(_ equal: Bool, _ i: Int) {
if equal {
cntEqual += 1
} else {
cntDiffer += 1
indexDiffer = i
}
}
func guessMajority(_ reader: ArrayReader) -> Int {
let n = reader.length()
let query0123 = reader.query(0, 1, 2, 3)
let query1234 = reader.query(1, 2, 3, 4)
f(query1234 == query0123, 4)
for i in 5..<n {
f(reader.query(1, 2, 3, i) == query0123, i)
}
f(reader.query(0, 2, 3, 4) == query1234, 1)
f(reader.query(0, 1, 3, 4) == query1234, 2)
f(reader.query(0, 1, 2, 4) == query1234, 3)
return cntEqual > cntDiffer ? 0 : cntDiffer > cntEqual ? indexDiffer : -1
}
}1 349
Задача: 761. Special Binary String
Сложность: hard
Специальные двоичные строки - это двоичные строки, обладающие следующими двумя свойствами: количество 0 равно количеству 1. Каждый префикс двоичной строки имеет не меньше 1, чем 0. Вам дана специальная двоичная строка s. Ход состоит в выборе двух последовательных, непустых специальных подстрок s и их обмене. Две строки являются последовательными, если последний символ первой строки находится ровно на один индекс раньше первого символа второй строки. Верните лексикографически наибольшую результирующую строку, возможную после применения указанных операций над строкой.
Пример:
Input: s = "11011000" Output: "11100100"👨💻 Алгоритм: 1⃣Определите, что специальная двоичная строка можно разбить на несколько специальных подстрок. 2⃣Рекурсивно примените к каждой подстроке этот алгоритм, чтобы найти лексикографически наибольшую строку. 3⃣Сортируйте полученные подстроки в лексикографическом порядке по убыванию и объединяйте их. 😎 Решение:
func makeLargestSpecial(_ s: String) -> String {
var count = 0, i = 0
var substrs = [String]()
let sArray = Array(s)
for (j, char) in sArray.enumerated() {
count += char == "1" ? 1 : -1
if count == 0 {
let substring = String(sArray[i + 1..<j])
substrs.append("1" + makeLargestSpecial(substring) + "0")
i = j + 1
}
}
return substrs.sorted(by: >).joined()
}1 349
Задача: 827. Making A Large Island
Сложность: hard
Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1.
Верните размер самого большого острова в grid после выполнения этой операции.
Остров — это группа 1, соединенных в 4 направлениях.
Пример:
Input: grid = [[1,1],[1,0]] Output: 4 Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.👨💻 Алгоритм: 1⃣Пройдите по матрице и пометьте каждую группу, используя уникальный индекс, и запомните её размер. 2⃣Для каждого 0 в матрице проверьте соседние группы и вычислите потенциальный размер острова, если изменить этот 0 на 1. 3⃣Возвращайте максимальный размер острова, учитывая как уже существующие острова, так и потенциальные, образованные после изменения 0 на 1. 😎 Решение:
class Solution {
var dr = [-1, 0, 1, 0]
var dc = [0, -1, 0, 1]
var grid = [[Int]]()
var N = 0
func largestIsland(_ grid: [[Int]]) -> Int {
self.grid = grid
N = grid.count
var index = 2
var area = [Int](repeating: 0, count: N * N + 2)
for r in 0..<N {
for c in 0..<N {
if grid[r][c] == 1 {
area[index] = dfs(r, c, index)
index += 1
}
}
}
var ans = 0
for x in area { ans = max(ans, x) }
for r in 0..<N {
for c in 0..<N {
if grid[r][c] == 0 {
var seen = Set<Int>()
for move in neighbors(r, c) {
if grid[move / N][move % N] > 1 {
seen.insert(grid[move / N][move % N])
}
}
var bns = 1
for i in seen { bns += area[i] }
ans = max(ans, bns)
}
}
}
return ans
}
func dfs(_ r: Int, _ c: Int, _ index: Int) -> Int {
var ans = 1
grid[r][c] = index
for move in neighbors(r, c) {
if grid[move / N][move % N] == 1 {
grid[move / N][move % N] = index
ans += dfs(move / N, move % N, index)
}
}
return ans
}
func neighbors(_ r: Int, _ c: Int) -> [Int] {
var ans = [Int]()
for k in 0..<4 {
let nr = r + dr[k]
let nc = c + dc[k]
if nr >= 0 && nr < N && nc >= 0 && nc < N {
ans.append(nr * N + nc)
}
}
return ans
}
}1 349
Задача: 1318. Minimum Flips to Make a OR b Equal to c
Сложность: medium
Даны три положительных числа a, b и c. Верните минимальное количество переворотов, необходимых в некоторых битах a и b, чтобы сделать (a OR b == c) (побитовая операция OR). Операция переворота состоит из изменения любого отдельного бита с 1 на 0 или с 0 на 1 в их двоичном представлении.
Пример:
Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)class Solution {
func minFlips(_ a: Int, _ b: Int, _ c: Int) -> Int {
var a = a, b = b, c = c
var answer = 0
while a != 0 || b != 0 || c != 0 {
if (c & 1) == 1 {
if (a & 1) == 0 && (b & 1) == 0 {
answer += 1
}
} else {
answer += (a & 1) + (b & 1)
}
a >>= 1
b >>= 1
c >>= 1
}
return answer
}
}1 349
Задача: 60. Permutation Sequence
Сложность: hard
Множество [1, 2, 3, ..., n] содержит в общей сложности n! уникальных перестановок.
Списком и маркировкой всех перестановок по порядку, мы получаем следующую последовательность для n = 3:
"123"
"132"
"213"
"231"
"312"
"321"
Дано n и k, верните k-ю перестановку последовательности.
Пример:
Input: n = 3, k = 3 Output: "213"👨💻 Алгоритм: 1⃣Сгенерируйте входной массив nums чисел от 1 до N. 2⃣Вычислите все факториальные основы от 0 до (N−1)!. 3⃣Уменьшите k на 1, чтобы значение попало в интервал (0, N!−1). 😎 Решение:
class Solution {
func getPermutation(_ n: Int, _ k: Int) -> String {
var factorials = [Int](repeating: 1, count: n)
var nums = [Character]()
for i in 1..<n {
factorials[i] = factorials[i - 1] * i
nums.append(Character(String(i + 1)))
}
var k = k - 1
var result = ""
for i in stride(from: n - 1, through: 0, by: -1) {
let idx = k / factorials[i]
k -= idx * factorials[i]
result.append(nums[idx])
nums.remove(at: idx)
}
return result
}
}1 349
Задача: 1101. The Earliest Moment When Everyone Become Friends
Сложность: medium
В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi.
Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b.
Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1.
Пример:
Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4 Output: 3 Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.👨💻 Алгоритм: 1⃣Отсортируйте логи по времени в хронологическом порядке, так как в задаче не указано, отсортированы ли они. 2⃣Пройдитесь по отсортированным логам, применяя структуру данных "Объединение-Поиск": Для каждого лога объедините двух участников, упомянутых в логе, с помощью функции union(a, b). Каждое объединение добавляет новые связи между участниками. 3⃣Следите за количеством групп: Изначально каждый участник рассматривается как отдельная группа. Количество групп уменьшается с каждым полезным объединением. Момент, когда количество групп уменьшается до одной, является самым ранним моментом, когда все участники становятся связанными (друзьями). Верните этот момент времени. Если такого момента не существует, верните -1. 😎 Решение:
class UnionFind {
private var parent: [Int]
private var rank: [Int]
init(_ n: Int) {
parent = Array(0..<n)
rank = Array(repeating: 1, count: n)
}
func find(_ x: Int) -> Int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
func union(_ x: Int, _ y: Int) -> Bool {
let rootX = find(x)
let rootY = find(y)
if rootX != rootY {
if rank[rootX] > rank[rootY] {
parent[rootY] = rootX
} else if rank[rootX] < rank[rootY] {
parent[rootX] = rootY
} else {
parent[rootY] = rootX
rank[rootX] += 1
}
return true
}
return false
}
}
class Solution {
func earliestAcq(_ logs: [[Int]], _ n: Int) -> Int {
let sortedLogs = logs.sorted { $0[0] < $1[0] }
var groupCount = n
let uf = UnionFind(n)
for log in sortedLogs {
let timestamp = log[0]
let friendA = log[1]
let friendB = log[2]
if uf.union(friendA, friendB) {
groupCount -= 1
}
if groupCount == 1 {
return timestamp
}
}
return -1
}
}1 349
Задача: 74. Search a 2D Matrix
Сложность: medium
Вам дана матрица из целых чисел размером m на n с следующими двумя свойствами:
Каждая строка отсортирована в порядке неубывания.
Первое число каждой строки больше последнего числа предыдущей строки.
Дано целое число target. Верните true, если target присутствует в матрице, и false в противном случае.
Вы должны написать решение с временной сложностью O(log(m * n)).
Пример:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true👨💻 Алгоритм: 1⃣Инициализируйте индексы слева и справа: left = 0 и right = m x n - 1. 2⃣Пока left <= right: Выберите индекс посередине виртуального массива в качестве опорного индекса: pivot_idx = (left + right) / 2. 3⃣Индекс соответствует row = pivot_idx // n и col = pivot_idx % n в исходной матрице, и, следовательно, можно получить pivot_element. Этот элемент делит виртуальный массив на две части. Сравните pivot_element и target, чтобы определить, в какой части нужно искать target. 😎 Решение:
func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
let m = matrix.count
if m == 0 { return false }
let n = matrix[0].count
var left = 0
var right = m * n - 1
var pivotIdx: Int
var pivotElement: Int
while left <= right {
pivotIdx = (left + right) / 2
pivotElement = matrix[pivotIdx / n][pivotIdx % n]
if target == pivotElement {
return true
} else {
if target < pivotElement {
right = pivotIdx - 1
} else {
left = pivotIdx + 1
}
}
}
return false
}1 349
Задача: 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
Сложность: medium
Дан прямоугольный торт размером h x w и два массива целых чисел horizontalCuts и verticalCuts, где:
horizontalCuts[i] — это расстояние от верхнего края прямоугольного торта до i-го горизонтального разреза,
verticalCuts[j] — это расстояние от левого края прямоугольного торта до j-го вертикального разреза.
Верните максимальную площадь кусочка торта после разрезания в каждом горизонтальном и вертикальном положении, указанном в массивах horizontalCuts и verticalCuts. Так как ответ может быть очень большим числом, верните его по модулю 10^9 + 7.
Пример:
Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts.
After you cut the cake, the green piece of cake has the maximum area.class Solution {
func maxArea(_ h: Int, _ w: Int, _ horizontalCuts: [Int], _ verticalCuts: [Int]) -> Int {
let horizontalCuts = horizontalCuts.sorted()
let verticalCuts = verticalCuts.sorted()
var maxHeight = max(horizontalCuts[0], h - horizontalCuts.last!)
for i in 1..<horizontalCuts.count {
maxHeight = max(maxHeight, horizontalCuts[i] - horizontalCuts[i - 1])
}
var maxWidth = max(verticalCuts[0], w - verticalCuts.last!)
for i in 1..<verticalCuts.count {
maxWidth = max(maxWidth, verticalCuts[i] - verticalCuts[i - 1])
}
return (maxHeight * maxWidth) % 1000000007
}
}1 349
Задача: 1464. Maximum Product of Two Elements in an Array
Сложность: easy
Дан массив целых чисел nums, выберите два разных индекса i и j этого массива. Верните максимальное значение (nums[i]-1)*(nums[j]-1).
Пример:
Input: nums = [3,4,5,2]
Output: 12
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value,
that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12. class Solution {
func maxProduct(_ nums: [Int]) -> Int {
var biggest = 0
var secondBiggest = 0
for num in nums {
if num > biggest {
secondBiggest = biggest
biggest = num
} else if num > secondBiggest {
secondBiggest = num
}
}
return (biggest - 1) * (secondBiggest - 1)
}
}1 349
Задача: 678. Valid Parenthesis String
Сложность: medium
Создайте карту, которая позволяет выполнять следующие действия:
Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:
Дана строка s, содержащая только три типа символов: '(', ')' и '*'. Вернуть true, если s является допустимой.
Следующие правила определяют допустимую строку:
Любая открывающая скобка '(' должна иметь соответствующую закрывающую скобку ')'.
Любая закрывающая скобка ')' должна иметь соответствующую открывающую скобку '('.
Открывающая скобка '(' должна идти перед соответствующей закрывающей скобкой ')'.
'*' может рассматриваться как одна закрывающая скобка ')', одна открывающая скобка '(' или пустая строка "".
Пример:
Input: s = "()" Output: true Example 2:👨💻 Алгоритм: 1⃣Инициализировать 2D вектор memo размером s.size() x s.size() - 1, представляющий неинициализированное состояние. Вызвать вспомогательную функцию isValidString с начальными параметрами index = 0, openCount = 0 и строкой s. Вернуть результат isValidString. 2⃣Вспомогательная функция isValidString. Базовый случай: если index достиг конца строки (index == s.size.), вернуть true, если openCount равен 0 (все скобки сбалансированы), и false в противном случае. Проверить, был ли результат для текущего index и openCount уже вычислен (мемоизирован) в memo. Если да, вернуть мемоизированный результат. Инициализировать isValid как false. Если текущий символ s[index] равен '*': Попробовать трактовать '*' как '(' и вызвать isValidString рекурсивно с index + 1 и openCount + 1. Если рекурсивный вызов вернет true, обновить isValid на true. Если openCount не равен нулю, попробовать трактовать '*' как ')' и вызвать isValidString рекурсивно с index + 1 и openCount - 1. Если рекурсивный вызов вернет true, обновить isValid на true. Попробовать трактовать '*' как пустой символ и вызвать isValidString рекурсивно с index + 1 и тем же openCount. Если рекурсивный вызов вернет true, обновить isValid на true. 3⃣Продолжение функции isValidString. Если текущий символ s[index] равен '(': Вызвать isValidString рекурсивно с index + 1 и openCount + 1. Обновить isValid с результатом рекурсивного вызова. Если текущий символ s[index] равен ')': Если openCount не равен нулю (есть открытые скобки), вызвать isValidString рекурсивно с index + 1 и openCount - 1. Обновить isValid с результатом рекурсивного вызова. Мемоизировать результат isValid в memo[index][openCount]. Вернуть isValid. 😎 Решение:
class Solution {
func checkValidString(_ s: String) -> Bool {
var memo = Array(repeating: Array(repeating: -1, count: s.count), count: s.count)
return isValidString(0, 0, s, &memo)
}
private func isValidString(_ index: Int, _ openCount: Int, _ str: String, _ memo: inout [[Int]]) -> Bool {
if index == str.count {
return openCount == 0
}
if memo[index][openCount] != -1 {
return memo[index][openCount] == 1
}
var isValid = false
let currentIndex = str.index(str.startIndex, offsetBy: index)
if str[currentIndex] == "*" {
isValid = isValidString(index + 1, openCount + 1, str, &memo)
if openCount > 0 {
isValid = isValid || isValidString(index + 1, openCount - 1, str, &memo)
}
isValid = isValid || isValidString(index + 1, openCount, str, &memo)
} else if str[currentIndex] == "(" {
isValid = isValidString(index + 1, openCount + 1, str, &memo)
} else if openCount > 0 {
isValid = isValidString(index + 1, openCount - 1, str, &memo)
}
memo[index][openCount] = isValid ? 1 : 0
return isValid
}
}1 349
Задача: 487. Max Consecutive Ones II
Сложность: medium
Дан бинарный массив nums, верните максимальное количество последовательных единиц в массиве, если можно перевернуть не более одного нуля.
Пример:
Input: nums = [1,0,1,1,0] Output: 4 Explanation: - If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones. - If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones. The max number of consecutive ones is 4.👨💻 Алгоритм: 1⃣Для каждого возможного начала последовательности в массиве nums начните считать количество нулей. 2⃣Для каждой последовательности проверяйте, сколько нулей содержится в ней. Если количество нулей не превышает одного, обновите максимальную длину последовательности единиц. 3⃣Продолжайте проверять все возможные последовательности в массиве, и верните максимальную длину последовательности единиц, удовлетворяющую условию. 😎 Решение:
class Solution {
func findMaxConsecutiveOnes(_ nums: [Int]) -> Int {
var longestSequence = 0
for left in 0..<nums.count {
var numZeroes = 0
for right in left..<nums.count {
if nums[right] == 0 {
numZeroes += 1
}
if numZeroes <= 1 {
longestSequence = max(longestSequence, right - left + 1)
}
}
}
return longestSequence
}
}1 349
Задача: 724. Find Pivot Index
Сложность: easy
Если задан массив целых чисел nums, вычислите поворотный индекс этого массива. Поворотный индекс - это индекс, при котором сумма всех чисел строго слева от индекса равна сумме всех чисел строго справа от индекса. Если индекс находится на левом краю массива, то сумма слева равна 0, так как слева нет элементов. Это относится и к правому краю массива. Возвращается самый левый поворотный индекс. Если такого индекса не существует, возвращается -1.
Пример:
Input: nums = [1,7,3,6,5,6] Output: 3👨💻 Алгоритм: 1⃣Вычислите сумму всех элементов массива. 2⃣Пройдите по массиву, вычисляя текущую сумму элементов слева и проверяя, равна ли она разности между общей суммой и текущей суммой справа. 3⃣Если текущий индекс удовлетворяет условию, верните его; если нет, продолжайте проверку. Если такой индекс не найден, верните -1. 😎 Решение:
func pivotIndex(_ nums: [Int]) -> Int {
let totalSum = nums.reduce(0, +)
var leftSum = 0
for i in 0..<nums.count {
if leftSum == totalSum - leftSum - nums[i] {
return i
}
leftSum += nums[i]
}
return -1
}