数据结构和算法

谁说前端不需要算法？

参考：

• algomooc
• labuladong
• 前端该如何准备数据结构和算法？
• LeetCode 探索，强烈推荐按课程学习

数据结构

常见的数据结构有

• 有序数据结构：栈、队列、链表，有序数据结构省空间（存储空间小）
• 无序数据结构：集合、字典、散列表，无序数据结构省时间（读取时间快）
• 复杂数据结构，树、堆、图

首先需要学习数据存储最基础的两种数据结构：数组和链表，对应有序数据结构和无序数据结构两种类型

然后了解栈、队列、树、堆等数据结构，他们都是由数组或者链表实现的

一般的算法题，就是对这些数据结构的操作，归根到底就是基础的增删查改

这些操作或多或少都涉及到遍历 + 访问

遍历有线性和非线性两种方式，线性的就是for、while循环，非线性的就是递归。

• 递归主体，就是要循环解决问题的代码
• 递归的跳出条件，递归不能一直递归下去，需要完成一定条件后跳出

递归容易造成爆栈，尾部调用可以解决递归的这个问题

常见解题思想

分治 (Divide and Conquer): 分治是一种将问题分解成更小的子问题，然后解决子问题并将结果合并起来得到原问题解的方法。

贪心算法（Greedy Algorithm）：贪心算法是一种在每一步都选择当前状态下最优解的策略，以期望最终达到全局最优解。贪心算法通常适用于具有最优子结构的问题，即问题的最优解可以通过子问题的最优解来求解。

动态规划（Dynamic Programming）：动态规划是一种通过将问题分解成子问题并记录子问题的解来避免重复计算的方法。动态规划通常用于解决具有重叠子问题和最优子结构性质的问题。

回溯算法（Backtracking）：回溯算法是一种通过尝试所有可能的解决方案并在搜索过程中剪枝来找到问题的解的方法。回溯算法通常适用于组合优化问题、排列组合问题等。

深度优先搜索（Depth-First Search，DFS）：深度优先搜索是一种通过不断深入到问题的解空间中，直到找到问题的解或者无法继续搜索为止的方法。DFS通常用于图遍历、树遍历等问题。

广度优先搜索（Breadth-First Search，BFS）：广度优先搜索是一种从问题的起始状态开始逐层扩展搜索，直到找到问题的解或者搜索完整个解空间为止的方法。BFS通常用于寻找最短路径、图的连通性等问题。

分支限界法（Branch and Bound）：分支限界法是一种通过扩展当前最有希望的解决方案并剪枝来搜索问题解空间的方法。它通常用于组合优化、排列组合等问题。

双指针法（Two Pointers）：双指针法是一种通过使用两个指针在数组或者列表中移动来解决问题的方法。它通常用于查找滑动窗口、快速求解两数之和等问题。

算法复杂度

参考：算法的时间与空间复杂度（一看就懂）

复杂度主要从算法所占用的「时间」和「空间」两个维度去考量

时间复杂度

时间复杂度用来衡量算法的运行次数。

常见的时间复杂度量级有：

常数阶O(1)

对数阶O(logN)

线性阶O(n)

线性对数阶O(nlogN)

平方阶O(n²)

立方阶O(n³)

K次方阶O(n^k)

指数阶(2^n)

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度