字節(jié)跳動(dòng)最匙考的 64 道JS算法題

緣起

現(xiàn)在大廠面試中，算法題幾乎為必考項(xiàng)角骤，且近幾年頻現(xiàn) LeetCode 真題隅忿，此篇為拿到字節(jié)、騰訊邦尊、京東 Offer 的筆者本人在準(zhǔn)備面試過(guò)程中親自刷過(guò)以及遇到過(guò)高頻算法題背桐。文章內(nèi)容會(huì)分模塊整理，對(duì)于筆者在面試過(guò)程中遇到的真題蝉揍，會(huì)給予著重 【??】標(biāo)出链峭。

同時(shí)，可以毫不客氣的說(shuō)又沾，如果你準(zhǔn)備時(shí)間有限弊仪，又想追求算法題準(zhǔn)備效率最大化熙卡，那么你只需要按照大綱把下面的題目刷完，并把代碼爛熟于心励饵，就幾乎可以應(yīng)對(duì) 90% 的面試算法考題了驳癌。

整理這篇內(nèi)容的目的一個(gè)是筆者在之前準(zhǔn)備面試時(shí)的一點(diǎn)積累，而它確實(shí)也幫助筆者在面試算法題中過(guò)關(guān)斬將役听，同時(shí)呢颓鲜，也希望能夠在金三銀四給予拼搏的你，一點(diǎn)點(diǎn)幫助就好禾嫉！??

文末有福利 ：）??

本篇內(nèi)容包括如下模塊：

  • 高頻算法題系列：鏈表
  • 【??】【有真題】高頻算法題系列：字符串
  • 【??】【有真題】高頻算法題系列：數(shù)組問(wèn)題
  • 高頻算法題系列：二叉樹(shù)
  • 【??】高頻算法題系列：排序算法
  • 【??】高頻算法題系列：二分查找
  • 【??】高頻算法題系列：動(dòng)態(tài)規(guī)劃
  • 高頻算法題系列：BFS
  • 【??】高頻算法題系列：棧
  • 【??】高頻算法題系列：DFS
  • 【??】高頻算法題系列：回溯算法

其中標(biāo)??的部分代表非常高頻的考題灾杰，其中不乏筆者遇到的原題蚊丐。其中對(duì)于每一類熙参，首先會(huì)列出包含的考題，然后針對(duì)每一道考題會(huì)給出難度麦备、考察知識(shí)點(diǎn)孽椰、是否是面試真題，在每道題詳細(xì)介紹時(shí)凛篙，還會(huì)給出每道題的 LeetCode 鏈接黍匾，幫助讀者理解題意，以及能夠進(jìn)行實(shí)際的測(cè)驗(yàn)呛梆，還可以觀看其他人的答案锐涯，更好的幫助準(zhǔn)備。

高頻算法題系列：鏈表

筆者遇到的高頻鏈表題主要包含這幾道：

  • 通過(guò)鏈表的后續(xù)遍歷判斷回文鏈表問(wèn)題 【簡(jiǎn)單】
  • 鏈表的反向輸出 【簡(jiǎn)單】
  • 合并 K 個(gè)升序鏈表 【困難】
  • K個(gè)一組翻轉(zhuǎn)鏈表 【困難】
  • 環(huán)形鏈表 【簡(jiǎn)單】
  • 排序鏈表 【中等】
  • 相交鏈表 【簡(jiǎn)單】

前序遍歷判斷回文鏈表

?? 【LeetCode 直通車(chē)】：234 回文鏈表（簡(jiǎn)單）

題解1

利用鏈表的后續(xù)遍歷填物，使用函數(shù)調(diào)用棧作為后序遍歷棧纹腌，來(lái)判斷是否回文

→點(diǎn)擊展開(kāi)查看


/**
  *
  */
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);
};

復(fù)制代碼

題解2

通過(guò) 快、慢指針找鏈表中點(diǎn)滞磺，然后反轉(zhuǎn)鏈表升薯，比較兩個(gè)鏈表兩側(cè)是否相等，來(lái)判斷是否是回文鏈表

