ByteDance s favorite 64 algorithm questions (JS version)

ByteDance s favorite 64 algorithm questions (JS version)

origin

Nowadays, algorithm questions are almost compulsory in interviews with big factories, and LeetCode real questions have appeared frequently in recent years. This article is the author who has obtained Byte, Tencent, and Jingdong Offer personally brushed and encountered in the process of preparing for the interview. High-frequency algorithmic questions. The content of the article will be organized in modules, and the real questions encountered by the author during the interview will be highlighted [ ].

At the same time, you can say unceremoniously that if you have limited preparation time and want to maximize the efficiency of algorithmic problem preparation, then you only need to follow the outline to finish the following topics and master the code, and you can almost deal with 90 % Of the interview algorithm test questions are out.

The purpose of organizing this content is the accumulation of the author when preparing for the interview, and it does help the author to pass the interview algorithm questions, and at the same time, I also hope to give you a little help in the golden three silver four. Just fine!

There are benefits at the end of the article:)

The content of this article includes the following modules:

  • High-frequency algorithm question series: linked list
  • [ ] [There are real questions] High-frequency algorithm question series: string
  • [ ] [There are real questions] High-frequency algorithm question series: array problems
  • High-frequency algorithm question series: Binary tree
  • High-frequency algorithm question series: Sorting algorithm
  • High-frequency algorithm question series: binary search
  • High-frequency algorithm question series: dynamic programming
  • High-frequency algorithm question series: BFS
  • High-frequency algorithm question series: stack
  • High-frequency algorithm question series: DFS
  • High-frequency algorithm question series: Backtracking algorithm

Among them, the part marked with represents very high frequency test questions, among which there are many original questions that the author encountered. For each category, the included test questions are first listed, and then for each test question, the difficulty, knowledge points, and whether it is a real interview question will be given. When each question is introduced in detail, the LeetCode of each question will also be given. Links to help readers understand the meaning of the questions, and to be able to conduct actual tests, and to watch other people s answers to better prepare.

High-frequency algorithm question series: linked list

The high-frequency linked list questions I encountered mainly include these:

  • Judge the problem of palindrome linked list through subsequent traversal of linked list [simple]
  • Reverse output of linked list [simple]
  • Combine K ascending linked lists difficulty
  • K flip list [difficulty]
  • Circular Linked List Simple
  • Sorted linked list [medium]
  • Intersecting Linked List Simple

Preorder traversal to determine palindrome linked list

[LeetCode through train]: 234 palindrome linked list (simple)

Solution 1

Use the subsequent traversal of the linked list and use the function call stack as a post-order traversal of the stack to determine whether it is a palindrome

Click to expand view
/** * */ var isPalindrome = function ( head ) { let left = head; function traverse ( right ) { if (right == null ) return true ; let res = traverse(right.next); res = res && (right.val === left.val); left = left.next; return res; } return traverse(head); }; Copy code

Solution 2

Use the fast and slow pointers to find the midpoint of the linked list, then reverse the linked list and compare whether the two linked lists are equal to each other to determine whether it is a palindrome linked list

Click to expand view
/** * */ var isPalindrome = function(head) { // slower let right = reverse(findCenter(head)); let left = head; // while (right != null) { if (left.val !== right.val) { return false; } left = left.next; right = right.next; } return true; } function findCenter(head) { let slower = head, faster = head; while (faster && faster.next != null) { slower = slower.next; faster = faster.next.next; } //If faster is not equal to null, it means it is an odd number, and slower moves one more grid if (faster != null ) { slower = slower.next; } return slower; } function reverse ( head ) { let prev = null , cur = head, nxt = head; while (cur != null ) { nxt = cur.next; cur.next = prev; prev = cur; cur = nxt; } return prev; } Copy code

Reverse linked list

[LeetCode through train]: 206 inverted linked list (simple)

answer

Click to expand view
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function ( head ) { if (head == null || head.next == null ) return head; let last = reverseList(head.next) ; head.next.next = head; head.next = null ; return last; }; Copy code

Combine K ascending linked lists

[LeetCode through train]: 23 merge K ascending linked lists (difficult)

answer

Click to expand view
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} */ /** * @param {ListNode[]} lists * @return {ListNode} */ var mergeKLists = function(lists) { if (lists.length === 0) return null; return mergeArr(lists); }; function mergeArr(lists) { if (lists.length <= 1) return lists[0]; let index = Math.floor(lists.length/2); const left = mergeArr(lists.slice(0, index)) const right = mergeArr(lists.slice(index)); return merge(left, right); } function merge(l1, l2) { if (l1 == null && l2 == null) return null; if (l1 != null && l2 == null) return l1; if (l1 == null && l2 != null) return l2; let newHead = null, head = null; while (l1 != null && l2 != null) { if(l1.val <l2.val) { if (!head) { newHead = l1; head = l1; } else { newHead.next = l1; newHead = newHead.next; } l1 = l1.next; } else { if (!head) { newHead = l2; head = l2; } else { newHead.next = l2; newHead = newHead.next; } l2 = l2.next; } } newHead.next = l1? l1: l2; return head; } Copy code

K flip list

[LeetCode through train]: 25 K flip list (difficulty)

answer

Click to expand view
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} */ /** * @param {ListNode} head * @param {number} k * @return {ListNode} */ var reverseKGroup = function(head, k) { let a = head, b = head; for (let i = 0; i < k; i++) { if (b == null) return head; b = b.next; } const newHead = reverse(a, b); a.next = reverseKGroup(b, k); return newHead; }; function reverse ( a, b ) { let prev = null , cur = a, nxt = a; while (cur != b) { nxt = cur.next; cur.next = prev; prev = cur; cur = nxt; } return prev; } Copy code

Circular linked list

[LeetCode through train]: 141 circular linked list (simple)

answer

Click to expand view
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} */ /** * @param {ListNode} head * @return {boolean} */ var hasCycle = function ( head ) { if (head == null || head.next == null ) return false ; let slower = head, faster = head; while (faster != null && faster.next != null ) { slower = slower.next; faster = faster.next.next; if (slower === faster) return true ; } return false ; }; Copy code

