Приветствуем вас! В данном канале будут публиковаться разборы задач с собеседований с сайта LeetCode.
🎉25
Наибольший общий префикс
Частота встречи задач на собеседованиях за последние шесть месяцев:
Facebook* — 21, Amazon — 16, Apple — 14, Adobe — 11, Google — 9, Microsoft — 6, Uber — 6.
Условие задачи:
Напишите функцию для поиска самого длинного общего префикса у массива строк. Если общего префикса нет, верните пустую строку.
Требуемая сложность:
O(S), S — сумма всех символов во всех строках.
Примеры:
Ввод:
Решение задачи
* — организация, признанная экстремистской на территории РФ.
Частота встречи задач на собеседованиях за последние шесть месяцев:
Facebook* — 21, Amazon — 16, Apple — 14, Adobe — 11, Google — 9, Microsoft — 6, Uber — 6.
Условие задачи:
Напишите функцию для поиска самого длинного общего префикса у массива строк. Если общего префикса нет, верните пустую строку.
Требуемая сложность:
O(S), S — сумма всех символов во всех строках.
Примеры:
Ввод:
strs = ["flower","flow","flight"]
Вывод: "fl"
Ввод: strs = ["dog","racecar","car"]
Вывод: ""
Среди введенных строк нет общего префикса.Решение задачи
* — организация, признанная экстремистской на территории РФ.
👍30
Суммы чисел
Частота встречи задач на собеседованиях за последние шесть месяцев:
Amazon — 107, Adobe — 52, Apple — 44, Microsoft — 43, Google — 40.
Условие задачи:
Даётся массив целых чисел и целочисленное целевое значение, требуется вернуть индексы двух чисел так, чтобы в сумме они составляли целевое значение. Каждый случай имеет ровно одно решение, и нельзя использовать один и тот же элемент дважды. Ответ можно вернуть в любом порядке.
Примеры:
Ввод:
Ввод:
Частота встречи задач на собеседованиях за последние шесть месяцев:
Amazon — 107, Adobe — 52, Apple — 44, Microsoft — 43, Google — 40.
Условие задачи:
Даётся массив целых чисел и целочисленное целевое значение, требуется вернуть индексы двух чисел так, чтобы в сумме они составляли целевое значение. Каждый случай имеет ровно одно решение, и нельзя использовать один и тот же элемент дважды. Ответ можно вернуть в любом порядке.
Примеры:
Ввод:
nums = [2,7,11,15], target = 9
Вывод: [0,1]
Поскольку nums [0] + nums [1] == 9, мы возвращаем [0, 1].Ввод:
nums = [3,2,4], target = 6
Вывод: [1,2]
Ввод: nums = [3,3], target = 6
Вывод: [0,1]
Решение задачи👍31
Длина последнего слова в строке
Частота встречи задач на собеседованиях за последние шесть месяцев:
Amazon — 3, Microsoft — 2, Google — 3.
Условие задачи:
Дана строка s, состоящая из слов и пробелов. Требуется вернуть длину последнего слова в строке.
Слово — это максимальная подстрока, состоящая только из символов, не содержащих пробелов.
Требуемая сложность:
O(N), N - длина строки.
Примеры:
Ввод:
Ввод:
Решение задачи
Частота встречи задач на собеседованиях за последние шесть месяцев:
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.Решение задачи
👍16🤔11👎1
Квадратный корень
Частота встречи задач на собеседованиях за последние шесть месяцев:
Amazon — 8, LinkedIn — 7, Adobe — 6, Microsoft — 3, Apple — 3, Google — 2.
Условие задачи:
Рассматриваем неотрицательное целое число x. Требуется вычислить и вернуть квадратный корень из x. Поскольку возвращаемый тип является целым числом, десятичные цифры усекаются, и возвращается только целочисленная часть результата.
Примеры:
Ввод:
Решение задачи
Частота встречи задач на собеседованиях за последние шесть месяцев:
Amazon — 8, LinkedIn — 7, Adobe — 6, Microsoft — 3, Apple — 3, Google — 2.
Условие задачи:
Рассматриваем неотрицательное целое число x. Требуется вычислить и вернуть квадратный корень из x. Поскольку возвращаемый тип является целым числом, десятичные цифры усекаются, и возвращается только целочисленная часть результата.
Примеры:
Ввод:
x = 4
Вывод: 2
Ввод: x = 8
Вывод: 2
Объяснение: Квадратный корень из 8 равен 2,82842..., и поскольку десятичная часть усечена, возвращается 2.Решение задачи
👍44
Максимальный подмассив
Частота встречи задач на собеседованиях за последние шесть месяцев:
LinledIn — 42, Amazon — 34, Apple — 20, Microsoft — 18, Google — 16, Adobe —16
Условие задачи:
Дан целочисленный массив nums. Требуется найти такой подмассив, который будет содержать максимальную сумму элементов внутри себя и вернуть сумму этих элементов.
Примеры:
Ввод:
Ввод:
Частота встречи задач на собеседованиях за последние шесть месяцев:
LinledIn — 42, Amazon — 34, Apple — 20, Microsoft — 18, Google — 16, Adobe —16
Условие задачи:
Дан целочисленный массив nums. Требуется найти такой подмассив, который будет содержать максимальную сумму элементов внутри себя и вернуть сумму этих элементов.
Примеры:
Ввод:
nums = [-2, 1, 4, -1, 2, -3]
Вывод: 6
Объяснение: [1, 4, -1, 2] будет иметь максимальную сумму, равную 6Ввод:
nums = [4]
Вывод: 4
Решение задачи👍59🤔10🎉4
Самая длинная подстрока без повторяющихся символов
Частота встречи задач на собеседованиях за последние шесть месяцев:
Amazon — 60, Microsoft — 34, Bloomberg — 19.
Для заданной строки s найдите длину самой длинной подстроки без повторяющихся символов.
Примеры:
Ввод: s = "abcabcbb"
Вывод: 3
Объяснение: Ответ "abc" длиной 3.
Ввод: s = "bbbbb"
Вывод: 1
Объяснение: Ответ "b" длиной 1.
Ввод: s = "pwwkew"
Вывод: 3
Объяснение: Ответ "wke" длиной 3.
Обратите внимание, что ответ должен быть подстрокой, «pwke» — это подпоследовательность, а не подстрока.
Решение задачи
Частота встречи задач на собеседованиях за последние шесть месяцев:
Amazon — 60, Microsoft — 34, Bloomberg — 19.
Для заданной строки s найдите длину самой длинной подстроки без повторяющихся символов.
Примеры:
Ввод: s = "abcabcbb"
Вывод: 3
Объяснение: Ответ "abc" длиной 3.
Ввод: s = "bbbbb"
Вывод: 1
Объяснение: Ответ "b" длиной 1.
Ввод: s = "pwwkew"
Вывод: 3
Объяснение: Ответ "wke" длиной 3.
Обратите внимание, что ответ должен быть подстрокой, «pwke» — это подпоследовательность, а не подстрока.
Решение задачи
👍47👎5
Медиана двух отсортированных массивов
Частота встречи задач на собеседованиях за последние шесть месяцев:
Amazon — 32, Apple — 23, Google — 19, Goldman Sachs — 18, Adobe — 16.
Имея два отсортированных массива nums1 и nums2 размера m и n соответственно, вернуть медиану этих массивов. Общая сложность времени выполнения должна быть O(log (m+n)).
Примеры:
Ввод: nums1 = [1,3], nums2 = [2]
Вывод: 2.00000
Объяснение: объединенный массив = [1,2,3], а медиана 2.
Ввод: nums1 = [1,2], nums2 = [3,4]
Вывод: 2.50000
Объяснение: объединенный массив = [1,2,3,4], а медиана (2 + 3) / 2 = 2.5.
Решение задачи на Java
Частота встречи задач на собеседованиях за последние шесть месяцев:
Amazon — 32, Apple — 23, Google — 19, Goldman Sachs — 18, Adobe — 16.
Имея два отсортированных массива nums1 и nums2 размера m и n соответственно, вернуть медиану этих массивов. Общая сложность времени выполнения должна быть O(log (m+n)).
Примеры:
Ввод: nums1 = [1,3], nums2 = [2]
Вывод: 2.00000
Объяснение: объединенный массив = [1,2,3], а медиана 2.
Ввод: nums1 = [1,2], nums2 = [3,4]
Вывод: 2.50000
Объяснение: объединенный массив = [1,2,3,4], а медиана (2 + 3) / 2 = 2.5.
Решение задачи на Java
👍15👎7🤔1
Весовая сумма списка
Частота встречи задач на собеседованиях за последние шесть месяцев:
Facebook* — 88, LinkedIn — 36, Amazon — 5
Условие задачи:
Вам предоставлен вложенный список целых чисел NestedList. Каждый элемент представляет собой либо целое число, либо список, элементами которого также могут быть целые числа или другие списки.
Глубина целого числа - это количество списков, внутри которых оно находится. Требуется вывести сумму каждого целого числа в вложенном списке, умноженную на его глубину.
Примеры:
Ввод:
Ввод:
* — организация, признанная экстремистской на территории РФ.
Частота встречи задач на собеседованиях за последние шесть месяцев:
Facebook* — 88, LinkedIn — 36, Amazon — 5
Условие задачи:
Вам предоставлен вложенный список целых чисел NestedList. Каждый элемент представляет собой либо целое число, либо список, элементами которого также могут быть целые числа или другие списки.
Глубина целого числа - это количество списков, внутри которых оно находится. Требуется вывести сумму каждого целого числа в вложенном списке, умноженную на его глубину.
Примеры:
Ввод:
nestedList = [[1,1],2,[1,1]]
Вывод: 10
Объяснение: четыре единицы имеют глубину 2, одна двойка at имеет глубину 1. 1*2 + 1*2 + 2*1 + 1*2 + 1*2 = 10.Ввод:
nestedList = [0]
Вывод: 0
Решение задачи* — организация, признанная экстремистской на территории РФ.
👍37❤2👎1🎉1
Прикреплять ли картинку с кодом-решением к посту или оставлять ее только в решении по ссылке?
Anonymous Poll
61%
Прикреплять
39%
Оставлять по ссылке
👍10👎1
Поиск мажоритарного элемента
Частота встречи задач на собеседованиях за последние шесть месяцев:
Amazon — 10, Google — 8, Apple — 8, Microsoft — 6, Bloomberg — 6, Adobe — 6
Условие задачи:
Дан массив nums размера n. Требуется вернуть мажоритарный элемент.
Мажоритарный элемент - это элемент, который появляется более n / 2 раз. Вы можете быть уверены, что мажоритарный элемент всегда существует в массиве.
Примеры:
Ввод:
Частота встречи задач на собеседованиях за последние шесть месяцев:
Amazon — 10, Google — 8, Apple — 8, Microsoft — 6, Bloomberg — 6, Adobe — 6
Условие задачи:
Дан массив nums размера n. Требуется вернуть мажоритарный элемент.
Мажоритарный элемент - это элемент, который появляется более n / 2 раз. Вы можете быть уверены, что мажоритарный элемент всегда существует в массиве.
Примеры:
Ввод:
nums = [4,2,4]
Вывод: 4
Ввод: nums = [8, 8, 6, 6, 6, 8, 8]
Вывод: 8
Решение задачи👍34
Число-палиндром
Условие задачи:
Получив целое число x, вернуть true, если x является палиндромом. Целое число является палиндромом, если оно читается одинаково как в прямом, так и в обратном порядке.
Примеры:
Ввод: х = 121
Вывод: true
Объяснение: 121 читается как 121 слева направо и справа налево.
Ввод: х = -121
Вывод: false
Объяснение: Слева направо это -121. Справа налево получается 121-. Следовательно, это не палиндром.
Ввод: х = 10
Вывод: false
Решение задачи
Условие задачи:
Получив целое число x, вернуть true, если x является палиндромом. Целое число является палиндромом, если оно читается одинаково как в прямом, так и в обратном порядке.
Примеры:
Ввод: х = 121
Вывод: true
Объяснение: 121 читается как 121 слева направо и справа налево.
Ввод: х = -121
Вывод: false
Объяснение: Слева направо это -121. Справа налево получается 121-. Следовательно, это не палиндром.
Ввод: х = 10
Вывод: false
Решение задачи
👍28🤔3🎉1
Единственный элемент
Условие задачи:
Дан непустой массив целых чисел nums, каждый элемент появляется дважды, за исключением одного. Найдите этот самый единственный элемент.
Вы должны реализовать решение с линейной сложностью и использовать только постоянное дополнительное пространство.
Пример:
Ввод:
Условие задачи:
Дан непустой массив целых чисел nums, каждый элемент появляется дважды, за исключением одного. Найдите этот самый единственный элемент.
Вы должны реализовать решение с линейной сложностью и использовать только постоянное дополнительное пространство.
Пример:
Ввод:
nums = [8, 8, 6]
Вывод: 6
Ввод: nums = [4, 1, 2, 1, 2]
Вывод: 4
Решение задачи👍25
Контейнер с наибольшим количеством воды
Вам дан целочисленный массив height длины n. Нарисовано n вертикальных линий, две конечные точки i-й линии равны (i, 0) и (i, height[i]). Найдите две линии, которые вместе с осью абсцисс образуют контейнер, содержащий наибольшее количество воды. Верните максимальное количество воды, которое может храниться в контейнере. Обратите внимание, что вы не можете наклонять контейнер.
Пример 1 (картинка):
Ввод: height = [1,8,6,2,5,4,8,3,7]
Вывод: 49
Объяснение: Вышеуказанные вертикальные линии представлены массивом [1,8,6,2,5,4,8,3,7]. В этом случае максимальная площадь воды (синяя секция), которую может содержать контейнер, составляет 49.
Пример 2:
Ввод: height = [1,1]
Вывод: 1
Решение задачи
Вам дан целочисленный массив height длины n. Нарисовано n вертикальных линий, две конечные точки i-й линии равны (i, 0) и (i, height[i]). Найдите две линии, которые вместе с осью абсцисс образуют контейнер, содержащий наибольшее количество воды. Верните максимальное количество воды, которое может храниться в контейнере. Обратите внимание, что вы не можете наклонять контейнер.
Пример 1 (картинка):
Ввод: height = [1,8,6,2,5,4,8,3,7]
Вывод: 49
Объяснение: Вышеуказанные вертикальные линии представлены массивом [1,8,6,2,5,4,8,3,7]. В этом случае максимальная площадь воды (синяя секция), которую может содержать контейнер, составляет 49.
Пример 2:
Ввод: height = [1,1]
Вывод: 1
Решение задачи
👍33
Добавление строк
Условие задачи:
Даны два неотрицательных целых числа, str1 и str2, представленные в виде строки. Требуется вернуть сумму str1 и str2 в виде строки.
Вы должны решить эту задачу, не используя какую-либо встроенную библиотеку для обработки больших целых чисел (например, BigInteger). Вы также не должны преобразовывать входные данные непосредственно в целые числа.
Примеры:
Ввод:
Условие задачи:
Даны два неотрицательных целых числа, str1 и str2, представленные в виде строки. Требуется вернуть сумму str1 и str2 в виде строки.
Вы должны решить эту задачу, не используя какую-либо встроенную библиотеку для обработки больших целых чисел (например, BigInteger). Вы также не должны преобразовывать входные данные непосредственно в целые числа.
Примеры:
Ввод:
str1 = "11", str2 = "123"
Вывод: 134
Ввод: str1 = "456", str2 = "77"
Вывод: 533
Решение задачи👍22
3Sum Closest
Имея целочисленный массив
Ввод: nums = [-1,2,1,-4], target = 1 Вывод: 2
Сумма, ближайшая к цели, равна 2. (-1 + 2 + 1 = 2).
Ввод: nums = [0,0,0], target = 1
Вывод: 0
Решение задачи
Имея целочисленный массив
nums длины n и целочисленную target, найдите три целых числа в nums, сумма которых ближе всего к target. Верните сумму трех целых чисел. Каждый вход будет иметь ровно одно решение.Ввод: nums = [-1,2,1,-4], target = 1 Вывод: 2
Сумма, ближайшая к цели, равна 2. (-1 + 2 + 1 = 2).
Ввод: nums = [0,0,0], target = 1
Вывод: 0
Решение задачи
👍17