→點(diǎn)擊展開(kāi)查看


/**
  *
  */
var isPalindrome = function(head) {
    // 反轉(zhuǎn) slower 鏈表
    let right = reverse(findCenter(head));
    let left = head;
    // 開(kāi)始比較
    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;
    }
    // 如果 faster 不等于 null击困，說(shuō)明是奇數(shù)個(gè)涎劈，slower 再移動(dòng)一格
    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;
}

復(fù)制代碼

反轉(zhuǎn)鏈表

?? 【LeetCode 直通車(chē)】：206 反轉(zhuǎn)鏈表（簡(jiǎn)單）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * 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;
};

復(fù)制代碼

合并K個(gè)升序鏈表

?? 【LeetCode 直通車(chē)】：23 合并K個(gè)升序鏈表（困難）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * 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;
}

復(fù)制代碼

K 個(gè)一組翻轉(zhuǎn)鏈表

?? 【LeetCode 直通車(chē)】：25 K 個(gè)一組翻轉(zhuǎn)鏈表（困難）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * 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;
}

復(fù)制代碼

環(huán)形鏈表

?? 【LeetCode 直通車(chē)】：141 環(huán)形鏈表（簡(jiǎn)單）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * 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;
};

復(fù)制代碼

排序鏈表

?? 【LeetCode 直通車(chē)】：148 排序鏈表（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * 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;
}

復(fù)制代碼

相交鏈表

?? 【LeetCode 直通車(chē)】：160 相交鏈表（簡(jiǎn)單）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * 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;
};

復(fù)制代碼

【??】高頻算法題系列：字符串

主要有以下幾類高頻考題：

  • 最長(zhǎng)回文子串 【中等】【雙指針】【面試真題】
  • 最長(zhǎng)公共前綴 【簡(jiǎn)單】【雙指針】
  • 無(wú)重復(fù)字符的最長(zhǎng)子串【中等】【雙指針】
  • 最小覆蓋子串 【困難】【滑動(dòng)窗口】【面試真題】

【面試真題】最長(zhǎng)回文子串【雙指針】

?? 【LeetCode 直通車(chē)】：5 最長(zhǎng)回文子串（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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);
}

復(fù)制代碼

最長(zhǎng)公共前綴【雙指針】

?? 【LeetCode 直通車(chē)】：14 最長(zhǎng)公共前綴（簡(jiǎn)單）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
}

復(fù)制代碼

無(wú)重復(fù)字符的最長(zhǎng)子串【雙指針】

?? 【LeetCode 直通車(chē)】：3 無(wú)重復(fù)字符的最長(zhǎng)子串（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
};

復(fù)制代碼

【面試真題】 最小覆蓋子串【滑動(dòng)窗口】

?? 【LeetCode 直通車(chē)】：76 最小覆蓋子串（困難）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
};

復(fù)制代碼

【??】高頻算法題系列：數(shù)組問(wèn)題

主要有幾類高頻考題：

  • 俄羅斯套娃信封問(wèn)題【困難】【排序+最長(zhǎng)上升子序列】【面試真題】
  • 最長(zhǎng)連續(xù)遞增序列 【簡(jiǎn)單】【雙指針】
  • 最長(zhǎng)連續(xù)序列【困難】【哈希表】
  • 盛最多水的容器【困難】【面試真題】
  • 尋找兩個(gè)正序數(shù)組的中位數(shù)【困難】【雙指針】
  • 刪除有序數(shù)組中的重復(fù)項(xiàng)【簡(jiǎn)單】【快慢指針】
  • 和為K的子數(shù)組【中等】【哈希表】
  • nSum 問(wèn)題【系列】【簡(jiǎn)單】【哈希表】
  • 接雨水【困難】【暴力+備忘錄優(yōu)化】【面試真題】
  • 跳躍游戲【系列】【中等】【貪心算法】