Sorted list

[LeetCode through train]: 148 sorted linked list (medium)

answer

Click to expand view
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} */ /** * @param {ListNode} head * @return {ListNode} */ var sortList = function ( head ) { if (head == null ) return null ; let newHead = head; return mergeSort(head); }; function mergeSort(head) { if (head.next != null) { let slower = getCenter(head); let nxt = slower.next; slower.next = null; console.log(head, slower, nxt); const left = mergeSort(head); const right = mergeSort(nxt); head = merge(left, right); } return head; } function merge(left, right) { let newHead = null, head = null; while (left != null && right != null) { if (left.val < right.val) { if (!head) { newHead = left; head = left; } else { newHead.next = left; newHead = newHead.next; } left = left.next; } else { if (!head) { newHead = right; head = right; } else { newHead.next = right; newHead = newHead.next; } right = right.next; } } newHead.next = left? left: right; return head; } function getCenter ( head ) { let slower = head, faster = head.next; while (faster != null && faster.next != null ) { slower = slower.next; faster = faster.next.next; } return slower; } Copy code

Intersecting linked list

[LeetCode through train]: 160 intersecting linked list (simple)

answer

Click to expand view
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} */ /** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { let lastHeadA = null; let lastHeadB = null; let originHeadA = headA; let originHeadB = headB; if (!headA || !headB) { return null; } while ( true ) { if (headB == headA) { return headB; } if (headA && headA.next == null ) { lastHeadA = headA; headA = originHeadB; } else { headA = headA.next; } if (headB && headB.next == null ) { lastHeadB = headB headB = originHeadA; } else { headB = headB.next; } if (lastHeadA && lastHeadB && lastHeadA != lastHeadB) { return null ; } } return null ; }; Copy code

High-frequency algorithm question series: string

There are mainly the following types of high-frequency exam questions:

  • The longest palindrome substring [medium] [dual pointer] [interview question]
  • Longest common prefix [simple] [dual pointer]
  • The longest substring without repeated characters [medium] [double pointer]
  • Minimum Covering Substring [Difficulty] [Sliding Window] [Real Interview Questions]

[True Interview Question] The longest palindrome substring [Dual pointer]

[LeetCode through train]: 5 longest palindrome substring (medium)

answer

Click to expand view
/** * @param {string} s * @return {string} */ var longestPalindrome = function(s) { if (s.length === 1) return s; let maxRes = 0, maxStr = ''; for (let i = 0; i < s.length; i++) { let str1 = palindrome(s, i, i); let str2 = palindrome(s, i, i + 1); if (str1.length > maxRes) { maxStr = str1; maxRes = str1.length; } if (str2.length> maxRes) { maxStr = str2; maxRes = str2.length; } } return maxStr; }; function palindrome ( s, l, r ) { while (l >= 0 && r <s.length && s[l] === s[r]) { l--; r++; } return s.slice(l + 1 , r); } Copy code

Longest common prefix [dual pointer]

[LeetCode through train]: 14 longest common prefix (simple)

answer

Click to expand view
/** * @param {string[]} strs * @return {string} */ var longestCommonPrefix = function(strs) { if (strs.length === 0) return ""; let first = strs[0]; if (first === "") return ""; let minLen = Number.MAX_SAFE_INTEGER; for (let i = 1; i < strs.length; i++) { const len = twoStrLongestCommonPrefix(first, strs[i]); minLen = Math .min(len, minLen); } return first.slice( 0 , minLen); }; function twoStrLongestCommonPrefix ( s, t ) { let i = 0 , j = 0 ; let cnt = 0 ; while (i <s.length && j <t.length) { console .log(s[i], t[j] , cnt) if (s[i] === t[j]) { cnt++; } else { return cnt; } i++; j++; } return cnt; } Copy code

The longest substring without repeated characters [double pointer]

[LeetCode through train]: 3 longest substring without repeated characters (medium)

answer

Click to expand view
/** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function ( s ) { let window = {}; let left = 0 , right = 0 ; let maxLen = 0 , maxStr = '' ; while ( right <s.length) { let c = s[right]; right++; if ( window [c]) window [c]++; else window [c] = 1 while ( window [c]> 1 ) { let d = s[left]; left++; window [d]--; } if (maxLen <right-left) { maxLen = right-left; } } return maxLen; }; Copy code

[Real Interview Questions] Minimum Coverage Substring [Sliding Window]

[LeetCode through train]: 76 minimum coverage substring (difficult)

answer

Click to expand view
/** * @param {string} s * @param {string} t * @return {string} */ var minWindow = function(s, t) { let need = {}, window = {}; for (let c of t) { if (!need[c]) need[c] = 1; else need[c]++; } let left = 0, right = 0; let valid = 0, len = Object.keys(need).length; let minLen = s.length + 1, minStr = ''; while (right < s.length) { const d = s[right]; right++; if (!window[d]) window[d] = 1; else window[d]++; if (need[d] && need[d] === window[d]) { valid++; } console .log( 'left-right' , left, right); while (valid === len) { if (right-left <minLen) { minLen = right-left; minStr = s.slice(left, right); } console .lo let c = s[left]; left++; window [c]--; if (need[c] && window [c] <need[c]) { valid--; } } } return minStr; }; Copy code

[ ] High-frequency algorithm question series: array problems

There are mainly several types of high-frequency exam questions:

  • Matryoshka Envelope Question [Difficulty] [Sequence + Longest Ascending Subsequence] [Real Interview Question]
  • The longest continuous increasing sequence [simple] [dual pointer]
  • The longest continuous sequence [difficulty] [hash table]
  • The container with the most water [difficulty] [interview question]
  • Find the median of two positively ordered arrays [difficulty] [double pointer]
  • Delete duplicate items in the ordered array [Simple] [Quick and slow pointer]
  • Sub-array whose sum is K [medium] [hash table]
  • nSum problem [series] [simple] [hash table]
  • Receiving the rain [difficulty] [violence + memo optimization] [real interview questions]
  • Jumping game [series] [medium] [greedy algorithm]

