熬夜肝了这一份来自牛客，LeetCode，剑指 Offer大佬整理的前端常用算法面试题.pdf，你也能进大厂

前言

1.2021年已过半，“金九银十”笔试即将要开始,整理一些算法题一起学习。
2.我统一使用JavaScript(V8/Node)解答,都已经调试通过。
3.一起加油！一起进步！

1.排序

以下两个函数是排序中会用到的通用函数，就不一一写了

function checkArray(array) {
  if (!array || array.length <= 2) return }
 function swap(array, left, right) {
  let rightValue = array[right]
  array[right] = array[left]
  array[left] = rightValue 
}

2.时间复杂度

通常使用最差的时间复杂度来衡量一个算法的好坏。
常数时间 O(1) 代表这个操作和数据量没关系，是一个固定时间的操作，比如说四则运算。
对于一个算法来说，可能会计算出如下操作次数 aN + 1 ， N 代表数据量。那么该算法的时间复杂度就是 O(N)。因为我们在计算时间复杂度的时候，数据量通常是非常大的，这时候低阶项和常数项可以忽略不计。
当然可能会出现两个算法都是 O(N) 的时间复杂度，那么对比两个算法的好坏就要通过对比低阶项和常数项了。

3.位运算

位运算在算法中很有用，速度可以比四则运算快很多。
在学习位运算之前应该知道十进制如何转二进制，二进制如何转十进制。这里说明下简单的计算方式

• 十进制 33 可以看成是 32 + 1 ，并且 33 应该是六位二进制的（因为 33 近似 32 ，而 32 是 2
  的五次方，所以是六位），那么 十进制 33 就是 100001 ，只要是 2 的次方，那么就是 1否则都为 0
• 那么二进制 100001 同理，首位是 2^5 ，末位是 2^0 ，相加得出 33

4.左移 <<

10 << 1 // -> 20

左移就是将二进制全部往左移动， 10 在二进制中表示为 1010 ，左移一位后变成 10100 ，转换为十进制也就是 20，所以基本可以把左移看成以下公式 a * (2 ^ b)

5.算数右移 >>

10 >> 1 // -> 5

算数右移就是将二进制全部往右移动并去除多余的右边， 10 在二进制中表示为 1010 ，右移一位后变成 101 ，转换为十进制也就是 5，所以基本可以把右移看成以下公式 int v = a / (2 ^ b)
右移很好用，比如可以用在二分算法中取中间值

13 >> 1 // -> 6

6.最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 动态规划
        res = cur = nums[0]
        for i in range(1, len(nums)):
            cur = max(nums[i], cur + nums[i])
            res = max(res, cur)
        return res

动态规划。时间复杂度O(n), 空间复杂度 O(1)。

7.链表

面试题：反转单向链表
题目需要将一个单向链表反转。思路很简单，使用三个变量分别表示当前节点和当前节点的前后节点，虽然这题很简单，但是却是一道面试常考题

以下是实现该算法的代码

var reverseList = function(head)
 { 
    // 判断下变量边界问题
    if (!head || !head.next) return head 
    // 初始设置为空，因为第一个节点反转后就是尾部，尾部节点指向 null
    let pre = null
    let current = head 
    let next 
    // 判断当前节点是否为空 
  // 不为空就先获取当前节点的下一节点 
  // 然后把当前节点的 next 设为上一个节点 
  // 然后把 current 设为下一个节点，pre 设为当前节点
  while(current) { 
    next = current.next 
    current.next = pre 
    pre = current 
    current = next
 }
  return pre 
 };

8.二叉树的先序，中序，后序遍历

先序遍历表示先访问根节点，然后访问左节点，最后访问右节点。
中序遍历表示先访问左节点，然后访问根节点，最后访问右节点。
后序遍历表示先访问左节点，然后访问右节点，最后访问根节点。

9.递归实现

递归实现相当简单，代码如下

function TreeNode(val) 
{
 this.val = val;
 this.left = this.right = null;
}
var traversal = function(root) {
 if (root)
 { 
 // 先序
 console.log(root);
 traversal(root.left);
 // 中序
 // console.log(root); 
 traversal(root.right);
 // 后序
 // console.log(root);
 }
};

10.树的深度

面试题：树的最大深度（题目需要求出一颗二叉树的最大深度）
以下是算法实现

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

11.动态规划

