LeetCode 75

Вопросы:

1. Merge Strings Alternately (Смешивание строк попеременно) Описание: Даны две строки word1 и word2. Необходимо создать новую строку, объединяя символы этих строк по очереди – сначала символ из word1, затем из word2, затем следующий из word1 и так далее. Если одна из строк закончилась, допишите оставшиеся символы другой строки в конец результирующей строки.

2. Greatest Common Divisor of Strings (Наибольший общий делитель строк) Описание: Даны две строки str1 и str2. Требуется найти наибольшую строку X, такую что str1 и str2 можно получить посредством конкатенации X несколько раз. Если такой строки не существует, вернуть пустую строку.

3. Kids With the Greatest Number of Candies (Дети с наибольшим количеством конфет) Описание: Даны массив чисел, где каждое число означает количество конфет у ребенка, и число extraCandies, обозначающее дополнительные конфеты. Для каждого ребенка необходимо определить, сможет ли он, добавив extraCandies к своему количеству, иметь не меньше конфет, чем у любого другого ребенка.

4. Can Place Flowers (Можно ли посадить цветы) Описание: Дано целочисленный массив, представляющий ряд клумбы, где 0 означает свободное место, а 1 – место, занятое цветком. Между двумя цветами нельзя сажать новые. Определите, можно ли посадить еще n цветков в клумбе, соблюдая правило (без изменения размещённых уже цветков).

5. Reverse Vowels of a String (Разворот гласных в строке) Описание: Дана строка s. Нужно развернуть только порядок гласных букв в строке, а все остальные символы оставить на своих местах. Гласными считаются символы «a», «e», «i», «o», «u» (и их заглавные варианты).

6. Reverse Words in a String (Разворот слов в строке) Описание: Дана строка s, состоящая из слов, разделённых пробелами. Необходимо вернуть строку, в которой слова располагаются в обратном порядке, при этом удалив лишние пробелы в начале, конце и между словами.

7. Product of Array Except Self (Произведение массива, кроме себя) Описание: Дано целочисленный массив nums. Для каждого элемента массива найдите произведение всех остальных элементов, то есть для индекса i нужно вычислить произведение всех элементов кроме nums[i]. Решение должно быть реализовано без использования операции деления.

8. Increasing Triplet Subsequence (Возрастающая подпоследовательность из трёх чисел) Описание: Дано целочисленный массив nums. Определите, существует ли подпоследовательность из трёх элементов, удовлетворяющая условию i < j < k и nums[i] < nums[j] < nums[k]. Если такая подпоследовательность существует – вернуть true, иначе false.

9. String Compression (Сжатие строки) Описание: Дан массив символов chars. Необходимо модифицировать массив, сжимая последовательности повторяющихся символов: если символ повторяется, запишите сначала сам символ, а затем количество его повторений в виде цифр. Результат сжатия должен размещаться в исходном массиве.

10. Move Zeroes (Перемещение нулей) Описание: Дан целочисленный массив nums. Требуется переместить все нулевые элементы в конец массива, сохранив относительный порядок ненулевых элементов. Операция должна быть выполнена на месте без копирования массива.

11. Is Subsequence (Является ли строка подпоследовательностью) Описание: Даны две строки s и t. Необходимо определить, является ли строка s подпоследовательностью строки t, то есть можно ли получить s путём удаления некоторых (или нуля) символов из t без изменения порядка оставшихся символов.

12. Container With Most Water (Контейнер с наибольшей площадью воды) Описание: Даны массив целых чисел heights, где каждый элемент представляет высоту вертикальной линии, размещённой на координате x. Найдите две линии, которые, вместе с осью x, образуют контейнер, содержащий максимальное количество воды. Объём воды ограничен расстоянием между линиями и меньшей из их высот.

13. Max Number of K-Sum Pairs (Максимальное количество пар с суммой k) Описание: Даны целочисленный массив nums и число k. Найдите максимальное количество пар элементов, таких что сумма двух чисел равна k. Каждый элемент можно использовать не более одного раза.

14. Maximum Average Subarray I (Подмассив с максимальным средним значением I) Описание: Даны массив целых чисел nums и целое число k. Найдите подмассив длины k, имеющий максимальное среднее значение, и верните это значение.

15. Maximum Number of Vowels in a Substring of Given Length (Максимальное число гласных в подстроке заданной длины) Описание: Дана строка s и целое число k. Найдите подстроку длины k, в которой содержится наибольшее количество гласных букв. Верните это количество.