[Real Interview Questions] Russian Doll s Envelope Question [Sort + Longest Ascending Subsequence]

[LeetCode through train]: 354 Matryoshka envelope problem (difficult)

answer

Click to expand view
/** * @param {number[][]} envelopes * @return {number} */ var maxEnvelopes = function ( envelopes ) { if (envelopes.length === 1 ) return 1 ; envelopes.sort((a, b) => { if (a[0] !== b[0]) return a[0] - b[0]; else return b[1] - a[1]; }); let LISArr = []; for (let [key, value] of envelopes) { LISArr.push(value); } console.log( LISArr); return LIS(LISArr); }; function LIS ( arr ) { let dp = []; let maxAns = 0 ; for ( let i = 0 ; i <arr.length; i++) { dp[i] = 1 ; } for ( let i = 1 ; i <arr.length; i++) { for ( let j = i; j >= 0 ; j--) { if (arr[i]> arr[j]) { dp[i] = Math .max(dp[i], dp[j] + 1 ) } maxAns = Math .max(maxAns, dp[i]); } } return maxAns; } Copy code

The longest continuous increasing sequence [fast and slow pointer]

[LeetCode through train]: 674 longest continuous increasing sequence (simple)

answer

Click to expand view
/** * @param {number[]} nums * @return {number} */ var findLengthOfLCIS = function(nums) { if (nums.length === 0) return 0; const n = nums.length; let left = 0, right = 1; let globalMaxLen = 1, maxLen = 1; while (right < n) { if (nums[right] > nums[left]) maxLen++; else { maxLen = 1 ; } left++; right++; globalMaxLen = Math .max(globalMaxLen, maxLen); } return globalMaxLen; }; Copy code

The longest continuous sequence [Hash table]

[LeetCode through train]: 128 longest continuous sequence (difficult)

answer

Click to expand view
/** * @param {number[]} nums * @return {number} */ var longestConsecutive = function(nums) { if (nums.length === 0) return 0; const set = new Set(nums); const n = nums.length; let globalLongest = 1; for (let i = 0; i < n; i++) { if (!set.has(nums[i] - 1)) { let longest = 1 ; let currentNum = nums[i]; while (set.has(currentNum + 1 )) { currentNum += 1 ; longest++; } globalLongest = Math .max(globalLongest, longest); } } return globalLongest; }; Copy code

[Real Interview Question] The container with the most water [Hash Table]

[LeetCode through train]: 11 containers with the most water (medium)

answer

Click to expand view
/** * @param {number[]} height * @return {number} */ var maxArea = function(height) { let n = height.length; let left = 0, right = n - 1; let maxOpacity = 0; while (left < right) { let res = Math.min(height[left], height[right]) * (right - left); maxOpacity = Math.max(maxOpacity, res); if (height[left] < height[right]) left++ else right--; } return maxOpacity; }; Copy code

Find the median of two positive arrays [double pointer]

[LeetCode through train]: 4 Find the median of two positive arrays (difficult)

answer

Click to expand view
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number} */ var findMedianSortedArrays = function ( nums1, nums2 ) { let m = nums1.length, n = nums2.length; let i = 0 , j = 0 ; let newArr = []; while (i <m && j <n) { if (nums1[i] <nums2[j]) { newArr.push(nums1[i++]); } else { newArr.push(nums2[j++]); } } newArr = newArr.concat(i <m? nums1.slice(i): nums2.slice(j)); const len = newArr.length; Console .log (newArr) IF (len% 2 === 0 ) { return (newArr [len/2 ] + newArr [len/2 - . 1 ])/2 ; } else { return newArr[ Math .floor(len/2 )]; } }; Copy code

Delete duplicate items in the ordered array [fast and slow pointer]

[LeetCode through train]: 26 delete duplicates in the ordered array (simple)

answer

Click to expand view
/** * @param {number[]} nums * @return {number} */ var removeDuplicates = function ( nums ) { if (nums.length <= 1 ) return nums.length; let lo = 0 , hi = 0 ; while ( hi <nums.length) { while (nums[lo] === nums[hi] && hi <nums.length) hi++; if (nums[lo] !== nums[hi] && hi <nums.length) { lo++; nums[lo] = nums[hi]; } hi++; } return lo + 1 ; }; Copy code

The sub-array whose sum is K [hash table]

[LeetCode through train]: 560 and a sub-array of K (medium)

answer

Click to expand view
/** * @param {number[]} nums * @param {number} k * @return {number} */ var subarraySum = function ( nums, k ) { let cnt = 0 ; let sum0_i = 0 , sum0_j = 0 ; let map = new Map (); map.set( 0 , 1 ); for ( let i = 0 ; i <= nums.length; i++) { sum0_i += nums[i]; sum0_j = sum0_i-k; console .log( 'map' , sum0_j, map.get(sum0_j)) if (map.has(sum0_j)) { cnt += map.get(sum0_j); } let sumCnt = map.get(sum0_i) || 0 ; map.set(sum0_i, sumCnt + 1 ); } return cnt; }; Copy code

nSum problem [hash table] [series]

Due to space limitations, only the code template of the first question is given here, which is also a real question that is often taken.

answer

Click to expand view
/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function ( nums, target ) { let map2 = new Map (); for ( let i = 0 ; i <nums.length; i++) { map2.set(nums[i], i); } for ( let i = 0 ; i <nums.length; i++) { if (map2.has(target-nums[i]) && map2.get(target-nums[i]) !== i) return [i, map2.get(target-nums[i])] } }; Copy code

[Real Interview Questions] Receiving Rainwater [Violence + Memo Optimization]

[LeetCode through train]: 42 catch rainwater (difficulty)

answer