动态规划背后的基本思想非常简单。就是将一个问题拆分为子问题，一般来说这些子问题都是非常相似的，那么我们可以通过只解决一次每个子问题来达到减少计算量的目的。
一旦得出每个子问题的解，就存储该结果以便下次使用。

12.合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

以下是实现该算法的代码

function mergeTwoLists(l1, l2) {
    if (l1 = null && l2 == null) {
        return null;
    }
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

使用递归完成迭代

13.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

//反转链表
function reverseList(head){
    //1、遍历链表，把链表里面的每个节点的值都拿下来，存在数组里面
    //（在这里我们存的节点的值，而不是存的整个节点，这样是可以节约内存的）
    let arr=[];//arr用于存储链表的节点的值
    let p=head;//p用于遍历链表
    while(p){
        arr.push(p.val);
        p=p.next;
    }
    //2、再次遍历链表，将数组里面的值倒序的赋值给每一个节点的val域就实现了链表的反转
    //（我们没有考虑新建一个链表，而是用了原来的链表，可以节约创建新链表的时间和内存）
    p=head;
    while(p){
        p.val=arr.pop();
        p=p.next;
    }
    return head;
}

1、遍历链表，把链表里面的每个节点的值都拿下来，存在数组里面
2、再次遍历链表，将数组里面的值倒序的赋值给每一个节点的val域就实现了链表的反转

14.二分查找算法（建立在已经排好序的情况下）

function binarySearch(arr, data) {
    var end = arr.length - 1,
        start = 0;

    while (start <= end) {
        var middle = Math.floor((start + end) / 2);
        if (arr[middle] > data) {
            end = middle - 1;
        } else if (arr[middle] < data) {
            start = middle + 1;
        } else {
            return middle;
        }
    }
    return -1;
}
var arr = [1, 2, 3, 4, 5, 6];
console.log(binarySearch(arr, 2));

15.斐波那契数列

相信大家都不陌生,在高中数学中都有接触过,斐波那契数列以如下被以递推的方法定义：

F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）

实现过程
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定 N，计算 F(N)。

以下是实现该算法的代码

/**
 * @param {number} N
 * @return {number}
 */
var fib = function(N) {
    if (N<2) return N;
    var frist = 0;
    var second = 1;
    for (var i=2;i<=N;i++) {
        second = frist + second;
        frist = second - frist;
    }
    return second;
};

for循环，用两个变量保存前两项斐波那契数即可。并且变量交换时也无需临时变量,空间复杂度O(N)

16.找出下列正数组的最大差值

输入 [10,5,11,7,8,9]
输出 6

这是通过一道题目去测试对于基本的数组的最大值的查找，很明显我们知道，最大差值肯定是一个数组中最大值与最小值的差。

 function getMaxProfit(arr) {
    var minPrice = arr[0];
    var maxProfit = 0;
    for (var i = 0; i < arr.length; i++) {
        var currentPrice = arr[i];
        minPrice = Math.min(minPrice, currentPrice);
        var potentialProfit = currentPrice - minPrice;
        maxProfit = Math.max(maxProfit, potentialProfit);
    }
    return maxProfit;
}

17.随机生成指定长度的字符串

实现一个算法，随机生成指制定长度的字符窜。

以下是实现算法的代码

比如给定 长度 8  输出 4ldkfg9j
function randomString(n) {  
  let str = 'abcdefghijklmnopqrstuvwxyz9876543210';
  let tmp = '',
      i = 0,
      l = str.length;
  for (i = 0; i < n; i++) {
    tmp += str.charAt(Math.floor(Math.random() * l));
  }
  return tmp;
}
module.exports = randomString;  

18.找到任意两个数字的最大和

找到两个最大的数并返回它们的和。

function topSum(arr){
        if(arr.length<2) return null;
        var first,second;
        if(arr[0]>arr[1]){
            first = arr[0];
            second=arr[1];
        }else{
            first = arr[1];
            second=arr[0];
        }
        for(var i=2;i<arr.length;i++){
            if(arr[i]>first){
                second = first;
                first = arr[i];
            }else if(arr[i]>second){
                second = arr[i];
            }
        }
        return first+second;
    }

19.去掉一组整型数组重复的值

比如输入: [1,13,24,11,11,14,1,2]
输出: [1,13,24,11,14,2]
需要去掉重复的11 和 1 这两个元素。

这道问题出现在诸多的前端面试题中，主要考察个人对Object的使用，利用key来进行筛选。

/** 
* unique an array 
**/ 
let unique = function(arr) {   
  let hashTable = {}; 
  let data = []; 
  for(let i=0,l=arr.length;i<l;i++) { 
    if(!hashTable[arr[i]]) { 
      hashTable[arr[i]] = true; 
      data.push(arr[i]); 
    } 
  } 
  return data 
} 
module.exports = unique;  

20.替换空格

请实现一个函数，将一个字符串中的每个空格替换成“%20”。

例如，当字符串为We Are Happy.
则经过替换之后的字符串为We%20Are%20Happy

解题思路：利用简单的正则获取空格,并且替换成%20即可。

部分正则规则:/g 匹配所有符合条件的元素.
\d：表示数字  ^：表示开头  $：表示结尾  +：匹配多个
例如: ^\d+$ 匹配的字符串只能是数字

let readline = require('readline');

let rl = readline.createInterface({
    input:process.stdin,
    output:process.stdout
})

rl.on('line',function(input){
    // let result = deal(input);
    let result = input.trim().replace(/ /g,'%20');  //replace(获取值,替换值)  
    console.log(result);
    
    return result;
})

21.实现一个函数，判断输入是不是回文字符串

function isPlalindrome(input) {
  if (typeof input !== 'string') return false;
  return input.split('').reverse().join('') === input;
}

22.腾讯：数组扁平化、去重、排序

面试题

已知如下数组：var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10];
编写一个程序将数组扁平化去并除其中重复部分数据，最终得到一个升序且不重复的数组

