数据结构和算法

数据结构和算法， 是大厂前端面试的“拦路虎”， 很多同学都望而生畏 。其实如果了解常用数据结构， 掌握基本的算法思维， 就 不能应对 。本章将通过多个面试题， 为你讲解算法面试题的解题思路， 同时复习常用数据结构和算法思维。

为何要考察

如果在短时间之内快速判断一个工程师是否优秀？ 考察算法是最合理的方式 —— 这是业界多年的经验积累。

前端面试考算法不是因为内卷 。算法一直在后端面试中被考察， 现在前端也考查， 说明前端能做的工作越来越多了 。这是好 事。

考察的重点

算法的时间复杂度和空间复杂度

三大算法思维： 贪心， 二分， 动态规划

常见数据结构

注意事项

算法， 有难度， 轻耐心学习

不仅关注题目本身， 更要关注知识点和解题思路

按顺序学习 （本章课程按顺序设计的）

看几个面试题

列举几个代表性的面试题， 具体参考视频。

复杂度

• 程序执行时需要的计算量和内存空间（和代码是否简洁无关）

• 复杂度是数量级（方便及记忆、推广），不是具体的数字

• 一般针对一个具体的算法，而非一个完整的系统

逻辑结构 vs 物理结构

两个没有任何关系，数组可以实现栈 栈不可以实现数组

• 栈 vs 数组

• 栈，逻辑结构，理论模型，不管如何实现，不收任何语言的限制

• 数组，物理结构，真实的功能实现，受限于编程语言

eg:

斐波那锲

• /**
   * @description: 循环 O(n)
   * @author: 仲灏<izhaong@outlook.com>🌶🌶🌶
   * @return {*}
   */
  export function fibonacci(n: number): number {
      if (n <= 0) return 0;
      if (n === 1) return 1;
  
      let n1 = 1;
      let n2 = 0;
      let res = 1;
      for (let i = 2; i <= n; i++) {
          res = n1 + n2;
          n2 = n1
          n1 = res
      }
  
      return res;
  }
  

动态规划

• 把一个大问题拆分成多个小问题, 主机向下拆解
• 用递归思路去分析问题, 再改为循环去实现
• 算法三大思维: 贪心 二分 动态规划

eg: 将数组中的0移到末尾

• 如输入[1，0， 3，0， 11，0]，输出「1，3， 11，0， 0， 0]
• 只移动0，其他顺序不变
• 必须在原数组进行操作

• 遍历数组，遇到0则 push 到数组末尾
• 用 splice 截取掉当前元素
• 时间复杂度是 O(n^2)—算法不可用

/**
 * @description: 时间复杂度O(n^2)
 * @author: 仲灏<izhaong@outlook.com>🌶🌶🌶
 * @param {number} arr
 * @return {*}
 */
export function moveZero1(arr: number[]): void {
    let length = arr.length
    if(!length) return
    let zeroLen = 0;
    for (let i = 0; i < length - zeroLen; i++) {
        if (arr[i] === 0) {
            arr.splice(i, 1);// 本身时间复杂度为 O(n)
            arr.push(0);
            zeroLen++;
            i--;
        }
    }
}

---

eg:求连续最多的字符和次数

interface IRes {
    char: string;
    length: number;
}

/**
 * @description: 求连续最多的字符和次数(嵌套循环) O(n)
 * @author: 仲灏<izhaong@outlook.com>🌶🌶🌶
 * @param {string} str
 * @return {*}
 */
export function findContinuousChar1(str: string): IRes {
    const res: IRes = {
        char: '',
        length: 0,
    };
    const length = str.length;
    if (!length) return res;

    let tempLength = 0;
    for (let i = 0; i < length; i++) {
        tempLength = 0;

        for (let j = i; j < length; j++) {
            if (str[i] === str[j]) {
                tempLength++;
            }

            if (str[i] !== str[j] || j === length - 1) {
                if (res.length < tempLength) {
                    res.char = str[i];
                    res.length = tempLength;
                }
                if (i < length - 1) {
                    i = j - 1; // 跳步
                }
                break;
            }
        }
    }
    return res;
}

/**
 * @description: 求连续最多的字符和次数(双指针) O(n)
 * @author: 仲灏<izhaong@outlook.com>🌶🌶🌶
 * @param {string} str
 * @return {*}
 */
export function findContinuousChar2(str: string): IRes {
    const res: IRes = {
        char: '',
        length: 0,
    };
    const length = str.length;
    if (!length) return res;

    let tempLength = 0;

    let i = 0;
    let j = 0;

    for (; i < length; i++) {
        if (str[i] === str[j]) {
            tempLength++;
        }
        if (str[i] !== str[j] || i === length - 1) {
            if (tempLength > res.length) {
                res.char = str[i];
                res.length = tempLength;
            }

            tempLength = 0;
            if (i < length - 1) {
                j = i;
                i--;
            }
        }
    }

    return res;
}

• 正则表达式--- 效率非常低, 慎用
• 累计各个元素的连续长度，最后求最大值——徒增空间复杂度
• PS：算法题尽量用“低级〞代码，慎用语法糖或者高级 API

重点

• 要注意实际复杂度，不要被代码表面迷惑
• 双指针常用于解决嵌套循环
• 算法题慎用正则表达式（实际工作可以用）

---

eg:

重点

• 尽量不要转换数据结构，尤其数组这种有序结构
• 尽量不要用内置 API，如 reverse，不好识别复杂度
• 数字操作最快，其次是字符串