Click to expand view
/** * @param {number[]} height * @return {number} */ var trap = function ( height ) { let l_max = [], r_max = []; let len = height.length; let maxCapacity = 0 ; for ( let i = 0 ; i <len; i++) { l_max[i] = height[i]; r_max[i] = height[i]; } for ( let i = 1 ; i <len; i++) { l_max[i] = Math .max(l_max[i- 1 ], height[i]); } for ( let j = len- 2 ; j >= 0 ; j--) { r_max[j] = Math .max(r_max[j + 1 ], height[j]); } for ( let i = 0 ; i <len; i++) { maxCapacity += Math .min(l_max[i], r_max[i])-height[i]; } return maxCapacity; }; Copy code

Jumping game [greedy algorithm] [series]

Due to space limitations, only the code template of the first question is given here, which is also a real question that is often taken.

answer

Click to expand view
/** * @param {number[]} nums * @return {boolean} */ var canJump = function ( nums ) { let faster = 0 ; for ( let i = 0 ; i <nums.length- 1 ; i++) { faster = Math .max(faster, i + nums[i]); if (faster <= i) return false ; } return faster >= nums.length- 1 ; }; Copy code

High-frequency algorithm question series: Binary tree

There are mainly the following types of high-frequency exam questions:

  • The nearest common ancestor of the binary tree [simple] [binary tree]
  • Search in binary search tree [simple] [binary tree]
  • Delete the node in the binary search tree [medium] [binary tree]
  • Number of nodes in a complete binary tree [medium] [binary tree]
  • Zigzag sequence traversal of binary tree [medium] [binary tree]

The nearest common ancestor of a binary tree [binary tree]

[LeetCode through train]: 236 the nearest common ancestor of the binary tree (simple)

answer

Click to expand view
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} */ /** * @param {TreeNode} root * @param {TreeNode} p * @param {TreeNode} q * @return {TreeNode} */ let visited; let parent; var lowestCommonAncestor = function ( root, p, q ) { visited = new Set (); parent = new Map (); dfs(root); while (p != null ) { visited.add(p.val); p = parent.get(p.val); } while (q != null ) { if (visited.has(q.val)) { return q; } q = parent.get(q.val); } return null ; }; function dfs ( root ) { if (root.left != null ) { parent.set(root.left.val, root); dfs(root.left); } if (root.right != null ) { parent.set(root.right.val, root); dfs(root.right); } } Copy code

Search in Binary Search Tree Binary Tree

[LeetCode through train]: Search in 700 binary search tree (simple)

answer

Click to expand view
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @param {number} val * @return {TreeNode} */ var searchBST = function(root, val) { if (root == null) return null; if (root.val === val) return root; if (root.val > val) { return searchBST(root.left, val); } else if (root.val <val) { return searchBST(root.right, val); } }; Copy code

Delete the node in the binary search tree [binary tree]

[LeetCode through train]: 450 delete nodes in the binary search tree (medium)

answer

Click to expand view
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} */ /** * @param {TreeNode} root * @param {number} key * @return {TreeNode} */ var deleteNode = function(root, key) { if (root == null) return null; if (root.val === key) { if (root.left == null && root.right == null) return null; if (root.left == null) return root.right; if (root.right == null) return root.left; if (root.left != null && root.right != null) { let target = getMinTreeMaxNode(root.left); root.val = target.val; root.left = deleteNode(root.left, target.val); } } if (root.val < key) { root.right = deleteNode(root.right, key); } else if (root.val > key) { root.left = deleteNode(root.left, key); } return root; }; function getMinTreeMaxNode ( root ) { if (root.right == null ) return root; return getMinTreeMaxNode(root.right); } Copy code

The number of nodes in a complete binary tree [binary tree]

[LeetCode through train]: 222 the number of nodes in a complete binary tree (medium)

answer

Click to expand view
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} */ /** * @param {TreeNode} root * @return {number} */ var countNodes = function(root) { if (root == null) return 0; let l = root, r = root; let lh = 0, rh = 0; while (l != null) { l = l.left; lh++; } while (r != null) { r = r.right; rh++; } if (lh === rh) { return Math.pow(2, lh) - 1; } return 1 + countNodes(root.left) + countNodes(root.right); }; Copy code

Zigzag sequence traversal of binary tree [binary tree]

[LeetCode through train]: 103 zigzag sequence traversal of binary tree (medium)

answer

