个人总结-常问问题
# 入门篇
# 定义
数据结构： 就是一个能组在一起的集合对象。比如数组 链表 队列等。
线性表结构 ： 数组、链表、堆、栈 非线性表结构 ： 树、图论 算法：就是解决问题的
# 时间复杂度
o(1）< o(log2n)<o(n)<o(nlog2n)<o(n^2)<o(n^3)<o(2^n)<o(n!)<o(n^n)
- o(log2n) ： while( i <= n){ i = i * 2; }
- O(n) for(i = 0 ; i < n;i++){}
- O(nlogn) ： for(int j = 0 ; j < n ;j++){ for(i = 0 ; i < n;i++){} }
- 平方：O(n^2) for(int j = 0 ; j < n ;j++){ for(int j = 0 ; j < n ;j++){} }
- N次方：O(n^n) O(n!) ： n张牌的洗牌
# 基本数据结构
# 数组
经典问题： 统计14亿年龄数据。 桶排序。 特点： 连续的内存（CPU高速缓存），相同数据类型，随机访问O(1)的效率。 为啥数组的下标要从0开始？ 申请的空间地址就是O(0)了，不需要1-1的额外操作。 下标：数组最优一个特点。这里可以通过下标表示成有意义的数据，不只是数据里面的标记，年龄和下标对应。 随机访问：可以直接通过下标定位到数组中的某一个数据 。 O(1) 复杂度。
# 链表
# 经典问题
- LRU（最近最少使用）缓存淘汰算法？ 找到删除，插入头节点，满了剔除尾节点。
- 约瑟夫问题？ 环形链表，用size判断结束。
# 特点
不需要连续的内存空间。 有指针引用。 有三种最常见的链表结构：单链表、双向链表和循环链表
# 实现
插入/删除3种方式（头插法、尾插法、中间插法），实现各不相同。
# 对比
容易动态扩容； 稀疏数组，往往会用链表来代替。链表容易出现栈溢出。
# 栈
# 经典问题
- 如何设计一个括号匹配的功能 ： 1个栈，左边就入栈，右边出栈匹配
- 如何设计一个浏览器的前进和后退功能 ： 两个栈，点后退A出站到B入站。点前进从B出站到A入站。 点新页面,A栈清空B栈
- 代码函数调用中的应用。
- 数学表达式求值： 两个栈来实现：一个放数字 一个放符号。
1.遇到是数字 我们就直接入栈到数字栈里面去。如果前一个也是数字，需要出栈*10 + 数字，再入栈。 2.遇到是符合 就把符号栈的栈顶拿出来做比较。如果说他比栈顶符号的优先级高就直接入栈，如果比符号栈顶的优先级低或者相同，就从符号栈里面取栈顶进行计算（从数字栈中取栈顶的2个数），计算完的结果还要再放入到数字栈中。 3.最后清空2个栈的内容。
# 特点
后进先出即Last In First Out （LIFO） 栈顶入栈，栈顶出栈。 出栈入栈都是O(1)的操作。 比较高效的数据结构。 通常用于匹配的操作。
# 实现
为啥不用数组和链表？？封装添加限制操作，防止误操作。 通常以数组头为栈底，数组尾为栈顶的。 通常以链表头为栈顶
# 队列
进行插入操作的端称为队尾，进行删除操作的端称为队头。 想想排队，入队就是队尾插入，出队就是对头移除。 先进先出（FIFO—first in first out）。
# 应用
优先队列： 普通用户，vip用户，svip用户。 阻塞队列： 并发队列。 队列在线程池中的应用
# 操作分类
- 单向队列（Queue）：只能在一段插入数据，另一端删除数据。
- 双向队列（Deque）：每一段都可以进行插入数据和删除数据的操作。
# 实现分类
顺序队列,是基于数组实现的 链式队列的实现 循环队列,是一种顺序存储结构表示的队列，为了解决假溢出问题而将他设置成头尾相接的循环队列。
数据结构为 少用一个存储位置。取余的方式定位 判断满：(tail+1)%n==head 怎么判断空？tail==head size的计算公式： (tail - head + cap) % cap;
# 算法思想
# 思想
# 枚举算法 | 暴力破解 | 枚举法
即对可能的解集合一一列举。 往往就是循环。 （最基础的思想，能解决所有问题。唯一缺点就是慢，最最基础的解法）。
# 数论算法
利用数学公式或者定理或者规律求解问题
# 回溯算法 | 试探法
和枚举类似，重点区别是试探不成功就不再继续了。
# 分治算法
大问题分解成同类子问题，而后再合并。 （同时子问题之间没有公共的子问题：如f(n)=f(n-1)+f(n-2) ）。
不能合并 可以考虑贪心或者dp
# 贪心算法
# 动态规划 | dp
# 递归
常用的编码实现，属于手段。 一般分2步: 递（分解） ， 归（合并）。 常用的场景：大化小、求解思路完全一样、终止条件。 3个条件满足 编码注意 ： 求解公式、一定能执行的终止条件
递归可以简化代码以及可读性高。 但是使用起来一定要注意，栈溢出和时间问题。 可以用循环优化它。
# 应用
- 斐波那契数列 ： f(n)=f(n-1)+f(n-2)
- 微信分销系统中有一个返利。
- n!，n的阶乘
# 递归的优化
- 使用非递归： 转化为循环，避免创建栈空间。
- 加入缓存 ： 避免重复计算。
- 尾递归 : 避免创建栈空间。 jdk源码里面大量使用。
什么是尾递归？尾递归就是调用函数一定出现在末尾，没有任何其他的操作了(不会在做计算如 f(n-1)+1 )。 避免创建栈空间: 因为我们编译器在编译代码时，如果发现函数末尾已经没有操作了，这时候就不会创建新的栈，而是覆盖到前面去。 实现特点： 尾递归就是传入结果，倒着算，同时也不需要在回溯了。