Приложение 📱 и решение технических вопросов интервью 🔡 Структура 🏛️ и вопросы алгоритма ❓на Javascript.
Введение
Это было путешествие по третьей серии структур данных и алгоритмов. Мы выполнили все или почти все основные требования для решения реальных вопросов алгоритмов.
Прочитали мои предыдущие статьи? Давайте достаточно поговорим о кодировании.
Сегодня мы собираемся решать настоящие вопросы технического собеседования в Javascript из вопросов по коду.
1. Использование алгоритма сортировки слиянием: массив сортировки слиянием
Вам даны два массива целых чисел nums1 и nums2, отсортированные в неубывающем порядке, и два целых числа m и n, представляющие количество элементов в nums1. strong> и nums2 соответственно.
Объедините nums1 и nums2 в один массив, отсортированный в неубывающем порядке.
Окончательный отсортированный массив не должен возвращаться функцией, а должен храниться внутри массива nums1. Для этого nums1 имеет длину m + n, где первые элементы m обозначают элементы, которые должны быть объединены, а последние n > установлены в 0 и должны игнорироваться. nums2 имеет длину n.
Ограничения:
- nums1.length == м + п
- nums2.length == n
- 0 <= m, n <= 200
- 1 <= m + n <= 200
- -109 ‹= число1[i], число2[j] ‹= 109
Следовать за:
Можете ли вы придумать алгоритм, работающий за время O(m + n)?
Прочтите этот вопрос правильно и попытайтесь решить его. Пытаясь написать псевдоалгоритм, прежде чем решать его с помощью кода, поскольку это самая важная часть решения вопросов DSA.
Айит… Давайте перейдем к решению.
Для решения данной проблемы мы можем использовать алгоритм сортировки слиянием. Поскольку входные массивы nums1 и nums2 уже отсортированы, мы можем воспользоваться этим фактом, чтобы эффективно объединить их в один отсортированный массив. Вот решение JavaScript:
function merge(nums1, m, nums2, n) {
let i = m - 1; // Index of last element in nums1
let j = n - 1; // Index of last element in nums2
let k = m + n - 1; // Index of last position in nums1
// Merge nums1 and nums2 starting from the end
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) {
nums1[k] = nums1[i];
i--;
} else {
nums1[k] = nums2[j];
j--;
}
k--;
}
// If there are remaining elements in nums2, append them to nums1
while (j >= 0) {
nums1[k] = nums2[j];
j--;
k--;
}
}
Объяснение:
Функция слияния принимает четыре параметра: nums1, m, nums2 и n. nums1 — целевой массив, в котором будет храниться объединенный результат, m — количество элементов в nums1, nums2 — массив, который нужно объединить, а n — количество элементов в nums2.
Мы инициализируем три указателя, i, j и k, чтобы отслеживать текущие позиции в nums1, nums2 и результат объединения соответственно.
Начиная с конца массивов, мы сравниваем элементы с индексами i и j. Если элемент в nums1 больше, чем элемент в nums2, мы помещаем его в правильную позицию в nums1 с индексом k и уменьшить i. В противном случае, если элемент в nums2 больше, мы помещаем его в nums1 с индексом k и уменьшаем j. Мы продолжаем этот процесс, пока не достигнем начала либо nums1, либо nums2.
После объединения всех элементов из nums2 в >nums1, если есть оставшиеся элементы в nums2, но не осталось ни одного в nums1, мы перебираем оставшиеся элементы nums2 и добавьте их к nums1 в правильных позициях.
Следуя этому подходу, мы объединяем два отсортированных массива nums1 и nums2 в один отсортированный массив, хранящийся в m, как требуется.
Пример использования:
В приведенном выше примере у нас есть nums1 как [1, 3, 5, 0, 0, 0] с m как 3, и nums2 как [2, 4, 6] с n как 3. После вызова функции слияния nums1 обновлено до [1, 2, 3, 4, 5, 6], что является результатом объединения обоих массивов в неубывающем порядке.
Временная сложность этого алгоритма составляет O(m + n), так как мы итерируем как nums1, так и nums2 один раз. Мы используем три указателя для отслеживания позиций, избегая необходимости в дополнительном пространстве.
Этот подход эффективен, поскольку позволяет избежать создания отдельного массива для объединенного результата и использует тот факт, что оба входных массива уже отсортированы. Объединяя массивы на месте, мы удовлетворяем требованиям условия задачи.
Функцию слияния можно использовать для эффективного слияния двух отсортированных массивов, и она обеспечивает решение проблемы слияния nums1 и nums2 в один отсортированный массив, хранящийся в nums1, с учетом заданных ограничений.
Примечание. Важно убедиться, что в nums1 достаточно места для размещения объединенного результата. Длина nums1 должна быть m + n, чтобы вместить как исходные элементы, так и дополнительное пространство для слияния.
2. Использование связанного списка: связанный список-палиндром
Учитывая заголовок односвязного списка, вернуть true, если это палиндром, или false в противном случае.
Пример 1:
Ввод: голова = [1,2,2,1]
Вывод: правда
Пример 2:
Ввод: голова = [1,2]
Вывод: ложь
Ограничения:
Количество узлов в списке находится в диапазоне [1, 105].
0 ‹= Node.val ‹= 9
Следовать за:
Сможете ли вы сделать это за O(n) времени и O(1) пространства?
Чтобы решить данную проблему, мы можем использовать подход с двумя указателями вместе с некоторыми манипуляциями со связанными списками. Вот решение JavaScript:
function isPalindrome(head) {
if (!head || !head.next) {
return true; // An empty list or a single node is considered a palindrome
}
// Find the middle of the linked list using the slow and fast pointer technique
let slow = head;
let fast = head;
while (fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
}
// Reverse the second half of the linked list
let prev = null;
let curr = slow.next;
while (curr) {
let next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// Compare the reversed second half with the first half of the linked list
let p1 = head;
let p2 = prev;
while (p2) {
if (p1.val !== p2.val) {
return false; // Values mismatch, not a palindrome
}
p1 = p1.next;
p2 = p2.next;
}
return true; // All values match, it is a palindrome
}
Объяснение:
Функция isPalindrome принимает в качестве входных данных заголовок односвязного списка и возвращает значение true, если связанный список является палиндромом, или false в противном случае.
Сначала мы обработаем некоторые особые случаи:
- Если связанный список пуст или содержит только один узел, он считается палиндромом по определению, поэтому мы возвращаем true.
- Для связанного списка с двумя или более узлами мы используем метод медленного и быстрого указателя, чтобы найти средний узел. Медленный указатель перемещается на один шаг, а быстрый указатель перемещается на два шага за раз. Когда быстрый указатель достигнет конца списка, медленный указатель окажется в середине.
Затем мы переворачиваем вторую половину связанного списка. Мы начинаем с узла рядом с серединой и переворачиваем указатели, чтобы создать новый обратно связанный список.
Наконец, мы сравниваем перевернутую вторую половину с первой половиной связанного списка. Мы используем два указателя, p1 и p2, начиная с головы и перевернутой второй половины соответственно. Мы обходим обе половины одновременно, сравнивая значения каждой пары узлов. Если какая-либо пара значений не совпадает, мы возвращаем false, указывая на то, что связанный список не является палиндромом. Если все пары значений совпадают, мы возвращаем true, указывая на то, что связанный список является палиндромом.
Временная сложность этого алгоритма равна O(n), так как мы перебираем связанный список только один раз. Мы переворачиваем вторую половину на месте, не используя дополнительное пространство, что соответствует требованию сложности пространства O (1).
Это решение эффективно проверяет, является ли связанный список палиндромом, используя характеристики палиндрома и манипулируя указателями связанного списка.
3. Использование хэш-карты: первый уникальный символ в строке
Для заданной строки s найти в ней первый неповторяющийся символ и вернуть его индекс. Если он не существует, верните -1.
Пример 1:
Ввод: s = leetcode
Вывод: 0
Пример 2:
Ввод: s = loveleetcode
Вывод: 2
Пример 3:
Вход: s = aabb
Выход: -1
Ограничения:
- 1 ‹= с.длина ‹= 105
- s состоит только из строчных английских букв.
Чтобы решить данную проблему, мы можем использовать хэш-карту для хранения частоты каждого символа в строке. Затем мы можем перебрать строку, чтобы найти первый символ с частотой 1. Вот решение JavaScript:
function firstUniqChar(s) {
const charCount = new Map();
// Store the frequency of each character in the hashmap
for (let i = 0; i < s.length; i++) {
const char = s[i];
charCount.set(char, (charCount.get(char) || 0) + 1);
}
// Iterate through the string to find the first non-repeating character
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (charCount.get(char) === 1) {
return i; // Found the first non-repeating character, return its index
}
}
return -1; // No non-repeating character found, return -1
}
Объяснение:
Функция firstUniqChar принимает на вход строку s и возвращает индекс первого неповторяющегося символа в строке. Если нет неповторяющихся символов, возвращается -1.
Мы используем хэш-карту charCount для хранения частоты каждого символа в строке. Ключи хэш-карты — это символы, а значения — их соответствующие частоты.
Сначала мы перебираем строку, чтобы заполнить хэш-карту. Для каждого символа мы проверяем, существует ли он уже как ключ в хэш-карте. Если это так, мы увеличиваем его частоту на 1. Если нет, мы добавляем его в хэш-карту с частотой 1.
Затем мы снова перебираем строку, чтобы найти первый неповторяющийся символ. Для каждого символа мы проверяем его частоту в хэш-карте. Если частота равна 1, мы нашли первый неповторяющийся символ, поэтому возвращаем его индекс.
Если мы завершим цикл, не найдя ни одного неповторяющегося символа, мы вернем -1, чтобы указать, что такого символа в строке нет.
Временная сложность этого алгоритма равна O(n), где n — длина строки. Мы перебираем строку дважды: один раз для заполнения хэш-карты и один раз для поиска первого неповторяющегося символа. Сложность пространства равна O(1), так как хэш-карта может иметь максимум 26 записей (для строчных английских букв).
Это решение эффективно находит первый неповторяющийся символ в строке, используя хэш-карту для хранения частот символов и перебирая строку для определения нужного символа.
4. Удалить дубликаты из отсортированного массива
Учитывая целочисленный массив nums, отсортированный в неубывающем порядке, удалите дубликаты на месте, чтобы каждый уникальный элемент появлялся только один раз. Относительный порядок элементов должен быть сохранен. Затем верните количество уникальных элементов в nums.
Считайте, что количество уникальных элементов nums равно k, чтобы вас приняли, вам нужно сделать следующее:
- Измените массив nums так, чтобы первые k элементов nums содержали уникальные элементы в том порядке, в котором они изначально присутствовали в nums. Остальные элементы nums не важны, как и размер nums.
- Вернуться к.
Пользовательский судья:
Судья проверит ваше решение с помощью следующего кода:
int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length
int k = removeDuplicates(nums); // Calls your implementation
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
Если все утверждения пройдены, ваше решение будет принято.
Пример 1:
Input: nums = [1,1,2] Output: 2, nums = [1,2,_] Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).
Пример 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4,_,_,_,_,_] Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).
Ограничения:
- 1 ‹= nums.length ‹= 3 * 104
- -100 ‹= числа[i] ‹= 100
- nums сортируется в порядке неубывания.
Чтобы решить данную проблему, мы можем использовать подход с двумя указателями для удаления дубликатов на месте. Вот решение JavaScript:
function removeDuplicates(nums) {
if (nums.length === 0) {
return 0; // Empty array has no duplicates
}
let uniqueIndex = 0; // Pointer to track the position of unique elements
// Iterate through the array starting from the second element
for (let i = 1; i < nums.length; i++) {
if (nums[i] !== nums[uniqueIndex]) {
uniqueIndex++;
nums[uniqueIndex] = nums[i]; // Move the unique element to its correct position
}
}
return uniqueIndex + 1; // Return the count of unique elements
}
Объяснение:
Функция removeDuplicates принимает в качестве входных данных массив целых чисел nums и возвращает количество уникальных элементов в массиве после удаления дубликатов.
Сначала рассмотрим частный случай:
- Если массив пуст, дубликатов нет, поэтому мы возвращаем 0.
Затем мы используем подход двух указателей для удаления дубликатов на месте. У нас есть указатель uniqueIndex, который отслеживает положение уникальных элементов. Изначально он указывает на первый элемент массива.
Мы перебираем массив, начиная со второго элемента. Для каждого элемента, если он отличается от элемента с уникальным индексом, это означает, что мы нашли новый уникальный элемент. Мы увеличиваем uniqueIndex и перемещаем новый уникальный элемент в правильное положение.
К концу итерации все дубликаты удаляются, а первые элементы uniqueIndex + 1 в массиве становятся уникальными элементами в их исходном порядке.
Мы возвращаем uniqueIndex + 1 как количество уникальных элементов.
Временная сложность этого алгоритма составляет O(n), где n — длина входного массива nums. Мы проходим по массиву один раз, сравнивая элементы и перемещая уникальные элементы на их правильные позиции. Сложность пространства составляет O(1), так как мы изменяем массив на месте, не используя дополнительное пространство.
Это решение эффективно удаляет дубликаты из отсортированного массива на месте, сохраняя при этом относительный порядок элементов и возвращая количество уникальных элементов.
5. Алгоритм Кадане: максимальный подмассив
Учитывая целочисленный массив nums, найдите подмассив с наибольшей суммой и верните его сумму.
Пример 1:
Ввод: nums = [-2,1,-3,4,-1,2,1,-5,4]
Вывод: 6
Объяснение: Подмассив [4,-1,2, 1] имеет наибольшую сумму 6
Пример 2:
Ввод: nums = [1]
Вывод: 1
Объяснение: Подмассив [1] имеет наибольшую сумму 1.
Пример 3:
Ввод: nums = [5,4,-1,7,8]
Вывод: 23
Объяснение: Подмассив [5,4,-1,7,8] имеет наибольшую сумму 23
Ограничения:
- 1 ‹= nums.length ‹= 105
- -104 ‹= числа[i] ‹= 104
Следовать за:
Если вы нашли решение O(n), попробуйте написать другое решение, используя подход «разделяй и властвуй», который является более тонким.
Для решения данной задачи мы можем использовать алгоритм Кадане, также известный как алгоритм максимальной суммы подмассивов. Этот алгоритм эффективно находит подмассив с наибольшей суммой. Вот решение JavaScript:
function maxSubArray(nums) {
let currentSum = nums[0]; // Initialize the current sum as the first element
let maxSum = nums[0]; // Initialize the maximum sum as the first element
// Iterate through the array starting from the second element
for (let i = 1; i < nums.length; i++) {
// Compare the current element with the sum of the current element and previous subarray
currentSum = Math.max(nums[i], currentSum + nums[i]);
// Update the maximum sum if the current sum is greater
maxSum = Math.max(maxSum, currentSum);
}
return maxSum; // Return the maximum subarray sum
}
Объяснение:
Функция maxSubArray принимает целочисленный массив nums в качестве входных данных и возвращает сумму подмассива с наибольшей суммой.
Мы инициализируем две переменные: currentSum и maxSum первым элементом массива. Эти переменные представляют текущую сумму и максимальную сумму, найденную на данный момент.
Мы перебираем массив, начиная со второго элемента. Для каждого элемента мы сравниваем текущий элемент с суммой текущего элемента и предыдущего подмассива. Мы выбираем максимум между самим текущим элементом и суммой текущего элемента и предыдущего подмассива.
На каждой итерации мы обновляем currentSum до максимального значения между текущим элементом и сумма текущего элемента и предыдущего подмассива. Мы также обновляем maxSum до максимального значения между текущим значением maxSum и currentSum.
К концу итерации maxSum будет содержать сумму подмассива с наибольшей суммой.
Временная сложность этого алгоритма составляет O(n), где n — длина входного массива nums. Мы проходим по массиву один раз, обновляя currentSum и maxSum. Сложность пространства составляет O(1), так как мы используем постоянный объем дополнительного пространства только для хранения currentSum и maxSum.
Это решение эффективно находит подмассив с наибольшей суммой, используя алгоритм Кадане, что делает его очень эффективным подходом к решению этой проблемы.
Я надеюсь, что этих примеров достаточно, чтобы освоить некоторые технические детали, чтобы подойти к решению вопроса технического алгоритма интервью.
Если вам нравится это, поставьте лайк или комментарий. Удачного кодирования 💻!