Click to expand view
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} */ /** * @param {TreeNode} root * @return {number[][]} */ let res; var zigzagLevelOrder = function ( root ) { if (root == null ) return []; res = []; BFS(root, true ); return res; }; function BFS(root, inOrder) { let arr = []; let resItem = []; let node; let stack1 = new Stack(); let stack2 = new Stack(); // let flag; stack1.push(root); res.push([root.val]); inOrder = !inOrder; while (!stack1.isEmpty() || !stack2.isEmpty()) { if (stack1.isEmpty()) { flag = 'stack1'; } else if (stack2.isEmpty()) { flag = 'stack2'; } // if (flag === 'stack2' && !stack1.isEmpty()) node = stack1.pop(); else if (flag === 'stack1' && !stack2.isEmpty()) node = stack2.pop(); if (inOrder) { if (node.left) { if (flag === 'stack1') { stack1.push(node.left); } else { stack2.push(node.left); } resItem.push(node.left.val); } if (node.right) { if (flag === 'stack1') { stack1.push(node.right); } else { stack2.push(node.right); } resItem.push(node.right.val); } } else { if (node.right) { if (flag === 'stack1') { stack1.push(node.right); } else { stack2.push(node.right); } resItem.push(node.right.val); } if (node.left) { if (flag === 'stack1') { stack1.push(node.left); } else { stack2.push(node.left); } resItem.push(node.left.val); } } // if ((flag === 'stack2' && stack1.isEmpty()) || (flag === 'stack1' && stack2.isEmpty())) { inOrder = !inOrder; // if (resItem.length > 0) { res.push(resItem); } resItem = []; } } } class Stack { constructor() { this.count = 0; this.items = []; } push(element) { this.items[this.count] = element; this.count++; } pop () { if ( this .isEmpty()) return undefined ; const element = this .items[ this .count- 1 ]; delete this .items[ this .count- 1 ]; this .count--; return element; } size () { return this .count; } isEmpty () { return this .size() === 0 ; } } Copy code

High-frequency algorithm question series: Sorting algorithm

There are mainly the following types of high-frequency exam questions:

  • Detonate the balloon with the least number of arrows [Medium] [Sort]
  • Combine interval [medium] [sort algorithm + interval question] [interview question]

Detonate the balloon with the least number of arrows [Sort Algorithm]

[LeetCode through train]: 452 Use the least number of arrows to detonate the balloon (medium)

answer

Click to expand view
/** * @param {number[][]} points * @return {number} */ var findMinArrowShots = function ( points ) { if (points.length === 0 ) return 0 ; points.sort( ( a, b ) => a[ 1 ]-b[ 1 ]); let cnt = 1 ; let resArr = [points[ 0 ]]; let curr, last; for ( let i = 1 ; i <points.length; i++) { curr = points[i]; last = resArr[resArr.length- 1 ]; if (curr[ 0 ]> last[ 1 ]) { resArr.push(curr); cnt++; } } return cnt; }; Copy code

Combine intervals [sort algorithm + interval problem]

[LeetCode through train]: 56 combined section (medium)

answer

Click to expand view
/** * @param {number[][]} intervals * @return {number[][]} */ var merge = function(intervals) { if (intervals.length === 0) return []; intervals.sort((a, b) => a[0] - b[0]); let mergeArr = [intervals[0]]; let last, curr; for (let j = 1; j < intervals.length; j++) { last = mergeArr[mergeArr.length - 1]; curr = intervals[j]; if (last[ 1 ] >= curr[ 0 ]) { last[ 1 ] = Math .max(curr[ 1 ], last[ 1 ]); } else { mergeArr.push(curr); } } return mergeArr; }; Copy code

High-frequency algorithm question series: binary search

There are mainly the following types of high-frequency exam questions:

  • Find the median of two positively ordered arrays [difficulty] [binary search]
  • Judgment subsequence [simple] [binary search]
  • Find the first and last position of the element in the sorted array [medium] [binary search]

Find the median of two positively ordered arrays [binary search]

[LeetCode through train]: 4 Find the median of two positive arrays (difficult)

answer

Click to expand view
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number} */ var findMedianSortedArrays = function(nums1, nums2) { let m = nums1.length, n = nums2.length; let i = 0, j = 0; let newArr = []; while (i < m && j < n) { if (nums1[i] < nums2[j]) { newArr.push(nums1[i++]); } else { newArr.push(nums2[j++]); } } newArr = newArr.concat(i <m? nums1.slice(i): nums2.slice(j)); const len = newArr.length; Console .log (newArr) IF (len% 2 === 0 ) { return (newArr [len/2 ] + newArr [len/2 - . 1 ])/2 ; } else { return newArr[ Math .floor(len/2 )]; } }; Copy code

Judgment subsequence [binary search]

[LeetCode through train]: 392 judgment subsequence (simple)

answer

Click to expand view
/** * @param {string} s * @param {string} t * @return {boolean} */ var isSubsequence = function(s, t) { let hash = {}; for (let i = 0; i < t.length; i++) { if (!hash[t[i]]) hash[t[i]] = []; hash[t[i]].push(i); } let lastMaxIndex = 0; for (let i = 0; i < s.length; i++) { if (hash[s[i]]) { const index = binarySearch(hash[s[i]], lastMaxIndex); console.log('index', index, hash[s[i]]); if (index === -1) return false; lastMaxIndex = hash[s[i]][index] + 1; } else return false; } return true; }; function binarySearch ( array, targetIndex ) { let left = 0 , right = array.length; while (left <right) { let mid = left + Math .floor((right-left)/ 2 ); if (array[mid] >= targetIndex) { right = mid; } else if (array[mid] <targetIndex) { left = mid + 1 ; } } if (left >= array.length || array[left] <targetIndex) return - 1 ; return left; } Copy code

Find the first and last position of the element in the sorted array [Binary search]

[LeetCode through train]: 34 Find the first and last positions of the element in the sorted array (medium)

answer

Click to expand view
/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var searchRange = function ( nums, target ) { const left = leftBound(nums, target); const right = rightBound (nums, target); return [left, right]; }; function leftBound(nums, target) { let left = 0; let right = nums.length - 1; while (left <= right) { let mid = Math.floor(left + (right - left)/2); if (nums[mid] === target) { right = mid - 1; } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } } if (left >= nums.length || nums[left] !== target) { return -1; } return left; } function rightBound(nums, target) { let left = 0; let right = nums.length - 1; while (left <= right) { let mid = Math.floor(left + (right - left)/2); if (nums[mid] === target) { left = mid + 1; } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid]> target) { right = mid- 1 ; } } if (right < 0 || nums[right] !== target) { return - 1 ; } return right; } Copy code

High-frequency algorithm question series: dynamic programming

There are mainly the following types of high-frequency exam questions:

  • The longest increasing subsequence [medium] [dynamic programming]
  • Change change [medium] [dynamic programming] [real interview questions]
  • The longest common subsequence [medium] [dynamic programming] [interview question]
  • Edit distance [difficulty] [dynamic programming]
  • The longest palindrome subsequence [medium] [dynamic programming] [interview question]
  • Maximum sub-sequence and [simple] [dynamic programming] [interview question]
  • The Best Time to Buy and Sell Stocks [Series] [Dynamic Programming] [Real Interview Questions]

The longest increasing subsequence [dynamic programming]

[LeetCode through train]: 300 longest increasing subsequence (medium)

answer

Click to expand view
/** * @param {number[]} nums * @return {number} */ var lengthOfLIS = function ( nums ) { let maxLen = 0 , n = nums.length; let dp = []; for ( let i = 0; i < n; i++) { dp[i] = 1; } for ( let i = 0 ; i <n; i++) { for ( let j = 0 ; j <i; j++) { if (nums[i] > nums[j]) { dp[i] = Math .max(dp[i], dp[j] + 1 ); } } maxLen = Math .max(maxLen, dp[i]); } return maxLen; }; Copy code

