数据结构和算法 | 仲灏小栈

![img](file:////private/var/folders/kc/qf5y8bzj1wj2gc4dh1rtsvhw0000gn/T/com.kingsoft.wpsoffice.mac/wps-izhaong/ksohtml/wpsyg6aGl.png)数据结构和算法

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

为何要考察

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

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

考察的重点

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

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

常见数据结构

注意事项

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

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

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

看几个面试题

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

复杂度

程序执行时需要的计算量和内存空间（和代码是否简洁无关）
复杂度是数量级（方便及记忆、推广），不是具体的数字
一般针对一个具体的算法，而非一个完整的系统

逻辑结构 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)—算法不可用

typ

/**
 * @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:求连续最多的字符和次数

typescript

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，不好识别复杂度
数字操作最快，其次是字符串

复杂度 ​

逻辑结构 vs 物理结构 ​

动态规划 ​

复杂度

逻辑结构 vs 物理结构

动态规划