16. Max Consecutive Ones III (Максимальное количество последовательных единиц после изменений) Описание: Дан бинарный массив nums и целое число k. Вам разрешается заменить не более k нулей на единицы. Найдите максимальную длину подмассива, состоящего только из единиц, которую можно получить после до k замен.

17. Longest Subarray of 1's After Deleting One Element (Самый длинный подмассив единиц после удаления одного элемента) Описание: Дан бинарный массив nums. Удалите ровно один элемент из массива, чтобы получить максимально возможную длину последовательной цепочки единиц, и верните эту длину.

18. Find the Highest Altitude (Нахождение наивысшей точки маршрута) Описание: Дан массив чисел gain, где каждый элемент обозначает изменение высоты относительно предыдущей точки. Начав с высоты 0, вычислите и верните наивысшую точку, которую достигает маршрут.

19. Find Pivot Index (Поиск опорного индекса) Описание: Дан массив целых чисел nums. Определите индекс, для которого сумма элементов слева от него равна сумме элементов справа. Если такой индекс существует, вернуть его; если нет – вернуть -1.

20. Find the Difference of Two Arrays (Нахождение разницы двух массивов) Описание: Даны два массива чисел. Верните список из двух массивов: первый содержит элементы, которые присутствуют в первом массиве, но отсутствуют во втором, а второй – элементы, которые есть во втором, но отсутствуют в первом.

21. Unique Number of Occurrences (Уникальное количество вхождений) Описание: Дано целочисленный массив arr. Определите, для каждого уникального числа, сколько раз оно встречается в массиве, и проверьте, что все эти количества являются различными. Если да – вернуть true, иначе false.

22. Determine if Two Strings Are Close (Определение, являются ли две строки похожими) Описание: Даны две строки word1 и word2. Строки называются «похожими», если можно преобразовать первую во вторую, выполняя операцию: поменять местами все вхождения двух различных символов. При этом нельзя добавлять или удалять символы – должен совпадать именно набор символов и их частоты (считая, что можно переставлять количества). Верните true, если строки похожи, иначе false.

23. Equal Row and Column Pairs (Равное количество одинаковых строк и столбцов) Описание: Дана квадратная матрица arr. Для каждой строки найдите количество столбцов, которые идентичны ей (сравнение идёт по порядку элементов). Верните общее число пар, где строка и столбец совпадают.

24. Removing Stars From a String (Удаление звездочек из строки) Описание: Дана строка s, содержащая строчные буквы английского алфавита и символы «*». Каждая звездочка удаляет ближайшую слева букву, которая ещё не была удалена. После применения всех операций удаления верните результирующую строку.

25. Asteroid Collision (Столкновение астероидов) Описание: Дано целочисленный массив asteroids, где абсолютное значение числа представляет размер астероида, а знак – направление движения (положительный – вправо, отрицательный – влево). Когда два астероида встречаются, меньший по размеру разрушется; если они равны – оба уничтожаются. Определите, какие астероиды останутся после всех столкновений, и верните их в порядке их появления.

26. Decode String (Декодирование строки) Описание: Дана закодированная строка, в которой встречаются числовые множители и вложенные квадратные скобки, например "3[a2[c]]". Необходимо декодировать строку, повторяя содержимое скобок соответствующее число раз, и вернуть получившийся результат.

27. Number of Recent Calls (Количество недавних вызовов) Описание: Реализуйте класс RecentCounter, который отслеживает количество вызовов метода ping(t) за последние 3000 миллисекунд. Каждый вызов метода ping(t) возвращает число запросов, совершённых за интервал [t-3000, t].

28. Dota2 Senate (Сенат Dota2) Описание: Дана строка senate, состоящая из символов 'R' и 'D', где каждый символ представляет депутата двух фракций. В каждом раунде один из депутатов может аннулировать голос другого. Процесс повторяется, пока одна из фракций не окажется полностью исключённой. Определите, какая фракция победит.

29. Delete the Middle Node of a Linked List (Удалить средний узел связанного списка) Описание: Дан односвязный список. Необходимо удалить средний узел списка. Если список содержит четное число узлов, удалить следует правый из двух центральных. Вернуть изменённый список.

30. Odd Even Linked List (Перестановка узлов: сначала нечетные, потом четные) Описание: Дана голова односвязного списка. Переставьте узлы так, чтобы сначала шли все узлы, находящиеся на нечетных позициях, а затем – на четных, сохранив относительный порядок среди нечетных и четных узлов отдельно.