[Real Interview Questions] Change Change [Dynamic Planning]

[LeetCode through train]: 322 change exchange (medium)

answer

Click to expand view
/** * @param {number[]} coins * @param {number} amount * @return {number} */ var coinChange = function ( coins, amount ) { if (amount === 0 ) return 0 ; let dp = [] ; for ( let i = 0; i <= amount; i++) { dp[i] = amount + 1 ; } dp[ 0 ] = 0 ; for ( let i = 0 ; i <= amount; i++) { for ( let j = 0 ; j <coins.length; j++) { if (i >= coins[j]) { dp[i] = Math .min(dp[i-coins[j]] + 1 , dp[i]) } } } return dp[amount] === amount + 1 ? -1 : dp[amount]; }; Copy code

[True Interview Question] The longest common subsequence [Dynamic Programming]

[LeetCode through train]: 1143 longest common subsequence (medium)

answer

Click to expand view
/** * @param {string} text1 * @param {string} text2 * @return {number} */ var longestCommonSubsequence = function(text1, text2) { let n1 = text1.length, n2 = text2.length; let dp = []; for (let i = -1; i < n1; i++) { dp[i] = []; for (let j = -1; j < n2;j++) { dp[i][j] = 0; } } for ( let i = 0 ; i <n1; i++) { for ( let j = 0 ; j <n2; j++) { if (text1[i] === text2[j]) { dp[i][j] = Math .max(dp[i][j], dp[i- 1 ][j- 1 ] + 1 ); } else { dp[i][j] = Math .max(dp[i- 1 ][j], dp[i][j- 1 ]) } } } return DP [N1 - . 1 ] [N2 - . 1 ]; }; Copy code

Edit distance [Dynamic programming]

[LeetCode through train]: 72 edit distance (difficult)

answer

Click to expand view
/** * @param {string} word1 * @param {string} word2 * @return {number} */ var minDistance = function(word1, word2) { let len1 = word1.length, len2 = word2.length; let dp = []; for (let i = 0; i <= len1; i++) { dp[i] = []; for (let j = 0; j <= len2; j++) { dp[i][j] = 0; if (i === 0) { dp[i][j] = j; } if (j === 0) { dp[i][j] = i; } } } for (let i = 1; i <= len1; i++) { for (let j = 1; j <= len2; j++) { if (word1[i - 1] === word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1); } } } return dp[len1][len2]; }; Copy code

[True Interview Question] The longest palindrome subsequence [Dynamic Programming]

[LeetCode through train]: 516 longest palindrome subsequence (medium)

answer

Click to expand view
/** * @param {string} s * @return {number} */ var longestPalindromeSubseq = function ( s ) { let dp = []; for ( let i = 0 ; i <s.length; i++) { dp[i] = []; for ( let j = 0 ; j <s.length; j++) { dp[i][j] = 0 ; } dp[i][i] = 1 ; } for ( let i = s.length- 1 ; i >= 0 ; i--) { for ( let j = i + 1 ; j <s.length; j++) { if (s[i] === s[ j]) { dp[i][j] = dp[i + 1 ][j- 1 ] + 2 ; } else { dp[i][j] = Math .max(dp[i + 1 ][j], dp[i][j- 1 ]); } } } return dp[ 0 ][s.length- 1 ]; }; Copy code

[Real Interview Questions] Maximum Subsequence and [Dynamic Programming]

[LeetCode through train]: 53 largest subsequence sum (simple)

answer

Click to expand view
/** * @param {number[]} nums * @return {number} */ var maxSubArray = function(nums) { let maxSum = -Infinity; let dp = [], n = nums.length; for (let i = -1; i < n; i++) { dp[i] = 0; } for (let i = 0; i < n; i++) { dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]); maxSum = Math.max(maxSum, dp[i]); } return maxSum; }; Copy code

[Real Interview Questions] The best time to buy and sell stocks [Dynamic Planning]

Due to space limitations, only the code template of the first question is given here. It is also a real question that is often tested. The author encountered it during the interview with byte beating.

answer

Click to expand view
/** * @param {number[]} prices * @return {number} */ var maxProfit = function(prices) { let dp = []; for (let i = -1; i < prices.length; i++) { dp[i] = [] for (let j = 0; j <= 1; j++) { dp[i][j] = []; dp[i][j][0] = 0; dp[i][j][1] = 0; if (i === -1) { dp[i][j][1] = -Infinity; } if (j === 0) { dp[i][j][1] = -Infinity; } if (j === -1) { dp[i][j][1] = -Infinity; } } } for (let i = 0; i < prices.length; i++) { for (let j = 1; j <= 1; j++) { dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]); dp[i][j][ 1 ] = Math .max(dp[i- 1 ][j][ 1 ], dp[i- 1 ][j- 1 ][ 0 ]-prices[i]); } } return dp[prices.length- 1 ][ 1 ][ 0 ]; }; Copy code

High-frequency algorithm question series: BFS

There are mainly the following types of high-frequency exam questions:

  • Turn on the turntable lock [medium] [BFS]
  • The minimum depth of the binary tree [simple] [BFS]

Turn on the turntable lock [BFS]

[LeetCode through train]: 752 Open the turntable lock (medium)

answer

