算法和数据结构基础

衡量流程中进行常数操作的次数

原则

最后，只考虑最高阶项

常数项时间

与功能无关，实现算法是额外需要的空间

Vector

Linked List

Priority Queue

Hash Set

Tree Set

HashMap

TreeMap

O(N^2)

每次循环找出最小的，放到最前面
循环次数：N, N-1, N-2....2, 1

不稳定

O(N^2)

稳定

O(N^2)

稳定

实现

适用于小的数组

左有序，右有序，合并为一个大的有序数组

实质：把比较行为变成了有序信息并传递。
大量的比较结果信息被保留传递下去。

时间复杂度O(NlogN)

额外空间复杂度O(N)

稳定

实现

Tips

应用

给定一个数组，和 一个整数num，把小于等于num的数防止数组的左边，大于num的数防止数组右边

不稳定

时间复杂度O(NlogN)

最差情况O(N^2)

额外空间复杂度O(logN)

不基于比较的排序，必须和数据的样本的数据状况强相关
当最小值和最大值很窄的才有意义

桶就是一个容器，可以是数组，队列，栈，或状态

计数排序

基数排序

堆结构：逻辑概念，就是用数组实现的完全二叉树结构
实现可以是数组或链表

不稳定

时间复杂度O(NlogN)

额外空间复杂度O(1)

结构类型

堆排序算法

两种堆调整的代价
heapify

语言提供的堆结构 vs 手写堆结构

例题：
已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k，并且k相对于数组长度来说是比较小的。
请选择一个合适的排序策略，对这个数组进行排序。

两个参数：arr + k
参考代码：algorithmbasic2020/src/class04/Code05_SortArrayDistanceLessK.java

不基于比较的排序，对样本数据有严格要求，不易改写

基于比较的排序，只要规定好连个样本怎么比较大小就可以直接复用

基于比较的排序，时间复杂度的极限是O(N*logN)

时间复杂度O(N*logN)，额外空间复杂度低于O(N)，且稳定的基于比较的排序是不存在的

为了绝对的速度选快排

为了省空间选堆排

为了稳定选归并

归并排序的额外空间复杂度可以变成O(1)，但是不再稳定
搜索“归并排序 内部缓存法”

"原地归并排序“是垃圾帖，会让时间复杂度变成O(N^2)

快速排序稳定性改进，“01 stable sort”，但是对样本数据要求更多

在整型数组中个，请把奇数放在数组左边，偶数放在数组右边，要求所有奇数之间原始的校对次序不变，所有偶数之间的原始相对次序不变。

时间复杂度做到O(1)， 额外空间复杂度做到O(1)

通常对稳定性进行考虑

需充分考虑利用O(N*logN) 和 O(N^2) 排序的各自优势

双向链表

数组

判断栈满或空的方法

固定长度

设计两个栈，一个Data，一个Min

比较：

两个队列：Data 和 Helper

两个栈：Push和Pop

log(b，a) > d ==> O(N^log(b,a))

log(b,a) <d ==> O(N^d)

log(b,a) == d ==> O(N^d * logN)

可分解性

分解后的等价性

存在递归终止条件

警惕堆栈溢出

警惕重复计算

函数调用耗时多

考虑空间复杂度

平衡二叉树

跳表（Skip Map)

1. 返回负数的时候，第一个参数排在前面
2. 返回正数的时候，第二个参数排在前面
3. 返回0的时候，谁在前面无所谓

Node结构：
public class TerieTree {
       public static class Node1 {
         private int pass = 0;
         private int end = 0;
         private Node1[] nexts;

         public Node1() {
             pass = 0;
             end = 0;
             nexts = new Node1[26];
         }
    }

    public static class Ter1() {
        private Node1 root;

        public Trie01() {
            root = new Node1();
        }
     ......
    }
}

插入Insert

查找Word单词出现的次数

查找有几个字符串是以pre这个字符串为前缀的

删除

Node结构：
public static class Node2 {
    public int pass;
    public int end;
    public HashMap<Integer, Node2> nexts;

    public Node2() {
        pass = 0;
        end = 0;
        nexts = new HashMap<>();
    }
}

如果某个问题带有前缀查找特征，则可以在节点内部增加某种特定信息，从而用前缀树的方法来处理

笔试，重点考察时间复杂度

面试，时间复杂度依然第一位，但一定要找到空间最省的方法

使用容器（哈希表，数组等）

快慢指针

输入链表头节点，奇数长度返回中点，偶数长度返回上中点

输入链表头节点，奇数长度返回中点，偶数长度返回下中点

输入链表头节点，奇数长度返回中点，偶数长度返回上中点前一个Node

输入链表头节点，奇数长度返回中点，偶数长度返回下中点前一个Node

参考代码：algorithmbasic2020/src/class02/Code01_ReverseList.java

单链表实现

双链表实现

参考代码：algorithmbasic2020/src/class02/Code02_DeleteGivenValue.java

实现

笔试：
遍历链表，每个节点加入一个栈。
然后再次遍历，每一个动作，从栈中弹出一个节点进行比较。
如果有不同，则返回false。否则，true。