31. Reverse Linked List (Разворот связанного списка) Описание: Дана голова односвязного списка. Необходимо изменить ссылки таким образом, чтобы список был развернут – то есть последний узел стал первым, а первый – последним.

32. Maximum Twin Sum of a Linked List (Максимальная сумма пар-свой пар в связанном списке) Описание: Дан односвязный список с четным числом узлов. Разделите список на пары, где первая пара состоит из первого и последнего узла, вторая – из второго и предпоследнего, и так далее. Вычислите сумму каждой пары и верните максимальную из полученных сумм.

33. Maximum Depth of Binary Tree (Максимальная глубина бинарного дерева) Описание: Дано бинарное дерево. Найдите его максимальную глубину – то есть максимальное количество узлов от корня до самого глубокого листа.

34. Leaf-Similar Trees (Деревья с похожими листьями) Описание: Даны два бинарных дерева. Два дерева считаются похожими, если последовательности значений их листовых узлов (при обходе слева направо) идентичны. Определите, являются ли два дерева листоподобными.

35. Count Good Nodes in Binary Tree (Подсчёт «хороших» узлов в бинарном дереве) Описание: В бинарном дереве узел называется «хорошим», если на пути от корня до этого узла не встречается узел с значением большим, чем текущее. Подсчитайте общее число «хороших» узлов.

36. Path Sum III (Пути с заданной суммой в бинарном дереве) Описание: Дано бинарное дерево и целое число targetSum. Найдите количество путей в дереве, сумма значений узлов которых равна targetSum. Путь может начинаться и заканчиваться в любом узле, но должен идти вниз (от родителя к ребёнку).

37. Longest ZigZag Path in a Binary Tree (Самый длинный зигзагообразный путь в бинарном дереве) Описание: В бинарном дереве найдите самый длинный путь, который чередует направления – после хода влево следующий ход должен быть вправо, и наоборот. Верните длину такого пути.

38. Lowest Common Ancestor of a Binary Tree (Наименьший общий предок в бинарном дереве) Описание: Дано бинарное дерево и два узла в нём. Найдите их наименьшего общего предка – то есть самый глубокий узел, который является предком обоих заданных узлов.

39. Binary Tree Right Side View (Вид справа от бинарного дерева) Описание: Дано бинарное дерево. Верните список значений узлов, которые видны при взгляде на дерево справа, то есть самый правый узел на каждом уровне дерева.

40. Maximum Level Sum of a Binary Tree (Максимальная сумма на уровне бинарного дерева) Описание: Дано бинарное дерево. Найдите уровень, сумма значений узлов которого максимальна, и верните эту сумму. Если таких уровней несколько, верните сумму на уровне, который находится ближе к корню.

41. Search in a Binary Search Tree (Поиск в бинарном дереве поиска) Описание: Дано бинарное дерево поиска (BST) и целое значение val. Найдите узел, значение которого равно val, и верните ссылку на поддерево, для которого этот узел является корнем; если такого узла нет – вернуть null.

42. Delete Node in a BST (Удаление узла в бинарном дереве поиска) Описание: Дано бинарное дерево поиска (BST) и значение key. Удалите узел с данным значением, сохранив свойства BST, и верните корень изменённого дерева.

43. Keys and Rooms (Ключи и комнаты) Описание: Даны n комнат, пронумерованных от 0 до n-1. Каждая комната содержит набор ключей, открывающих некоторые другие комнаты. Начав с комнаты 0, определите, можно ли посетить все комнаты, используя ключи из посещённых.

44. Number of Provinces (Количество провинций) Описание: Дана матрица isConnected, где isConnected[i][j] = 1 означает, что город i напрямую соединён с городом j. Провинция – это группа городов, непосредственно или косвенно соединённых друг с другом. Найдите и верните количество провинций.

45. Reorder Routes to Make All Paths Lead to the City Zero (Переориентация дорог так, чтобы все пути вели в город 0) Описание: Даны n городов и массив дорог, каждая дорога – направленное ребро между двумя городами. Требуется переориентировать минимальное число дорог так, чтобы из любого города можно было добраться до города 0. Верните это минимальное число переориентаций.

46. Evaluate Division (Вычисление деления) Описание: Заданы уравнения в виде a / b = k, где a и b – строки, а k – вещественное число. Затем даны запросы вида x / y. Необходимо для каждого запроса вычислить значение данного отношения, используя известные уравнения, или вернуть -1, если отношение невозможно вывести.

