Наиболее эффективное поднятие по ступеням

Сложность задачи: Лёгкая.

Условие задачи: дан целочисленный массив cost, где cost[i] - вес i-ой ступеньки. Находясь на ступени, можно шагнуть либо на следующую либо через одну.

Начинать путь можно либо со ступени с индексом 0 либо с индексом 1.

Задача - пройти всю лестницу с минумальной суммой весов ступеней.

Пример:

Ввод: cost = [10,15,20]
Вывод: 15

Ввод: cost = [1,100,1,1,1,100,1,1,100,1]
Вывод: 6

Решение задачи

Топ k наиболее часто встречающихся элементов

Сложность: Средняя

Условие задачи: дан целочисленный массив и целое число k. Необходимо вернуть k часто встречающихся элементов. Порядок чисел в ответе не имеет значения.

Гарантируется, что ответ уникальный. То есть несколько элементов не могут встречаться одинаковое количество раз.

Пример:

Ввод: nums = [1,1,1,2,2,3], k = 2
Вывод: [1,2]

Ввод: nums = [1], k = 1
Вывод: [1]

Решение задачи

Является ли строка палиндромом

Сложность: Лёгкая

Условие: палиндромом является фраза, которая после перевода в нижний регистр всех символов, а также удаления всех знаков препинания, читается одинаково как слева направо, так и справа налево.

Задача - вернуть true, если строка палиндром, false - в противном случае.

Пример:

Ввод: s = "A man, a plan, a canal: Panama"
Вывод: true
Объяснение: "amanaplanacanalpanama" является палиндромом.

Ввод: s = "race a car"
Вывод: false
Объяснение: "raceacar" не является палиндромом.

Ввод: s = " "
Вывод: true
Объяснение: s - пустая строка "" после удаления всех знаков препинания и пробелов.
Так как пустая строка читается одинаково в обоих направлениях, то она является палиндромом.

Решение задачи

Сумма двух чисел II (в отсортированном массиве)

Сложность: Средняя.

Условие задачи: дан одномерный целочисленный массив, элементы которого расположены в порядке неубывания.

Требуется вернуть индексы (начиная с единицы) двух элементов, сумма которых будет равна целевому значению.

Гарантируется, что ответ уникальный, и при этом каждый элемент массива можно использовать однокрастно.

Решение должно быть O(1) по памяти.

Пример:

Ввод: numbers = [2,7,11,15], target = 9
Вывод: [1,2]
Объяснение: Сумма 2 и 7 дает необходимое значение - 9, но так как нам нужны индексы в ответе мы выводим 1 и 2.

Ввод: numbers = [2,3,4], target = 6
Вывод: [1,3]

Решение задачи

Нахождение опорного элемента

Сложность: Лёгкая

Условие задачи: дан массив, состоящий из целых чисел. Необходимо вернуть опорный элемент массива.

Опорным называется такое число массива, относительно которого сумма элементов находящихся слева, равна сумме элементов, расположенных справа.

Необходимо вернуть индекс самого левого опороного элемента, в случае отсутствия такового - вернуть -1.

Пример:

Ввод: nums = [1,7,3,6,5,6]
Вывод: 3

Объяснение:
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

Ввод: nums = [1,2,3]
Вывод: -1

Ввод: nums = [2,1,-1]
Вывод: 0