Click to expand view
/** * @param {string[]} deadends * @param {string} target * @return {number} */ var openLock = function(deadends, target) { let queue = new Queue(); let visited = new Set(); let step = 0; queue.push('0000'); visited.add('0000'); while (!queue.isEmpty()) { let size = queue.size(); for (let i = 0; i < size; i++) { let str = queue.pop(); if (deadends.includes(str)) continue; if (target === str) { return step; } for (let j = 0; j < 4; j++) { let plusStr = plusOne(str, j); let minusStr = minusOne(str, j); if (!visited.has(plusStr)) { queue.push(plusStr); visited.add(plusStr) } if (!visited.has(minusStr)) { queue.push(minusStr); visited.add(minusStr) } } } step++; } return -1; }; function plusOne(str, index) { let strArr = str.split(''); if (strArr[index] === '9') { strArr[index] = '0' } else { strArr[index] = (Number(strArr[index]) + 1).toString() } return strArr.join(''); } function minusOne(str, index) { let strArr = str.split(''); if (strArr[index] === '0') { strArr[index] = '9' } else { strArr[index] = (Number(strArr[index]) - 1).toString() } return strArr.join(''); } class Queue { constructor() { this .items = []; this.count = 0; this.lowerCount = 0; } push ( elem) { this.items[this.count++] = elem; } pop() { if ( this.isEmpty()) { return; } const elem = this .items[ this .lowerCount]; delete this .items[ this .lowerCount]; this .lowerCount++; return elem; } isEmpty() { if ( this .size() === 0 ) return true ; return false; } size () { return this .count- this .lowerCount; } } Copy code

The minimum depth of the binary tree [BFS]

[LeetCode through train]: 111 minimum depth of binary tree (simple)

answer

Click to expand view
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} */ /** * @param {TreeNode} root * @return {number} */ var minDepth = function(root) { if (root == null) return 0; let depth = 1; let queue = new Queue(); queue.push(root); while (!queue.isEmpty()) { let size = queue.size(); for (let i = 0; i < size; i++) { const node = queue.pop(); if (node.left == null && node.right == null) return depth; if (node.left) { queue.push(node.left); } if (node.right) { queue.push(node.right); } } depth++; } return depth; }; class Queue { constructor() { this.items = []; this.count = 0; this.lowerCount = 0; } push(elem) { this.items[this.count++] = elem; } pop() { if (this.isEmpty()) { return; } const elem = this .items[ this .lowerCount]; delete this .items[ this .lowerCount]; this .lowerCount++; return elem; } isEmpty() { if ( this .size() === 0 ) return true ; return false ; } size () { return this .count- this .lowerCount; } } Copy code

High-frequency algorithm question series: stack

There are mainly the following types of high-frequency exam questions:

  • Minimal stack [simple] [stack]
  • Effective brackets [medium] [stack] [real interview questions]
  • Simplified path [medium] [stack]
  • The next bigger element [series] [stack]

Minimal stack [stack]

[LeetCode through train]: 155 smallest stack (simple)

answer

Click to expand view
/** * initialize your data structure here. */ var MinStack = function () { this.stack = []; this.minArr = []; this.count = 0; this.min = Number.MAX_SAFE_INTEGER; }; /** * @param {number} x * @return {void} */ MinStack.prototype.push = function(x) { this.min = Math.min(this.min, x); this.minArr[this.count] = this.min; this.stack[this.count] = x; this.count++; }; /** * @return {void} */ MinStack.prototype.pop = function() { const element = this.stack[this.count - 1]; if (this.count - 2 >= 0) this.min = this.minArr[this.count - 2]; else this.min = Number.MAX_SAFE_INTEGER; delete this.stack[this.count - 1]; delete this.minArr[this.count - 1]; this.count--; return element; }; /** * @return {number} */ MinStack.prototype.top = function() { if (this.count >= 1) { return this.stack[this.count - 1]; } return null; }; /** * @return {number} */ MinStack.prototype.getMin = function() { const element = this.minArr[this.count - 1]; return element; }; /** * Your MinStack object will be instantiated and called as such: * var obj = new MinStack() * obj.push(x) * obj.pop() * var param_3 = obj.top() * var param_4 = obj.getMin() */ Copy code

[Series] The next bigger element [Stack]

Due to space limitations, only the code template for the first question is given here

answer

Click to expand view
/** * @param {number[]} nums * @return {number[]} */ var nextGreaterElements = function ( nums ) { let ans = []; let stack = new Stack(); const n = nums.length; for ( let i = 2 * n- 1 ; i >= 0 ; i--) { while (!stack.isEmpty() && stack.top() <= nums[i % n]) { stack.pop(); } ans[i % n] = stack.isEmpty() ? -1 : stack.top(); stack.push(nums[i % n]); } return ans; }; class Stack { constructor () { this .count = 0 ; this .items = []; } top () { if ( this .isEmpty()) return undefined ; return this .items[ this .count- 1 ]; } push ( element ) { this .items[ this .count] = element; this .count++; } pop () { if ( this .isEmpty()) return undefined ; const element = this .items[ this .count- 1 ]; delete this .items[ this .count- 1 ]; this .count--; return element; } isEmpty () { return this .size() === 0 ; } size () { return this .count; } } Copy code

[Real Interview Questions] Effective Brackets [Stack]

[LeetCode through train]: 20 valid brackets (medium)

answer

Click to expand view
/** * @param {string} s * @return {boolean} */ var isValid = function(s) { if (s.length === 0) { return true; } if (s.length % 2 !== 0) { return false; } let map = { ')': '(', ']': '[', '}': '{', }; let left = ['(', '[', '{']; let right = [')', ']', '}']; let stack = new Stack(); for (let i = 0; i < s.length; i++) { if (!right.includes(s[i])) { stack.push(s[i]); } else { const matchStr = map[s[i]]; while (!stack.isEmpty()) { const element = stack.pop(); if (left.includes(element) && matchStr !== element) return false ; if (element === matchStr) break; } } } return stack.isEmpty(); }; class Stack { constructor() { this .count = 0 ; this.items = []; } push ( element ) { this .items[ this .count] = element; this .count++; } pop () { if ( this .isEmpty()) return undefined ; const element = this .items[ this .count- 1 ]; delete this .items[ this .count- 1 ]; this .count--; return element; } isEmpty () { return this .size() === 0 ; } size () { return this .count; } } Copy code

Simplify the path [stack]

[LeetCode through train]: 71 simplified path (medium)

answer