47. Nearest Exit from Entrance in Maze (Ближайший выход из лабиринта) Описание: Дана матрица, представляющая лабиринт, где '+' – стены, а '.' – свободные проходы. Дана стартовая позиция (entrance). Найдите кратчайший путь от входа до ближайшего выхода, который находится на границе лабиринта. Если выхода нет – верните -1.

48. Rotting Oranges (Гнилые апельсины) Описание: Дана матрица, где 0 означает пустую клетку, 1 – свежий апельсин, 2 – гнилой апельсин. Каждый ход (за одну минуту) каждый гнилой апельсин заражает соседние (по 4 направлениям) свежие апельсины. Определите, через сколько минут все свежие апельсины сгниют, или верните -1, если это невозможно.

49. Kth Largest Element in an Array (K-е по величине число в массиве) Описание: Даны массив чисел nums и целое число k. Найдите k-е по величине число в массиве (т.е. k-е максимальное значение).

50. Smallest Number in Infinite Set (Наименьшее число в бесконечном наборе) Описание: Реализуйте класс, который управляет набором положительных целых чисел. Класс должен поддерживать методы popSmallest(), возвращающий наименьшее число из набора (и удаляющий его), и addBack(num), добавляющий число обратно в набор, если оно там отсутствует.

51. Maximum Subsequence Score (Максимальный балл подпоследовательности) Описание: Даны два массива чисел и целое число k. Необходимо выбрать подпоследовательность индексов длины k таким образом, чтобы оценка, вычисляемая как (сумма элементов из первого массива, соответствующих выбранным индексам) умноженная на минимальное значение из второго массива среди выбранных, была максимальной. Верните этот максимум.

52. Total Cost to Hire K Workers (Общая стоимость найма k работников) Описание: Даны массив затрат, каждый элемент которого представляет стоимость найма работника, и целое число k. При выборе работника можно выбирать кандидата с начала или конца очереди (с определёнными ограничениями). Необходимо вычислить минимальную общую стоимость, по которой можно нанять k работников.

53. Guess Number Higher or Lower (Угадай число: больше или меньше) Описание: Задача – угадать загаданный компьютерном числом в диапазоне от 1 до n. Для проверки вашего предположения доступна функция guess(num), которая возвращает 0, если вы угадали, -1, если загаданное число меньше, и 1, если загаданное число больше вашего предположения. Найдите загаданное число, минимизируя количество вызовов guess.

54. Successful Pairs of Spells and Potions (Успешные пары заклинаний и зелий) Описание: Даны два массива чисел spells и potions, а также целое число success. Для каждого заклинания в spells определите, с каким количеством зелий из массива potions произведение будет не меньше success. Верните массив, где i-й элемент – количество зелий, удовлетворяющих условию для i-го заклинания.

55. Find Peak Element (Нахождение пикового элемента) Описание: Дан массив чисел nums. Найдите индекс одного из пиковых элементов, то есть такой индекс i, для которого выполняется условие: nums[i] > nums[i-1] (если i > 0) и nums[i] > nums[i+1] (если i < n-1). Гарантируется, что такой элемент существует.

56. Koko Eating Bananas (Коко ест бананы) Описание: Даны кучки бананов (массив piles) и целое число h, обозначающее количество часов. Коко может съедать бананы со скоростью x бананов в час, где за час она съедает одну кучу (если в куче меньше x, то съедает их все). Определите минимальную скорость x, с которой Коко сможет съесть все бананы за h часов.

57. Letter Combinations of a Phone Number (Комбинации букв по номеру телефона) Описание: Дана строка digits, состоящая из цифр от 2 до 9. В соответствии со стандартной раскладкой телефона каждая цифра соответствует набору букв. Верните все возможные комбинации букв, которые можно получить, сопоставляя каждой цифре её буквы.

58. Combination Sum III (Сумма комбинаций III) Описание: Найдите все возможные комбинации из k чисел (от 1 до 9), сумма которых равна n. Каждое число может быть использовано не более одного раза, и наборы комбинаций не должны повторяться.

59. N-th Tribonacci Number (N-е число Трибоначчи) Описание: Последовательность Трибоначчи определяется следующим образом: T₀ = 0, T₁ = 1, T₂ = 1, а для n ≥ 3: Tₙ = Tₙ₋₁ + Tₙ₋₂ + Tₙ₋₃. Найдите n-е число Трибоначчи.