let arr =[[1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10]
function newArray ( ) {
  while(arr.some(Array.isArray)){
    arr = [].concat(...arr)
  }
  arr = [...new Set(arr)].sort((a,b)=>{
    return a-b
  })
  return arr
}
newArray()
console.log(arr);

23.编写一个函数计算多个数组的交集

要求：输出结果中的每个元素一定是唯一的

const getIntersection = (...arrs) => {
    return Array.from(new Set(arrs.reduce((total, arr) => {
        return arr.filter(item => total.includes(item));
    })));
}

24.选择排序

选择排序是从数组的开头开始，将第一个元素和其他元素作比较，检查完所有的元素后，最小的放在第一个位置，接下来再开始从第二个元素开始，重复以上一直到最后。

很简单嘛：外层循环从0开始到length-1， 然后内层比较，最小的放开头

function selectSort(arr) {
    var len = arr.length;
    for(let i = 0 ;i < len - 1; i++) {
        for(let j = i ; j<len; j++) {
            if(arr[j] < arr[i]) {
                [arr[i],arr[j]] = [arr[j],arr[i]];
            }
        }
    }
    return arr
}

• 外层循环的i表示第几轮，arr[i]就表示当前轮次最靠前(小)的位置；
• 内层从i开始，依次往后数，找到比开头小的，互换位置即可

25.爬楼梯问题

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

分析： 这个问题要倒过来看，要到达n级楼梯，只有两种方式，从（n-1）级 或 （n-2）级到达的。所以可以用递推的思想去想这题，假设有一个数组s[n], 那么s[1] = 1（由于一开始就在第一级，只有一种方法）， s[2] = 1（只能从s[1]上去 没有其他方法）。

那么就可以推出s[3] ~ s[n]了。

下面继续模拟一下， s[3] = s[1] + s[2]， 因为只能从第一级跨两步， 或者第二级跨一步。

function cStairs(n) {
    if(n === 1 || n === 2) {
        return 1;
    } else {
        return cStairs(n-1) + cStairs(n-2)
    }
}

没错，其实就是斐波纳契数列

26.栈实现队列

使用栈实现队列的下列操作：
push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。
示例：

let queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

解题思路
既然栈是先进后出, 要想得到先进先出的效果，我们不妨用两个栈。
当进行push操作时，push 到 stack1，而进行pop和peek的操作时，我们通过stack2。

当然这其中有一个特殊情况，就是stack2是空，如何来进行pop和peek? 很简单，把stack1中的元素依次 pop 并推入stack2中，然后正常地操作 stack2即可，如下图所示:

这就能保证先入先出的效果了。

以下是实现该算法的代码

var MyQueue = function() {
    this.stack1 = [];
    this.stack2 = [];
};

MyQueue.prototype.push = function(x) {
    this.stack1.push(x);
};
// 将 stack1 的元素转移到 stack2
MyQueue.prototype.transform = function() {
  while(this.stack1.length) {
    this.stack2.push(this.stack1.pop());
  }
}

MyQueue.prototype.pop = function() {
  if(!this.stack2.length) this.transform();
  return this.stack2.pop();
};

MyQueue.prototype.peek = function() {
    if(!this.stack2.length) this.transform();
    return this.stack2[this.stack2.length - 1];
};

MyQueue.prototype.empty = function() {
    return !this.stack1.length && !this.stack2.length;
};

27.队列实现栈

和上一题的效果刚好相反，用队列先进先出的方式来实现先进后出的效果。

解题思路

回到我们的目标，我们的目标是拿到队尾的值，也就是3。这就好办了，我们让前面的元素统统出队，只留队尾元素即可，剩下的元素让另外一个队列保存。

代码实现

var MyStack = function() {
    this.queue1 = [];
    this.queue2 = [];
};
MyStack.prototype.push = function(x) {
    if(!this.queue2.length) this.queue1.push(x);
    else {
        // queue2 已经有值
        this.queue2.push(x);
        // 旧的栈顶移到 queue1 中
        this.queue1.push(this.queue2.shift());
    }

};
MyStack.prototype.transform = function() {
    while(this.queue1.length !== 1) {
        this.queue2.push(this.queue1.shift())
    }
    // queue2 保存了前面的元素
    // 让 queue1 和 queue2 交换
    // 现在queue1 包含前面的元素，queue2 里面就只包含队尾的元素
    let tmp = this.queue1;
    this.queue1 = this.queue2;
    this.queue2 = tmp;
}
MyStack.prototype.pop = function() {
    if(!this.queue2.length) this.transform();
    return this.queue2.shift();
};
MyStack.prototype.top = function() {
    if(!this.queue2.length) this.transform();
    return this.queue2[0];
};
MyStack.prototype.empty = function() {
    return !this.queue1.length && !this.queue2.length;
};

实现过程中，值得注意的一点是，queue1 始终保存前面的元素，queue2 始终保存队尾元素（即栈顶元素 ）。

但是当 push 的时候有一个陷阱，就是当queue2已经有元素的时候，不能将新值 push 到 queue1，因为此时的栈顶元素应该更新。此时对于新的值来说，应先 push 到 queue2， 然后将旧的栈顶从queue2出队，推入 queue1，这样就实现了更新栈顶的操作。

28.双指针问题

最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

解题思路： 先按照升序排序，然后分别从左往右依次选择一个基础点 i（0 <= i <= nums.length - 3），在基础点的右侧用双指针去不断的找最小的差值。

假设基础点是 i，初始化的时候，双指针分别是：

• left：i + 1，基础点右边一位。
• right: nums.length - 1 数组最后一位。

然后求此时的和，如果和大于 target，那么可以把右指针左移一位，去试试更小一点的值，反之则把左指针右移。

在这个过程中，不断更新全局的最小差值 min，和此时记录下来的和 res。最后返回 res 即可。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
let threeSumClosest = function (nums, target) {
  let n = nums.length
  if (n === 3) {
    return getSum(nums)
  }
  // 先升序排序 此为解题的前置条件
  nums.sort((a, b) => a - b)

  let min = Infinity // 和 target 的最小差
  let res

  // 从左往右依次尝试定一个基础指针 右边至少再保留两位 否则无法凑成3个
  for (let i = 0; i <= nums.length - 3; i++) {
    let basic = nums[i]
    let left = i + 1 // 左指针先从 i 右侧的第一位开始尝试
    let right = n - 1 // 右指针先从数组最后一项开始尝试

    while (left < right) {
      let sum = basic + nums[left] + nums[right] // 三数求和
      // 更新最小差
      let diff = Math.abs(sum - target)
      if (diff < min) {
        min = diff
        res = sum
      }
      if (sum < target) {
        // 求出的和如果小于目标值的话 可以尝试把左指针右移 扩大值
        left++
      } else if (sum > target) {
        // 反之则右指针左移
        right--
      } else {
        // 相等的话 差就为0 一定是答案
        return sum
      }
    }
  }

  return res
}

function getSum(nums) {
  return nums.reduce((total, cur) => total + cur, 0)
}

以上这些题目你都会做了吗？我想你绝对会懵逼！不服？来，评论区里show出你的代码！（怂。。。）有问题也希望各位大佬批评指出，核实修改。