【面試真題】俄羅斯套娃信封問(wèn)題【排序+最長(zhǎng)上升子序列】

?? 【LeetCode 直通車(chē)】：354 俄羅斯套娃信封問(wèn)題（困難）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
}

復(fù)制代碼

最長(zhǎng)連續(xù)遞增序列【快慢指針】

?? 【LeetCode 直通車(chē)】：674 最長(zhǎng)連續(xù)遞增序列（簡(jiǎn)單）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
};

復(fù)制代碼

最長(zhǎng)連續(xù)序列 【哈希表】

?? 【LeetCode 直通車(chē)】：128 最長(zhǎng)連續(xù)序列（困難）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
};

復(fù)制代碼

【面試真題】盛最多水的容器【哈希表】

?? 【LeetCode 直通車(chē)】：11 盛最多水的容器（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
};

復(fù)制代碼

尋找兩個(gè)正序數(shù)組的中位數(shù)【雙指針】

?? 【LeetCode 直通車(chē)】：4 尋找兩個(gè)正序數(shù)組的中位數(shù)（困難）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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)];
    }
};

復(fù)制代碼

刪除有序數(shù)組中的重復(fù)項(xiàng)【快慢指針】

?? 【LeetCode 直通車(chē)】：26 刪除有序數(shù)組中的重復(fù)項(xiàng)（簡(jiǎn)單）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
};

復(fù)制代碼

和為K的子數(shù)組【哈希表】

?? 【LeetCode 直通車(chē)】：560 和為K的子數(shù)組（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
};

復(fù)制代碼

nSum問(wèn)題【哈希表】【系列】

受限于篇幅，這里只給出第一道題的代碼模板阅茶，也是一面持朊叮考真題。

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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])]
  }
};

復(fù)制代碼

【面試真題】接雨水【暴力+備忘錄優(yōu)化】

?? 【LeetCode 直通車(chē)】：42 接雨水（困難）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
};

復(fù)制代碼

跳躍游戲【貪心算法】【系列】

受限于篇幅脸哀，這里只給出第一道題的代碼模板蹦浦，也是一面常考真題企蹭。

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
};

復(fù)制代碼

高頻算法題系列：二叉樹(shù)

主要有以下幾類高頻考題：

  • 二叉樹(shù)的最近公共祖先【簡(jiǎn)單】【二叉樹(shù)】
  • 二叉搜索樹(shù)中的搜索【簡(jiǎn)單】【二叉樹(shù)】
  • 刪除二叉搜索樹(shù)中的節(jié)點(diǎn)【中等】【二叉樹(shù)】
  • 完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)【中等】【二叉樹(shù)】
  • 二叉樹(shù)的鋸齒形層序遍歷【中等】【二叉樹(shù)】

二叉樹(shù)的最近公共祖先【二叉樹(shù)】

?? 【LeetCode 直通車(chē)】：236 二叉樹(shù)的最近公共祖先（簡(jiǎn)單）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * 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);
    }
}

復(fù)制代碼

二叉搜索樹(shù)中的搜索【二叉樹(shù)】

?? 【LeetCode 直通車(chē)】：700 二叉搜索樹(shù)中的搜索（簡(jiǎn)單）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * 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);
    }
};

復(fù)制代碼

刪除二叉搜索樹(shù)中的節(jié)點(diǎn)【二叉樹(shù)】

?? 【LeetCode 直通車(chē)】：450 刪除二叉搜索樹(shù)中的節(jié)點(diǎn)（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * 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);
}

復(fù)制代碼

完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)【二叉樹(shù)】

?? 【LeetCode 直通車(chē)】：222 完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * 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);
};

復(fù)制代碼

二叉樹(shù)的鋸齒形層序遍歷【二叉樹(shù)】

