2019 is coming to an end, I believe many children are beginning to be eager to find new opportunities, but too busy to brush algorithm questions, feel guilty during the interview. Here are 40 classic interview algorithm questions in LeetCode, which are a bit long. I suggest you collect them and digest them slowly, so that you can get a satisfactory offer in the coming year.
More content, sorting is not easy, I hope you pay attention to the public number [front-end], more quality front-end original good article.
1, [LeetCode] the sum of two numbers
Given an array of integers and a target value, find two numbers that neutralize the target value in the array. You can assume that there is only one answer for each input and that the same elements cannot be reused. Example: Given nums = [2, 7, 11, 15], target = 9
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 []; };Copy the code2. [LeetCode] Sum of paths
Given a binary tree and a destination sum, determine whether there is a path from the root node to the leaf node in the tree. The sum of the values of all nodes along the path equals the destination sum. Note: Leaf nodes are nodes that have no child nodes.
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); };Copy the code3, [LeetCode] the minimum depth of binary tree
Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node. Note: Leaf nodes are nodes that have no child nodes.
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; };Copy the code[LeetCode] binary sum
Given two binary strings, return their sum (in binary).
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(''); };Copy the code5, the square root of x
Implement the int SQRT (int x) function. Calculates and returns the square root of x, where x is a non-negative integer. Since the return type is an integer, only the integer part of the result is retained, and the fractional part is omitted.
var mySqrt = function(x) { var i = 1; while(x>=i*i){ i++; } return i-1; }; ES6 var mySqrt = function(x) {return math.floor (x ** 0.5); // integer x^0.5};Copy the code6, [LeetCode] + 1
Given a non-negative integer represented by a non-empty array of integers, add one to that number. The highest digit is stored at the beginning of an array, where each element stores only one digit.
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;
};
Copy the code7, [LeetCode] the length of the last word
Given a string containing only uppercase and lowercase letters and a space ‘ ‘, return the length of its last word.
var lengthOfLastWord = function(s) {
s = s.trim();
var arr = s.split(' ');
return arr[arr.length-1].length;
};
Copy the code8, [LeetCode] maximum subsequence sum
Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.
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;
};
Copy the code9, [LeetCode] count off
A counting sequence is a sequence of integers in which the integers are counted in order to get the next number.
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;
};
Copy the code[LeetCode] Yang Hui triangle
Given a non-negative integer numRows, generate the former numRows of the Yanghui triangle. In Yang Hui’s triangle, each number is the sum of the numbers on its upper left and upper right. Example: input: 5 output: [[1], [1, 1], [1, 2, 1],,3,3,1 [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;
};
Copy the code11. [LeetCode] Yang Hui triangle II
Given a nonnegative index k, where k ≤ 33, return the KTH row of the Yang Hui triangle.
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; };Copy the code[LeetCode] intersects the linked list
Write a program to find the start node where two singly linked lists intersect. For example,
If l1 is equal to c3, let it point to B1 in B. If L2 is equal to C3, let it point to A1 in A. If l2 is equal to C3, let it point to C1. A1 → A2 → C1 → C2 → c3 → B1 → B2 → B3 → C1 → b1 → B2 → 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; };Copy the code13, [LeetCode]
You are a professional thief, planning to rob the houses along the street. There is a certain amount of cash hidden in each room, and the only constraint on your ability to steal is that adjoining houses are equipped with interconnected security systems that will automatically alert the police if two houses are broken into on the same night. Given an array of non-negative integers representing the amount stored in each house, calculate the maximum amount you can steal without setting off the alarm. [I] = res[I]+nums[I]; [I] = res[I]+nums[I]; If no, the value is: res[I] = res[i-1]; So the maximum amount is the greater value of both.
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]; };Copy the code[LeetCode] minimum stack
Design a stack that supports push, pop, and top operations and can retrieve the smallest element in constant time. Push (x) – Pushes the element X onto the stack. Pop () – Removes the top element of the stack. Top () – Gets the top element on the stack. GetMin () – Retrieves the smallest element in the stack.
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;
};
Copy the code15, [LeetCode] a number that appears only once
Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once.
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]; }}};Copy the code[LeetCode] verify palindrome string
Given a string, verify that it is a palindrome string, considering only alphanumeric characters, regardless of letter case. Note: In this case, we define an empty string as a valid palindrome string.
var isPalindrome = function(s) {
var str1 = s.toUpperCase().replace(/\W/g,'');
var str2 = str1.split('').reverse().join('');
return str1==str2;
};
Copy the code[LeetCode] The best time to buy and sell stocks II
Given an array, its ith element is the price of a given stock on the ith day. Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as possible. Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).
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;
};
Copy the code[LeetCode] removes elements
Given an array nums and a value val, you remove all elements with a value equal to val in place, returning the new length of the array. Instead of using extra array space, you must modify the input array in place and do so with O(1) extra space. The order of elements can be changed. You don’t need to worry about the element after the new length in the array.
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; }; Var element = 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; };Copy the code19, [LeetCode] Balanced binary tree
Given a binary tree, determine whether it is a highly balanced binary tree. In this case, a highly balanced binary tree is defined as: the absolute value of the height difference between the left and right subtrees of each node of a binary tree is no more than 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; }};Copy the code[LeetCode] removes duplicates from sorted array
Given a sorted array, you need to remove duplicate elements in place so that each element appears only once, returning the new length of the removed array.
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; };Copy the code[LeetCode] merges two ordered lists
Merges two ordered lists into a new ordered list and returns. A new list is formed by concatenating all the nodes of a given two lists.
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; };Copy the code[LeetCode] valid parentheses
Given a string containing only ‘(‘,’) ‘, ‘{‘,’} ‘, ‘[‘,’] ‘, check whether the string is valid. A valid string must meet the following requirements: The left parenthesis must be closed with the same type of the right parenthesis. The left parentheses must be closed in the correct order. Note that an empty string can be considered a valid string.
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; }};Copy the code[LeetCode] specifies the longest public prefix
Write a function to find the longest public prefix in an array of strings. Returns the empty string “” if no common prefix exists.
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; };Copy the code24, [LeetCode] Roman numeral to integer
Roman numerals contain the following seven characters: I, V, X, L, C, D and M. Character value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, the Roman numeral 2 is written as II, which is the parallel 1. Write XII as X + II. Write XXVII as 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; };Copy the code[LeetCode] Palindrome number
Checks whether an integer is a palindrome. Palindromes are integers that read in positive (left to right) and backward (right to left) order.
var isPalindrome = function(x) { var num = x.toString(); return x == num.split('').reverse().join(''); }; 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; };Copy the code[LeetCode] inverts integers
Given a 32 – bit signed integer, invert the number in the integer.
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; };Copy the code[LeetCode] implements strStr()
Given a Haystack string and a Needle string, find the first position in the Haystack string where the Needle string appears (starting from 0). If none exists, -1 is returned.
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. };Copy the code[LeetCode] searches for insert location
Given a sorted array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the position where it will be inserted in order.
var searchInsert = function(nums, target) {
var len = nums.length;
for(var i=0; i<len; i++){
if(target<=nums[i]){
return i;
}
}
return len;
};
Copy the code[LeetCode] converts an ordered array into a binary search tree
Converts an ordered array in ascending order into a highly balanced binary search tree. In this case, a highly balanced binary tree means that the absolute value of the height difference between the left and right subtrees of each node of a binary tree is less than 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; };Copy the code[LeetCode] binary tree hierarchy traversal II
Given a binary tree, return a bottom-up hierarchical traversal of its node values. (that is, from the layer where the leaf node is located to the layer where the root node is located, layer by layer from left to right)
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;
};
Copy the code[LeetCode] The maximum depth of a binary tree
Given a binary tree, find its maximum depth. The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node. Note: Leaf nodes are nodes that have no child nodes.
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; };Copy the code32. [LeetCode] Take the stairs
Suppose you’re climbing stairs. It takes n steps to get to the top. You can climb one or two steps at a time. How many different ways can you climb to the top? 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]; } return a; };Copy the code[LeetCode] merges two ordered arrays
Given two ordered integer arrays nums1 and nums2, merge nums2 into nums1 such that num1 becomes an ordered array. Note: The number of elements initialized for nums1 and nums2 is m and N, respectively. You can assume that NUMs1 has enough space (space size greater than or equal to m + n) to hold elements in NUMs2. Example: input: nums1 =,2,3,0,0,0 [1], m = 3 nums2 = [6] 2, n = 3 output:,2,2,3,5,6 [1]
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; })};Copy the code34, [LeetCode] same tree
Given two binary trees, write a function to check if they are the same. Two trees are considered identical if they are structurally identical and the nodes have the same value.
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); };Copy the code[LeetCode] symmetric binary tree
Given a binary tree, check whether it is mirror – symmetric.
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); };Copy the code[LeetCode] removes duplicate elements from the sorted list
Removes duplicate elements from sorted linked lists
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;
};
Copy the code[LeetCode]Excel table column name
Given a positive integer, return its corresponding column name in the Excel table. For example, 1 -> A 2 -> B 3 -> C… 26 -> Z 27 -> AA 28 -> AB …
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;
};
Copy the codeWelcome to pay attention to the front end public number: front end, more interview experience and internal push opportunities.
