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

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

Условие задачи:
Дана строка s. Требуется вернуть все ее палиндромные перестановки (без дубликатов).

Вы можете вернуть ответ в любом порядке. Если s не имеет палиндромной перестановки, вернуть пустой список.

Пример:
Ввод: s = "aabb"
Вывод: ["abba","baab"]

Ввод: s = "abc"
Вывод: []

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

​Валидный судоку

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

Условие:
Определите, валидна ли доска судоку 9 x 9. Только заполненные ячейки должны быть проверены в соответствии со следующими правилами:
1. Каждая строка должна содержать цифры 1–9 без повторения.
2. Каждый столбец должен содержать цифры 1–9 без повторения.
3. Каждый из девяти подблоков сетки 3 x 3 должен содержать цифры 1–9 без повторения.

Доска судоку (частично заполненная) может быть валидной, но не обязательно решаемой. Только заполненные ячейки должны быть проверены в соответствии с указанными правилами.

Примеры:
Пример 1 (на картинке):
Ввод: board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Вывод: true

Пример 2:
Ввод: board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Вывод: false
Объяснение: то же, что и в примере 1, за исключением того, что цифра 5 в верхнем левом углу изменена на 8. Поскольку в верхнем левом подблоке 3x3 есть две восьмерки, это неверно.

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

Объединение интервалов

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

Условие задачи:
Дан массив интервалов, где intervals[i] = [start(i), end(i)]. Требуется объединить все перекрывающиеся интервалы и вернуть массив непересекающихся интервалов, которые охватывают все интервалы во входных данных.

Пример:
Ввод: intervals = [[1,3],[2,6],[8,10],[15,18]]
Вывод: [[1,6],[8,10],[15,18]]
Объяснение: Поскольку интервалы [1,3] и [2,6] перекрываются, объединим их в [1,6].

Ввод: intervals = [[1,4],[4,5]]
Вывод: [[1,5]]

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

Размещение предложения на экране

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

Условие задачи:
Дан экран rows x cols и предложение, представленное в виде списка строк. Требуется вернуть количество раз, которое данное предложение может быть размещено на экране.

Порядок слов в предложении должен оставаться неизменным, а слово не может быть разбито на две строки. Один пробел должен разделять два последовательных слова в строке.

Пример:
Ввод: sentence = ["hello","world"], rows = 2, cols = 8
Вывод: 1
Объяснение:
hello---
world---
Символ «-» означает пустое место на экране.

Ввод: sentence = ["a", "bcd", "e"], rows = 3, cols = 6
Вывод: 2

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

Уникальные тропы

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

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

Робот может двигаться лишь вправо и вниз.

Пример:

Ввод: m = 3, n = 7
Вывод: 28.

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

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

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

Условие задачи: дан целочисленный массив 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).

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