2019 год скоро подходит к концу, я считаю, что многие детские ботиночки начинают передвигаться и искать новые возможности, но они слишком заняты работой и им некогда писать алгоритмические вопросы, поэтому на собеседовании они чувствуют себя виноватыми. Вот 40 классических вопросов алгоритма собеседования на LeetCode. Содержание немного длинное. Рекомендуется сначала собрать его, медленно переварить и успешно получить удовлетворительное предложение в следующем году.
Больше контента, который нелегко организовать, я надеюсь, что все обратят внимание на общедоступный номер [интерфейс], более качественный исходный текст интерфейса.
1. [LeetCode] Сумма двух чисел
Учитывая массив целых чисел и целевое значение, найдите в массиве два числа, сумма которых равна целевому значению. Вы можете предположить, что каждый ввод соответствует только одному ответу и что одни и те же элементы нельзя использовать повторно. Пример: Учитывая числа = [2, 7, 11, 15], цель = 9 потому что nums[0] + nums[1] = 2 + 7 = 9 Итак, верните [0, 1]
var twoSum = function(nums, target) {
var len = nums.length;
for(var i=0; i<len; i++){
for(var j=i+1; j<len;j++){
if(nums[i] + nums[j] == target){
return [i, j];
}
}
}
return [];
};
2. Сумма путей [LeetCode]
Учитывая бинарное дерево и целевую сумму, определите, существует ли путь от корневого узла к листовому узлу в дереве, Сумма всех значений узлов на этом пути равна целевой сумме. Объяснение: Листовой узел — это узел, у которого нет дочерних узлов.
var hasPathSum = function(root, sum) {
if (!root) return false;
var cur = sum-root.val;
if (!root.left&&!root.right&&cur==0) return true;
if (!root.left) return hasPathSum(root.right, cur);
if (!root.right) return hasPathSum(root.left, cur);
return hasPathSum(root.left, cur)||hasPathSum(root.right, cur);
};
3. [LeetCode] Минимальная глубина бинарного дерева
Для заданного бинарного дерева найти его минимальную глубину. Минимальная глубина — это количество узлов на кратчайшем пути от корневого узла до ближайшего конечного узла. Объяснение: Листовой узел — это узел, у которого нет дочерних узлов.
var minDepth = function(root) {
if (!root) return 0;
if (!root.left&&!root.right) return 1;
if (!root.left) return minDepth(root.right)+1;
if (!root.right) return minDepth(root.left)+1;
return Math.min(minDepth(root.left), minDepth(root.right))+1;
};
4. [LeetCode] Двоичное суммирование
Учитывая две двоичные строки, вернуть их сумму (в двоичном представлении).
var addBinary = function(a, b) {
var res = [];
var num = 0;
var addOne = 0;//是否进位
//字符串对其
while(a.length < b.length){
a = 0 + a;
}
while(b.length < a.length){
b = 0 + b;
}
for (var i=a.length-1; i>=0; i--){
num = parseInt(a[i])+parseInt(b[i])+addOne;
if(num>=2){
res[i] = num-2;
addOne = 1;
}else{
res[i] = num;
addOne = 0;
}
}
if(addOne>0){
res.unshift(1);
}
return res.join('');
};
5. Квадратный корень из [LeetCode]x
Реализуйте функцию int sqrt(int x). Вычисляет и возвращает квадратный корень из x, где x — целое неотрицательное число. Поскольку тип возвращаемого значения — целое число, сохраняется только целая часть результата, а дробная часть будет округлена.
var mySqrt = function(x) {
var i = 1;
while(x>=i*i){
i++;
}
return i-1;
};
//方法2 ES6
var mySqrt = function(x) {
return Math.floor(x ** 0.5);//向下取整 x^0.5
};
6. [LeetCode] плюс один
Учитывая неотрицательное целое число, представленное непустым массивом целых чисел, добавьте единицу к этому числу. Старшая цифра хранится в первой позиции массива, и каждый элемент массива хранит только одно число.
var plusOne = function(digits) {
var len = digits.length;
for (var i=len-1; i>=0; i--){
if(digits[i]<9){
digits[i]++;
return digits;
}
digits[i] = 0;
}
digits.unshift(1);
return digits;
};
7. [LeetCode] Длина последнего слова
Учитывая строку, содержащую только прописные и строчные буквы и пробелы ' ', вернуть длину ее последнего слова.
var lengthOfLastWord = function(s) {
s = s.trim();
var arr = s.split(' ');
return arr[arr.length-1].length;
};
8. [LeetCode] Максимальная сумма подзаказа
Дан целочисленный массив nums, найти непрерывный подмассив с наибольшей суммой (подмассив содержит хотя бы один элемент) и вернуть его наибольшую сумму.
var maxSubArray = function(nums) {
var max = nums[0];
var sum = 0;
for (let num of nums){
if (sum < 0){
sum = 0;
}
sum += num;
max = Math.max(sum, max);
}
return max;
};
9. Количество [LeetCode]
Последовательность представления чисел представляет собой последовательность целых чисел, и числа сообщаются в порядке целых чисел, чтобы получить следующее число.
var countAndSay = function(n) {
var resultStr = '1';
for (var i=1; i<n; i++){
var repeatCount = 1;
var str = '';
for (var j=0; j<resultStr.length; j++) {
if (resultStr[j]===resultStr[j+1]){
repeatCount++;
} else {
str += repeatCount + resultStr[j];
repeatCount = 1;
}
}
resultStr = str;
}
return resultStr;
};
10. [LeetCode] Треугольник Ян Хуэй
Учитывая неотрицательное целое число numRows, сгенерируйте первые строки numRows треугольника Ян Хуэй. В треугольнике Янхуэй каждое число представляет собой сумму своих верхних левых и верхних правых чисел. Пример: Вход: 5 выход: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]
var generate = function(numRows) {
var res = [];
for (var i=0; i<numRows; i++){
var arr = [1];
for (var j=1; j<i; j++){
arr[j] = res[i-1][j]+res[i-1][j-1];
}
arr[i] = 1;
res.push(arr);
}
return res;
};
11. [LeetCode] Треугольник Ян Хуэй II
Учитывая неотрицательный индекс k, где k ≤ 33, вернуть k-ю строку треугольника Янга-Хуэй.
var getRow = function(rowIndex) {
var res = [1];
if (rowIndex==0) return [1];
if (rowIndex==1) {
return [1,1];
}
var arr = getRow(rowIndex-1);
for (var i=1; i<rowIndex; i++){
res[i] = arr[i]+arr[i-1];
}
res.push(1);
return res;
};
12. [LeetCode] Пересекающийся связанный список
Напишите программу, которая находит начальный узел в месте пересечения двух односвязных списков. Например
Идеи: Проходим по таблице A, когда указатель l1 равен хвосту c3, пусть он указывает на b1 таблицы B Проходим по таблице B, когда указатель l2 равен хвосту c3, пусть он указывает на a1 таблицы A Если два связанных списка пересекаются, они будут указывать на c1 одновременно, потому что: a1 → a2 → c1 → c2 → c3 → b1 → b2 → b3 → c1 и b1 → b2 → b3 → c1 → c2 → c3 → a1 → a2 → c1 равны.
var getIntersectionNode = function(headA, headB) {
if (!headA || !headB) return null;
if (headA == headB) return headA;
var l1 = headA;
var l2 = headB;
var count = 0;
while(l1 != l2 && count < 3){
if (!l1.next || !l2.next) count++;
l1 = l1.next ? l1.next : headB;
l2 = l2.next ? l2.next : headA;
}
return l1==l2 ? l1 : null;
};
13. [LeetCode] Ограбление
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。 Идеи: 偷取第 i 家时，有两种选择： 偷取第 i 家，此时金额为：res[i] = res[i-2]+nums[i]; 不偷，此时金额为：res[i] = res[i-1]; 所以最高金额为两者取较大值。
var rob = function(nums) {
var len = nums.length;
if (len < 2) return nums[len-1]?nums[len-1]:0;
var res = [nums[0], Math.max(nums[0], nums[1])];
for (let i=2; i<len; i++){
res[i] = Math.max(res[i-1], nums[i]+res[i-2]);
}
return res[len-1];
};
14. [LeetCode] Минимальный стек
Разработайте стек, который поддерживает операции push, pop и top и извлекает наименьший элемент за постоянное время. push(x) – Поместить элемент x в стек. pop() — удаляет верхний элемент из стека. top() — Получить верхний элемент стека. getMin() — извлекает наименьший элемент в стеке.
var MinStack = function() {
this.stack = []
};
MinStack.prototype.push = function(x) {
this.stack[this.stack.length] = x;
};
MinStack.prototype.pop = function() {
this.stack.length--;
};
MinStack.prototype.top = function() {
return this.stack[this.stack.length-1];
};
MinStack.prototype.getMin = function() {
var min = this.stack[0];
var len = this.stack.length;
for (var i=1; i<len; i++){
if (this.stack[i]<min){
min = this.stack[i];
}
}
return min;
};
15. [LeetCode] Число, которое появляется только один раз
Учитывая непустой массив целых чисел, каждый элемент появляется дважды, кроме одного, который появляется только один раз. Найдите элемент, который встречается только один раз.
var singleNumber = function(nums) {
nums.sort(function(a, b){
return a-b;
});
var len = nums.length;
for (var i=0; i<len; i=i+2){
if(nums[i]!=nums[i+1]){
return nums[i];
}
}
};
16. [LeetCode] Проверка строки палиндрома
Учитывая строку, убедитесь, что это палиндром, учитывая только буквенно-цифровые символы, игнорируя регистр букв. Объяснение: В этой задаче мы определяем пустую строку как допустимый палиндром.
var isPalindrome = function(s) {
var str1 = s.toUpperCase().replace(/\W/g,'');
var str2 = str1.split('').reverse().join('');
return str1==str2;
};
17. [LeetCode] Лучшее время для покупки и продажи акций II
Дан массив, i-й элемент которого представляет собой цену данной акции в i-й день. Разработайте алгоритм для расчета максимальной прибыли, которую вы можете получить. Вы можете совершить столько сделок, сколько сможете (покупая и продавая акции несколько раз). Примечание. Вы не можете участвовать в нескольких сделках одновременно (вы должны продать предыдущие акции, прежде чем покупать снова).
var maxProfit = function(prices) {
var max = 0;
var len = prices.length;
for (var i=0; i<len-1; i++){
if (prices[i+1]>prices[i]){
max += prices[i+1]-prices[i];
}
}
return max;
};
18. [LeetCode] удалить элемент
Учитывая массив nums и значение val, вам нужно удалить все элементы, значение которых равно val на месте, и вернуть новую длину удаленного массива. Не используйте дополнительное пространство массива, вам нужно изменить входной массив на месте и сделать это с дополнительным пространством O (1). Порядок элементов можно изменить. Вам не нужно рассматривать элементы в массиве за пределами новой длины.
var removeElement = function(nums, val) {
var i = 0;
var len = nums.length;
for (var j = 0; j<len; j++){
if(nums[j]!==val){
nums[i] = nums[j]
i++;
}
}
return i;
};
//方法2
var removeElement = function(nums, val) {
var i = 0;
var len = nums.length;
while (i < len){
if (nums[i] == val) {
nums[i] = nums[len-1];
len--;
} else {
i++;
}
}
return len;
};
19. [LeetCode] Сбалансированное бинарное дерево
Учитывая бинарное дерево, определите, является ли оно хорошо сбалансированным бинарным деревом. В этой задаче сбалансированное по высоте бинарное дерево определяется как: Абсолютное значение разницы высот между левым и правым поддеревьями каждого узла бинарного дерева не превышает 1.
var isBalanced = function(root) {
if (!root) return true;
if (Math.abs(depth(root.left)-depth(root.right))>1) return false;
return isBalanced(root.left) && isBalanced(root.right);
function depth(node){
if (!node) return 0;
var left = depth(node.left);
var right = depth(node.right);
return Math.max(left, right)+1;
}
};
20. [LeetCode] Удалить дубликаты в отсортированном массиве
Учитывая отсортированный массив, вам нужно удалить повторяющиеся элементы на месте, чтобы каждый элемент встречался только один раз, и вернуть новую длину удаленного массива.
var removeDuplicates = function(nums) {
var i = 0;
var len = nums.length;
for (var j=1; j<len; j++){
if (nums[i] !== nums[j]){
i++;
nums[i] = nums[j]
}
}
return i+1;
};
21. [LeetCode] Объединить два нумерованных списка
Объединить два отсортированных связанных списка в новый отсортированный связанный список и вернуться. Новый связанный список формируется путем соединения всех узлов данных двух связанных списков.
var mergeTwoLists = function (l1, l2) {
var lHead = new ListNode(0);
var lCur = lHead;
while (l1 !== null && l2 !== null) {
if(l1.val < l2.val) {
lCur.next = l1;
lCur = lCur.next;
l1 = l1.next;
} else {
lCur.next = l2;
lCur = lCur.next;
l2 = l2.next;
}
}
if (l1 === null) {
lCur.next = l2;
}
if (l2 === null) {
lCur.next = l1;
}
return lHead.next;
};
22. [LeetCode] Допустимые скобки
Учитывая строку, содержащую только '(', ')', '{', '}', '[', ']', определите, является ли строка допустимой. Действительная строка должна удовлетворять: Открывающие скобки должны быть закрыты закрывающими скобками того же типа. Левые скобки должны быть закрыты в правильном порядке. Обратите внимание, что пустые строки считаются допустимыми строками.
var isValid = function(s) {
var stack = [];
var len = s.length;
for (var i=0; i<len; i++){
var char = s[i];
var stackLen = stack.length;
if(stackLen==0) {
stack.push(char);
}else{
if(isMatch(stack[stackLen-1],char)){
stack.pop();
}else{
stack.push(char);
}
}
}
return stack.length==0;
function isMatch(char1, char2){
if (char1=='(' && char2==')'||
char1=='{' && char2=='}'||
char1=='[' && char2==']'
){
return true;
}
return false;
}
};
23. [LeetCode] Самый длинный общий префикс
Напишите функцию для поиска самого длинного общего префикса в массиве строк. Если общего префикса не существует, возвращается пустая строка "".
var longestCommonPrefix = function(strs) {
if (!strs.length) return '';
var str1 = strs[0];
var res = '';
var str1Len = str1.length;
var strsLen = strs.length;
for (var i=0; i<str1Len; i++) {
for (var j=1; j<strsLen; j++) {
if (str1[i] !== strs[j][i]) {
return res;
}
}
res += str1[i];
}
return res;
};
24, [литкод] римский номер конвейера
Римские цифры содержат следующие семь знаков: I, V, X, L, C, D и M. значение символа я 1 V5 Х 10 л 50 С 100 Д 500 М 1000 Например, римская цифра 2 записывается как II, то есть две единицы рядом друг с другом, а 12 записывается как XII, то есть X + II. 27 записывается как XXVII, то есть XX + V + II.
var romanToInt = function(s) {
var romanObj = {'I': 1,'V': 5,'X': 10,'L': 50,'C': 100,'D': 500,'M': 1000};
var num = 0;
var len = s.length;
for (var i=0; i<len-1; i++) {
var curNum = romanObj[s.charAt(i)];
var rightNum = romanObj[s.charAt(i+1)];
num += curNum>=rightNum?curNum:-curNum;
}
num += romanObj[s.charAt(i)]
return num;
};
25. [LeetCode] номер палиндрома
Определяет, является ли целое число палиндромом. Палиндром — это целое число, которое одинаково читается в положительном порядке (слева направо) и в обратном порядке (справа налево).
var isPalindrome = function(x) {
var num = x.toString();
return x == num.split('').reverse().join('');
};
//方法2 找到中间位置，然后两边对比
var isPalindrome = function(x) {
var str = x.toString();
var len = str.length;
var halfLen = (len-1)/2;
for (var i=0; i<halfLen; i++){
if(str.charAt(i)!==str.charAt(len-1-i)){
return false;
}
}
return true;
};
26. [LeetCode] Обратное целое
Учитывая 32-битное целое число со знаком, поменяйте местами числа в целом числе.
var reverse = function(x) {
var num = x.toString().split('').reverse();
var res = parseInt(num.join(''));
if(res>2**31) return 0;
return x>0?res:-res;
};
27. [LeetCode] Реализовать функцию strStr()
Для заданной строки и строки иглы стога сена позиция иглы для поиска первого вхождения строки (начиная с 0) в строке стога сена. Если нет, возвращается -1.
var strStr = function(haystack, needle) {
if (needle=='') return 0;
var len2 = needle.length;
var len = haystack.length - len2;
for (var i = 0; i<=len; i++) {
if (haystack.substring(i, i+len2) == needle) {
return i;
}
}
return -1;
};
//超简做法
var strStr = function(haystack, needle) {
return haystack.indexOf(needle);
};
28. [LeetCode] поиск позиции вставки
Учитывая отсортированный массив и целевое значение, найдите целевое значение в массиве и верните его индекс. Если целевое значение не существует в массиве, возвращает позицию, в которую оно будет вставлено по порядку.
var searchInsert = function(nums, target) {
var len = nums.length;
for(var i=0; i<len; i++){
if(target<=nums[i]){
return i;
}
}
return len;
};
29. [LeetCode] Преобразование упорядоченного массива в двоичное дерево поиска.
Преобразует отсортированный по возрастанию массив в сбалансированное по высоте двоичное дерево поиска. В этом вопросе сбалансированное по высоте бинарное дерево означает, что абсолютное значение разницы высот между левым и правым поддеревьями каждого узла бинарного дерева не превышает 1.
var sortedArrayToBST = function(nums) {
var len = nums.length;
if(!len) return null;
if(len===1) return new TreeNode(nums[0]);
var mid = parseInt(len/2);
var root = new TreeNode(nums[mid]);
root.left = sortedArrayToBST(nums.slice(0, mid));
root.right = sortedArrayToBST(nums.slice(mid+1));
return root;
};
30. [LeetCode] Иерархический обход бинарного дерева II
Учитывая бинарное дерево, верните восходящий уровень обхода его значений узлов. (То есть от слоя, где расположен листовой узел, к слою, где расположен корневой узел, обходя слой за слоем слева направо)
var levelOrderBottom = function(root) {
var queue = [];
var result = [];
if(root) queue.push(root);
while(queue.length){
var arr = [];
var len = queue.length
for(var i=0; i<len; i++){
var curNode = queue.shift();
arr.push(curNode.val);
if(curNode.left) queue.push(curNode.left);
if(curNode.right) queue.push(curNode.right);
}
result.unshift(arr);
}
return result;
};
31. [LeetCode] Максимальная глубина бинарного дерева
Для заданного бинарного дерева найти его максимальную глубину. Глубина бинарного дерева — это количество узлов на самом длинном пути от корневого узла до самого дальнего листового узла. Объяснение: Листовой узел — это узел, у которого нет дочерних узлов.
var maxDepth = function(root) {
if(!root) return 0;
var left_depth = maxDepth(root.left);
var right_depth = maxDepth(root.right);
return Math.max(left_depth, right_depth)+1;
};
32. [LeetCode] Подъем по лестнице
Предположим, вы поднимаетесь по лестнице. Вам нужно n шагов, чтобы добраться до вершины здания. Вы можете подняться на 1 или 2 ступеньки каждый раз. Сколькими способами можно добраться до вершины здания? Идеи: ф(1) : 1 ф(2) : 11 , 2 f(3) : 12, 111, 21 f(4) : 121, 1111, 211, 112, 22 f(n) = f(n-1) + f(n-2)
var climbStairs = function(n) {
let a = b = 1;
for (let i = 0; i < n; i++) {
[a, b] = [b, a + b];//ES6的递归写法
}
return a;
};
33. [LeetCode] Объединить два упорядоченных массива
Имея два отсортированных целочисленных массива nums1 и nums2, объедините nums2 с nums1, сделав num1 отсортированным массивом. проиллюстрировать: Инициализируйте nums1 и nums2 с m и n элементами соответственно. Вы можете предположить, что в nums1 достаточно места (размер пространства больше или равен m + n) для хранения элементов в nums2. Пример: войти: числа1 = [1,2,3,0,0,0], м = 3 числа2 = [2,5,6], n = 3 Вывод: [1,2,2,3,5,6]
var merge = function(nums1, m, nums2, n) {
for (let i=0; i<n; i++){
nums1[m+i] = nums2[i]
}
nums1.sort(function(a, b){
return a-b;
})
};
34. [LeetCode] То самое дерево
Имея два бинарных дерева, напишите функцию, проверяющую, совпадают ли они. Два дерева считаются идентичными, если они структурно идентичны и узлы имеют одинаковые значения.
var isSameTree = function(p, q) {
if (p===null && q===null) return true;
if (p===null || q===null) return false;
if (p.val != q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};
35. [LeetCode] Симметричное двоичное дерево
Имея бинарное дерево, проверьте, является ли оно зеркально симметричным.
var isSymmetric = function(root) {
if (!root) return true;
var leftAndRight = function(left, right){
if (!left && !right) return true;
if (!left || !right) return false;
if (left.val != right.val) return false;
return leftAndRight(left.left, right.right) && leftAndRight(left.right, right.left);
}
return leftAndRight(root.left, root.right);
};
36. [LeetCode] Удалить повторяющиеся элементы в отсортированном списке
Удалить повторяющиеся элементы в отсортированном связанном списке
var deleteDuplicates = function(head) {
var l = head;
if(l==null) return null
while(l.next){
if(l.val == l.next.val){
l.next = l.next.next;
}else{
l = l.next;
}
}
return head;
};
37. [LeetCode] Имя столбца таблицы Excel
Учитывая положительное целое число, верните соответствующее имя столбца в таблице Excel. Например, 1 -> А 2 -> Б 3 -> С ... 26 -> Я 27 -> АА 28 -> АВ ...
var convertToTitle = function(n) {
var res='';
while(n>0){
var a = parseInt((n-1)%26);
n = parseInt((n-1)/26);
res = String.fromCharCode(a+65) + res;
}
return res;
};
Добро пожаловать в публичный аккаунт фронтенда: фронтенд, больше опыта интервью и возможности внутреннего продвижения.