?? 【LeetCode 直通車(chē)】：103 二叉樹(shù)的鋸齒形層序遍歷（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * 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();
    // 判斷交換時(shí)機(jī)
    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';
        }
        // 決定取那個(gè)棧里面的元素
        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);
            }
        }
        // 判斷下次翻轉(zhuǎn)的時(shí)機(jī)
        if ((flag === 'stack2' && stack1.isEmpty()) || (flag === 'stack1' && stack2.isEmpty())) {
            inOrder = !inOrder;
            // 需要翻轉(zhuǎn)了白筹，就加一輪值
            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;
    }
}

復(fù)制代碼

【??】高頻算法題系列：排序算法

主要有以下幾類高頻考題：

  • 用最少數(shù)量的箭引爆氣球【中等】【排序】
  • 合并區(qū)間【中等】【排序算法+區(qū)間問(wèn)題】【面試真題】

用最少數(shù)量的箭引爆氣球【排序算法】

?? 【LeetCode 直通車(chē)】：452 用最少數(shù)量的箭引爆氣球（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
};

復(fù)制代碼

合并區(qū)間【排序算法+區(qū)間問(wèn)題】

?? 【LeetCode 直通車(chē)】：56 合并區(qū)間（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
};

復(fù)制代碼

高頻算法題系列：二分查找

主要有以下幾類高頻考題：

  • 尋找兩個(gè)正序數(shù)組的中位數(shù)【困難】【二分查找】
  • 判斷子序列【簡(jiǎn)單】【二分查找】
  • 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置【中等】【二分查找】

尋找兩個(gè)正序數(shù)組的中位數(shù)【二分查找】

?? 【LeetCode 直通車(chē)】：4 尋找兩個(gè)正序數(shù)組的中位數(shù)（困難）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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)];
    }
};

復(fù)制代碼

判斷子序列【二分查找】

?? 【LeetCode 直通車(chē)】：392 判斷子序列（簡(jiǎn)單）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
}

復(fù)制代碼

?? 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置【二分搜索】

?? 【LeetCode 直通車(chē)】：34 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
}

復(fù)制代碼

【??】高頻算法題系列：動(dòng)態(tài)規(guī)劃

主要有以下幾類高頻考題：

  • 最長(zhǎng)遞增子序列【中等】【動(dòng)態(tài)規(guī)劃】
  • 零錢(qián)兌換【中等】【動(dòng)態(tài)規(guī)劃】【面試真題】
  • 最長(zhǎng)公共子序列 【中等】【動(dòng)態(tài)規(guī)劃】【面試真題】
  • 編輯距離 【困難】【動(dòng)態(tài)規(guī)劃】
  • 最長(zhǎng)回文子序列【中等】【動(dòng)態(tài)規(guī)劃】【面試真題】
  • 最大子序和【簡(jiǎn)單】【動(dòng)態(tài)規(guī)劃】【面試真題】
  • 買(mǎi)賣(mài)股票的最佳時(shí)機(jī)系列【系列】【動(dòng)態(tài)規(guī)劃】【面試真題】

最長(zhǎng)遞增子序列【動(dòng)態(tài)規(guī)劃】

?? 【LeetCode 直通車(chē)】：300 最長(zhǎng)遞增子序列（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
};

復(fù)制代碼

【面試真題】 零錢(qián)兌換【動(dòng)態(tài)規(guī)劃】

?? 【LeetCode 直通車(chē)】：322 零錢(qián)兌換（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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];
};

復(fù)制代碼

【面試真題】 最長(zhǎng)公共子序列【動(dòng)態(tài)規(guī)劃】

?? 【LeetCode 直通車(chē)】：1143 最長(zhǎng)公共子序列（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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];
};

復(fù)制代碼

編輯距離【動(dòng)態(tài)規(guī)劃】

?? 【LeetCode 直通車(chē)】：72 編輯距離（困難）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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];
};

復(fù)制代碼

【面試真題】最長(zhǎng)回文子序列【動(dòng)態(tài)規(guī)劃】

?? 【LeetCode 直通車(chē)】：516 最長(zhǎng)回文子序列（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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];
};

復(fù)制代碼

