اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
Swift | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
نمایش بیشتر
شبکه:1 340
مشترکین
-124 ساعت
-107 روز
-2330 روز
آرشیو پست ها
1 340
#medium
Задача: 328. Odd Even Linked List
Дан заголовок односвязного списка. Сгруппируйте все узлы с нечетными индексами вместе, а затем узлы с четными индексами, и верните упорядоченный список.
Первый узел считается нечетным, второй узел — четным и так далее.
Учтите, что относительный порядок внутри обеих групп (четной и нечетной) должен оставаться таким же, как в исходном списке.
Вы должны решить задачу с дополнительной сложностью по памяти O(1) и временной сложностью O(n).
Пример:
Input: head = [2,1,3,5,6,4,7] Output: [2,3,6,7,1,5,4]👨💻 Алгоритм: 1⃣Инициализация указателей: Создайте указатели odd и even для работы с нечетными и четными узлами, соответственно. Инициализируйте odd началом списка head, а even — следующим узлом head.next. Также создайте указатель evenHead для сохранения начала четного списка. 2⃣Разделение списка: Используйте цикл для прохождения списка, перенаправляя нечетные узлы в oddList, а четные узлы в evenList. Обновляйте указатели odd и even в процессе итерации. 3⃣Соединение списков: После окончания цикла соедините конец нечетного списка с началом четного списка, используя указатель evenHead. 😎 Решение:
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) {
self.val = val
self.next = nil
}
}
class Solution {
func oddEvenList(_ head: ListNode?) -> ListNode? {
if head == nil { return nil }
var odd = head
var even = head?.next
let evenHead = even
while even != nil && even?.next != nil {
odd?.next = even?.next
odd = odd?.next
even?.next = odd?.next
even = even?.next
}
odd?.next = evenHead
return head
}
}1 340
Перец на канале «Записки необычного препода» делает невозможное!
А именно — встраивает мышление на английском взрослым людям.
Как обычно пытаются научить «думать на языке»? Методом «бери больше, кидай дальше». Слушайте песни, смотрите фильмы, читайте книги в оригинале, и оно само как-нибудь запустится.
Тут всё совсем не так. Тут происходит встраивание языка на кардинально других принципах. В результате вы ощущаете грамматику и слова «изнутри». Так, как бы вы их ощущали, будь вы носителем английского языка.
Почитать подробнее про эту технологию можно тут.
Есть конкретный механизм мышления. Он состоит из визуального слоя, слоя смыслов и слоя слов. Механизм разбивается на элементы. Каждый элемент тренируется отдельно. Оттренированные элементы стыкуются друг с другом с помощью специальных упражнений.
Здесь:
- Пошаговая технология;
- Разбор механик мышления на языке;
- Простота — любое сложное упражнение должно быть разбито на простые.
- Измеримость — все упражнения тренируются до норматива (как правило в секундах). Норматив гарантирует освоение упражнения на уровне навыка.
- Сумма упражнений неизбежно приводит к мышлению на языке. Так же, как правильно собранные вместе детали создают автомобиль.
Вот, например:
- как найти английские артикли в русском;
- как освоить что угодно в 10 раз быстрее;
- как взломать английскую грамматику.
Подписывайся, чтобы узнать больше.
1 340
#medium
Задача: 353. Design Snake Game
Спроектируйте игру «Змейка», которая играется на устройстве с экраном размером высота x ширина. Поиграйте в игру онлайн, если вы не знакомы с ней.
Змейка изначально расположена в верхнем левом углу (0, 0) с длиной 1 единица.
Вам дан массив еды, где food[i] = (ri, ci) — это строка и столбец положения кусочка еды, которую змейка может съесть. Когда змейка съедает кусочек еды, ее длина и очки игры увеличиваются на 1.
Каждый кусочек еды появляется на экране по очереди, что означает, что второй кусочек еды не появится, пока змейка не съест первый кусочек еды.
Когда кусочек еды появляется на экране, гарантируется, что он не появится на блоке, занятом змейкой.
Игра заканчивается, если змейка выходит за границы (ударяется о стену) или если ее голова занимает место, которое занимает ее тело после движения (например, змейка длиной 4 не может столкнуться сама с собой).
Реализуйте класс SnakeGame:
SnakeGame(int width, int height, int[][] food) Инициализирует объект с экраном размером высота x ширина и позициями еды.
int move(String direction) Возвращает количество очков после применения одного движения змейки в указанном направлении. Если игра окончена, возвращает -1.
Пример:
["SnakeGame", "move", "move", "move", "move", "move", "move"] [[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]] Output [null, 0, 0, 1, 1, 2, -1]👨💻 Алгоритм: 1⃣Инициализация: Инициализируйте очередь, содержащую начальную позицию змейки (0,0), и словарь для отслеживания позиций тела змейки. 2⃣Вычисление новой головы и проверка завершения игры: Вычислите новую позицию головы в зависимости от направления движения. Проверьте, ударилась ли змейка о границы или кусает ли она сама себя, проверяя наличие новой головы в словаре (исключая текущий хвост). Если любое из этих условий выполнено, завершите игру. 3⃣Обновление состояния змейки: Если змейка съедает еду, добавьте новую голову в очередь и словарь, не удаляя хвост. Если еды нет, переместите голову, добавив её в очередь и словарь, и удалите хвост из очереди и словаря. Верните текущую длину змейки или -1, если игра завершена. 😎 Решение:
import Foundation
class SnakeGame {
private var snake: Deque = Deque([(0, 0)])
private var snakeSet: Set = Set([(0, 0)])
private var width: Int
private var height: Int
private var food: [[Int]]
private var foodIndex = 0
private let movement = ["U": [-1, 0], "L": [0, -1], "R": [0, 1], "D": [1, 0]]
init(_ width: Int, _ height: Int, _ food: [[Int]]) {
self.width = width
self.height = height
self.food = food
}
func move(_ direction: String) -> Int {
let newHead = (snake.first!.0 + movement[direction]![0],
snake.first!.1 + movement[direction]![1])
let crossesBoundary1 = newHead.0 < 0 || newHead.0 >= height
let crossesBoundary2 = newHead.1 < 0 || newHead.1 >= width
let bitesItself = snakeSet.contains(newHead) && newHead != snake.last!
if crossesBoundary1 || crossesBoundary2 || bitesItself {
return -1
}
let nextFoodItem = foodIndex < food.count ? food[foodIndex] : nil
if foodIndex < food.count && nextFoodItem![0] == newHead.0 && nextFoodItem![1] == newHead.1 {
foodIndex += 1
} else {
let tail = snake.removeLast()
snakeSet.remove(tail)
}
snake.insert(newHead, at: 0)
snakeSet.insert(newHead)
return snake.count - 1
}
}1 340
#hard
Задача: 352. Data Stream as Disjoint Intervals
Дано поступление данных из последовательности неотрицательных целых чисел a1, a2, ..., an, необходимо обобщить увиденные числа в виде списка непересекающихся интервалов.
Реализуйте класс SummaryRanges:
SummaryRanges() Инициализирует объект с пустым потоком.
void addNum(int value) Добавляет целое число в поток.
int[][] getIntervals() Возвращает обобщение текущих чисел в потоке в виде списка непересекающихся интервалов [starti, endi]. Ответ должен быть отсортирован по starti.
Пример:
Input ["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"] [[], [1], [], [3], [], [7], [], [2], [], [6], []] Output [null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]👨💻 Алгоритм: 1⃣Инициализировать структуру данных TreeSet для хранения значений. 2⃣addNum(int value) Просто добавить value в values. Если эквивалент TreeSet вашего языка программирования позволяет дублировать значения, как например SortedList в Python, нужно также проверить, что value не существует в values, так как дубликаты нарушат алгоритм. 3⃣getIntervals Если values пуст, вернуть пустой массив. Создать пустой список интервалов. Установить left = right = -1. left представляет левую границу текущего интервала, а right представляет правую границу. Итерировать по values. На каждой итерации: Если left < 0, установить left = right = value. Иначе, если value = right + 1, установить right = value, так как мы можем продолжить текущий интервал. Иначе, мы не можем продолжить текущий интервал. Вставить [left, right] в intervals и установить left = right = value для начала нового интервала. Вставить [left, right] в intervals и вернуть intervals. 😎 Решение:
class SummaryRanges {
var values: Set<Int>
init() {
values = Set<Int>()
}
func addNum(_ value: Int) {
values.insert(value)
}
func getIntervals() -> [[Int]] {
if values.isEmpty {
return []
}
var intervals = [[Int]]()
var left = -1, right = -1
for value in values.sorted() {
if left < 0 {
left = value
right = value
} else if value == right + 1 {
right = value
} else {
intervals.append([left, right])
left = value
right = value
}
}
intervals.append([left, right])
return intervals
}
}1 340
Программист — лекарство от больных тимлидов, тупых багов и тех самых митов в 10 утра ☠️
Здесь собирают лучшие мемы про айтишников, чтобы спасти вашу психику от died'осов на работе.
Идеально зачиллить вечерком и скинуть друзьям: @progeri
1 340
#medium
Задача: 289. Game of Life
Согласно статье Википедии: "Игра Жизнь, также известная просто как Жизнь, — это клеточный автомат, созданный британским математиком Джоном Хортоном Конуэем в 1970 году."
Доска состоит из сетки клеток размером m x n, где каждая клетка имеет начальное состояние: живая (представляется числом 1) или мёртвая (представляется числом 0). Каждая клетка взаимодействует с восемью соседями (по горизонтали, вертикали и диагоналям) согласно следующим четырём правилам (взято из вышеупомянутой статьи Википедии):
Любая живая клетка с менее чем двумя живыми соседями умирает, как будто из-за недостатка населения.
Любая живая клетка с двумя или тремя живыми соседями остаётся живой до следующего поколения.
Любая живая клетка с более чем тремя живыми соседями умирает, как будто из-за перенаселения.
Любая мёртвая клетка с ровно тремя живыми соседями становится живой, как будто вследствие размножения.
Следующее состояние создаётся путем одновременного применения вышеупомянутых правил ко всем клеткам в текущем состоянии, где рождения и смерти происходят одновременно. Дано текущее состояние сетки m x n, верните следующее состояние.
Пример:
Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]] Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]👨💻 Алгоритм: 1⃣Итерация по клеткам доски: Пройдите через каждую клетку на доске. Для каждой клетки подсчитайте количество живых соседей, проверяя все восемь соседних клеток. 2⃣Применение правил: На основе количества живых соседей и текущего состояния клетки примените правила игры: Любая живая клетка с менее чем двумя живыми соседями умирает (становится -1). Любая живая клетка с двумя или тремя живыми соседями остаётся живой (без изменений). Любая живая клетка с более чем тремя живыми соседями умирает (становится -1). Любая мёртвая клетка с ровно тремя живыми соседями становится живой (становится 2). 3⃣Обновление доски: Пройдите через доску ещё раз и обновите состояния клеток: Если значение клетки больше 0, установите её в 1 (живая). Если значение клетки меньше или равно 0, установите её в 0 (мёртвая). 😎 Решение:
class Solution {
func gameOfLife(_ board: inout [[Int]]) {
let neighbors = [0, 1, -1]
let rows = board.count
let cols = board[0].count
for row in 0..<rows {
for col in 0..<cols {
var liveNeighbors = 0
for i in 0..<3 {
for j in 0..<3 {
if !(neighbors[i] == 0 && neighbors[j] == 0) {
let r = row + neighbors[i]
let c = col + neighbors[j]
if r >= 0 && r < rows && c >= 0 && c < cols && abs(board[r][c]) == 1 {
liveNeighbors += 1
}
}
}
}
if board[row][col] == 1 && (liveNeighbors < 2 || liveNeighbors > 3) {
board[row][col] = -1
}
if board[row][col] == 0 && liveNeighbors == 3 {
board[row][col] = 2
}
}
}
for row in 0..<rows {
for col in 0..<cols {
board[row][col] = board[row][col] > 0 ? 1 : 0
}
}
}
}1 340
#medium
Задача: 288. Unique Word Abbreviation
Сокращение слова — это объединение его первой буквы, количества символов между первой и последней буквой и последней буквы. Если слово состоит только из двух символов, то оно является сокращением само по себе.
Например:
dog --> d1g, потому что между первой буквой 'd' и последней буквой 'g' одна буква.
internationalization --> i18n, потому что между первой буквой 'i' и последней буквой 'n' 18 букв.
it --> it, потому что любое слово из двух символов является своим собственным сокращением.
Реализуйте класс ValidWordAbbr:
ValidWordAbbr(String[] dictionary) Инициализирует объект со словарем слов.
boolean isUnique(string word) Возвращает true, если выполняется одно из следующих условий (в противном случае возвращает false):
В словаре нет слова, сокращение которого равно сокращению слова word.
Для любого слова в словаре, сокращение которого равно сокращению слова word, это слово и word одинаковы.
Пример:
Input
["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"], ["cake"]]
Output
[null, false, true, false, true, true]
Explanation
ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // return false, dictionary word "deer" and word "dear" have the same abbreviation "d2r" but are not the same.
validWordAbbr.isUnique("cart"); // return true, no words in the dictionary have the abbreviation "c2t".
validWordAbbr.isUnique("cane"); // return false, dictionary word "cake" and word "cane" have the same abbreviation "c2e" but are not the same.
validWordAbbr.isUnique("make"); // return true, no words in the dictionary have the abbreviation "m2e".
validWordAbbr.isUnique("cake"); // return true, because "cake" is already in the dictionary and no other word in the dictionary has "c2e" abbreviation.class ValidWordAbbr {
private var abbrDict = [String: Bool]()
private var dict: Set<String>
init(_ dictionary: [String]) {
dict = Set(dictionary)
for word in dict {
let abbr = toAbbr(word)
abbrDict[abbr] = !(abbrDict[abbr] ?? false)
}
}
func isUnique(_ word: String) -> Bool {
let abbr = toAbbr(word)
let hasAbbr = abbrDict[abbr]
return hasAbbr == nil || (hasAbbr == true && dict.contains(word))
}
private func toAbbr(_ word: String) -> String {
let n = word.count
if n <= 2 {
return word
}
return "\(word.first!)\(n - 2)\(word.last!)"
}
}1 340
⚡️ Вся база знаний по IT в одном месте!
🧑💻 IT База — краткие разборы самого важного из мира IT. Сотни мастхев-ресурсов, каждый день новые материалы по работе и подготовке к собеседованиям. Подойдёт как новичкам, так и состоявшимся айтишникам;
🖥 Frontend База — всё для фронтенд разработчиков. Готовые решения для проектов, полезные курсы по JS/HTML/CSS, готовые роадмапы для комфортного освоения в профессии и дальнейшего развития;
👣 Backend База — самое важное для бэкендеров. Всё о работе с PHP, MySQL, MongoDB, Golang и Rust в одном месте, плюс полные курсы и лайфхаки для работы на каждый день;
🖥 База Знаний — склад полезных курсов и материалов, где легко найти что-то нужное по хэштегам. Если вам что-то интересно про IT, то оно уже лежит на Базе, проверяйте.
⏲ Успей подписаться, чтобы не потерять!
1 340
#easy
Задача: 459. Repeated Substring Pattern
Дана строка s, проверьте, может ли она быть построена путем взятия подстроки и добавления нескольких копий этой подстроки друг за другом.
Пример:
Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.👨💻 Алгоритм: 1⃣Создайте целочисленную переменную n, равную длине строки s. 2⃣Итерация по всем префиксным подстрокам длины i от 1 до n/2: Если i делит n, объявите пустую строку pattern. Используйте внутренний цикл, который выполняется n/i раз для конкатенации подстроки, сформированной из первых i символов строки s. Если pattern равен s, вернуть true. 3⃣Если нет подстроки, которую можно повторить для формирования s, вернуть false. 😎 Решение:
class Solution {
func repeatedSubstringPattern(_ s: String) -> Bool {
let n = s.count
for i in 1...n / 2 {
if n % i == 0 {
var pattern = ""
let substr = String(s.prefix(i))
for _ in 0..<n / i {
pattern += substr
}
if s == pattern {
return true
}
}
}
return false
}
}1 340
#medium
Задача: 287. Find the Duplicate Number
Дан массив целых чисел nums, содержащий n + 1 целых чисел, где каждое число находится в диапазоне [1, n] включительно.
В массиве есть только одно повторяющееся число, верните это повторяющееся число.
Вы должны решить задачу, не изменяя массив nums и используя только постоянное дополнительное пространство.
Пример:
Input: nums = [1,3,4,2,2] Output: 2👨💻 Алгоритм: 1⃣Определение дубликата: Итерируйте по массиву, оценивая каждый элемент (назовем его cur). Используйте абсолютное значение текущего элемента, чтобы получить индекс. Если элемент по индексу cur отрицательный, значит, мы уже встречали этот элемент ранее, и cur является дубликатом. Сохраните cur как дубликат и выйдите из цикла. Если элемент по индексу cur положительный, инвертируйте знак этого элемента, чтобы пометить его как встреченный, и перейдите к следующему элементу. 2⃣Восстановление массива: Пройдите по массиву и измените все отрицательные элементы обратно на положительные, чтобы восстановить исходное состояние массива. 3⃣Возврат результата: Верните найденный дубликат. 😎 Решение:
class Solution {
func findDuplicate(_ nums: [Int]) -> Int {
var nums = nums
var duplicate = -1
for i in 0..<nums.count {
let cur = abs(nums[i])
if nums[cur] < 0 {
duplicate = cur
break
}
nums[cur] *= -1
}
for i in 0..<nums.count {
nums[i] = abs(nums[i])
}
return duplicate
}
}1 340
#medium
Задача: 286. Walls and Gates
Вам дана сетка размером m x n, представляющая комнаты, инициализированные следующими значениями:
-1: Стена или препятствие.
0: Ворота.
INF: Бесконечность, обозначающая пустую комнату. Мы используем значение 2^31 - 1 = 2147483647 для представления INF, так как можно предположить, что расстояние до ворот меньше 2147483647.
Заполните каждую пустую комнату расстоянием до ближайших ворот. Если невозможно добраться до ворот, комната должна быть заполнена значением INF.
Пример:
Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]] Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]👨💻 Алгоритм: 1⃣Обход всех комнат: Пройдите через каждую клетку сетки, инициализируя очередь для BFS. Если клетка содержит ворота (0), добавьте её в очередь. 2⃣BFS для поиска кратчайшего пути: Используйте BFS для распространения из каждого ворот в соседние пустые комнаты. Обновите значение расстояния до ближайших ворот для каждой комнаты, которую вы посещаете, если это расстояние меньше текущего значения. 3⃣Проверка всех направлений: Для каждой клетки проверьте все возможные направления (вверх, вниз, влево, вправо) и добавляйте в очередь те, которые являются пустыми комнатами. 😎 Решение:
class Solution {
private let INF = 2147483647
private let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
func wallsAndGates(_ rooms: inout [[Int]]) {
let m = rooms.count
let n = rooms[0].count
var queue = [(Int, Int)]()
for i in 0..<m {
for j in 0..<n {
if rooms[i][j] == 0 {
queue.append((i, j))
}
}
}
while !queue.isEmpty {
let (x, y) = queue.removeFirst()
for (dx, dy) in directions {
let nx = x + dx
let ny = y + dy
if nx >= 0, ny >= 0, nx < m, ny < n, rooms[nx][ny] == INF {
rooms[nx][ny] = rooms[x][y] + 1
queue.append((nx, ny))
}
}
}
}
}1 340
#medium
Задача: 285. Inorder Successor in BST
Дан корень бинарного дерева поиска и узел p в нем. Верните преемника этого узла в порядке возрастания в бинарном дереве поиска (BST). Если у данного узла нет преемника в порядке возрастания в дереве, верните null.
Преемник узла p — это узел с наименьшим ключом, который больше p.val.
Пример:
Input: root = [2,1,3], p = 1 Output: 2 Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.👨💻 Алгоритм: 1⃣Определение переменных класса: Определите две переменные класса: previous и inorderSuccessorNode. Переменная previous будет использоваться при обработке второго случая, а inorderSuccessorNode будет содержать результат, который нужно вернуть. 2⃣Обработка двух случаев: В функции inorderSuccessor сначала проверьте, какой из двух случаев нужно обработать, проверяя наличие правого дочернего элемента. Правый дочерний элемент существует: - присвойте правый дочерний элемент узлу leftmost и итерируйтесь, пока не достигнете узла (leftmost), у которого нет левого дочернего элемента. Итерируйте, присваивая leftmost = leftmost.left, пока не получите левый узел в поддереве. Правый дочерний элемент не существует: - определите функцию inorderCase2 и передайте ей узел и узел p. - выполните простой обход в порядке возрастания: сначала рекурсируйте на левый дочерний элемент узла. - когда рекурсия вернется, проверьте, равна ли переменная класса previous узлу p. Если это так, значит p является предшественником узла, или, другими словами, узел является преемником узла p. Назначьте inorderSuccessorNode узлу и вернитесь из функции. - наконец, верните inorderSuccessorNode как результат. 3⃣Итерация и обновление: В функции inorderCase2 обновляйте previous текущим узлом и продолжайте рекурсировать на правый дочерний элемент. 😎 Решение:
class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) {
self.val = val
self.left = nil
self.right = nil
}
}
class Solution {
private var previous: TreeNode?
private var inorderSuccessorNode: TreeNode?
func inorderSuccessor(_ root: TreeNode?, _ p: TreeNode?) -> TreeNode? {
if let right = p?.right {
var leftmost = right
while leftmost.left != nil {
leftmost = leftmost.left!
}
self.inorderSuccessorNode = leftmost
} else {
self.inorderCase2(root, p)
}
return self.inorderSuccessorNode
}
private func inorderCase2(_ node: TreeNode?, _ p: TreeNode?) {
guard let node = node else { return }
inorderCase2(node.left, p)
if previous === p && inorderSuccessorNode == nil {
inorderSuccessorNode = node
return
}
previous = node
inorderCase2(node.right, p)
}
}1 340
#medium
Задача: 284. Peeking Iterator
Создайте итератор, который поддерживает операцию peek (просмотр следующего элемента) на существующем итераторе, помимо операций hasNext (проверка наличия следующего элемента) и next (получение следующего элемента).
Реализуйте класс PeekingIterator:
PeekingIterator(Iterator<int> nums): Инициализирует объект с заданным итератором целых чисел.
int next(): Возвращает следующий элемент в массиве и перемещает указатель на следующий элемент.
boolean hasNext(): Возвращает true, если в массиве еще есть элементы.
int peek(): Возвращает следующий элемент в массиве без перемещения указателя.
Пример:
Input ["PeekingIterator", "next", "peek", "next", "next", "hasNext"] [[[1, 2, 3]], [], [], [], [], []] Output [null, 1, 2, 2, 3, false] Explanation PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3] peekingIterator.next(); // return 1, the pointer moves to the next element [1,2,3]. peekingIterator.peek(); // return 2, the pointer does not move [1,2,3]. peekingIterator.next(); // return 2, the pointer moves to the next element [1,2,3] peekingIterator.next(); // return 3, the pointer moves to the next element [1,2,3] peekingIterator.hasNext(); // return False👨💻 Алгоритм: 1⃣Инициализация итератора: В конструкторе класса PeekingIterator инициализируйте итератор и проверьте, есть ли следующий элемент. Если есть, установите его как next, иначе установите next в null. 2⃣Операция peek: Метод peek возвращает значение next, не перемещая указатель итератора. 3⃣Операции next и hasNext: Метод next возвращает текущее значение next, обновляет next к следующему элементу в итераторе и перемещает указатель итератора. Если нет следующего элемента, бросает исключение NoSuchElementException. Метод hasNext возвращает true, если next не равно null, и false в противном случае. 😎 Решение:
class PeekingIterator {
private var iterator: IndexingIterator<[Int]>
private var nextElement: Int?
init(_ nums: [Int]) {
self.iterator = nums.makeIterator()
self.nextElement = self.iterator.next()
}
func next() -> Int {
let currentElement = nextElement
nextElement = iterator.next()
return currentElement!
}
func hasNext() -> Bool {
return nextElement != nil
}
func peek() -> Int {
return nextElement!
}
}1 340
#easy
Задача: 283. Move Zeroes
Дан целочисленный массив nums. Переместите все нули в конец массива, сохраняя относительный порядок ненулевых элементов.
Обратите внимание, что вы должны сделать это на месте, не создавая копию массива.
Пример:
Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0]👨💻 Алгоритм: 1⃣Инициализация указателей: Инициализируйте два указателя: lastNonZeroFoundAt для отслеживания позиции последнего ненулевого элемента и cur для итерации по массиву. 2⃣Итерация и обмен элементами: Итерируйтесь по массиву с помощью указателя cur. Если текущий элемент ненулевой, поменяйте его местами с элементом, на который указывает lastNonZeroFoundAt, и продвиньте указатель lastNonZeroFoundAt. 3⃣Завершение итерации: Повторяйте шаг 2 до конца массива. В итоге все нули будут перемещены в конец массива, сохраняя относительный порядок ненулевых элементов. 😎 Решение:
class Solution {
func moveZeroes(_ nums: inout [Int]) {
var lastNonZeroFoundAt = 0
for cur in 0..<nums.count {
if nums[cur] != 0 {
nums.swapAt(lastNonZeroFoundAt, cur)
lastNonZeroFoundAt += 1
}
}
}
}1 340
#hard
Задача: 282. Expression Add Operators
Дана строка num, содержащая только цифры, и целое число target. Верните все возможные варианты вставки бинарных операторов '+', '-', и/или '*' между цифрами строки num так, чтобы результирующее выражение вычислялось в значение target.
Учтите, что операнды в возвращаемых выражениях не должны содержать ведущих нулей.
Пример:
Input: num = "232", target = 8 Output: ["2*3+2","2+3*2"] Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.👨💻 Алгоритм: 1⃣Инициализация и рекурсивный вызов: Создайте класс Solution с полями для хранения результирующих выражений, строки цифр и целевого значения. Инициализируйте эти поля в методе addOperators и запустите рекурсивный метод для генерации всех возможных выражений. 2⃣Рекурсивная генерация выражений: В методе recurse на каждом шаге рассматривайте текущий индекс, предыдущий операнд, текущий операнд и текущее значение выражения. Обрабатывайте все возможные операторы: без оператора (расширение текущего операнда), сложение, вычитание и умножение. На каждом шаге обновляйте текущее значение и выражение. 3⃣Проверка и запись валидных выражений: Когда вся строка цифр обработана, проверяйте, соответствует ли итоговое значение целевому значению и нет ли остатков операндов. Если выражение валидное, записывайте его в список результатов. 😎 Решение:
class Solution {
var answer = [String]()
var digits = ""
var target: Int64 = 0
func recurse(_ index: Int, _ previousOperand: Int64, _ currentOperand: Int64, _ value: Int64, _ ops: inout [String]) {
if index == digits.count {
if value == target && currentOperand == 0 {
answer.append(ops.joined())
}
return
}
let nums = Array(digits)
let currentDigit = Int64(String(nums[index]))!
let currentOperand = currentOperand * 10 + currentDigit
let currentValRep = String(currentOperand)
if currentOperand > 0 {
recurse(index + 1, previousOperand, currentOperand, value, &ops)
}
ops.append("+")
ops.append(currentValRep)
recurse(index + 1, currentOperand, 0, value + currentOperand, &ops)
ops.removeLast(2)
if !ops.isEmpty {
ops.append("-")
ops.append(currentValRep)
recurse(index + 1, -currentOperand, 0, value - currentOperand, &ops)
ops.removeLast(2)
ops.append("*")
ops.append(currentValRep)
recurse(index + 1, currentOperand * previousOperand, 0, value - previousOperand + (currentOperand * previousOperand), &ops)
ops.removeLast(2)
}
}
func addOperators(_ num: String, _ target: Int) -> [String] {
if num.isEmpty {
return []
}
self.target = Int64(target)
self.digits = num
self.answer = []
var ops = [String]()
recurse(0, 0, 0, 0, &ops)
return answer
}
}1 340
#medium
Задача: 281. Zigzag Iterator
Даны два вектора целых чисел v1 и v2, реализуйте итератор, который возвращает их элементы поочередно.
Реализуйте класс ZigzagIterator:
ZigzagIterator(List<int> v1, List<int> v2) инициализирует объект с двумя векторами v1 и v2.
boolean hasNext() возвращает true, если в итераторе еще есть элементы, и false в противном случае.
int next() возвращает текущий элемент итератора и перемещает итератор к следующему элементу.
Пример:
Input: v1 = [1,2], v2 = [3,4,5,6] Output: [1,3,2,4,5,6] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,3,2,4,5,6].👨💻 Алгоритм: 1⃣Инициализация объекта: Создайте класс ZigzagIterator с двумя списками v1 и v2. Сохраните эти списки в структуре vectors. Инициализируйте очередь queue, содержащую пары индексов: индекс списка и индекс элемента в этом списке, если список не пуст. 2⃣Метод next: Удалите первую пару индексов из очереди. Извлеките элемент из соответствующего списка по указанным индексам. Если в текущем списке есть еще элементы, добавьте новую пару индексов (тот же список, следующий элемент) в конец очереди. Верните извлеченный элемент. 3⃣Метод hasNext: Проверьте, пуста ли очередь. Верните true, если в очереди есть элементы, и false в противном случае. 😎 Решение:
class ZigzagIterator {
private var vectors: [[Int]]
private var queue: [(Int, Int)] = []
init(_ v1: [Int], _ v2: [Int]) {
self.vectors = [v1, v2]
for (index, vec) in vectors.enumerated() {
if !vec.isEmpty {
queue.append((index, 0))
}
}
}
func next() -> Int {
let (vecIndex, elemIndex) = queue.removeFirst()
let nextElemIndex = elemIndex + 1
if nextElemIndex < vectors[vecIndex].count {
queue.append((vecIndex, nextElemIndex))
}
return vectors[vecIndex][elemIndex]
}
func hasNext() -> Bool {
return !queue.isEmpty
}
}1 340
#medium
Задача: 433. Minimum Genetic Mutation
Генетическая строка может быть представлена строкой длиной 8 символов, содержащей символы 'A', 'C', 'G' и 'T'.
Предположим, нам нужно исследовать мутацию от генетической строки startGene до генетической строки endGene, где одна мутация определяется как изменение одного символа в генетической строке.
Например, "AACCGGTT" --> "AACCGGTA" является одной мутацией.
Также существует генетический банк bank, который содержит все допустимые генетические мутации. Генетическая строка должна быть в банке, чтобы считаться допустимой.
Даны две генетические строки startGene и endGene и генетический банк bank, верните минимальное количество мутаций, необходимых для мутации от startGene до endGene. Если такой мутации не существует, верните -1.
Обратите внимание, что начальная строка считается допустимой, поэтому она может не быть включена в банк.
Пример:
Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"] Output: 1👨💻 Алгоритм: 1⃣Инициализируйте очередь и множество seen. Очередь будет использоваться для выполнения BFS, а множество seen будет использоваться для предотвращения повторного посещения одного и того же узла. Изначально в очередь и множество должен быть помещен startGene. 2⃣Выполняйте BFS. На каждом узле, если node == endGene, верните количество шагов, пройденных до этого момента. В противном случае, итеративно заменяйте каждый символ в строке на один из "A", "C", "G", "T" для нахождения соседей. Для каждого соседа, если он еще не был посещен и находится в bank, добавьте его в очередь и в множество seen. 3⃣Если BFS завершился и endGene не был найден, задача невыполнима. Верните -1. 😎 Решение:
class Solution {
func minMutation(_ start: String, _ end: String, _ bank: [String]) -> Int {
var queue: [String] = [start]
var seen: Set<String> = [start]
var steps = 0
while !queue.isEmpty {
for _ in 0..<queue.count {
let node = queue.removeFirst()
if node == end {
return steps
}
for c in "ACGT" {
for i in node.indices {
var neighbor = Array(node)
neighbor[i] = c
let neighborStr = String(neighbor)
if !seen.contains(neighborStr) && bank.contains(neighborStr) {
queue.append(neighborStr)
seen.insert(neighborStr)
}
}
}
}
steps += 1
}
return -1
}
}1 340
#medium
Задача: 395. Longest Substring with At Least K Repeating Characters
Дана строка s и целое число k, верните длину самой длинной подстроки строки s, такая что частота каждого символа в этой подстроке больше или равна k.
Если такой подстроки не существует, верните 0.
Пример:
Input: s = "aaabb", k = 3 Output: 3 Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.👨💻 Алгоритм: 1⃣Генерируйте подстроки из строки s, начиная с индекса start и заканчивая индексом end. Используйте массив countMap для хранения частоты каждого символа в подстроке. 2⃣Метод isValid использует countMap для проверки, что каждый символ в подстроке встречается как минимум k раз. Если условие выполняется, текущая подстрока считается допустимой. 3⃣Отслеживайте максимальную длину допустимой подстроки, обновляя её, когда найдена более длинная подстрока, удовлетворяющая условиям. В конце возвращайте длину самой длинной подстроки. 😎 Решение:
class Solution {
func longestSubstring(_ s: String, _ k: Int) -> Int {
let n = s.count
if n == 0 || k > n {
return 0
}
var countMap = [Int](repeating: 0, count: 26)
var result = 0
let sArray = Array(s)
for start in 0..<n {
countMap = [Int](repeating: 0, count: 26)
for end in start..<n {
countMap[Int(sArray[end].asciiValue! - Character("a").asciiValue!)] += 1
if isValid(countMap, k) {
result = max(result, end - start + 1)
}
}
}
return result
}
func isValid(_ countMap: [Int], _ k: Int) -> Bool {
var countLetters = 0, countAtLeastK = 0
for count in countMap {
if count > 0 { countLetters += 1 }
if count >= k { countAtLeastK += 1 }
}
return countAtLeastK == countLetters
}
}1 340
#medium
Задача: 280. Wiggle Sort
Дан целочисленный массив nums, упорядочьте его так, чтобы nums[0] <= nums[1] >= nums[2] <= nums[3]....
Вы можете считать, что входной массив всегда имеет допустимый ответ.
Пример:
Input: nums = [3,5,2,1,6,4] Output: [3,5,1,6,2,4] Explanation: [1,6,2,5,3,4] is also accepted.👨💻 Алгоритм: 1⃣Итерируйтесь по каждому элементу с индексом i в массиве nums, начиная с 0 и до nums.length - 2, так как последний элемент не имеет следующего элемента для обмена. 2⃣Проверьте, является ли i четным и nums[i] > nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1]. 3⃣Проверьте, является ли i нечетным и nums[i] < nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1]. 😎 Решение:
class Solution {
func swap(_ nums: inout [Int], _ i: Int, _ j: Int) {
let temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
func wiggleSort(_ nums: inout [Int]) {
for i in 0..<nums.count - 1 {
if (i % 2 == 0 && nums[i] > nums[i + 1]) || (i % 2 == 1 && nums[i] < nums[i + 1]) {
swap(&nums, i, i + 1)
}
}
}
}