Считалка

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

Условие задачи: последовательность "Посчитай и скажи" - это последовательность строк цифр, определяемая рекурсивной формулой:

посчитайте и скажите(1) = "1"
countAndSay(n) - это способ, которым вы бы "сказали" строку цифр из countAndSay(n-1), которая затем преобразуется в другую строку цифр.
Чтобы определить, как вы "произносите" строку цифр, разделите ее на минимальное количество подстрок таким образом, чтобы каждая подстрока содержала ровно одну уникальную цифру. Затем для каждой подстроки произнесите количество цифр, затем произнесите цифру. Наконец, объедините каждую указанную цифру.

Например, высказывание и преобразование для цифровой строки "3322251" (*во вложении)

Дается положительное целое число n, верните n-й член последовательности "посчитай и скажи".

Пример:

Ввод: n = 1
Вывод: "1"

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

Международная азбука Морзе

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

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

"a" соответствует ".-",
"b" соответствует "-...",
"c" соответствует "-.-." и так далее.
Для удобства ниже приведена полная таблица для 26 букв английского алфавита:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
Дан массив строк words, где каждое слово может быть записано как объединение азбуки Морзе каждой буквы.

Верните количество различных преобразований среди всех слов, которые у нас есть.

Пример:

Ввод: words = ["gin","zen","gig","msg"]
Вывод: 2

Объяснение:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."

Ввод: words = ["a"]
Вывод: 1

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

Обход по времени

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

Условие задачи: предоставляется сеть из n узлов, помеченных от 1 до n. Вам также дается время, список времени прохождения в соответствии с указаниями ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время, необходимое сигналу для прохождения от источника до цели.

Мы отправим сигнал с заданного узла k. Необходимо вернуть минимальное время, необходимое для приема сигнала всеми n узлами. Если все n узлов не могут принять сигнал, верните значение -1.

Пример:

Ввод: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Вывод: 2

Ввод: times = [[1,2,1]], n = 2, k = 1
Вывод: 1

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

Найти ближайший узел к заданным двум узлам

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

Условие задачи: дается ориентированный граф из n узлов, пронумерованных от 0 до n - 1, где каждый узел имеет не более одного исходящего ребра.

Граф представлен заданными 0-индексированными ребрами массива размера n, указывающими на то, что существует направленное ребро от узла i к ребрам узла[i]. Если нет исходящего ребра из i, то ребра[i] == -1.

Вам также даны два целых числа node1 и node2.

Возвращает индекс узла, до которого можно добраться как из узла 1, так и из узла 2, таким образом, чтобы максимальное расстояние от узла 1 до этого узла и от узла 2 до этого узла было сведено к минимуму. Если ответов несколько, верните узел с наименьшим индексом, а если возможного ответа не существует, верните -1.

Обратите внимание, что ребра могут содержать циклы.

Пример:

Ввод: edges = [2,2,3,-1], node1 = 0, node2 = 1
Вывод: 2

Ввод: edges = [1,2,-1], node1 = 0, node2 = 2
Вывод: 2

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

Разделение на палиндромы

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

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

Пример:

Ввод: s = "aab"
Вывод: [["a","a","b"],["aa","b"]]
Объяснение:

Ввод: s = "a"
Вывод: s = "a"

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

Минимальная сумма индексов двух списков

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

Условие задачи: дается два массива строк list1 и list2, найдите общие строки с наименьшей суммой индексов.

Общая строка - это строка, которая появилась как в list1, так и в list2.

Общая строка с наименьшей суммой индексов - это общая строка, такая, что если она появилась в list1[i] и list2[j], то i + j должно быть минимальным значением среди всех других общих строк.

Возвращает все общие строки с наименьшей суммой индексов. Верните ответ в любом порядке.

Пример:

Ввод: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Вывод: ["Shogun"]

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

Перестановки II

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

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

Пример:

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

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

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

Длина последнего слова в строке

Частота встречи задач на собеседованиях за последние шесть месяцев:
Amazon — 3, Microsoft — 2, Google — 3.

Условие задачи:
Дана строка s, состоящая из слов и пробелов. Требуется вернуть длину последнего слова в строке.

Слово — это максимальная подстрока, состоящая только из символов, не содержащих пробелов.

Требуемая сложность:
O(N), N - длина строки.

Примеры:
Ввод: s = "Hello World"
Вывод: 5
Объяснение: Последнее слово строки s "World" имеет длину 5.

Ввод: s = " fly me to the moon "
Вывод: 4
Объяснение: Последнее слово строки s "moon" имеет длину 4.

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

Одно редактирование

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

Условие задачи:
Даны две строки s и t. Требуется вернуть true, если обе они находятся на расстоянии редактирования друг от друга, в противном случае вернуть false.