【面試真題】?? 最大子序和【動(dòng)態(tài)規(guī)劃】

?? 【LeetCode 直通車(chē)】：53 最大子序和（簡(jiǎn)單）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
};

復(fù)制代碼

【面試真題】?? 買(mǎi)賣(mài)股票的最佳時(shí)機(jī)【動(dòng)態(tài)規(guī)劃】

受限于篇幅智末，這里只給出第一道題的代碼模板，也是一面惩胶樱考真題系馆，筆者在面試字節(jié)跳動(dòng)時(shí)就遇到過(guò)。

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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];
};

復(fù)制代碼

高頻算法題系列：BFS

主要有以下幾類高頻考題：

  • 打開(kāi)轉(zhuǎn)盤(pán)鎖【中等】【BFS】
  • 二叉樹(shù)的最小深度【簡(jiǎn)單】【BFS】

打開(kāi)轉(zhuǎn)盤(pán)鎖【BFS】

?? 【LeetCode 直通車(chē)】：752 打開(kāi)轉(zhuǎn)盤(pán)鎖（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
  }
}

復(fù)制代碼

二叉樹(shù)的最小深度【BFS】

?? 【LeetCode 直通車(chē)】：111 二叉樹(shù)的最小深度（簡(jiǎn)單）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * 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;
  }
}

復(fù)制代碼

【??】高頻算法題系列：棧

主要有以下幾類高頻考題：

  • 最小椡缯眨【簡(jiǎn)單】【椨赡ⅲ】
  • 有效的括號(hào)【中等】【棧】【面試真題】
  • 簡(jiǎn)化路徑【中等】【棿】
  • 下一個(gè)更大元素 【系列】【椖崮穑】

最小棧【椫灿埃】

?? 【LeetCode 直通車(chē)】：155 最小棧（簡(jiǎn)單）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * 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()
 */

復(fù)制代碼

【系列】下一個(gè)更大元素 【椛亚妫】

受限于篇幅，這里只給出第一道題的代碼模板

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
    }
}

復(fù)制代碼

【面試真題】有效的括號(hào)【椝急遥】

?? 【LeetCode 直通車(chē)】：20 有效的括號(hào)（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
    }
}

復(fù)制代碼

簡(jiǎn)化路徑【椔瓜欤】

?? 【LeetCode 直通車(chē)】：71 簡(jiǎn)化路徑（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
    }
}

復(fù)制代碼

【??】高頻算法題系列：DFS

主要有以下幾類高頻考題：

  • 島嶼的最大面積【中等】【DFS】
  • 相同的樹(shù)【簡(jiǎn)單】【DFS】

島嶼的最大面積【DFS】

?? 【LeetCode 直通車(chē)】：695 島嶼的最大面積（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
}

復(fù)制代碼

相同的樹(shù)【DFS】

?? 【LeetCode 直通車(chē)】：100 相同的樹(shù)（簡(jiǎn)單）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * 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);
};

復(fù)制代碼

【??】高頻算法題系列：回溯算法

主要有以下幾類高頻考題：

  • N皇后【困難】【回溯算法】【面試真題】
  • 全排列【中等】【回溯算法】
  • 括號(hào)生成【中等】【回溯算法】
  • 復(fù)原 IP 地址【中等】【回溯算法】
  • 子集 【簡(jiǎn)單】【回溯算法】

【面試真題】N皇后【回溯算法】

?? 【LeetCode 直通車(chē)】：51 N皇后（困難）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
}

復(fù)制代碼

全排列【回溯算法】

?? 【LeetCode 直通車(chē)】：46 全排列（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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();
    }
}

復(fù)制代碼

括號(hào)生成【回溯算法】

?? 【LeetCode 直通車(chē)】：22 括號(hào)生成（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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;
    }
}

復(fù)制代碼

復(fù)原 IP 地址【回溯算法】

?? 【LeetCode 直通車(chē)】：93 復(fù)原 IP 地址（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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();
    }
}

復(fù)制代碼