Объяснение:
Опорный элемент - 0.
Left sum = 0 (нет элементов левее индекса 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

Решение задачи

Изоморфизм строки

Сложность: Лёгкая

Условие задачи: даны две строки s и t. Просят проверить их на изоморфность.

Две строки считаются изоморфными, если одной букве из одной строки ставится в соответствие уникальная буква из другой строки. Соответствие должно быть уникальным.

Пример:

Ввод: s = "egg", t = "add"
Вывод: true

Объяснение: "e" <--> "t", "g" <--> "d"

Ввод: s = "foo", t = "bar"
Вывод: false

Объяснение: "f" <--> "b", "o" <--> "a", "o" <--> "r". Два символа из второй строки соответствуют одному символу из первой строки.

Решение задачи

Является ли строка подпоследовательностью

Сложность: Лёгкая.

Условие задачи: даны две строки s и t, верните true, если s - подпоследовательность строки t, false - в ином случае.

Подпоследовательностью является строка, полученная из исходной строки путем удаления символов без изменения поряжка следования символов.

Пример:

Ввод: s = "abc", t = "ahbgdc"
Вывод: true

Ввод: s = "axc", t = "ahbgdc"
Вывод: false

Решение задачи

Определение количества островов

Сложность: Средняя

Условие задачи: дан двумерный массив размера m x n. "1" отвечает за сушу, "0" - за океан. Требуется опеределить количество островов, расположенных на карте.

Островом считается территория, образованная из "1", расположенных сверху, справа, снизу и слева относительно друг друга.

Пример:

Ввод:
grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Вывод: 1

Ввод: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Вывод: 3

Решение задачи

Перевернуть порядок следования элементов связного списка

Сложность: Лёгкая

Условие задачи: дан указатель на начало связного списка, надо вернуть его элементы в обратном порядке.

Пример:

Ввод: head = [1,2,3,4,5]
Вывод: [5,4,3,2,1]

Решение задачи

Поиск длины строки с наибольшим количеством одинаковых символов

Сложность: Средняя

Условие задачи: дана строка s и число k. Предлагается выбрать в строке любой символ и заменить его на наиболее повторяющийся. Таких замен можно делать не более, чем k-раз.

Трубуется найти максимальную длину строки с одинаковым символом. Символом может быть любая из букв латинского алфавита, находящаяся в верхнем регистре.

Пример:

Ввод: s = "ABAB", k = 2
Вывод: 4

Объяснение: заменить можно две 'A' на два символа 'B'. Или же наоборот.

Ввод: s = "AABABBA", k = 1
Вывод: 4

Решение задачи

Нахождение всех анаграмм в строке

Сложность: Средняя

Условие задачи: даны две строки s и p, надо вернуть все индексы стартовых позиций, с которых начинаются анаграммы внутри строки s.

Анаграмма - строка, составленная путём перестановок букв из какого либо базового набора.

Пример:

Ввод: s = "cbaebabacd", p = "abc"
Вывод: [0,6]

Объяснение:
Подстрока "cba" начинается с индекса 0, она является анаграммой строки "abc".
Подстрока "bac" начинается с индекса 6, она является анаграммой строки "abc".

Ввод: s = "abab", p = "ab"
Вывод: [0,1,2]

Решение задачи

Топ k-наиболее часто встречающихся слов

Сложность: Средняя

Условие задачи: дан массив строк, необходимо вернуть k-наиболее частых элементов.

При одинаковом количестве появлений нескольких слов, необходимо отсортировать данные слова в лексикографическом порядке.

Пример:

Ввод:
words = ["i","love","leetcode","i","love","coding"],
k = 2
Вывод: ["i","love"]

Объяснение: "i" и "love" два наиболее частых слова.
Но заметим, что "i" идет первее, чем "love" как раз-таки из-за алфавитного порядка.

Ввод: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Вывод: ["the","is","sunny","day"]

Решение задачи

Сместить массив

Сложность: Средняя

Условие задачи: дан массив, необходимо сместить массив на k-элементов, где k - неотрицательное число.

Пример:

Ввод: nums = [1,2,3,4,5,6,7], k = 3
Вывод: [5,6,7,1,2,3,4]

Ввод: nums = [-1,-100,3,99], k = 2
Вывод: [3,99,-1,-100]

Решение задачи

Сдвиг нулей

Сложность: Лёгкая

Условие задачи: дан массив, необходимо переместить все нулевые элементы к концу массива, к его правой границе.

Решение должно изменять исходный массив, не используя дополнительной памяти.

Пример:

Ввод: nums = [0,1,0,3,12]
Вывод: [1,3,12,0,0]

Ввод: nums = [0]
Вывод: [0]

Решение задачи

Swap Adjacent in LR String

Сложность задачи: Средняя

Условие задачи:
В строке, состоящей из символов «L», «R» и «X», например «RXXLRXRXL», перемещение состоит либо в замене одного вхождения «XL» на «LX», либо в замене одного вхождения «RX» на "ХР". Учитывая начальную строку и конец конечной строки, вернуть True тогда и только тогда, когда существует последовательность ходов для преобразования одной строки в другую.

Пример:
Ввод: start = "RXXLRXRXL", end = "XRLXXRRLX"
Вывод: true
Объяснение: Мы можем преобразовать начало в конец, выполнив следующие шаги:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

Ввод: start = "X", end = "L"
Вывод: false

Решение задачи

Самая длинная подстрока без повторений

Сложность: Средняя.

Условие задачи: дана строка надо найти самую длинную подстроку, в которой не будет повторений.

Пример:

Ввод: s = "abcabcbb"
Вывод: 3
Объяснение: ответом является подстрока "abc", длина которой равна 3.

Ввод: s = "bbbbb"
Вывод: 1

Ввод: s = "pwwkew"
Вывод: 3
Объяснение: ответ - "wke" (длина = 3).

Решение задачи

Бинарный поиск

Сложность: Лёгкая

Условие задачи: дан целочисленный массив, отсортированный в порядке возрастания. Необходимо найти индекс target-значения. Если целевое значение отсутствует - нужно вернуть -1.

Пример:

Ввод: nums = [-1,0,3,5,9,12], target = 9
Вывод: 4

Ввод: nums = [-1,0,3,5,9,12], target = 2
Вывод: -1

Решение задачи

Пересечение двух массивов II

Сложность: Лёгкая

Условие задачи: даны два целочисленных массива, необходимо вернуть все элементы, встречающиеся в каждом из них. Ответ может быть возвращен в любом порядке.

Пример:

Ввод: nums1 = [1,2,2,1], nums2 = [2,2]
Вывод: [2,2]

Ввод: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Вывод: [4,9] или [9,4]

Решение задачи

Изменение порядка следования элементов связного списка

Сложность: Средняя

Условие задачи : дан связный список:
L0 → L1 → … → Ln - 1 → Ln.

Надо переопределить порядок следования элементов на следующий:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

Пример:

Ввод: head = [1,2,3,4]
Вывод: [1,4,2,3]

Ввод: [1,2,3,4,5]
Вывод: [1,5,2,4,3]

Решение задачи

Середина связного списка

Сложность: Лёгкая

Условие задачи: дан связный список. Необходимо вернуть указатель на серединный элемент исходного списка.

Пример:

Ввод: head = [1,2,3,4,5]
Вывод: [3,4,5]
Объяснение: серединный узел - узел 3.

Ввод: head = [1,2,3,4,5,6]
Вывод: [4,5,6]
Объяснение: лист имеет два серединных значения: 3 и 4, мы возвращаем второй.

Решение задачи

Реализация класса MinStack

Сложность: Средняя

Условиеи задачи: разработай пользовательский класс MinStack(), который будет иметь следующие методы:

- void push(int val), который добавляет элемент в стак;
- void pop(), удаляющий верхний элемент стака;
- int top(), возвращающий верхний элемент на стаке;
- int getMin(), возвращающий минимальный элемент в стаке на момент вызова метода.

Требуется реализовать все методы таким образом чтобы каждый из них имел временную сложность O(1).

Пример:

Ввод:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Вывод:
[null,null,null,null,-3,null,0,-2]

Объяснение:

MinStack minStack = новый объект класса MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2

Решение задачи