因为stack加入，再弹出，表示一个逆序。

利用快慢指针：
找到中点，
然后从慢指针开始，后半部压入栈，
然后从链表头开始比对栈中的每一个出栈节点，直到栈为空。
如果有任何一个栈节点不等于链表的节点，则为false，否则为true。

利用快慢指针：
找到中点；
调整中点指向null；
中点后的next指针反转指向前一个节点；
然后从两端向中间遍历，如果有不等，则为false。
直到任何L指针或R指针指向null，则结束比较，返回true

笔试：
把链表放在数组里，在数组上做partition

笔试：
利用Hash表，记录
<key,value> => <Origin Node, Clone Node>

面试：
不用Hash表，强制将Clone Node插入原链表中。
如 1->2->3 ==> 1->1'->2->2'->3->3'
利用此结构代替Hash表，记录新老Node对信息。

判断是否有环，有环的情况下返回第一个入环的节点

如果两个链表都无环，则此两链表一定最后的节点是相同的节点。
实现：

如果为两个有环链表，放回第一个相交节点，否则不相交，返回null。
如果两个有环链表相交，一定共用环。

如果一个有环，一个无环，则这两个链表不可能相交。

主方法

取巧的办法可以。
来到删除节点，copy下一个节点的值到该节点，然后删除下一个节点。

递归实现

非递归实现

用队列
头压队列
队列不为空，弹出，加左，再加右，

利用flag实现监控某层是否结束

求树最大宽度

可以用先序或者中序或者后序或者按层遍历，来实现二叉树的序列化
用了什么方式序列化，就用什么方式反序列化

先序实现

宽度优先序列化实现

Broto force方法

实现：
1. 当X有右树的时候，后继节点是右子树的最左的节点；
2. 当X没有右树的时候，X节点是后继父节点的左子树的最右的孩子。
方法：向上找父节点，直到自己是父节点的左孩子，且父节点不是空，则此父节点是后继；
如果父节点为空，则X为此树的最右节点，不存在后继节点

假设以X节点为头，假设可以向X左树和X右树要任何信息

在上一步的假设下，讨论以X为头节点的树，得到答案的可能性（最重要）

列出所有可能性后，确定到底需要向左树和右树要什么样的信息

把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息S

递归函数都返回S，每一颗子树都这么要求

写代码，在代码中考虑如何把左树的信息和右树的信息整合出整棵树的信息

实现：

与X无关

与X有关

实现

与X无关

与X有关

可获得信息：
左：最大子搜size
      bool isAllBST
       maxValue

可获得信息：
右：最大子搜size
      bool isAllBST
       minValue

实现

X来：
X.happy
a不来的子树的最大快乐值
b不来的子树的最大快乐值
c不来的子树的最大快乐值

X不来：
X = 0；
a来的子树的最大值，或a不来的子树的最大值；
b来的子树的最大值，或b不来的子树的最大值;
c来的子树的最大值，或c不来的子树的最大值

ChildTopic

实现

宽度优先遍历：
1）任何节点，有右无左，则false。否则继续。
2）一旦遇到左右孩子不双全，后续遇到的所有节点必须为叶节点。

实现

实现1

递归套路：

测试

方法1：
通过遍历，生成一个map<节点，父节点>。
对a遍历，把所有的父节点加入一个set
对b遍历，查看是否父节点在set中。
第一个发现的节点，则是最低公共祖先。

方法2：递归套路

ChildTopic

解决套路：
1. 实现一个不依靠贪心策略的解法X，可以用最暴力的尝试；
2. 脑补出贪心策略A，贪心策略B，贪心策略C。。。
3. 用解法X和对数器，用实验的方法得知哪个贪心策略正确；
4. 不用纠结贪心策略的证明

暴力解法

贪心算法：
选择对结束时间进行排序，早结束的先安排

暴力解法：
1。每个位置去放灯，和不放灯；
2. 验证是否满足条件

贪心算法：
1. i位置为X，则略过，直接到i+1去判断；
2. i位置为.，则：（此分支情况下，均需要放灯）
1） i+1为X，则i应该放灯；
     转到i+2位置上去判断
2）i+1为., 则：
    i) i+2位置为X，则i+1上放灯
    ii）i+2位置为.，则i+1上放灯
    转到i+3位置上去判断

（i位置不会被之前位置影响到）

可以利用数组下标代表user标号=>优化

Node节点定义：
// 点结构的描述 A 0
public class Node {
    public int value;
    public int in; // 直接入度
    public int out; // 直接出度
    public ArrayList<Node> nexts; //直接邻居（由自己出发能到达的节点）
    public ArrayList<Edge> edges; //到达直接邻居的边

    public Node(int value) {
        this.value = value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}

”边“的定义：
public class Edge {
    public int weight;
    public Node from;
    public Node to;

