用Js怒刷LeetCode

简介

文中所有题目均为精心挑选过的超高频题目，所以大家可以收藏起来

适用人群

针对有一定数据结构基础(了解链表, 二叉树, 二叉堆, 递归)的基本概念,并对时间空间复杂度有基本认知的。

食用指南

将文中列出的每道题至少手写3遍

面试前可以按照本文整理出来的题目直接过一遍

说明

文章更新频率: 除休息日外,每天在题目下方更新一道题的题解

有LeetCode原题的将贴上原地址，不在文章内做题目描述

Tc: Time complexity (时间复杂度)

Sc: Space complexity (空间复杂度)

题目类型

数组篇

1.twoSum [要求Tc: O(n) Sc:O(n)] (字节跳动)

LeetCode第1题

按照题目要求,我们第一时间想到的会是两层循环暴力解法：

解法1：Time = O(n²), Space = O(1)

思路:遍历每个元素nums[j]，并查找是否存在一个值与 target – nums[j] 相等的目标元素。

function twoSum(nums, target) {
     for (let i = 0; i 

解法2:Time = O(n), Space = O(n)：

我们可以通过哈希表空间换时间。在进行迭代并将元素插入到表中的同时，我们回过头来检查哈希表中是否已经存在当前元素所对应的目标元素，如果存在，那我们就找到了问题的解，将其返回即可.(时间复杂度为O(n),空间复杂度也为O(n))

符合题目要求bingo✌

var twoSum = function(nums, target) {
    let reduceHash = {};
    for (let i = 0; i 

2.缺失的数字 [要求Tc: O(n) Sc:O(n)] (字节跳动)

剑指Offer第53题

解法：

思路:我们先把所有输入了的数字存入hash表,因为给定的数组是有序的，所以可以再过一遍hash表，遍历过程中如果某个数字在hash表中不存在，则该数字就是缺失的那个数字

var missingNumber = function(nums) {
    const hash = {};
    for (let i = 0; i 

3.移动零 [要求Tc: O(n) Sc:O(1), 移动后不能改变原来其他元素的相对位置] (二线公司)

LeetCode第283题

解法：

思路: 双指针同向而行,fast指针遇到非0就把slow指针位置的字符替换掉，slow指针前进一步。直到fast指针把数组所有元素遍历完毕。(典型的两个挡板，三个区域思想),再把slow指针后面的所有元素替换为0。

同向性质:

变量的物理意义: slow的左侧不包含slow都是非0的数字，slow的右侧包含slow都应该为0，按照这个物理意义就可以达到原地算法的要求。因为快慢指针是同向而行的，所以算法为稳定算法(不会影响元素的相对位置)

var moveZeroes = function(nums) {
    let slow = 0;
    for (let fast = 0; fast 

4.洗牌算法(乱序数组)[要求Tc: O(n) Sc:O(1),要求每个元素的打乱的概率相同] (快手)

LeetCode第384题

解法:

思路: 本题思路就是使用Fisher-Yates洗牌算法。

参考视频：传送门

function shuffle(arr) {
    let m = arr.length;
    while (m) {
        let random = (Math.random() * m--) | 0;
        [arr[random],arr[m]] = [arr[m],arr[random]];
    }
    return arr;
}
console.log(shuffle([1,5,6,7,6]));

5.两个数组的交集 [要求Tc: O(n) Sc:O(n)] (阿里)

LeetCode第349题

解法:

思路: 本题思路是看nums1数组里是否含有nums2的元素，如果有就添加到结果中返回。

let res = [];
for (let i = 0; i 

6.RainbowSort [要求Tc: O(n) Sc:O(1)] (盛大)

给定一系列球，其中球的颜色只能是红色，黄色或蓝色，对球进行排序，以使所有红色球都分组在左侧，所有黄色球都分组在中间，所有蓝色球分组在右侧。

例：

[红]被排序为[红]

[黄，红]被排序为[红，黄]

[黄,红,红,蓝,黄,红,蓝]被排序为[红,红,红,黄,黄,蓝,蓝]

假设条件:

输入数组不为null。

corner case:

如果输入数组的长度为零怎么办？在这种情况下，我们应该直接返回空数组。

解法：

思路: 本题思路是挡板思想,使用三个挡板四个区域的思想进行划分(交换数组元素位置)

挡板的物理意义: [0-i)全是红色,[i,j)之间为黄色,(k->n-1]全为蓝色，[j-k]为未知探索区域

j为快指针

const input = ['黄','红','红','蓝','黄','红','蓝']
function rainbowSort(rainbow) {
    let i = 0, j = 0, k = rainbow.length - 1;
    while (j 

7.移除元素 [要求Tc: O(n) Sc:O(1)]

LeetCode第27题

解法：

思路: 双指针同向而行,快指针遇到非val就把slow指针位置的字符替换掉，slow指针前进，直到数组所有元素遍历完毕。(典型的两个挡板，三个区域思想)

变量的物理意义: slow的左侧不包含slow都是非val的元素，slow的右侧包含slow都应该为不包含val的元素，按照这个物理意义就可以达到原地算法的要求。因为快慢指针是同向而行的，所以算法为稳定算法(不会影响元素的相对位置)

挡板性质:

同向而行: slow指针左边是处理好的元素 fast指针右边是未知探索区域,两个挡板中间不关注(最后的结果不会改变元素相对位置)

var removeElement = function(nums, val) {
    let slow = 0;
    for(let fast = 0; fast 

8.按奇偶排序数组[要求Tc: O(n) Sc:O(1)] (腾讯)

LeetCode第905题

解法：

思路: 继续使用挡板思想,两个挡板三个区域,同向而行,[0-i)是偶数,[j-n-1]是未探索区域

挡板性质:

同向而行: slow指针左边是处理好的元素 fast指针右边是未知探索区域,两个挡板中间不关注(最后的结果不会改变元素相对位置)

解法1:(不改变元素相对位置:同向而行)

var sortArrayByParity = function(A) {
    for (let i = 0, j = 0; j 

挡板性质:

相向而行: left指针左边是处理好的元素,right指针右边也是处理好的元素, 两个挡板中间是未处理区域(最后的结果可能会改变元素相对位置)

解法2:(改变元素相对位置:相向而行)

var sortArrayByParityII = function(A) {
    let i = 0, j = A.length - 1;
    while (i 

9.数组中出现次数超过一半的数字 [要求Tc: O(n) Sc:O(1)]

LeetCode第169题

思路: 这道题属于火拼问题,见一个sha一个(抵消),最后留下的就是超过一半的元素。

先保留第一个元素，接着遍历，如果遇到和他相同的则加次数，否则就减次数，如果次数为0了就要换另一个元素了。

比如: A B C A

第一次保留A,用A跟剩下的打架，碰到不是A的就把A的个数减1，如果遇到A就增加个数，直到遇到不同的元素把A的次数抵消完就把A踢下去,并且把次数重新设置为1。

如此下去最后肯定有个多出来的就是题解了。

var majorityElement = function(array) {
    let count = 1;
    let num = array[0];
    for (let i = 1; i 

10.合并两个有序数组 [要求Tc: O(m + n) Sc:O(n)] (腾讯)

例:

输入:nums1 = [1,3], nums2 = [4,5,7]

输出: [1,3,4,5,7]

function merge(left, right) {
    let result = [];
    let i = 0, j = 0;
    while (i 

11.有序数组中小于某个数的个数 [要求Tc: O(logn) Sc:O(1)] (今日头条)

例:

输入:[1, 2, 3, 4]

输入目标值:2

输出: 1

思路: 题目提到有序数组，第一时间就应该想到二分(再加之复杂度要求logn级别)。其实这道题就是让写个二分查找,仔细想想，你要找的那个数的下标不就代表前面有几个比他小的数字吗？

function binarySearch(array, target) {
    let low = 0;
    let high = array.length - 1;
    while (low  target) {
            high = mid - 1;
        } else if (middleValue 

12.数组去重[要求Tc: O(n) Sc:O(1)]

LeetCode第26题

该算法要求原地算法，所以继续使用挡板思想(没理解的可以回到上文提及处继续理解)。

因为他至少有一个元素是不会重复的(至少会保留一个元素)，所以从下标1开始处理。

解法1: 从索引1开始(处理好的元素不包含slow位置)

var removeDuplicates = function(arr) {
    let slow = 1;
    for (let fast = 1; fast 

解法2: 从索引0开始,(处理好的元素包含slow位置)

var removeDuplicates = function(arr) {
    let slow = 0;
    for (let fast = 1; fast 

13.去掉连续的a和c,保留所有b [要求Tc: O(n) Sc:O(1) 元素相对位置不变] (字节跳动)

思路: 还是使用快慢指针,同向而行

function removeAC(arr) {
    let slow = 0,fast = 0;
    while (fast 

14.最长公共前缀 (拼多多)

例: [‘aaafsd’, ‘aawwewer’, ‘aaddfff’] => ‘aa’

LeetCode第14题

function LCP(arr) {
    if (!arr.length) {
        return '';
    }
    let ans = arr[0];
    for (let i = 1; i 

15.给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次,找到所有出现两次的元素[要求Tc: O(n) Sc:O(1)] (字节跳动)

例:
输入:
[4,3,2,7,8,2,3,1]
输出:
[2,3]

解：目前没有思路

16.数组中所有元素组成的最大数是多少 (作业帮)

例: [50, 2, 5, 9] => 95502

思路: 我们把最大的数字依次排序肯定就是最大数(降序排列)

var largestNumber = function(nums) {
    nums = nums.sort((a, b) => {
        let S1 = `${a}${b}`;
        let S2 = `${b}${a}`;
        return S2 - S1;
    });
    return nums[0] ? nums.join('') : '0';
};

LeetCode第179题

字符串篇

1.回文数 [要求Tc: O(log10n) Sc:O(1) 或 Tc: O(n) Sc:O(1)] (腾讯)

LeetCode第9题

思路: 使用双指针一个在前，一个在后, 前后对比。遇到两个指针不同就返回false。

function palindrome(x) {
    let i = 0, j = x.length - 1;
    while (i 

2.反转字符串 [要求Tc: O(n) Sc:O(1)]

LeetCode第344题

思路: 使用双指针一个在前，一个在后, 每次都交换即可

var reverseString = function(s) {
    let slow = 0;
    for (let fast = s.length - 1, slow = 0; fast >= slow; fast--) {
        swap(s, slow++, fast);
    }
};
function swap(arr, l, r){
    let temp = arr[l];
    arr[l] = arr[r];
    arr[r] = temp;
}

3.翻转单词顺序 [要求Tc: O(n) Sc:O(n)] (字节跳动)

剑指Offer第58题

思路: 将字符串按空格分割,然后按照上题的方法交换单词顺序即可。

var reverseWords = function(s) {
    let strArr = s.split(' ').filter(Boolean);
    let reversed = strArr;
    reverse(reversed, 0, reversed.length - 1);
    return reversed.join(' ');
};
function reverse(input, left, right) {
    if (left >= right) {
        return;
    }
    swap(input, left, right);
    reverse(input, left + 1, right -1);
}
function swap(arr, l, r) {
    [arr[l],arr[r]] = [arr[r],arr[l]];
}

4.有效的字母异位词(Anagram) [要求Tc: O(n) Sc:O(n)]

LeetCode第242题

思路: 我们可以使用hash存储每个单词出现的次数，再用另一个字符串遍历一次进行减减操作，只要次数有不等于0的字母则返回false

var isAnagram = function(s, t) {
    if (s.length !== t.length) return false;

    let map = new Map();

    for (let item of s) {
        if (map.get(item)) {
            map.set(item, map.get(item) + 1);
        } else {
            map.set(item, 1);
        }
    }
    for (let item of t) {
        if (map.get(item)) {
            map.set(item, map.get(item) - 1);
        } else {
            return false;
        }
    }
    return true;
};

5.找出字符串中出现次数最多的字母 [要求Tc: O(n) Sc:O(n)]

例1: 输入 ‘abccdtc’

输出: ‘c’

例2: 输入 ‘abbbbccdtc’

输出: ‘b’

function maxCount(str) {
    let hash = {};
    let maxCount = 0;
    let maxElement = '';
    for (let i = 0; i 

6.替换空格 [要求Tc: O(n) Sc:O(1) 不允许使用正则表达式] (今日头条)

剑指Offer第5题

思路: 使用快慢指针,同向而行，快指针负责判断是不是空格，慢指针左侧都是处理好的元素。

var replaceSpace = function(s) {
    s = s.split('');
    for (let fast = 0; fast 

其他解法(不推荐面试中使用):

var replaceSpace = function(s) {
    s = s.split(' ').join('%20');
    return s;
};

var replaceSpace = function(s) {
    s = s.replace(/s+/g,'%20');
    return s;
};

7.第一个只出现一次的字符 [要求Tc: O(n) Sc:O(n)]

剑指Offer第50题

思路: 遍历过程中存hash表,如果当前值第一次出现就设置为false,后续处理遍历值为false的,遇到为false的就直接返回。

var firstUniqChar = function(s) {
    let hash = {};
    let firstAppearLetter = '';
    if (s === '') {
        return ' ';
    } else {
        for (let i = 0; i 

8.左旋转字符串 [要求Tc: O(n) Sc:O(n)]

剑指Offer第58题

var reverseLeftWords = function(s, n) {
    let frontStr = s.slice(0, n);
    let backStr = s.slice(n);
    return backStr + frontStr;
};

9.字符串全排列 [要求Tc: O(n!) Sc:O(n²)] (阿里)

剑指Offer第38题

var permutation = function(s) {
    let solution = [];
    if (s.length === 0) {
        return solution;
    }
    permutationHelper(s, solution);
    return solution;
};
function permutationHelper(s, solution, used = [], path = []) {
    if (path.length === s.length) {
        solution.push(path.slice(0).join(''));
        return;
    }
    let levelSet = new Set();
    for (let i = 0; i 

10.合并连续数字 [要求Tc: O(n) Sc:O(1)] (今日头条)

题目描述:

输入:[0, 2, 3, 5, 6, 7, 8, 9, 11, 13, 56, 57]

输出结果：

0,2-3,5-9,11,13,56-57

思路: 三指针,同向而行,slow左边的为处理好的元素,f指针快速向前走,begin指针记录区间开始区间, prev指针记录区间结束位置。

function combine(arr) {
    let f = 1, slow = 0;
    let prev = -1;
    while (f 

11.字符串相加 (腾讯)

LeetCode第415题

var addStrings = function(num1, num2) {
    let res = [];
    let i = num1.length - 1, j = num2.length - 1, carry = 0;
    while (i >= 0 || j >= 0) {
        let n1 = i >= 0 ? num1.charAt(i) - 0: 0;
        let n2 = j >= 0 ? num2.charAt(j) - 0: 0;
        let tmp = n1 + n2 + carry;
        carry = parseInt(tmp / 10);//算出十位数
        res.push(tmp % 10);//算出个位数
        i--; j--;
    }
    if(carry == 1) res.push('1');
    return res.reverse().join('')
};

栈/队列篇

1.实现一个栈，入栈push、出栈pop、返回最小值min的复杂度为0(1) (滴滴)

LeetCode第115题

思路: stack2为存储最小值的数组,使用同步加同步减的思路,stack1进来的新元素比stack2的top元素大则无视,否则stack2顶部的元素变成刚刚进来的小值。

var MinStack = function() {
    this.stack1 = [];
    this.stack2 = [];
};
/**  * @param {number} x
 * @return {void} */
MinStack.prototype.push = function(x) { //同步加同步减push pop
    this.stack1.push(x);
    if (this.stack2.length === 0) {
        this.stack2.push(x);
    } else {
        let temp = this.stack2[this.stack2.length - 1];
        if (x 

2.使用两个栈实现一个队列 (滴滴)

剑指Offer第9题

思路: 我们既然要实现队列,那肯定就是要有其中一个栈作为辅助栈，用来倒腾另一个栈中的数据(我们这里的stack1为主栈，stack2为辅助栈);

var CQueue = function() {
    this.stack1 = [];//2 1
    this.stack2 = [];
    this.count = 0;
};

/**  * @param {number} value
 * @return {void} */
CQueue.prototype.appendTail = function(value) {
    while (this.stack1.length) { //如果stack1中有元素那就先把stack1中所有元素放到stack2中
        this.stack2.push(this.stack1.pop());
    }
    this.stack1.push(value);//添加新的值到stack1中
    while (this.stack2.length) {
        this.stack1.push(this.stack2.pop()); //然后再把stack2中的元素放到stack1中
    }
    //这几步的意思是让stack1具有队列的性质(先进先出) 因为stack2代表stack1中之前的数据，然后会压到新数据的上面
    this.count++;

};

/** * @return {number} */
CQueue.prototype.deleteHead = function() {
    if (this.count == 0) {
        return -1;
    }
    this.count--;
    return this.stack1.pop();//使用pop栈的方法，因为咱们利用辅助栈倒腾了一下所以直接pop后结果就是按照队列的性质输出了先进的值
};

3.有效的括号[要求Tc: O(n) Sc:O(n)] (哔哩哔哩)

LeetCode第20题

思路: 使用栈保存括号，遇到左括号直接入栈，遇到右括号就把栈顶的弹出来和当前的右括号匹配,如果匹配失败说明不合法直接返回false,最后判断栈是不是空(是不是所有括号都抵消完毕了),不为空也说明不合法。

var isValid = function(str) {
    let map = {
        '{': '}',
        '(': ')',
        '[': ']'
    }
    let stack = []
    for (let i = 0; i 

链表篇

1.从尾到头打印单链表[要求Tc: O(n) Sc:O(n)]

剑指Offer第6题

思路: 基于stack的特性(后进先出),所以我们从头到尾过一遍链表，最后按照栈的顺序弹出就可以得到结果。

var reversePrint = function(head) {
    let stack = [];
    let cur = head;
    while (cur !== null) {
        stack.push(cur.val);
        cur = cur.next;
    }
    let print = [];
    while (stack.length) {
        print.push(stack.pop())
    }
    return print;
};

2.删除链表的倒数第K个结点[要求Tc: O(L) Sc:O(1)]

LeetCode第19题

var removeNthFromEnd = function(head, n) {
    let dummyNode = new ListNode(0);
    dummyNode.next = head;
    let fast = dummyNode, slow = dummyNode;
    // 快先走 n+1 步
    while(n--) {
        fast = fast.next
    }
    // fast、slow 一起前进
    while(fast && fast.next) {
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
    return dummyNode.next
};

3.判断单链表是否有环[要求Tc: O(n) Sc:O(1)] (有赞)

LeetCode第141题

var hasCycle = function(head) {
    if (head === null) {
        return false;
    }
    let slow = fast = head;
    while (fast.next !== null && fast.next.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            return true;
        }
    }
    return false;
};

4.反转单链表[要求Tc: O(n) Sc:O(1)] (链表类超高频)

剑指Offer第24题

反转思路如下过程:

原始链表:
head -> 2 -> 3 -> 4 -> null

             4 -> null
pre(null)    cur  next

null   null
        pre    cur   next

null  

迭代解法(从左到右反转):

var reverseList = function(head) {
    if (head === null || head.next === null) {
        return head;
    }
    let pre = null, cur = head;
    while (cur !== null) {
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
};

递归解法:(从右往左反转)

var reverseList = function(head) {
    if(head === null || head.next === null) {
        return head;
    }
    let newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

原始链表:
2 -> 3 -> null

第一次调用reverseList:

2  ->  3 -> null
head  newHead

head.next.next = head 干的事是: (2的next是3,将3的next指向2)：
2    3

head.next = null 干的事是:
null 

return newHead 干的事是:
null 

第二次调用reverseList:

2  ->  3 -> null
      head
base case: return newHead = 3

5.判断两个链表是否相交，若相交，求交点(链表没有环)[要求Tc: O(m+n) Sc:O(n)] (字节跳动)

LeetCode第160题

headA:a+c+b
headB:b+c+a

因为 a+c+b === b+c+a 因此终有一刻他们能相交

var getIntersectionNode = function(headA, headB) {
    if (headA === null || headB === null) {
        return null;
    }
    let nodeA = headA;
    let nodeB = headB;
    while (nodeA !== nodeB) {
        nodeA = nodeA ? nodeA.next : headB;
        nodeB = nodeB ? nodeB.next : headA;
    }
    return nodeA;
};

6.查找单链表的中间节点，要求只能遍历一次链表[要求Tc: O(n) Sc:O(1)]

LeetCode第876题

var middleNode = function(head) {
    let slow = head;
    let fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

7.合并两个有序链表，合并后依然有序[要求Tc: O(m+n) Sc:O(1)]

剑指Offer第25题

var mergeTwoLists = function(l1, l2) {
    let dummyHead = new ListNode(0);
    let cur1 = l1;
    let cur2 = l2;
    let tail = dummyHead;
    while (cur1 !== null && cur2 !== null) {
        if (cur1.val 

8.查找单链表的倒数第K个节点，要求只能遍历一次链表[要求Tc: O(n) Sc:O(1)]

剑指Offer第22题

var getKthFromEnd = function(head, k) {
    let fast = head, slow = head;
    for (let i = 0; i 

二叉树篇

1.二叉树的删除实现[要求Tc: O(H) Sc:O(H)] (字节跳动)

LeetCode第450题

var deleteNode = function(root, key) {
    this.root = recursionDelete(root, key);
    return this.root;
};
function recursionDelete(root, key) {
    if (root === null) {
        return null;
    }
    if (root.val > key) {
        root.left = recursionDelete(root.left, key);
        return root;
    } else if (root.val 

2.判断一棵树是否是平衡树[要求Tc: O(n) Sc:O(n)] (字节跳动)

LeetCode第110题

var isBalanced = function(root) {
    if (root === null) {
        return true;
    }
    const lh = maxDepth(root.left);
    const rh = maxDepth(root.right);
    if (Math.abs(lh - rh) > 1) {
        return false;
    }
    return isBalanced(root.left) && isBalanced(root.right);
};
function maxDepth(root) {
    if (root === null) {
        return 0;
    }
    const left = maxDepth(root.left);
    const right = maxDepth(root.right);
    return Math.max(left, right) + 1;
};

3.二叉树最大深度[要求Tc: O(n) Sc:O(n)] (阿里)

剑指Offer第55题

function maxDepth(root) {
    if (root === null) {
        return 0;
    }
    const left = maxDepth(root.left);
    const right = maxDepth(root.right);
    return Math.max(left, right) + 1;
};

5.二叉树中和为某一值的路径[要求Tc: O(n) Sc:O(n)] (字节跳动)

剑指Offer第34题

第34题解:

var pathSum = function(root, sum) {
    if(!root) return [];
    const solution = [];
    let path = []
    pathSumHelper(root,sum,solution,path);
    return solution;
};
function pathSumHelper(root,sum,solution,path) {
    path.push(root.val);
    if(root.left == null && root.right == null && calcPath(path) == sum) {
        solution.push([...path]);
    }
    if(root.left){
        pathSumHelper(root.left,sum,solution,path);
    }
    if(root.right){
        pathSumHelper(root.right,sum,solution,path);
    }
    path.pop();
}
function calcPath(path){
    let total = 0;
    for(let i = 0;i

6.LCA[要求Tc: O(n) Sc:O(n)] (字节跳动)

LeetCode第236题

var lowestCommonAncestor = function(root, p, q) {
    if(!root || root.val == p.val || root.val == q.val) return root;
    let left = lowestCommonAncestor(root.left, p, q);
    let right = lowestCommonAncestor(root.right, p, q);
    //如果left不存在p或q就返回right的结果。如果left存在，right不存在就返回left结果。如果left和right都存在就返回根节点
    if(left == null) return right;
    else if(right == null) return left;
    return root;
};

7. 二叉树层序遍历[要求Tc: O(n) Sc:O(n)] (必会题)

LeetCode第102题

var levelOrder = function(root) {
    if (root === null) {
        return [];
    }
    const result = [];
    let queue = [root];
    while (queue.length) {
        const level = [];
        let size = queue.length;
        for (let i = 0; i 

8.是否是BST[要求Tc: O(n) Sc:O(n)] (有赞)

LeetCode第98题

var isValidBST = function(root) {
    let min = -Infinity;
    let max = Infinity;
    return isValidBSTHelper(root, min, max);
};
function isValidBSTHelper(root, min, max) {
    if (root === null) {
        return true;
    }
    if(root.val = max) {
        return false;
    }
    return isValidBSTHelper(root.left, min, root.val) && isValidBSTHelper(root.right, root.val, max);
}

9.是否是完全二叉树[要求Tc: O(n) Sc:O(n)] (字节跳动)

LeetCode第958题

var isCompleteTree = function(root) {
    if (root === null) {
        return true;
    }
    let queue = [root];
    let flag = false;
    while (queue.length) {
       let cur = queue.shift();
       if (cur.left === null) {
           flag = true;
       } else if (flag) {
           return false;
       } else {
           queue.push(cur.left);
       }
       if (cur.right === null) {
           flag = true;
       } else if (flag) {
           return false;
       } else {
           queue.push(cur.right);
       }
    }
    return true;
};

10.翻转二叉树[要求Tc: O(n) Sc:O(n)]

LeetCode第226题

var invertTree = function(root) {
    if(root == null) {
        return [];
    }
    invertTreeHelper(root);
    return root;
};
function invertTreeHelper(root) {
    if (root == null) {
        return;
    }
    let tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    invertTree(root.left);
    invertTree(root.right);
}

11.二叉树的右视图[要求Tc: O(n) Sc:O(n)] (字节跳动)

LeetCode第199题

var rightSideView = function(root) {
    const result = [];
    if (root === null) {
        return result;
    }
    let queue = [root];
    while (queue.length) {
        const level = [];
        let size = queue.length;
        for (let i = 0; i 

12.判断对称二叉树[要求Tc: O(n) Sc:O(n)]

LeetCode第101题

var isSymmetric = function(root) {
    return isSymmetricHelper(root, root);
};
function isSymmetricHelper(one, two) {
    if (one === null && two === null) {
        return true;
    } else if (one === null || two === null) {
        return false;
    } else if (one.val !== two.val) {
        return false;
    }
    return isSymmetricHelper(one.left,two.right) && isSymmetricHelper(one.right,two.left);
}

13. 二叉树的锯齿形层次遍历[要求Tc: O(n) Sc:O(n)] (字节跳动)

LeetCode第103题

var zigzagLevelOrder = function(root) {
  const printArr = []
  if (!root) return printArr
  const list = []
  list.push({ level: 0, node: root })
  while(list.length > 0) {
    const { level, node } = list.shift()
    if (!printArr[level]) {
      printArr[level] = []
    }
    if (level % 2 === 0) {
      printArr[level].push(node.val)
    } else {
      printArr[level].unshift(node.val)
    }
    node.left && list.push({ level: level + 1, node: node.left })
    node.right && list.push({ level: level + 1, node: node.right })
  }
  return printArr
};

14.构造二叉树

LeetCode第106题

var buildTree = function(preorder, inorder) {
    function help(inorder) {
        if (!inorder|| !inorder.length) return null;
        let top = preorder.shift(), p = inorder.indexOf(top);
        let root = new TreeNode(top);
        root.left = help(inorder.slice(0, p));
        root.right = help(inorder.slice(p+1));
        return root;
    }
    return help(inorder);
};

LeetCode第105题

var buildTree = function(preorder, inorder) {
    function help(inorder) {
        if (!inorder|| !inorder.length) return null;
        let top = preorder.shift(), p = inorder.indexOf(top);
        let root = new TreeNode(top);
        root.left = help(inorder.slice(0, p));
        root.right = help(inorder.slice(p + 1));
        return root;
    }
    return help(inorder);
};

堆/优先队列篇

1.寻找第k大元素[要求Tc: O(nlogn) Sc:O(1)] (腾讯, 字节跳动, 阿里)

常见题型

二分查找篇

1.查找给定值[要求Tc: O(logn) Sc:O(1)] (二分查找高频)

LeetCode第704题

function binarySearch(array, target) {
    let left = 0;
    let right = array.length - 1;
    while (left  target) {
            right = mid - 1;
        } else if (middleValue 

2.查找最接近目标值的值[要求Tc: O(logn) Sc:O(1)]

给定目标整数T和按升序排序的整数数组A，找到A中的索引i，以使A [i]最接近T。

假设条件:

数组中可以有重复的元素，并且我们可以返回具有相同值的任何索引。

例:

A = [1,2,3]，T = 2，返回1

A =[1，4，6]，T = 3，返回1

A = [1，4，6]，T = 5，返回1或2

A = [1、3、3、4]，T = 2，返回0或1或2

corner case:

如果A为空或A为零长度怎么办？在这种情况下，我们应该返回-1。

function binarySearch(array, target) {
    if (array.length === 0) {
        return -1;
    }
    let left = 0;
    let right = array.length - 1;
    while (left = Math.abs(target - array[right])) {
        return right;
    } else {
        return left;
    }
}
const index = binarySearch([1, 2, 5, 6], 4);
console.log(index); // 2

3.第一个出现的目标值[要求Tc: O(logn) Sc:O(1)] (二分查找高频)

给定目标整数T和按升序排序的整数数组A，请找到A中T首次出现的索引，如果没有这样的索引，则返回-1。

假设条件

数组中可以有重复的元素。

例:

A = [1,2,3]，T = 2，返回1

A = [1,2,3]，T = 4，返回-1

A = [1,2,2,2,3]，T = 2，返回1

corner case:

如果A为零或长度为零的A怎么办？在这种情况下，我们应该返回-1。

function binarySearch(array, target) {
    if (array.length === 0) {
        return -1;
    }
    let left = 0;
    let right = array.length - 1;
    while (left 

4.查找最接近目标值的k个数[要求Tc: O(logn + k) Sc:O(1)]

给定目标整数T，非负整数K和按升序排序的整数数组A，找到A中最接近T的K个数字。 如果存在平局，则始终首选较小的元素。

假设条件:

A不为空
K保证大于等于0，K保证小于等于A.length
返回大小为K的整数数组，其中包含A中的K个最接近的数字（不是索引），并按数字和T之间的差值升序排列。

例:

A = [1，2，3]，T = 2，K = 3，返回[2，1，3]或[2，3，1]

A = [1，4，6，8]，T = 3，K = 3，返回[4，1，6]

function binarySearch(array, target, k) {
    if (array.length === 0) {
        return -1;
    }
    let left = 0;
    let right = array.length - 1;
    while (left = array.length) {//can be merged two conditions
            result[i] = array[l--];
        } else if (l 

动态规划篇

1.斐波那契数列(要求Tc: O(n) Sc:O(n)/O(1)) (动态规划类超高频)

LeetCode第704题

var fib = function(n) {
    let a = 0, b = 1, sum;
    for (let i = 0; i 

2.爬楼梯(要求Tc: O(n) Sc:O(n)/O(1)) (动态规划类超高频)

LeetCode第70题

var climbStairs = function(n) {
    if (n === 1) {
        return 1;
    }
    let dp = [];
    dp[1] = 1;
    dp[2] = 2;
    for (let i = 3; i 

递归篇

1.岛屿数量(要求Tc: O(MN) Sc:O(MN)) s

LeetCode第200题

let dfs = function (grid, i, j) {
  // 把当前项变为0, 防止重新查找
  grid[i][j] = 0;
  // 当前项 上下左右检查
  if (grid[i - 1] && grid[i - 1][j] == 1) dfs(grid, i - 1, j);  // 上
  if (grid[i + 1] && grid[i + 1][j] == 1) dfs(grid, i + 1, j);  // 下
  if (grid[i][j - 1] && grid[i][j - 1] == 1) dfs(grid, i, j - 1);  // 左
  if (grid[i][j + 1] && grid[i][j + 1] == 1) dfs(grid, i, j + 1);  // 右
}
var numIslands = function(grid) {
  if (grid.length 

2.从一个数组中找出 N 个数，其和为 M 的所有可能(不能重复使用已经使用过的元素) (今日头条)

参考题解1

参考题解2

3.子集(要求Tc: O(N×2N) Sc:O(N×2N)) (腾讯)

LeetCode第78题

var subsets = function(nums) {
    if (!nums.length) {
        return [];
    }
    let solution = [];
    let levelResult = [];
    subsetsHelper(nums,0,levelResult,solution);
    return solution;
};
function subsetsHelper(nums,level,lresult,solution) {
    //base base
    if (level === nums.length) {
        solution.push([].concat(lresult));
        return;
    }
    lresult.push(nums[level]);
    subsetsHelper(nums, level + 1,lresult, solution);//回溯
    lresult.pop();
    subsetsHelper(nums, level + 1, lresult, solution);//回溯
}

5.扁平化对象(虾皮)

输入:

{
  "a": {
    "b": {
      "c": {
        "d": 1
      }
    }
  },
  "aa": 2,
  "c": [
    1,
    2
  ]
} 

要求输出:

{ 'a.b.c.d': 1, aa: 2, 'c[0]': 1, 'c[1]': 2 }

function convert(obj) {
  let str = '', res = {};
  const inner = (obj) => {
    const keys = Object.keys(obj);
    keys.forEach((item) => {
      const type = Object.prototype.toString.call(obj[item]).slice(8, -1);
      if (type === 'Object') {
        str += item + '.';
        inner(obj[item], str, res);
      } else if (type === 'Array') {
        obj[item].forEach((items, index) => {
          const key = `${item}[${index}]`;
          res[key] = items;
        });
      } else {
        str += item;
        res[str] = obj[item];
        str = '';
      }
    });
    return res;
  };
  return inner(obj);
}

console.log(convert(obj));

6.归类(天猫)

输入:

const industry_list = [
  {
    "parent_ind": "女装",
    "name": "连衣裙"
  },
  {
    "name": "女装"
  },
  {
    "parent_ind": "女装",
    "name": "半身裙"
  },
  {
    "parent_ind": "女装",
    "name": "A字裙"
  },
  {
    "name": "数码"
  },
  {
    "parent_ind": "数码",
    "name": "电脑配件"
  },
  {
    "parent_ind": "电脑配件",
    "name": "内存"
  },
];
> 输出:
/*{  "数码": {    "电脑配件": {        "内存" : {}     }  },  "女装" : {     "连衣裙": {},    "半身裙": {},    "A字裙": {}  }}*/
function convert_format(data) {
  const res = {};
  const map = data.reduce((res, v) => (res[v.name] = v, res), {});
  console.log(map);
  for (const item of data) {
    if (!item.parent_ind) {
      res[item.name] = {};
    }
  }
  for (const item of data) {
    if (item.parent_ind in map) {
      if (map[item.parent_ind].parent_ind) {
        const path = dfs(item.name);
        let re = res[path[0]];
        for (let i = 1; i  {
      path.unshift(name);
      if (!map[name].parent_ind) {
        return;
      }
      inner(map[name].parent_ind, path);
    };
    inner(name, path);
    return path;
  }
}


const result = convert_format(industry_list);
console.log(result);

排序篇

1.快速排序(要求Tc: O(nlogn) Sc:O(nlogn)) (排序类超高频)

function quickSort(array) {
    if (array === null || array.length === 0) {
        return array;
    }
    doQuickSort(array, 0, array.length - 1);
    return array;
}
function doQuickSort(array,left,right) {
    if (left >= right) {
        return;
    }
    let pivotPos = partition(array,left,right);
    doQuickSort(array,left, pivotPos - 1);
    doQuickSort(array,pivotPos + 1, right);
}
function partition(array,left,right) {
        let pivotIdx = (left + Math.random() * (right - left + 1)) | 0;
    let pivot = array[pivotIdx];
    // swap pivot 元素到最右边的位置
    swap(array, right, pivotIdx);

    let leftBound = left;
    let rightBound = right - 1;

    while (leftBound = pivot) {
                rightBound--;
            } else {
                swap(array, leftBound, rightBound);
                leftBound++;
                rightBound--;
            }
    } // leftBound == rightBound + 1
    // swap 回 pivot元素到中间的位置
    swap(array, leftBound, right);
    return leftBound;
}
function swap(array, i, j) {
    let tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

2.归并排序(要求Tc: O(nlogn) Sc:O(n))

function mergeSort(array) {
    if (array.length > 1) {
        const length = array.length;
        const mid = Math.floor(length / 2);
        const left = mergeSort(array.slice(0,mid));
        const right = mergeSort(array.slice(mid,length));
        array = merge(left,right);
    }
    return array;
}
function merge(left,right) {
    let i = 0,j = 0;
    const result = [];
    while (i  right[j] ? left[i++] : right[j++]);
    }
    return result.concat(i 

3.插入排序(要求Tc: O(n²) Sc:O(1))

function insertionSort(array) {
    for (let i = 1; i  0 && array[j - 1] > temp) {
            array[j] = array[j - 1];
            j--;
        }
        array[j] = temp;
    }
    return array;
}

LeetCode第912题

结语

以上题目均为精选高频题，希望对大家有帮助.

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net