Говорят, что строка s находится на расстоянии редактирования от строки t, если вы можете:
• Вставить ровно один символ в s, чтобы получить t.
• Удалить ровно один символ из s, чтобы получить t.
• Заменить ровно один символ s другим символом, чтобы получить t.

Пример:
Ввод: s = "ab", t = "acb"
Вывод: true
Объяснение: Мы можем вставить 'c' в s, чтобы получить t.

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

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

Длина последнего слова в строке

Частота встречи задач на собеседованиях за последние шесть месяцев:
Amazon — 3, Microsoft — 2, Google — 3.

Условие задачи:
Дана строка s, состоящая из слов и пробелов. Требуется вернуть длину последнего слова в строке.

Слово — это максимальная подстрока, состоящая только из символов, не содержащих пробелов.

Требуемая сложность:
O(N), N - длина строки.

Примеры:
Ввод: s = "Hello World"
Вывод: 5
Объяснение: Последнее слово строки s "World" имеет длину 5.

Ввод: s = " fly me to the moon "
Вывод: 4
Объяснение: Последнее слово строки s "moon" имеет длину 4.

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

Минимальное большее

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

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

Необходимо вернуть наименьший символ в буквах, который лексикографически больше целевого. Если такого символа не существует, верните первый символ буквами.

Пример:

Ввод: letters = ["c","f","j"], target = "a"
Вывод: "c"

Ввод: letters = ["c","f","j"], target = "c"
Вывод: "f"

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

Среднее по уровню

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

Условие задачи: дается корень двоичного дерева, верните среднее значение узлов на каждом уровне в виде массива. Будут приняты ответы в пределах 10-5 от фактического ответа.

Пример:

Ввод: root = [3,9,20,null,null,15,7]
Вывод: [3.00000,14.50000,11.00000]

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

Неубывающий подмассив

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

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

Пример:

Ввод: nums = [4,6,7,7]
Вывод: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

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

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

Строка из дерева

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

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

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

Пример:

Ввод: root = [1,2,3,4]
Вывод: "1(2(4))(3)"

Ввод: root = [1,2,3,null,4]
Вывод: "1(2()(4))(3)"

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

Количество точек на прямой

Сложность: Тяжёлая

Условие задачи: дается массив точек, где точки [i] = [xi, yi] представляют точку на плоскости X-Y, верните максимальное количество точек, которые лежат на одной прямой.

Пример:

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

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

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

Мороженое

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

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

В магазине есть n батончиков мороженого. Вам дается массив costs длины n, где costs[i] - это цена i-го батончика мороженого в монетах. У мальчика изначально есть монеты, которые можно потратить, и он хочет купить как можно больше батончиков мороженого.

Верните максимальное количество батончиков мороженого, которые мальчик может купить за монеты coins.

Мальчик может купить батончики мороженого в любом порядке.

Пример:

Ввод: costs = [1,3,2,4,1], coins = 7
Вывод: 4
Объяснение:1 + 3 + 2 + 1 = 7.

Ввод: costs = [10,6,8,7,7,8], coins = 5
Вывод: 0

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

Сортировка столбцов

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

Условие задачи: предоставляется массив из n строк strs, все одинаковой длины.

Строки могут быть расположены таким образом, чтобы на каждой строке было по одной, образуя сетку. Например, strs = ["abc", "bce", "ce"] может быть организован как:

abc
bce
cae

Вам нужно удалить столбцы, которые не отсортированы лексикографически. В приведенном выше примере (с индексом 0) столбцы 0 ('a', 'b', 'c') и 2 ('c', 'e', 'e') отсортированы, в то время как столбец 1 ('b', 'c', 'a') не отсортирован., таким образом, вы бы удалили столбец 1.

Верните количество столбцов, которые нужно удалять.

Пример:

Ввод: strs = ["cba","daf","ghi"]
Вывод: 1

Ввод: strs = ["a","b"]
Вывод: 0

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

Сбор урожая яблок

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

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

Ребра неориентированного дерева заданы в массиве ребер, где ребра[i] = [ai, bi] означают, что существует ребро, соединяющее вершины ai и bi. Кроме того, существует логический массив has Apple, где has Apple[i] = true означает, что в вершине i есть яблоко; в противном случае в ней нет никакого яблока.

Пример:

Ввод: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
Вывод: 8


Ввод: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]
Вывод: 6

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

Минимальная разница между узлами бинарного дерева

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

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

Пример:

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

Ввод: root = [1,0,48,null,null,12,49]
Вывод: 1

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

Усадка клумбы

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

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

Учитывая целочисленный массив flowerbed, содержащий 0 и 1, где 0 означает пустой, а 1 означает непустой, и целое число n, верните, если на клумбе можно посадить n новых цветов, не нарушая правила отсутствия соседних цветов.

Пример:

Ввод: flowerbed = [1,0,0,0,1], n = 1
Вывод: true

Ввод: flowerbed = [1,0,0,0,1], n = 2
Вывод: false

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