    public Edge(int weight, Node from, Node to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}

”图“的定义：
public class Graph {
    public HashMap<Integer, Node> nodes;
    public HashSet<Edge> edges;

    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}

Set：标记访问过的节点（避免环的访问）

队列：

Set：标记访问过的节点（避免环的访问）

栈：记录遍历时走的路径

业务处理在第一次入栈的时候做

1）在图中找到所有入度为0的点输出
2）把所有入度为0的点在图中删除，继续找入度为0的点输出，周而复始
3）图的所有点都被删除后，依次输出的顺序就是拓扑排序

要求：有向图且其中没有环
应用：事件安排、编译顺序

实现

中心思想时始终以边为主袋地位，无论如何都要选择权值最小的边，但是前提是使用此边后不能构成连通图。所以这个算法的第一步是将所有的边从小到大排序，之后按排列的顺序来一步一步选择我们需要的边。

1）总是从权值最小的边开始考虑，依次考察权值依次变大的边；
2）当前的边要么进入最小生成树的集合，要么丢弃
3）如果当前的边进入最小生成树的集合中不会形成环，就要当前边
4）如果当前的边进入最小生成树的集合中会形成环，就不要当前边
4）考察完所有边之后，最小生成树的集合也就得到了

实现

时间复杂度为O(e⋅loge)，e为边的数目，与顶点数量无关，适合稀疏图。

从某个顶点v开始，列出顶点 v 所有邻接点的边，选择权值最小的边（vi-->vj）加入到最小生成树中，并标记该边已被访问过；
再从vj开始 列出顶点vj所有邻接点的边，从中选择所有未被访问过的边中权值最小的边 vj-->vk 加入到最小生成树中，并标记该边已被访问过。

重复上述操作，直到找到n-1条边为止。

时间复杂度为O(n2)，n为顶点的数量，其时间复杂度与边得数目无关，适合稠密图。

贪心算法的一种

ChildTopic

分解为三步

考虑所有的情况

所有情况都归结为一种实现：
From，To， Other
从From移动到To，依靠Other做辅助

最优解时间复杂度O（2^N - 1)

实现

两次递归调用

子串：
子序列：位置先后不能乱，但可以不连续

ChildTopic

实现

实现

利用“分治限界”的思想

实现

algorithmbasic2020/src/class11/Code06_ConvertToLetterString.java

实现方法一

背包问题

对应code：algorithmbasic2020/src/class11/Code07_Knapsack.java

实现一

实现二

动态规划实现

对应code：algorithmbasic2020/src/class11/Code08_CardsInLine.java

实现一

基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

时间复杂度O(N^N)

应用位运算方法，减少常数项，加速了常数时间

code link：algorithmbasic2020/src/class12/Code01_RobotWalk.java

可以利用缓存子过程的结果

code：algorithmbasic2020/src/class12/Code02_StickersToSpellWord.java

arr中的顺序完全无所谓

ChildTopic

algorithmbasic2020/src/class12/Code05_PalindromeSubsequence.java

做一个二维表

填充第一行和第一列

dp[i][j]

返回dp[str1.length -1][str2.length - 1]

从左往右的尝试模型

范围上的尝试模型

多样本位置全对应的尝试模型

寻找业务限制的尝试模型

每一个可变参数的类型，一定不要比int类型更加复杂

原则1）可以违反，让类型突破到一维线性结构，那必须是唯一可变参数

如果发现原则1）被违反，但不违反原则2），只需要做到记忆化搜索即可

可变参数的个数，尽可能少！

图例

可变参数数量尽可能少

1）已经有了一个不违背原则的暴力递归，而且的确存在解的重复调用；
2）找到哪些参数的变化会影响返回值，对每一个列出变化范围；
3）参数间的所有的组合数量，意味着表的大小；
4）记忆化搜索的方法就是傻缓存，非常容易得到；
5）规定好严格表的大小，分析位置的依赖顺序，然后从基础填写到最终解：
6）对于有枚举行为的决策过程，进一步优化

空间压缩

状态化简

四边形不等式

其他

有重复调用同一个子问题的解，这种递归可以优化

如果每一个子问题都是不同的解，无法优化也不用优化

摸一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划

任何动态规划问题，都一定对应着某一个有解的重复调用的暴力递归

但不是所有的暴力递归，都一定对应着动态规划

解决一个问题，可能有很多尝试方法
可能在很多尝试方法中，又有若干个尝试方法有动态规划的方式
一个问题可能要若干个的动态规划的解法

1. R++新数从右侧进入窗口
2. L++数从左侧出窗口
3. 任何时候L<=R

创建一个双端队列(LinkedList) (其实队列中存放arr的下标)
只能从尾进，只能从头出
维持双端队列中从大到小排列。

实现：trainingcamp001/src/class01/Code01_SlidingWindowMaxArray.java

实现：trainingcamp001/src/class01/Code02_AllLessNumSubArray.java

优化总结：
1）数据状况是否可以优化
2）问题本身是否可以优化

实现：trainingcamp001/src/class01/Code03_MonotonousStack.java

ChildTopic

实现：trainingcamp001/src/class01/Code04_AllTimesMinToMax.java

建立一个以0开始的累加和数组：
i位置表示0~i的累加和

题目中的“正整数”建立了累加和的单调性映射

利用单调栈