目的
程序 = 数据结构 + 算法
了解数据结构、算法思想、优缺点、合理运用到项目中， 常见算法：
一、数据结构
1. 栈
调用栈： 后进先出（先进后出）
调用栈可能很长，需要占用很多的内存 --->竖着的 长方形
不能用于查找
优化：采用循环、尾递归
扩展：思考代码中方法名称、参数名称 存放的位置
实例：递归算法、函数调用（JVM)、深度优先遍历、两个栈实现一个队列、实现括号验证
1.1 括号验证
// https://leetcode-cn.com/problems/valid-parentheses/
//括号验证 : 遍历字符， （[{ 入栈，)]} 时，出栈校验
class Solution {
public boolean isValid(String s)
{
if(s == null || s.length()==0)
{
return true;
}
Stack<Character> stack = new Stack<>();
for(char c:s.toCharArray())
{
if(c=='(' || c=='[' || c=='{')
{
stack.push(c);
}
if(c ==')')
{
if(stack.isEmpty() || stack.pop()!='(')
{
return false;
}
}
if(c ==']')
{
if(stack.isEmpty() || stack.pop()!='(')
{
return false;
}
}
if(c =='}')
{
if(stack.isEmpty() || stack.pop()!='{')
{
return false;
}
}
}
return stack.isEmpty();
}
}
// 注意：
/**
* 1. 基础用法: String.toCharArray()、length() 需要加括号。
* 2. 栈初始化: Stack<Character> stack = new Stack<>()
* 3. 最后一步： stack.isEmpty(); // [
* 4. 校验（先自查 ）
*/
1.2 最小栈
// 取出栈内最小值。 思路： 同时操作两个栈，同时入栈、同时出栈。 =》 取栈 最大
class MinStack {
/** initialize your data structure here. */
Stack<Integer> stack;
Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if(minStack.isEmpty() || val < minStack.peek())
{
minStack.push(val);
}
else
{
minStack.push(minStack.peek());
}
}
public void pop() {
minStack.pop();
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
1.3 最大区间
class MaxSection {
//int[] numbers ={5,2,3,4,1}
public int getMax(int[] numbers)
{
//如果数据为空
if(numbers==null ||numbers.length ==0)
{
return 0;
}
//保存的是索引
Stack<Integer> stack = new Stack<>();
int max=0;
int[] sum = new int[numbers.length+1];
for(int i = 1;i<numbers.length;i++)
{
sum[i] = sum[i-1]+numbers[i-1];
}
for(int i=0;i<numbers.length;i++)
{
while(!stack.isEmpty() && numbers[i]<numbers[stack.peek()])
{
int index = stack.pop();
int left = i;
int right =i;
if(stack.isEmpty())
{
left = 0;
}else
{
left = index;
}
max = Math.max(max,numbers[index] * (sum[right]-sum[left])));
}
stack.push(i);
}
//最后一部分数据都是 从小到大排列,则未取完
while(!stack.isEmpty())
{
int index = stack.pop;
int left = numbers.length;
int right = numbers.length;
if(stack.isEmpty())
{
left = 0;
}else
{
left = index;
}
max = Math.max(max,numbers[index] * (sum[right]-sum[left])));
}
retrun max;
}
}
1.4 两个栈实现队列
分成两段： 第一个栈存新来的数据，第二个栈则取；
- 当第二个栈没有数据时，则从第一个栈，取出数据，放置到第二个栈（新来的数据在最上面 ）。
- 当要队列取数是，则从第二个栈取数。
2. 队列
实例：公交车站，排队等车、系统中各个资源管理、消息缓冲区管理、广度优先搜索
特点：先进先出
5.散列表
定义：根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访 问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
内部机制： 实现、冲突、散列函数
散列函数：
<1.它必须是一致的（同一输入，输出结果相同）
<2.它应将不同的输入映射到不同的数字 ** （没有冲突的情况） 很难
（1）散列函数很重要（最理想的情况：将键均匀映射到散列的不同位置）
（2）散列的链表不能太长，影响查询效率
构造方法：
（1）直接定址法（关键码本身和地址之间存在某个线性函数关系时，散列函数取为关键码的线性函数，即：H(key)=a*key+b，a、b均为常数。） 查找表较小且连续，不常用
（2）除留余数法（通过选择适当的正整数p，按计算公式H(K)=K mod p来计算关键码K的散列地址。
） 常用：Integer等数据类型 源码中hashcode
（3）平方取中法（将关键码K平方，取K^2中间几位作为其散列地址H(K)的值。
）
（4）随机数法（采用随机函数作为散列函数H(Key)=random(Key)，其中random为随机函数。）
当关键码长度不等时，采用该方法较恰当。
解决Hash冲突的处理方法：
（1）再hash
（2）缓冲区
（3）开放定址法(从发生冲突位置的下一个位置开始寻找空的散列地址。发生冲突时，线性探测下一个散列地址是：Hi=(H(key)+di)%m，（di=1,2,3...,m-1）)
（4）拉链法()
实例： HashTable、HashMap、加密算法、查找、海量数据处理
<1.模拟映射关系 -->将散列用于查找 （通过姓名查询电话号码）
<2.防止重复（投票站投票，不允许1人多投）
<3.将散列用于缓存（网站缓存，不用每次请求服务器）
性能：
1.较低的填充因子（散列包含的元素个数/位置总数）
2.良好的散列函数（各个语言内置有散列函数）
6.图
图有节点和边组成。
概念： 邻接表、邻接矩阵、邻接点、度
7.有向图
有方向，单向关系
8.无向图
无方向
9.树
树是一种特殊的图。
实例：家谱
最小生成树：n个顶点的连通图中选择n-1条边，构成权值之和最小的连通子图，被称为最小生成树。
参考
«算法图解»
- ”程序员小灰“ 公众号 (推荐)
- 网课（腾讯课堂）