Click to expand view
/** * @param {string} path * @return {string} */ var simplifyPath = function ( path ) { let newPath = path.split( '/' ); newPath = newPath.filter(item => item !== ""); const stack = new Stack(); for (let s of newPath) { if (s === '..') stack.pop(); else if (s !== '.') stack.push(s); } if (stack.isEmpty()) return '/'; let str = ''; while (!stack.isEmpty()) { const element = stack.pop(); str = '/' + element + str; } return str; }; function handleBack(stack, tag, num) { if (!stack.isEmpty()) return num; const element = stack.pop(); if (element === '..') return handleBack(stack, tag, num + 1); else { stack.push(element); return num; } } class Stack { constructor() { this.count = 0; this.items = []; } push(element) { this.items[this.count] = element; this.count++; } pop() { if (this.isEmpty()) return undefined; const element = this.items[this.count - 1]; delete this.items[this.count - 1]; this.count--; return element; } size() { return this.count; } isEmpty() { return this.size() === 0; } }

DFS

  • DFS
  • DFS

DFS

LeetCode 695

/** * @param {number[][]} grid * @return {number} */ let maxX, maxY;let visited;let globalMaxArea; var maxAreaOfIsland = function(grid) { visited = new Set(); maxX = grid.length; maxY = grid[0].length; globalMaxArea = 0; for (let i = 0; i < maxX; i++) { for (let j = 0; j < maxY; j++) { if (grid[i][j] === 1) { visited.add(`(${i}, ${j})`); globalMaxArea = Math.max(globalMaxArea, dfs(grid, i, j)); } visited.clear(); } } return globalMaxArea; }; function dfs(grid, x, y) { let res = 1; for (let i = -1; i <= 1; i++) { for (let j = -1; j <= 1; j++) { if (Math.abs(i) === Math.abs(j)) continue; const newX = x + i; const newY = y + j; if (newX >= maxX || newX < 0 || newY >= maxY || newY < 0) continue; if (visited.has(`(${newX}, ${newY})`)) continue; visited.add(`(${newX}, ${newY})`); const areaCnt = grid[newX][newY] if (areaCnt === 1) { const cnt = dfs(grid, newX, newY); res += cnt; } } } return res; }

DFS

LeetCode 100

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} p * @param {TreeNode} q * @return {boolean} */ 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); };

  • N
  • IP

N

LeetCode 51 N

/** * @param {number} n * @return {string[][]} */ let result = []; var solveNQueens = function(n) { result = []; let board = []; for (let i = 0; i < n; i++) { board[i] = []; for (let j = 0; j < n; j++) { board[i][j] = '.' } } backtrack(0, board, n); return result; }; function deepClone(board) { let res = []; for (let i = 0; i < board.length; i++) { res.push(board[i].join('')); } return res; } function backtrack(row, board, n) { if (row === n) { result.push(deepClone(board)); return; } for (let j = 0; j < n; j++) { if (checkInValid(board, row, j, n)) continue; board[row][j] = 'Q'; backtrack(row + 1, board, n); board[row][j] = '.'; } } function checkInValid(board, row, column, n) { // for (let i = 0; i < n; i++) { if (board[i][column] === 'Q') return true; } for (let i = row - 1, j = column + 1; i >= 0 && j < n; i--, j++) { if (board[i][j] === 'Q') return true; } for (let i = row - 1, j = column - 1; i >= 0 && j >= 0; i--, j--) { if (board[i][j] === 'Q') return true; } return false; }

LeetCode 46

/** * @param {number[]} nums * @return {number[][]} */ let results = [];var permute = function(nums) { results = []; backtrack(nums, []); return results; }; function backtrack(nums, track) { if (nums.length === track.length) { results.push(track.slice()); return; } for (let i = 0; i < nums.length; i++) { if (track.includes(nums[i])) continue; track.push(nums[i]); backtrack(nums, track); track.pop(); } }

LeetCode 22

/** * @param {number} n * @return {string[]} */ var generateParenthesis = function(n) { let validRes = []; backtrack(n * 2, validRes, ''); return validRes; }; function backtrack(len, validRes, bracket) { if (bracket.length === len) { if (isValidCombination(bracket)) { validRes.push(bracket); } return; } for (let str of ['(', ')']) { bracket += str; backtrack(len, validRes, bracket); bracket = bracket.slice(0, bracket.length - 1); } } function isValidCombination(bracket) { let stack = new Stack(); for (let i = 0; i < bracket.length; i++) { const str = bracket[i]; if (str === '(') { stack.push(str); } else if (str === ')') { const top = stack.pop(); if (top !== '(') return false; } } return stack.isEmpty(); } class Stack { constructor() { this.count = 0; this.items = []; } push(element) { this.items[this.count] = element; this.count++; } pop() { if (this.isEmpty()) return; const element = this.items[this.count - 1]; delete this.items[this.count - 1]; this.count--; return element; } size() { return this.count; } isEmpty() { return this.size() === 0; } }

IP

LeetCode 93 IP

/** * @param {string} s * @return {string[]} */ var restoreIpAddresses = function(s) { if (s.length > 12) return []; let res = []; const track = []; backtrack(s, track, res); return res; }; function backtrack(s, track, res) { if (track.length === 4 && s.length === 0) { res.push(track.join('.')); return; } let len = s.length >= 3 ? 3 : s.length; for (let i = 0; i < len; i++) { const c = s.slice(0, i + 1); if (parseInt(c) > 255) continue; if (i >= 1 && parseInt(c) < parseInt((1 + '0'.repeat(i)))) continue; track.push(c); backtrack(s.slice(i + 1), track, res); track.pop(); } }

LeetCode 78

/** * @param {number[]} nums * @return {number[][]} */ var subsets = function(nums) { if (nums.length === 0) return [[]]; let resArr = []; backtrack(nums, 0, [], resArr); return resArr; }; function backtrack(nums, index, subArr, resArr) { if (Array.isArray(subArr)) { resArr.push(subArr.slice()); } if (index === nums.length) { return; } for (let i = index; i < nums.length; i++) { subArr.push(nums[i]); backtrack(nums, i + 1, subArr, resArr); subArr.pop(nums[i]); } }

labuladong Github 86.2K Star

~