60. Min Cost Climbing Stairs (Минимальная стоимость подъёма по ступенькам) Описание: Дано массив cost, где cost[i] – стоимость i-й ступеньки. Вы можете начать с 0-й или 1-й ступеньки и двигаться шагом 1 или 2. Найдите минимальную сумму затрат, необходимую для достижения вершины (после последней ступеньки).

61. House Robber (Ограбление домов) Описание: Дано целочисленный массив nums, где каждый элемент представляет сумму денег в отдельном доме. Жилой вор не может грабить два соседних дома. Определите максимальную сумму денег, которую можно собрать, грабя дома по заданному правилу.

62. Domino and Tromino Tiling (Покрытие доски домино и тромино) Описание: Дана доска размером 2×n. Требуется определить число способов заполнить её плитками домино (размерами 2×1) и тромино (размерами, образующими L-образную фигуру) так, чтобы не было пробелов и перекрытий.

63. Unique Paths (Уникальные пути) Описание: Даны два целых числа m и n, обозначающие размеры прямоугольной сетки. Вы должны двигаться от верхнего левого угла до нижнего правого, разрешены только шаги вправо и вниз. Определите, сколько существует уникальных путей.

64. Longest Common Subsequence (Наибольшая общая подпоследовательность) Описание: Даны две строки text1 и text2. Найдите длину их наибольшей общей подпоследовательности – последовательности символов, которая встречается в обоих строках в сохранённом порядке, но не обязательно подряд.

65. Best Time to Buy and Sell Stock with Transaction Fee (Лучшее время для покупки и продажи акций с комиссией) Описание: Дано целочисленный массив prices, где prices[i] – цена акции в i-й день, и целое число fee, представляющее комиссию за проведение сделки. Найдите максимальную прибыль, которую можно получить при неограниченном числе сделок, с условием уплаты комиссии за каждую продажу.

66. Edit Distance (Расстояние редактирования) Описание: Даны две строки word1 и word2. Найдите минимальное количество операций (вставка, удаление, замена символа), необходимых для преобразования word1 в word2.

67. Counting Bits (Подсчёт единиц в двоичном представлении) Описание: Дано целое число n. Для каждого числа i от 0 до n вычислите количество единиц в его двоичном представлении и верните массив таких подсчётов.

68. Single Number (Единственный не дублирующийся элемент) Описание: Дан целочисленный массив nums, где каждый элемент встречается дважды, кроме одного, который встречается один раз. Найдите этот уникальный элемент.

69. Minimum Flips to Make a OR b Equal to c (Минимальное число переворотов битов, чтобы a OR b давало c) Описание: Даны три целых числа a, b и c. Рассматривая их двоичные представления, найдите минимальное количество битовых переворотов в a и b, чтобы побитовое OR этих чисел стало равно c.

70. Implement Trie (Prefix Tree) (Реализация префиксного дерева Trie) Описание: Реализуйте структуру данных Trie (префиксное дерево) с поддержкой следующих операций: insert(word) – добавление слова, search(word) – поиск полного слова, startsWith(prefix) – проверка, существует ли в дереве слово с данным префиксом.

71. Search Suggestions System (Система предложений при поиске) Описание: Даны массив строк products и строка searchWord. По мере ввода символов из searchWord верните список списков, где для каждого префикса searchWord возвращаются до 3 лексикографически наименьших слова из products, начинающихся с этого префикса.

72. Non-overlapping Intervals (Несмещающиеся интервалы) Описание: Дан массив интервалов, где каждый интервал определяется началом и концом. Определите минимальное число интервалов, которые нужно удалить, чтобы оставшиеся интервалы не пересекались.

73. Minimum Number of Arrows to Burst Balloons (Минимальное число стрел для поражения шаров) Описание: Даны координаты воздушных шаров в виде массива интервалов, где каждый интервал [x_start, x_end] представляет положение шара по оси x. Стрела, выпущенная вертикально, может пробить все шары, пересекающиеся с её траекторией. Найдите минимальное количество стрел, достаточное для того, чтобы поразить все шары.

74. Daily Temperatures (Ежедневные температуры) Описание: Дан массив целых чисел temperatures, где каждое число представляет температуру в определённый день. Для каждого дня найдите, через сколько дней температура станет выше, чем в данный день. Если такого дня не существует – верните 0 для этого дня.

75. Online Stock Span (Онлайн подсчёт «спана» акций) Описание: Реализуйте класс StockSpanner, который для каждого нового входящего значения цены акции (метод next(price)) возвращает количество последовательных дней (включая текущий), в течение которых цена акции была меньше или равна текущей цене.