高频合集 | 全栈大前端

# 快速排序

普通版

const quickSort=function(array){
    //边界判断
    if(array.length<2)return array
    //设置基准值
    const pivot =array[0]
    const left= []
    const right =[]
    for(let i=0;i<array.length;i++){
        const value=array[i]
        if(value<pivot){
            left.push(value)
        }else{
            right.push(value)
        }
    }
    //递归,合并数组
    return [...quickSort(left),pivot,...quickSort(right)]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5行精简版

const quickSort=function(array){
    //边界排除
    if(array.length<2)return array
    //找到基准值
    const pivot =array[array.length-1]
    //比基准值小的，放到左侧数组
    let left =array.filter((v,i)=>v<=pivot && i!=array.length-1)
    //比基准值大的，放入右侧数组
    let right =array.filter((v,i)=>v>pivot)
    //递归 左侧和右侧数组，解构并合并
    return [...quickSort(left),pivot,...quickSort(right)]
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 二分查找(简单) (opens new window)

var search = function(nums, target) {
    let low = 0, high = nums.length - 1;
    while (low <= high) {
        const mid = Math.floor((high - low) / 2) + low;
        const num = nums[mid];
        if (num === target) {
            return mid;
        } else if (num > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 两数之合

暴力法

const twoNum=function (num,target){
    for(let i =0;i<nums.length;i++){
        for(let j=i+1;j<nums.length;j++){
            if(nums[i]+nums[j]==target){
                return [i,j]
            }
        }
    }
}

1
2
3
4
5
6
7
8
9

求差-对象方式

function twoSum(nums, target) {
  let temp = {};
  for (let i = 0; i < nums.length; i++) {
    const diff = temp[target - nums[i]];
    if (diff !== undefined) {
      return [diff, i];
    }
    temp[nums[i]] = i;
  }
}

1
2
3
4
5
6
7
8
9
10

求差-map 方式

//求差-map方式
const twoSum = function (nums, target) {
  const map = new Map();
  const len = nums.length;
  for (let i = 0; i < len; i++) {
    const diff = target - nums[i];
    if (map.has(diff)) {
      return [map.get(diff), i];
    }
    map.set(nums[i], i);
  }
};

1
2
3
4
5
6
7
8
9
10
11
12

# 三数之和

//排序+对撞指针
const threeSum= function(nums){
    //边界判断
    if(!nums||num.length<3) return []
    const result=[]
    nums.sort((a,b)=>a-b);
    for(let i =0;i<nums.length;i++){
        //跳过重复数字
        if(i&&nums[i]===nums[i-1]) continue
        //左指针
        let left = i+1;
        //右指针
        let right =nums.length-1;
        while(left<right){
            const sum = nums[i]+nums[left]+nums[right]
            //大于0移动右指针
            if(sum>0){
                right--
            }else if(sum<0){
                left++
            }else{
                result.push([nums[i],nums[left++],nums[right--]]);
                //跳过重复数字
                while(nums[left]===nums[left-1]){
                    left++;
                }
                while(nums[right]==nums[right+1]){
                    right--
                }
            }
        }
    }
    return result
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 判断有效括号

const isValid =function(s){
  if(typeof s !=='string')return false
  const map={
      '{':'}',
      '[':']',
      '(':')'
  }
    let stack=[]
    for(let i=0;i<s.length;i++){
        const value=s[i]
        if(value=='{'||value=='['||value=='('){
            stack.push(map[value])
        }else{
            if(!stack.length ||stack.pop()!==value){
                return false
            }
        }
    }
    return !stack.length
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 用栈实现队列

const MyQueue =function (){
    //初始化两个栈
    this.stack1=[]
    this.stack2=[]
}
MyQueue.prototype.push=function(x){
    this.stack1.push(x)
}
MyQueue.prototype.pop=function(){
    if(this.stack2.length<=0){
        while(this.stack1.length!==0){
            this.stack2.push(this.stack1.pop())
        }
    }
    return this.stack2.pop()
}
MyQueue.prototype.peek=function(){
    if(this.stack2.length<=0){
        while(this.stack1.length!==0){
            this.stack2.push(this.stack1.pop())
        }
    }
    const stack2Len=this.stack2.length
    return stack2Len && this.stack2[stack2Len-1]
}
MyQueue.prototype.empty=function(){
    return !this.stack1.length && !this.stack2.length
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 环形链表

标记法

const hasCycle=function(head){
    //边界判断
    if(!head||!head.next)return false
    //循环链表
    while(head){
        if(head.flag)return true
        head.flag=true
        head=head.next
    }
    return false
}

1
2
3
4
5
6
7
8
9
10
11

快慢指针

const hasCycle=function(head){
  if(!head||!head.next) return false
  let fast=head.next.next
  let slow=head.next
  while(fast!=slow){
      if(!fast ||!fast.next) return false
      fast=fast.next.next
      slow=slow.next
  }
  return true
}

1
2
3
4
5
6
7
8
9
10
11

# 链表中环的入口节点

标记法

const detectCycle=function(head){
    while(head){
        if(head.flag){
            return head
        }else{
            head.flag=true
            head=head.next
        }
    }
    return null
}

1
2
3
4
5
6
7
8
9
10
11

# 反转链表

//递归
const reverseList =function(head){
        if(!head || !head.next){
            return head
        }
        let next=head.next
        const reverseHead= reverseList(next)
        head.next=null
        next.next=head
        return reverseHead
}

//迭代
const reverseList=function(head){
    //初始化前驱节点为null
    let pre=null
    //初始化目标节点为头节点
    let cur =head
    //只要目标节点不为null,遍历就得继续
    while(cur !==null){
        //记录next 节点
        let next=cur.next
        //反转指针
        cur.next=pre
        //pre 往前走一步
        pre=cur
        //cur 往前走一步
        cur=next
    }
    //反转结束后,pre 就会变成链表头节点
    return pre
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 二叉树的（前中后）序遍历

前序

// 递归实现
const preorderTraversal=function(root,array=[]){
    if(root){
        //递归实现
        array.push(root.val);
        preorderTraversal(root.right,array)
        perorderTraversal(root.left,array)
    }
    return array
}

//非递归实现
const preorderTraversal=function(root){
    //初始化数据
    const res=[];
    const stack=[];
    while(root||stack.length){
        while(root){
            res.push(root.val);
            stack.push(root)
            root=root.left;
        }
        root=stack.pop()
        root=root.right
    }
    return res
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

中序

//递归实现
const inorderTraversal=function(root,array=[]){
    if(root){
        inorderTraversal(root,left,array)
        array.push(root.val)
        inorderTraversal(root.right,array)
    }
    return array
}

//非递归实现
const inorderTraversal=function(root,array=[]){
    //初始化数据
    const res =[]
    const stack=[]
    while(root||stack.length){
        while(root){
            stack.push(root);
            root=root.left
        }
        root= stack.pop();
        res.push(root.val)
        root=root.right
    }
    return res
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

后序

//递归
const postorderTraversal=function(root,array=[]){
    if(root){
        postorderTraversal(root.left,array)
        postorderTraversal(root.right,array)
        array.push(root.val,array)
    }
}
//非递归
const postorderTraversal=function(root){
    const res =[]
    const stack=[]
    while(root||stack.length){
        while(root){
            stack.push(root)
            res.unshift(root.val)
            root=root.right
        }
        root= stack.pop()
        root.left;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 反转二叉树

const invertTree =function (root){
  // 边界条件，当root为空时直接返回
    if(!root) return root;
    // 先交换root的左右子树，这里我们利用js的解构赋值的新特性可以迅速的交换左右子树
    [root.left, root.right] = [root.right, root.left];
    // 分别递归左右子树
    invertTree(root.left)
    invertTree(root.right)
    return root;
}

1
2
3
4
5
6
7
8
9
10

# 二叉树的层序遍历

var levelOrder = function(root,depth=0,res=[]) {
    if(!root)return res
    if(!res[depth]){
        res[depth]=[]
    }
    res[depth].push(root.val)
    levelOrder(root.left,depth+1,res)
    levelOrder(root.right,depth+1,res)
    return res
};

1
2
3
4
5
6
7
8
9
10

# LRU Cache

//最近最少使用原则，使用就更新，不使用往队列后面排
class LRU {
  constructor(max) {
    this.cache = new Map();
    this.max = max;
  }
  get(key) {
    if (this.cache.has(key)) {
      //存在即更新
      let temp = this.cache.get(key);
      this.cache.delete(key);
      this.cache.set(key);
      return temp;
    }
    return -1;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      //存在即删除
      this.cache.delete(key);
    } else if (this.cache.size >= this.max) {
      //缓存超过最大阀值,删除最后一位
      this.cache.delete(this.cache.keys().next().value);
    }
    //更新
    this.cache.set(key, value);
  }
}

const cache = new LRU(2 /* 缓存容量 */);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // 返回  1
cache.put(3, 3); // 该操作会使得密钥 2 作废
console.log(cache.get(2)); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
console.log(cache.get(1)); // 返回 -1 (未找到)
console.log(cache.get(3)); // 返回  3
console.log(cache.get(4)); // 返回  4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# 无重复字符的最长子串

const lengthOfLongestSubstring=function(s){
    let arr =[],max=0
    for(let i =0;i<s.length;i++){
        let index =arr.indexOf(s[i])
        if(index!==-1){
            arr.splice(0,index+1)
        }
        arr.push(s.charAt(i))
        max = Math.max(arr.length,ma)
    }
    return max
}

1
2
3
4
5
6
7
8
9
10
11
12

# 最小的K个数

const findKthLargest=function(nums,k){
    return nums.sort((a,b)=>a-b).slice(0,k)
}

1
2
3

# 前K个高频元素

const topKFrequent =function(nums,k){
    let map =new Map()
    let arr=[...new Set(nums)]
    nums.map((num)=>{
        if(map.has(num)){
            map.set(num,map.get(num)+1)
        }else{
            map.set(num,1)
        }
    })
    return arr.sort((a,b)=>map.get(b)-map.get(a)).slice(0,k)
}

1
2
3
4
5
6
7
8
9
10
11
12

# 斐波拉契数列

    const fib =function(n,memory=[]){
        if(n<2)return n
        if(!memory[n]){
            memory[n]=fib(n-1,memory)+fib(n-2,memory)
        }
        return memory[n]
    }

1
2
3
4
5
6
7

# 跳台阶

    const numWays= function(n){
        if(n<=1)return 1
        if(n===2)return 2
        return (numWays(n-1)+numWays(n-2))%10000007
    }

1
2
3
4
5

# 爬楼梯

const climbStairs =function(n){
    const f=[];
    f[1]=1;
    f[2]=2
    for(let i=3;i<=n;i++){
        f[i]=f[i-2]+f[i-1]
    }
    //返回目标值
    return f[n]
}

1
2
3
4
5
6
7
8
9
10
11

# 其他高频题汇总

必须干掉这10道，面试100%遇到! (opens new window)

# 算法面试 TOP150系列

简单题(上) (opens new window)

简单题(下) (opens new window)

中等题 (opens new window)

← 动态规划 JavaScript之基础函数 →