اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
Swift | LeetCode
رفتن به کانال در Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+bn3i_aLL0-A2ZGMy Вопросы собесов t.me/+wtkjBoN6OI5hNGEy Вакансии t.me/+3o9-Ytdiv_E5OGIy
نمایش بیشتر1 363
مشترکین
اطلاعاتی وجود ندارد24 ساعت
اطلاعاتی وجود ندارد7 روز
-730 روز
آرشیو پست ها
1 363
Задача: 897. Increasing Order Search Tree
Сложность: easy
Задав корень дерева двоичного поиска, перестройте дерево по порядку так, чтобы самый левый узел дерева теперь был корнем дерева, а каждый узел не имел левого и только одного правого дочернего узла.
Пример:
Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9] Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]👨💻 Алгоритм: 1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов. 2⃣Перестроить дерево, устанавливая каждый узел из списка как правый дочерний элемент предыдущего узла и устанавливая левые дочерние элементы в null. 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
}
}
func increasingBST(_ root: TreeNode?) -> TreeNode? {
var nodes: [TreeNode] = []
func inorder(_ node: TreeNode?) {
guard let node = node else { return }
inorder(node.left)
nodes.append(node)
inorder(node.right)
}
inorder(root)
for i in 0..<nodes.count - 1 {
nodes[i].left = nil
nodes[i].right = nodes[i + 1]
}
nodes.last?.left = nil
nodes.last?.right = nil
return nodes.first
}1 363
Задача: 642. Design Search Autocomplete System
Сложность: hard
Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае.
Пример:
Input ["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"] [[3], [1], [2], [3], [4], [], [], [], [4], []] Output [null, true, true, true, false, 2, true, true, true, 4]👨💻 Алгоритм: 1⃣Инициализация и проверка состояний: Реализуйте конструктор для инициализации кольцевой двусторонней очереди заданного размера и методы для проверки пустоты и полноты очереди. 2⃣Операции вставки: Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры. 3⃣Операции удаления: Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди. 😎 Решение:
class TrieNode {
var children = [Character: TrieNode]()
var count = [String: Int]()
}
class AutocompleteSystem {
private var root = TrieNode()
private var prefix = ""
init(_ sentences: [String], _ times: [Int]) {
for i in 0..<sentences.count {
add(sentences[i], times[i])
}
}
private func add(_ sentence: String, _ count: Int) {
var node = root
for char in sentence {
if node.children[char] == nil {
node.children[char] = TrieNode()
}
node = node.children[char]!
node.count[sentence, default: 0] += count
}
}
func input(_ c: Character) -> [String] {
if c == "#" {
add(prefix, 1)
prefix = ""
return []
}
prefix.append(c)
var node = root
for char in prefix {
if node.children[char] == nil {
return []
}
node = node.children[char]!
}
let pq = node.count.sorted { lhs, rhs in
if lhs.value == rhs.value {
return lhs.key < rhs.key
}
return lhs.value > rhs.value
}
return Array(pq.prefix(3)).map { $0.key }
}
}1 363
Задача: 521. Longest Uncommon Subsequence I
Сложность: easy
Даны две строки a и b. Верните длину самой длинной несообщей подпоследовательности между a и b. Если такой несообщей подпоследовательности не существует, верните -1.
Несообщая подпоследовательность между двумя строками — это строка, которая является подпоследовательностью только одной из них.
Пример:
Input: a = "aba", b = "cdc" Output: 3 Explanation: One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc". Note that "cdc" is also a longest uncommon subsequence.👨💻 Алгоритм: 1⃣Если строка a равна строке b, верните -1, так как не существует несообщей подпоследовательности. 2⃣В противном случае: Вычислите длины строк a и b. 3⃣Верните длину более длинной строки. 😎 Решение:
class Solution {
func findLUSlength(_ a: String, _ b: String) -> Int {
if a == b {
return -1
} else {
return max(a.count, b.count)
}
}
}1 363
Задача: 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 363
Задача: 583. Delete Operation for Two Strings
Сложность: medium
Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми.
На одном шаге можно удалить ровно один символ в любой строке.
Пример:
Input: word1 = "sea", word2 = "eat" Output: 2 Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".👨💻 Алгоритм: 1⃣ Инициализация массива: Создайте одномерный массив dp для хранения минимального количества удалений, необходимых для уравнивания строк word1 и word2. 2⃣ Заполнение массива: Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки. 3⃣ Обновление и результат: Скопируйте временный массив temp обратно в dp после обработки каждой строки. В конце верните значение из dp, представляющее минимальное количество удалений. 😎 Решение:
class Solution {
func minDistance(_ word1: String, _ word2: String) -> Int {
let m = word1.count, n = word2.count
var dp = [Int](repeating: 0, count: n + 1)
let s1 = Array(word1), s2 = Array(word2)
for i in 0...m {
var temp = [Int](repeating: 0, count: n + 1)
for j in 0...n {
if i == 0 || j == 0 {
temp[j] = i + j
} else if s1[i - 1] == s2[j - 1] {
temp[j] = dp[j - 1]
} else {
temp[j] = 1 + min(dp[j], temp[j - 1])
}
}
dp = temp
}
return dp[n]
}
}1 363
Задача: 1328. Break a Palindrome
Сложность: medium
Дана палиндромная строка из строчных английских букв palindrome. Замените ровно один символ на любую строчную английскую букву так, чтобы результирующая строка не была палиндромом и чтобы она была лексикографически наименьшей из возможных.
Верните получившуюся строку. Если нет способа заменить символ, чтобы строка перестала быть палиндромом, верните пустую строку.
Строка a лексикографически меньше строки b (одинаковой длины), если в первой позиции, где они отличаются, у строки a символ строго меньше соответствующего символа в строке b. Например, "abcc" лексикографически меньше "abcd", потому что первой различающейся позицией является четвертая, и 'c' меньше, чем 'd'.
Пример:
Input: palindrome = "abccba"
Output: "aaccba"
Explanation: There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba".
Of all the ways, "aaccba" is the lexicographically smallest.class Solution {
func breakPalindrome(_ palindrome: String) -> String {
var palindromeArray = Array(palindrome)
let length = palindromeArray.count
if length == 1 {
return ""
}
for i in 0..<length / 2 {
if palindromeArray[i] != "a" {
palindromeArray[i] = "a"
return String(palindromeArray)
}
}
palindromeArray[length - 1] = "b"
return String(palindromeArray)
}
}1 363
Задача: 717. 1-bit and 2-bit Characters
Сложность: easy
У нас есть два специальных символа: первый символ может быть представлен одним битом 0. Второй символ может быть представлен двумя битами (10 или 11). Если задан двоичный массив bits, который заканчивается 0, верните true, если последний символ должен быть однобитным.
Пример:
Input: bits = [1,0,0] Output: true👨💻 Алгоритм: 1⃣Инициализируйте индекс для итерации по массиву. 2⃣Пройдите по массиву, увеличивая индекс на 1, если текущий бит равен 0, и на 2, если текущий бит равен 1. 3⃣Проверьте, достиг ли индекс последнего элемента массива, и верните результат. 😎 Решение:
func isOneBitCharacter(_ bits: [Int]) -> Bool {
var i = 0
while i < bits.count - 1 {
i += bits[i] + 1
}
return i == bits.count - 1
}1 363
Задача: 435. Non-overlapping Intervals
Сложность: medium
Дан массив интервалов intervals, где intervals[i] = [starti, endi]. Верните минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не пересекались.
Пример:
Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.👨💻 Алгоритм: 1⃣Отсортируйте интервалы по времени окончания. 2⃣Инициализируйте переменную ответа ans = 0 и целое число k для представления самого последнего времени окончания. k следует инициализировать небольшим значением, например, INT_MIN. 3⃣Итеративно пройдитесь по интервалам. Для каждого интервала: Если время начала больше или равно k, обновите k до времени окончания текущего интервала. В противном случае увеличьте ans. Верните ans. 😎 Решение:
class Solution {
func eraseOverlapIntervals(_ intervals: [[Int]]) -> Int {
let sortedIntervals = intervals.sorted { $0[1] < $1[1] }
var ans = 0
var k = Int.min
for interval in sortedIntervals {
let x = interval[0]
let y = interval[1]
if x >= k {
k = y
} else {
ans += 1
}
}
return ans
}
}1 363
Задача: 245. Shortest Word Distance II
Сложность: medium
Дан массив строк wordsDict и две строки word1 и word2, которые уже существуют в массиве. Верните наименьшее расстояние между вхождениями этих двух слов в списке.
Обратите внимание, что word1 и word2 могут быть одинаковыми. Гарантируется, что они представляют собой два отдельных слова в списке.
Пример:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding" Output: 1👨💻 Алгоритм: 1⃣Переберите список wordsDict и сохраните индексы слова word1 в список indices1 и индексы слова word2 в список indices2. Инициализируйте переменную shortestDistance = INT_MAX. 2⃣Переберите индексы в списке indices1 и для каждого индекса найдите верхнюю границу в списке indices2, используя бинарный поиск, и сохраните этот индекс в переменную x. Рассмотрите индексы indices2[x] и indices2[x - 1], обновляя shortestDistance, если индексы не совпадают. 3⃣Верните значение переменной shortestDistance. 😎 Решение:
class Solution {
func shortestWordDistance(_ wordsDict: [String], _ word1: String, _ word2: String) -> Int {
var indices1 = [Int]()
var indices2 = [Int]()
for (i, word) in wordsDict.enumerated() {
if word == word1 {
indices1.append(i)
}
if word == word2 {
indices2.append(i)
}
}
var shortestDistance = Int.max
for index in indices1 {
let x = indices2.partitioningIndex(where: { $0 > index })
if x < indices2.count {
shortestDistance = min(shortestDistance, indices2[x] - index)
}
if x > 0 && indices2[x - 1] != index {
shortestDistance = min(shortestDistance, index - indices2[x - 1])
}
}
return shortestDistance
}
}1 363
Задача: 567. Permutation in String
Сложность: medium
Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае.
Другими словами, верните true, если одна из перестановок s1 является подстрокой s2.
Пример:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
👨💻 Алгоритм:
1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2.
2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1.
3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false.
😎 Решение:
class Solution {
func checkInclusion(_ s1: String, _ s2: String) -> Bool {
let s1Len = s1.count, s2Len = s2.count
if s1Len > s2Len { return false }
let s1Arr = Array(s1), s2Arr = Array(s2)
var s1Count = [Int](repeating: 0, count: 26)
var s2Count = [Int](repeating: 0, count: 26)
for i in 0..<s1Len {
s1Count[Int(s1Arr[i].asciiValue! - Character("a").asciiValue!)] += 1
s2Count[Int(s2Arr[i].asciiValue! - Character("a").asciiValue!)] += 1
}
for i in 0..<(s2Len - s1Len) {
if s1Count == s2Count { return true }
s2Count[Int(s2Arr[i].asciiValue! - Character("a").asciiValue!)] -= 1
s2Count[Int(s2Arr[i + s1Len].asciiValue! - Character("a").asciiValue!)] += 1
}
return s1Count == s2Count
}
}1 363
Задача: 442. Find All Duplicates in an Array
Сложность: medium
Дан целочисленный массив nums длины n, где все целые числа nums находятся в диапазоне [1, n], и каждое число появляется один или два раза. Верните массив всех чисел, которые появляются дважды.
Вы должны написать алгоритм, который работает за время O(n) и использует только постоянное дополнительное пространство.
Пример:
Input: nums = [4,3,2,7,8,2,3,1] Output: [2,3]👨💻 Алгоритм: 1⃣Когда мы итерируемся по элементам входного массива, мы можем просто искать любое другое вхождение текущего элемента в оставшейся части массива. 2⃣Поскольку элемент может появляться только один или два раза, нам не нужно беспокоиться о получении дубликатов элементов, которые появляются дважды: Случай I: Если элемент встречается в массиве только один раз, при поиске его в остальной части массива ничего не найдется. Случай II: Если элемент встречается дважды, вы найдете второе вхождение элемента в оставшейся части массива. Когда вы наткнетесь на второе вхождение в более поздней итерации, это будет аналогично случаю I (поскольку больше вхождений этого элемента в оставшейся части массива не будет). 3⃣Таким образом, можно эффективно определить все элементы, которые встречаются дважды, и добавить их в результирующий массив, проходя по каждому элементу массива и проверяя наличие его второго вхождения в оставшейся части массива. 😎 Решение:
class Solution {
func findDuplicates(_ nums: [Int]) -> [Int] {
var ans = [Int]()
for i in 0..<nums.count {
for j in (i+1)..<nums.count {
if nums[j] == nums[i] {
ans.append(nums[i])
break
}
}
}
return ans
}
}1 363
Сегодня последний день!
Акция на Пожизненный easyoffer PRO - по цене 1 года заканчивается сегодня.
PRO подписка включает:
– Доступ ко всем профессиям сайта без ограничений
– Все текущие и новые функции, которые будут появляться на сайте
👉 Акция до 31 марта 23:59 по МСК https://easyoffer.ru/pro
1 363
Задача: 946. Validate Stack Sequences
Сложность: medium
Вам дан целочисленный массив nums. За один ход вы можете выбрать индекс i, где 0 <= i < nums.length, и увеличить nums[i] на 1. Верните минимальное количество ходов, чтобы каждое значение в nums было уникальным. Тестовые примеры генерируются так, чтобы ответ умещался в 32-битное целое число.
Пример:
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1] Output: true👨💻 Алгоритм: 1⃣Инициализировать пустой стек. Использовать указатель j для отслеживания текущей позиции в массиве popped. 2⃣Пройти по каждому элементу в массиве pushed: Добавить элемент в стек. Проверить верхний элемент стека: Если он совпадает с текущим элементом в popped, удалить элемент из стека и увеличить указатель j. 3⃣В конце вернуть true, если указатель j достиг конца массива popped, иначе вернуть false. 😎 Решение:
class Solution {
func validateStackSequences(_ pushed: [Int], _ popped: [Int]) -> Bool {
var stack = [Int]()
var j = 0
for x in pushed {
stack.append(x)
while !stack.isEmpty && j < popped.count && stack.last == popped[j] {
stack.removeLast()
j += 1
}
}
return j == popped.count
}
}1 363
Задача: 1155. Number of Dice Rolls With Target Sum
Сложность: medium
У вас есть n кубиков, и на каждом кубике k граней, пронумерованных от 1 до k.
Даны три целых числа n, k и target. Необходимо вернуть количество возможных способов (из общего количества kn способов) выбросить кубики так, чтобы сумма выпавших чисел равнялась target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.class Solution {
let MOD = 1_000_000_007
func waysToTarget(_ memo: inout [[Int]], _ diceIndex: Int, _ n: Int, _ currSum: Int, _ target: Int, _ k: Int) -> Int {
if diceIndex == n {
return currSum == target ? 1 : 0
}
if memo[diceIndex][currSum] != -1 {
return memo[diceIndex][currSum]
}
var ways = 0
for i in 1...min(k, target - currSum) {
ways = (ways + waysToTarget(&memo, diceIndex + 1, n, currSum + i, target, k)) % MOD
}
memo[diceIndex][currSum] = ways
return ways
}
func numRollsToTarget(_ n: Int, _ k: Int, _ target: Int) -> Int {
var memo = Array(repeating: Array(repeating: -1, count: target + 1), count: n + 1)
return waysToTarget(&memo, 0, n, 0, target, k)
}
}1 363
Завтра последний день!
Успей купить пожизненный easyoffer PRO - по цене 1 года
Покупаешь один раз — пользуешься всю жизнь.
👉 Акция до 31 марта: https://easyoffer.ru/pro
1 363
Задача: 434. Number of Segments in a String
Сложность: easy
Дана строка s, верните количество сегментов в строке.
Сегмент определяется как непрерывная последовательность символов, отличных от пробелов.
Пример:
Input: s = "Hello, my name is John" Output: 5 Explanation: The five segments are ["Hello,", "my", "name", "is", "John"]👨💻 Алгоритм: 1⃣Инициализируйте счетчик сегментов segment_count равным 0. 2⃣Итеративно пройдитесь по строке s. Для каждого индекса i проверьте, начинается ли на этом индексе сегмент: Если символ s[i] не является пробелом, и (либо это первый символ строки, либо предыдущий символ s[i-1] является пробелом), увеличьте segment_count. 3⃣Верните segment_count. 😎 Решение:
class Solution {
func countSegments(_ s: String) -> Int {
var segmentCount = 0
let chars = Array(s)
for i in 0..<chars.count {
if (i == 0 || chars[i - 1] == " ") && chars[i] != " " {
segmentCount += 1
}
}
return segmentCount
}
}1 363
Задача: 316. Remove Duplicate Letters
Сложность: medium
Дана строка
s, удалите повторяющиеся буквы так, чтобы каждая буква появилась один раз и только один раз. Вы должны сделать так, чтобы результат был наименьшим в лексикографическом порядке среди всех возможных результатов.
Пример:
Input: s = "bcabc" Output: "abc"👨💻 Алгоритм: 1⃣Инициализация стека Создайте стек, который будет хранить результат, построенный по мере итерации строки. 2⃣Итерация по строке На каждой итерации добавляйте текущий символ в стек, если он еще не был использован. Перед добавлением текущего символа удаляйте как можно больше символов из вершины стека, если это возможно и улучшает лексикографический порядок. 3⃣Удаление символов Удаляйте символы с вершины стека при выполнении следующих условий: Символ на вершине стека больше текущего символа. Символ может быть удален, так как он встречается позже в строке. На каждом этапе итерации по строке жадно минимизируйте содержимое стека. 😎 Решение:
class Solution {
func removeDuplicateLetters(_ s: String) -> String {
var stack = [Character]()
var seen = Set<Character>()
let lastOccurrence = Dictionary(uniqueKeysWithValues: s.enumerated().map { ($1, $0) })
for (i, c) in s.enumerated() {
if !seen.contains(c) {
while let last = stack.last, c < last, i < lastOccurrence[last]! {
seen.remove(stack.popLast()!)
}
seen.insert(c)
stack.append(c)
}
}
return String(stack)
}
}1 363
Задача: 496. Next Greater Element I
Сложность: easy
Следующий больший элемент для некоторого элемента x в массиве — это первый больший элемент, который находится справа от x в том же массиве.
Вам даны два различных целочисленных массива с индексами, начинающимися с 0: nums1 и nums2, где nums1 является подмножеством nums2.
Для каждого 0 <= i < nums1.length найдите индекс j, такой что nums1[i] == nums2[j], и определите следующий больший элемент для nums2[j] в nums2. Если следующего большего элемента нет, то ответ для этого запроса — -1.
Верните массив ans длиной nums1.length, где ans[i] — это следующий больший элемент, как описано выше.
Пример:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2] Output: [-1,3,-1] Explanation: The next greater element for each value of nums1 is as follows: - 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1. - 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3. - 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.👨💻 Алгоритм: 1⃣Инициализация и поиск совпадений Создайте массив res для хранения результатов. Для каждого элемента nums1[i] найдите его индекс j в массиве nums2. 2⃣Поиск следующего большего элемента После нахождения индекса j в nums2 начните поиск элемента справа от nums2[j], который больше nums1[i]. Если такой элемент найден, добавьте его в res. 3⃣Заполнение результата Если следующий больший элемент не найден, добавьте -1 в соответствующую позицию res. Верните массив res. 😎 Решение:
class Solution {
func nextGreaterElement(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var res = [Int](repeating: -1, count: nums1.count)
for i in 0..<nums1.count {
var found = false
for j in 0..<nums2.count {
if nums2[j] == nums1[i] {
found = true
}
if found && nums2[j] > nums1[i] {
res[i] = nums2[j]
break
}
}
}
return res
}
}1 363
Задача: 1039. Minimum Score Triangulation of Polygon
Сложность: medium
У вас есть выпуклый n-сторонний многоугольник, каждая вершина которого имеет целочисленное значение. Вам дан целочисленный массив values, где values[i] - это значение i-й вершины (т.е. по часовой стрелке). Вы должны триангулировать многоугольник на n - 2 треугольника. Для каждого треугольника значение этого треугольника равно произведению значений его вершин, а общий балл триангуляции равен сумме этих значений для всех n - 2 треугольников в триангуляции. Верните наименьший возможный общий балл, который вы можете получить с помощью некоторой триангуляции многоугольника.
Пример:
Input: values = [1,2,3] Output: 6👨💻 Алгоритм: 1⃣Инициализация: Создаем двумерный массив dp, где dp[i][j] будет хранить минимальный возможный общий балл триангуляции многоугольника, состоящего из вершин от i до j. 2⃣Основное заполнение dp: Проходим по всем возможным длинам подмногоугольников, начиная с треугольников (длина 3) до всего многоугольника (длина n). Для каждого подмногоугольника находим минимальный возможный общий балл, проверяя все возможные треугольники, которые могут быть образованы из этого подмногоугольника. Заполнение dp для каждого подмногоугольника: Для каждого подмногоугольника от i до j, и для каждой возможной вершины k между i и j, обновляем значение dp[i][j], как сумму минимальных значений триангуляций левой и правой частей подмногоугольника, а также значения текущего треугольника, образованного вершинами i, k и j. 3⃣Возврат результата: Ответ будет в dp[0][n-1], который хранит минимальный возможный общий балл триангуляции для всего многоугольника. 😎 Решение:
class Solution {
func minScoreTriangulation(_ values: [Int]) -> Int {
let n = values.count
var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
for length in 2..<n {
for i in 0..<(n - length) {
let j = i + length
dp[i][j] = Int.max
for k in (i + 1)..<j {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k])
}
}
}
return dp[0][n - 1]
}
}1 363
Задача: 55. Jump Game
Сложность: medium
Вам дан массив целых чисел nums. Изначально вы находитесь на первом индексе массива, и каждый элемент массива представляет вашу максимальную длину прыжка в этой позиции.
Верните true, если вы можете достичь последнего индекса, или false в противном случае.
Пример:
Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.👨💻Алгоритм: 1⃣Инициализация таблицы памяти: Изначально все элементы таблицы памяти имеют статус UNKNOWN, за исключением последнего, который является (тривиально) GOOD (может достичь сам себя). 2⃣Модификация алгоритма обратного трассирования: Измените алгоритм обратного трассирования таким образом, чтобы на рекурсивном шаге сначала проверялось, известен ли индекс (GOOD/BAD). Если индекс известен, тогда возвращается True/False. 3⃣Выполнение и сохранение результатов: Если индекс не известен, выполняйте шаги обратного трассирования, как ранее. После определения значения текущего индекса, сохраните его в таблице памяти. 😎 Решение:
enum Index {
case good, bad, unknown
}
class Solution {
var memo: [Index]
init(_ nums: [Int]) {
self.memo = Array(repeating: .unknown, count: nums.count)
self.memo[nums.count - 1] = .good
}
func canJumpFromPosition(_ position: Int, _ nums: [Int]) -> Bool {
if memo[position] != .unknown {
return memo[position] == .good
}
let furthestJump = min(position + nums[position], nums.count - 1)
for nextPosition in (position + 1)...furthestJump {
if canJumpFromPosition(nextPosition, nums) {
memo[position] = .good
return true
}
}
memo[position] = .bad
return false
}
func canJump(_ nums: [Int]) -> Bool {
return canJumpFromPosition(0, nums)
}
}