子集【回溯算法】

?? 【LeetCode 直通車(chē)】：78 子集（中等）

題解

→點(diǎn)擊展開(kāi)查看


/**
 * @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]);
    }
}

復(fù)制代碼

原文地址 干貨文章分享 - 字節(jié)跳動(dòng)最常考的 64 道JS算法題

原創(chuàng)不易

喜歡的話原創(chuàng)不易谷饿，給點(diǎn)鼓勵(lì)吧 ?? 別忘了 分享惶我、點(diǎn)贊、在看 三連哦~博投。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末绸贡，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子毅哗，更是在濱河造成了極大的恐慌听怕，老刑警劉巖，帶你破解...
    沈念sama閱讀 211,290評(píng)論 6贊 491
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件黎做，死亡現(xiàn)場(chǎng)離奇詭異叉跛，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)蒸殿，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,107評(píng)論 2贊 385
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門(mén)筷厘，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人宏所，你說(shuō)我怎么就攤上這事酥艳。” “怎么了爬骤？”我有些...
    開(kāi)封第一講書(shū)人閱讀 156,872評(píng)論 0贊 347
  • 道士緝兇錄：失蹤的賣(mài)姜人
    文/不壞的土叔 我叫張陵充石，是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我霞玄，道長(zhǎng)骤铃，這世上最難降的妖魔是什么拉岁？ 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 56,415評(píng)論 1贊 283
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任，我火速辦了婚禮惰爬，結(jié)果婚禮上喊暖，老公的妹妹穿的比我還像新娘。我一直安慰自己撕瞧，他們只是感情好陵叽，可當(dāng)我...
    茶點(diǎn)故事閱讀 65,453評(píng)論 6贊 385
  • 惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
    文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著丛版，像睡著了一般巩掺。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上页畦，一...
    開(kāi)封第一講書(shū)人閱讀 49,784評(píng)論 1贊 290
  • 城市分裂傳說(shuō)
    那天胖替，我揣著相機(jī)與錄音，去河邊找鬼寇漫。 笑死刊殉，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的州胳。 我是一名探鬼主播，決...
    沈念sama閱讀 38,927評(píng)論 3贊 406
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開(kāi)眼逸月，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼栓撞！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起碗硬，我...
    開(kāi)封第一講書(shū)人閱讀 37,691評(píng)論 0贊 266
  • 萬(wàn)榮殺人案實(shí)錄
    序言：老撾萬(wàn)榮一對(duì)情侶失蹤瓤湘，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后恩尾，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體弛说，經(jīng)...
    沈念sama閱讀 44,137評(píng)論 1贊 303
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,472評(píng)論 2贊 326
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年翰意，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了木人。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,622評(píng)論 1贊 340
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡冀偶，死狀恐怖醒第，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情进鸠，我是刑警寧澤稠曼，帶...
    沈念sama閱讀 34,289評(píng)論 4贊 329
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站客年，受9級(jí)特大地震影響霞幅，放射性物質(zhì)發(fā)生泄漏漠吻。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,887評(píng)論 3贊 312
  • 男人毒藥：我在死后第九天來(lái)索命
    文/蒙蒙 一司恳、第九天 我趴在偏房一處隱蔽的房頂上張望侥猩。 院中可真熱鬧，春花似錦抵赢、人聲如沸欺劳。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,741評(píng)論 0贊 21
  • 一樁弒父案铅鲤，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)划提。三九已至，卻和暖如春邢享，著一層夾襖步出監(jiān)牢的瞬間鹏往，已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 31,977評(píng)論 1贊 265
  • 情欲美人皮
    我被黑心中介騙來(lái)泰國(guó)打工骇塘， 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留伊履，地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 46,316評(píng)論 2贊 360
  • 代替公主和親
    正文 我出身青樓款违，卻偏偏與公主長(zhǎng)得像唐瀑，于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子插爹，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,490評(píng)論 2贊 348

推薦閱讀更多精彩內(nèi)容