内容

12a2024/10/3大约 61 分钟

内容

数据结构

哈希类结构

哈希类结构是根据关键码值key value直接进行访问的结构，通过将关键码值映射到表中的一个位置，查找记录或对应结果，加快查找速度，映射存储位置的函数称为散列函数，核心是将码值映射到数组的索引上，实现快速存取
主要代表是哈希表和哈希集合，哈希集合用于查找记录，哈希表用于查找对应结果
如果是数字索引，数字范围不大且保证没有碰撞，可以使用数组作为哈希结构存储记录(bool)或对应结果，操作方便，且时间消耗更低

哈希集合HashSet

常用于快速查找对应元素是否存在，对于一个按下标访问的数据结构而言，难以快速频繁了解某个元素是否存在于此结构中
如果希望频繁查找无序数组等按下标访问的数据结构或是之前获取到的结果序列中是否存在某个值，可以考虑使用哈希集
常用api

// 创建
Set<String> set = new HashSet<>();

// 加入值，如果之前不包含此值，返回true
boolean add(String e);
// 加入值，如果set有修改返回true
boolean addAll(Collection<String> c);

// 如果Object.equals为true，删除值，如果删除返回true
boolean remove(Object o);
// 删除值，如果set有修改返回true
boolean removeAll(Collection<?> c);

// 值判断，存在返回true
boolean contains(Object o);
// 值判断，如果提供的值集合是哈希表的子集，返回true
boolean contains(Collection<?> c);

// 清空
void clear();
// 为空判断，为空返回true
boolean isEmpty();

二进制集合

如果数据范围不大，且容易与数字 $[1, 64]$ 内的数一对一映射，可以考虑用数位代替集合，即使用一个long类型整数每个数位代表一个情况，使用移位和与运算判断某种情况是否存在，使用移位和或运算添加某种情况

哈希表HashMap

用于存储需要随机访问的键值结果，对于大量访问非数字索引的结果很有帮助
如果需要存储一些以非数字为索引的结果或需要快速增删的离散数字结果列表可以考虑使用哈希表，对于连续数字索引性能不如数组
常用api

// 创建
HashMap<String, Integer> map = new HashMap<>();

// 合并键值对，如果键不存在，相当于put方法
// 如果键存在，将执行remappingFunction(oldValue, newValue) -> value
V merge(K key, V value, 
        BiFunction<? super V, ? super V, ? extends V> remappingFunction);
// 加入键值对，替换原有值，返回先前值
V put(K key, V value);
// 如果值不存在，插入值，返回先前值
V putIfAbsent(K key, V value);

// 删除键值对，如果键值对存在，返回true
boolean remove(Object key);

// 如果键值对不存在，利用mappingFuction(key) -> value插入新值，返回原值
V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction);
// 如果键值对存在，利用remappingFunction(key, oldValue) -> value覆盖原值，返回新值
V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction);

// 获取值，如果值不存在，返回null，如果是基本类型，无法转换，会遇到NullPointerException
V get(Object key);
// 获取值，如果值不存在，返回默认值
V getOrDefault(Object key, V defaultValue);

// 键判断，存在返回true
boolean containsKey(Object key);
// 值判断，存在返回true，是遍历键值对查找
boolean containsValue(Object value);

// 清空
void clear();
// 为空判断，为空返回true
boolean isEmpty();

// 遍历键值，由于Map本身不支持foreach循环遍历，可以使用以下方法转集合遍历
// 获取包含所有key的集合，修改会影响map
Set<K> keySet();
// 获取包含所有value的集合，修改会影响map
Set<V> valueSet();
// 获取包含所有value的collection列表，修改会影响Map
Collection<V> values();
// 获取所有键值对，Entry可以使用getKey()、setKey()、getValue()、setValue()方法
Set<Map.Entry<K, V>> entrySet();

树状结构

堆(优先队列)PriorityQueue

堆是完全二叉树，一般通过一维数组利用层次遍历存储实现，堆二叉树满足每个子节点都小于或大于父节点，即小根堆和大根堆
堆一般用于解决Top-k问题、求中位数或用于快速合并多个长序列、文件
- 关于中位数(其他分位数求法类似)求法细节：设置一个大根堆和一个小根堆，对于一个长度为n的数组而言，中位数应该在n/2+1位置或是n/2和n/2+1的平均值，维护两个堆，保证两个堆的大小为n/2。当数组存入两个堆之后，两个堆的堆顶就是n/2和n/2+1的值，如果需要对动态增加值的数组频繁求中位数，堆能很好地减少时间
常用api

// 创建小根堆，默认
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
// 创建大根堆，注意有负数时，使用 (a, b) -> b - a 可能导致溢出
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a,b)->Integer.compare(b,a));
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Comparator.reverseOrder());

// 添加值，添加成功返回true，两个方法继承自集合和队列
boolean add(E e);
boolean offer(E e);

// 删除根元素并返回，如果堆为空，返回null
E poll();

// 查看根元素，如果堆为空返回null
E peek();

// 移除一个指定元素，使用o.equals(e)进行遍历判断，删除成功返回true
boolean remove(Object o);
// 是否包含某个元素，使用o.equals(e)进行遍历判断，存在返回true
boolean contains(Object o);

// 当前堆大小
int size();
// 是否为空，为空返回true
boolean isEmpty();

红黑树TreeSet

视频讲解
红黑树是一种平衡二叉搜索树，可以保证其内元素有序，同时和其他集合一样，每个元素是唯一的，适用于需要随时添加元素且保证有序的场景
红黑树的特点
- 平衡树：任意节点左右子树的高度相差不大于1
- 二叉搜索树：对于每个节点，如果子节点不为空节点，大小顺序为左 > 根 > 右
- 根节点是黑色的，叶子节点不存放数据也都是黑色的(也可以忽略掉)
- 任何两个相邻的节点不能同时为红色
- 任意节点到可到达的叶子节点包含相同数量的黑色节点(最长路径不超过最短路径的两倍)，黑色节点的数量最多不超过 $log(n + 1)$
- 包含 $n$ $n$ 个元素的红黑树的高度趋于 $logn$ $l o g n$ ，最大不超过 $2(log(n+1))$ $2 (l o g (n + 1))$
  - 删除所有红色节点可以构成4叉树，由于一条路径上的黑色节点数量即4叉树的最大高度为 $log(n+1)$ ，加上红色节点最多为 $2(log(n+1))$

插入：插入采用二叉搜索树的旋转插入方法，旋转是为了保证二叉搜索树的特性。为了减少违反的规则数量，规定插入的节点为红色，最多只违反根节点为黑色和相邻节点不同时为红色的规则

插入情况	操作
未破坏任何性质	不调整
插入结点是根结点	插入节点直接变黑
插入节点的父节点为红且叔叔是红色	叔父爷节点变色，爷爷变插入节点，重复判断
插入节点的父节点为红且叔叔是黑色	`(LL,RR,LR,RL)`旋转，并对爷爷节点和旋转中心点进行变色

叔叔节点有可能是空的叶子节点，为黑色

旋转操作：对于插入节点与爷爷节点的位置关系，有四种旋转方法
- LL旋转：插入节点是爷爷节点的左节点的左节点，以爷爷节点为旋转点，父节点为旋转中心点进行右旋，下面两张图为插入开始和插入结果(变色后)
- RR旋转：插入节点是爷爷节点的右节点的右节点，以爷爷节点为旋转点，父节点为旋转中心点进行左旋，下面两张图为插入开始和插入结果(变色后)
- LR旋转：插入节点是爷爷节点的左节点的右节点，先以插入节点为旋转中心点左旋父节点(爷爷节点的左孩子)，再以此时的插入节点为旋转中心点右旋爷爷节点，下面三张图为插入开始、插入中间状态和插入结果(变色后)
- RL旋转：插入节点是爷爷节点的右节点的左节点，先以插入节点为旋转中心右旋父节点(爷爷节点的右孩子)，再以此时的插入节点为旋转中心左旋爷爷节点，下面三张图为插入开始、插入中间状态和插入结果(变色后)
图片过程
LL旋转
RR旋转
LR旋转
RL旋转
:::

删除：删除同样采用二叉搜索树的删除方法，然后调整颜色
双黑节点是指因为违反性质出现的代表出现两次黑色节点的空叶子节点
- 只有左孩子或右孩子：此时孩子一定为红色且无子节点，才能满足到每个叶子节点的黑色节点数量相同，自身一定为黑色，才能满足红色节点不相邻，删除需要用孩子节点的值代替当前值，再删除孩子节点
- 没有孩子节点且自身为红节点：直接删除，不会违反颜色性质
- 没有孩子节点，兄弟是黑色节点，且兄弟至少有一个红孩子：第一个红孩子是在操作中优先级更高的孩子，指的是ll型和rr型，下面三张图为删除之后，变色之后和调整完成
  - 修改兄弟的第一个红孩子的颜色为兄弟节点的颜色，修改兄弟节点的颜色为父节点的颜色，修改父节点的颜色为黑，即有根据下图中对红孩子r和需要删除节点的兄弟节点s、需要删除的节点的父节点p的标注
    对于ll型或rr型，r变s，s变p，p变黑；对于lr型或rl型，r变p，p变黑
  - 根据兄弟的第一个红孩子和爷爷节点的相对位置进行旋转(方法和插入一致)
图片过程
LL旋转
RR旋转
LR旋转
RL旋转
:::
- 没有孩子节点，兄弟是黑色节点且兄弟的孩子都是黑色：此时相对于经过兄弟节点的路径比到删除节点(删除后已成为叶子节点)的路径的黑色节点多 $1$ 个，因此需要将兄弟节点变为红色，平衡父节点的左右子树，之后再进行父节点和他的兄弟节点的平衡，即需要兄弟变红，双黑节点向上移动(移动到父节点)，上移会遇到一下几种情况
  - 如果父节点是根节点：相对于整棵树都额外经过了一个黑节点，无需操作
  - 如果父节点是红节点：直接将父节点变为黑色即可消除双黑
  - 如果父节点是黑节点：相对于删除父节点，根据父节点的兄弟节点情况进行调整
- 没有孩子节点，兄弟节点是红色：下面四张图为变色前，变色后，旋转后，删除完成后
  - 兄弟节点和父节点变色
  - 之后让父节点以兄弟节点为旋转中心点，向需要删除节点旋转，保持双黑节点不变
  - 根据旋转后的情况，消除双黑节点(相对于删除节点，根据情况进行调整)
  图片过程
常用api

// 创建，默认升序
// 对于数字根据数值排序
// 对于字符串等实现了Comparable接口的类而言，使用compareTo方法比较
// 对于自建类需要实现Comparable接口或传入比较函数，如果两个方法都有，传入比较函数的优先级更高
TreeSet<String> treeSet = new TreeSet<>();
// 传入的比较函数应该检查在取更大或更小元素时，是否符合预期，不然应该考虑TreeMap，存储对应的数据结构
TreeSet<int[]> intSet = new TreeSet<>((a, b) -> b.length - a.length);

// 添加值，set改变返回true
boolean add(E e);
boolean addAll(Collection<? extends E> c);

// 移除值，set改变返回true
// 判断是否相同是通过equals函数实现的
boolean remove(Object o);
boolean removeAll(Collection<?> c);
// 传入判断函数，对每个元素进行判断删除返回true的元素
boolean removeIf(Predicate<? super E> filter);

// 遍历，遍历的元素将按顺序获取，支持foreach
// 也可以使用迭代器，iterate.hasNext()判断是否还有元素，iterate.next()获取下一个元素
Iterator<String> iterate = numbers.iterator();

// 获取值，如果找不到返回null
// 迭代器的第一个元素，排序中的最小值
E first();
// 迭代器的最后一个元素，排序中的最大值
E last();
// 获取比此元素大的最小元素
E higher(E e);
// 获取比此元素小的最大元素
E lower(E e);
// 获取大于等于此元素的最小元素
E floor(E e);
// 获取小于等于此元素的最大元素
E ceiling(E e);

// 存储的数目
int size();

// 子集合，获取从某个元素开始到最后一个元素的有序集合
// 可以传入第二个boolean变量控制最终集合是否包含传入元素，默认为true即包含此元素
SortedSet<E> tailSet(E fromElement);

// 对应treeMap，支持Map的基本函数get() put()
TreeMap<Integer, Integer> map = new TreeMap<>();

// 获取键值对或键，无结果返回null
//返回小于key的第一个元素：
Map.Entry<K,V> lowerEntry(K key);
//返回小于key的第一个键：
K lowerKey(K key);
//返回小于等于key的第一个元素：
Map.Entry<K,V> floorEntry(K key);
//返回小于等于key的第一个键：
K floorKey(K key);
//返回大于或者等于key的第一个元素：
Map.Entry<K,V> ceilingEntry(K key);
//返回大于或者等于key的第一个键：
K ceilingKey(K key);
//返回大于key的第一个元素：
Map.Entry<K,V> higherEntry(K key);
//返回大于key的第一个键：
K higherKey(K key);

//返回集合中第一个元素：
Map.Entry<K,V> firstEntry();
//返回集合中最后一个元素：
Map.Entry<K,V> lastEntry();

并查集

并查集是利用树状结构判断某些元素是否在同一集合，并快速处理合并的结构，对特点类型的问题很有帮助，比如：图的联通变化和快速查询，森林中有几颗树，判断两个节点是否属于同一个联通分量，其他需要频繁合并和查询是否在同一集合的情况
原理：
- 初始时创建足够数量的点，表示集合项，一般初始时将节点视为一个集合
- 每个集合都是一棵树，初始时每个集合可能只有一个节点
- 对每一个集合选出一个代表元(一般选择树根节点，所有集合内元素只需向上遍历，找到根节点)，每次查询是否在同一个集合只需要查看两个元素所在集合的代表元是否相同
- 合并实际上是将一个集合树作为集合树的子树，此时需要修改代表元
下方讨论时默认初始状态为所有节点都在不同集合中，可根据需要初始化
实现：
- 可以发现对于每个节点，想要完成并和查操作，不需要真的完全模拟树操作，只需要找到代表元和修改代表元。如果索引可以为整型，使用数组存储所有元素的父节点；如果无法找到整型作为索引，可以使用哈希表存储
- 初始化时，对每个元素设置当前的父节点，可以默认规定根节点的父节点是他本身
- 需要知道某个节点在哪个集合，通过父节点信息向上递归寻找，就能找到根节点(递归终点为父节点是节点本身)
- 合并两个集合将一个集合的根节点的父节点设置为另一个集合的根节点
优化：
- 对合并优化，由于合并时没有考虑树的高度，不能保证树的平衡，查询根节点的时间会增加，因此可以额外设计一个数组，存储每个节点的高度，初始时，默认为1，每次合并之后，根节点高度加1，每次合并时选择高度大的作为根进行合并
- 对获取根节点优化，因为每次寻找根节点都是从当前节点向上查找，可以在每次查找完成后，将结果存入父节点索引数组，使树结构扁平

c++

const int  N=1005     //指定并查集所能包含元素的个数（由题意决定）
int pre[N];          //存储每个结点的前驱结点 
int rank[N];         //树的高度 
void init(int n)         //初始化函数，对录入的 n个结点进行初始化 
{
    for(int i = 0; i < n; i++){
        pre[i] = i;        //每个结点的上级都是自己 
        rank[i] = 1;       //每个结点构成的树的高度为 1 
    } 
}
int find(int x)             //查找结点 x的根结点 
{
    if(pre[x] == x) return x;    //递归出口：x的上级为 x本身，则 x为根结点 
    return find(pre[x]);    //递归查找 
} 
 
int find(int x)         //改进查找算法：完成路径压缩，将 x的上级直接变为根结点，那么树的高度就会大大降低 
{
    if(pre[x] == x) return x;  //递归出口：x的上级为 x本身，即 x为根结点 
    return pre[x] = find(pre[x]);   //此代码相当于先找到根结点 rootx，然后 pre[x]=rootx 
} 

bool isSame(int x, int y)        //判断两个结点是否连通 
{
    return find(x) == find(y);   //判断两个结点的根结点（即代表元）是否相同 
}

bool join(int x,int y)
{
    x = find(x);      //寻找 x的代表元
    y = find(y);      //寻找 y的代表元
    if(x == y) return false;   //如果 x和 y的代表元一致，说明他们共属同一集合，则不需要合并，返回 false，表示合并失败；否则，执行下面的逻辑
    if(rank[x] > rank[y]) pre[y]=x;  //如果 x的高度大于 y，则令 y的上级为 x
    else        //否则
    {
        if(rank[x]==rank[y]) rank[y]++; //如果 x的高度和 y的高度相同，则令 y的高度加1
        pre[x]=y;      //让 x的上级为 y
    }
    return true;      //返回 true，表示合并成功
}

java

class unionSet {
    int[] pre;
    int[] rank;
    int n;

    public unionSet(int n) {
        this.n = n;
        pre = new int[n];
        rank = new int[n];
        for(int i = 0; i < n; ++i) {
            pre[i] = i;
            rank[i] = 1;
        }
    }

    void join(int x, int y) {
        x = find(x);
        y = find(y);

        if(rank[x] < rank[y]) {
            int tmp = x;
            x = y;
            y = tmp;
        }

        pre[y] = x;
        ++rank[x];
    }

    int find(int x) {
        if(x == pre[x]) {
            return x;
        }

        return pre[x] = find(pre[x]);
    }
}

方法

枚举

枚举:通过考虑所有可能情况种类,将所有情况罗列,得出结果
- 通常用于统计某件事发生次数
- 对于枚举而言实现优化可能十分困难
使用:说起来简单,将题目中满足题目条件的情况事先考虑出来,找规律,并想好后续处理,返回。不同题目需要统计的内容也不尽相同
例题: 我们可以分析出,对每一位上而言,这个数字和后面的数字出现1有关联(设该数为x)
1️⃣ 如果在个位上出现大于等于1的数,那么计数加1,否则不做处理n = x mod 10
$count(n) = \left\{ \begin{array}{rcl} 0 & & {n < 0}\\ 1 & & {n >= 1} \end{array} \right.$
2️⃣ 如果数字的个位与十位一起取出,当这个数小于10,则在十位上不可能出现1,如果该数大于20,则十位出现1的次数为10其余数字出现次数为个位数字加1n = x mod 100
$count(n) = \left\{ \begin{array}{rcl} 0 && {n < 10}\\ 10 && {n > 20}\\n\%10 + 1 &&{n\subseteq[10,20]} \end{array} \right.$
3️⃣ 如果数字的百位及以后一起取出,当这个数小于100,则在十位上不可能出现1,如果该数大于200,则十位出现1的次数为100其余数字出现次数为十位个位数字加1n = x mod 1000
$count(n) = \left\{ \begin{array}{rcl} 0 && {n < 100}\\ 100 && {n > 200}\\n\%100 + 1 &&{n\subseteq[100,200]} \end{array} \right.$
4️⃣ 可以继续得到所有的位上面可能出现的1的个数,以十位为例:m = x\100,n = x mod 100,因此我们可以知道有m组大于20的数,和剩下的数字n,因此结果为10*m + count(n)

class Solution {
    public int countDigitOne(int n) {
        long mulk = 1;
        int ans = 0;
        for (int k = 0; n >= mulk; ++k) {
            ans += (n / (mulk * 10)) * mulk + Math.min(Math.max(n % (mulk * 10) - mulk + 1, 0), mulk);
            mulk *= 10;
        }
        return ans;
    }
}

动态规划

动态规划是一种递归的转化方式,能将递归的方法变成循环多次的方法,简化了回调函数结果的步骤,节约了时间。是通过提前定义存放递归结果的空间,利用边界状态,反推出其他状态,一步步推导到所求结果的过程
动态规划首先是如同递归一样,分析出边界条件,也就是已知的情况(一般情况下,边界条件都是当前要处理的大问题的小区间问题),然后得出后续的情况相比于前面的情况,存在的数学关系得出推导方向(类似递归体),再定义相应的空间存放结果集,通过初始化和后续填充结果集,完成从简入繁的过程,最后返回相应的结果
- 通常这个过程被称为寻找状态(每次递归结果是什么),寻找转移方程(数学关系),状态已知部分的初始化(初始边界条件),题目需要的结果(通过数学关系需要得到什么)
- 如果没有头绪,使用记忆化搜索(存储计算结果)优化递归也可以,记忆化搜索就类似动态规划,将递归参数作为区分的手段,将每次递归的结果存放在一个空间内,需要用到时,直接取出,避免重复计算
常见的转移有两种，一种是和物品序列有关的，每次向序列中添加一些项可以利用之前序列的结果简化计算；一种是和计算的数值有关的，如果希望得到更高的数值，可以考虑用低数值结果简化计算

例题: 516.最长回文子序列 516.最长回文子序列解答

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] f = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            f[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    f[i][j] = f[i + 1][j - 1] + 2;
                } else {
                    f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                }
            }
        }
        return f[0][n - 1];
    }
}

记忆化搜索

记忆化搜索可以说是对枚举的改进，在一些题目中，枚举所有的可能性的时间复杂度可能超过 $O(n^3)$ ，且在枚举的过程中，可以发现某些数据被多次计算，一般这种数据是可以被复用的，即不会因为后续的计算而改变结果，因此可以在第一次计算完成后存储起来，通过特定的方式检索，来减少计算消耗，降低时间消耗
一般在进行记忆化搜索时，可以在函数外设置全局数组存储在特定状态下的计算结果，在存储和取值时使用条件作为索引
在写计算结果的函数时，一般通过递归完成，开始时先查找该状态下的结果是否计算过，如果计算过直接返回，如果没有计算过利用之前状态进行计算，然后填入全局数组中

记忆化搜索和动态规划

记忆化搜索一般是通过递归完成的，是从结果开始，逐渐向前计算，直到找到有结果的初始状态，然后再将递归路径上的结果填入，避免重复计算
动态规划是从初始状态开始，逐步推进，计算到最终结果的所在状态
二者都是利用状态之间的关系简化计算，每个状态只会计算一次，而且在状态计算之前，需要依赖的状态都需要被正确计算

状态数组的优化

有的时候，在经历了记忆化搜索或动态规划之后，计算复杂度还是过高，此时就要考虑其他方法对状态数组进行优化
预计算剪枝：对于某些输入情况，可能能够快速地计算得到最终结果，通过预计算剪枝，将满足某些条件的结果预先通过其他方法计算，快速计算某些情况的结果，对于经常出现对应情况时较有用
一比一翻译成堆：如果一个问题目前是通过递归计算，就可以将过程转换成非递归，减少调用栈空间
压缩数组大小：能够方便地降低空间复杂度，因为使用状态转移时，状态不总是由一个参数决定，有时存在二维数组关系并进行多轮计算，可以发现
- 将外层的遍历循环看作轮次，可以发现这种情况下需要根据之前一轮甚至多轮的计算结果计算本轮的一维数组
- 状态转移要求之前的状态先被计算出来，在之后的计算过程中不需要再使用两次计算前的状态，可以空出这些空间
- 在大多数转移关系中只会存在对内层循环的参数的单侧的取值，这时可以将数组压缩一个维度，只需要选择一个方向遍历(从小到大或从大到小)，在计算这一层的结果时确保当前需要用到的上一层的计算结果未被覆盖，完成本轮计算
- 如果最终未降维，需要配合取余操作mod，选择对应的外层索引
位优化：能够降低空间复杂度，配合位运算也能降低时间复杂度，将状态存储在数位中，即使用一个数字存储所有状态，一般只用在状态是bool类型的时候，每一进制位代表一个状态
状态合并：利用编译原理中的状态合并思想，将相同转移的状态合并，通常需要画状态转移图才能知道哪些状态是相同的

矩阵快速幂：将状态转移通过矩阵M表示，第i轮递推结果为f[i]，f[i]=Mf[i-1]最终结果 $f[n]=M^nf[0]$ ，其中的M可以通过幂运算快速完成，具体过程如下

// a^n * f0
private long[][] powMul(long[][] a, int n, long[][] f0) {
    long[][] res = f0;
    while (n > 0) {
        if ((n & 1) > 0) {
            res = mul(a, res);
        }
        a = mul(a, a);
        n >>= 1;
    }
    return res;
}

// 返回矩阵 a 和矩阵 b 相乘的结果
private long[][] mul(long[][] a, long[][] b) {
    long[][] c = new long[a.length][b[0].length];
    for (int i = 0; i < a.length; i++) {
        for (int k = 0; k < a[i].length; k++) {
            if (a[i][k] == 0) {
                continue;
            }
            for (int j = 0; j < b[k].length; j++) {
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
            }
        }
    }
    return c;
}

滑动窗口

滑动窗口是求解关于连续子序列问题的便捷方法，一般可以分为子序列长度不变和可变两种情况，并且是求满足某些条件的子序列的某个信息
滑动窗口的主要目的是维护一个由两个下标确定的子序列，通过长度和位置的变化满足条件，收集对应信息
- 位置的变化用于遍历整个序列的所有子序列，当以能够作为起始位置的点都遍历完毕，结束
- 同时长度的变化也和条件绑定，即长度变化只是为了达到满足条件的状态，实现变相剪枝，也说明使用滑动窗口要求窗口大小变化应该都对应逼近条件
- 也就是说我们期望滑动窗口中的值正负号需要相同(最终条件值能够单调递增或递减)，才能确保窗口左指针始终向右移动，不会出现需要向右移动才能逼近条件的情况，否则滑动窗口的复杂度会退化为 $O(n^2)$
- 对于正负都有的情况需要考虑使用前缀和+枚举(枚举右维护左)解决，但最终条件不一定是求连续序列的最大和；当然也可以使用动态规划剪枝完成

对于序列长度不可变的情况，假设限定了子序列的长度为k

对当前元素做出处理
在长度超过k时移除最左元素造成的影响
需要在长度达到k时

判断是否满足条件，收集信息

// 例：求长度为k的子序列有多少求和超过s
// 滑动窗口的参数为int[] nums, int k, int s
int n = nums.length;
int sum = 0;
int ans = 0;

for(int i = 0; i < n; ++i) {
    // 如果当前将长度大于k，移出最左元素
    if(i > k - 1) {
        sum -= nums[i - k];
    }
    // 对当前元素处理，求和
    sum += nums[i];

    // 收集信息
    if(sum > s) {
        ++ans;
    }
}

对于序列长度可变的情况，问题之间的差异很大，但一般是解决子序列中至多和至少有 $k$ 个满足某个条件的元素的问题

变长滑动窗口要求连续子序列问题有单调性，也就是子序列越长，越满足要求，此时滑动窗口固定的序列就是恰好临界的子序列，而在滑动窗口左边是满足条件元素个数 $n>=k$ 的子序列，在滑动窗口中是 $n>k$ 的子序列
这种情况下，右指针一般自由移动，在每次右指针移动时，尝试移动左指针，统计结果

对于至多和至少问题的流程大概如下：

long ans = 0;
int cntMx = 0, left = 0;
// 移动右指针
for (int x : nums) {
    // 处理右指针移动的影响
    if (x == target) {
        cntMx++;
    }
    // 尝试移动左指针
    while (cntMx == k) {
        // 处理左指针移动的影响
        if (nums[left++] == mx) {
            cntMx--;
        }
    }

    // 统计结果，此部分也可以写在处理左指针移动的影响前
    // 这样的话需要修改移动左指针条件等判断条件
    
    // 如果是至少有k个满足条件元素的问题
    // 右端点为right，左端点从0到left-1都满足
    ans += left;
    // 如果是至多有k个满足条件元素的问题
    // ans += right - left + 1;
}
return ans;

需要注意的是，由于滑动窗口中是通过双指针限定子序列范围的，并且双指针都只能向右移动，如果需要指针回退，就没办法使用滑动窗口，可能需要记录更多之前的状态，使用比如动态规划或其他方法

恰好型滑动窗口

对于某些寻找连续子序列中恰好某个元素出现次数为 $k$ 的问题，可以通过两次滑动窗口完成，也就是将恰好问题转化为至少问题，创建一个变长滑动窗口函数 $f(nums,k)$ 来寻找至少有 $k$ 次出现的子序列个数，就可以将恰好 $k$ 个转化为 $f(nums,k)-f(nums,k+1)$

二分法查找

二分法是 $O(\log(n))$ $O (lo g (n))$ 的时间复杂度算法,用于可识别结果会出现在哪一边，减少非必要查找
- 通常用于查找有序的可能结果列表，寻找在条件达成边界上的临界值，比如：寻找有序列表中的数字最小的满足条件的值、在有序且明显有相关的解空间中寻找边界值
通过二分法可以对排好序的元素进行快速查找

private static int binaryFind(int[] list, int i) {
        int l = 0,r = list.length - 1;
        while(l <= r){
            int n = l + (r - l)/2;//同int n = l + (r -l >> 1);
            if(list[n] == i){
                return n;
                break;
            }else if (list[n] > i){
                r = n - 1;
            }else if (list[n] < i){
                l = n + 1;
            }
        }
        return - 1;
    }

初级二分:查找某一值。
- 与上方例子一样,上方例子就是一种二分的方法,一般模板如下:

int l = ···,r = ···;//初始搜索区间
while(l ··· r){//搜索区间不为空,继续循环
    int n = l + (r -l)/2;//中间索引
    if(list[n] == i){//如果list[n]就是要找的值,返回索引结束
        return n;
    }else if (list[n] > i){//如果中间索引比要找的值大,收紧右侧区间
        r = ···;
    }else if (list[n] < i){//如果中间索引比要找的值小,收紧左侧区间
        l = ···;
    }
}
return - 1;

从中可以看出,二分法的写法和左右边界有关,回到上方示例函数binaryFind,使用的是闭区间 $[l,r]$ 进行搜索,因此在使用的时候: 1️⃣ while循环要判断搜索区间是否为空,在闭区间搜索中，区间为空，即l > r结束 2️⃣ 在list[n]比结果小时, $[l,n]$ 就不用搜索了,肯定比结果小,因此接下来搜索区间就变成了 $[n + 1,r]$ ,同理,在list[n]比结果大时, $[n,r]$ 就不用搜索了 3️⃣ 返回的是当前的(匹配的)结果的下标

当搜索区间为 $[l,r)$ 即 $[0,list.length - 1]$ 时,同样: 1️⃣ while循环条件为l < r,因为当l = r时,搜索区间已经为空了 2️⃣ 在list[n]比结果小时,, $[l,n]$ 就不用搜索了,肯定比结果小,因此接下来搜索区间变成了 $[n + 1,r]$ ,同理,在list[n]比结果大时, $[n,r]$ 就不用搜索了,r = n - 1 3️⃣ 返回的是当前的(匹配的)结果的下标

高级二分:查找序列中小于(大于)某一值的左(右)边界
- 对于日常使用而言，不能只局限于搜索到某个元素，可能还要搜索元素的左（右）边界，同样也是上方的模板,基本结构不变

当要搜索左边界时：找出大于(大于等于)某一值的最小值 1️⃣ 首先，可设搜索边界为l = 0,r = list.length,也可以使用l = 0,r = list[n].length - 1的闭区间搜索(下面使用这种方法) 2️⃣ 在while循环中,同样判断搜索区间空间不为空,继续循环要l <= r 3️⃣ 当中间值list[n] < i时,在 $[l,n]$ 区间内不存在比i大的值,因此,搜索区间变成 $[n + 1,r]$ 4️⃣ 当该值list[n] == i时,在 $[n + 1,r]$ 内,只有可能出现大于等于list[n]的值,如果是寻找比i大的最小值左边界,搜索区间就变成了 $[n + 1,r]$ ,如果是寻找大于等于i的最小值左边界,搜索区间就变成了 $[l,n]$ 5️⃣ 当该值list[n] > i时,在 $[n + 1,r]$ 区间内不可能出现左边界,搜索区间就变成了 $[l,n]$ 6️⃣ 返回值是一方边界,这个值对应第一个满足条件的值 7️⃣ 注意:如果使用闭区间 $[l,r]$ 搜索,会更加麻烦,由于当区间只有1,却是执行改变右边界 $r$ ,使死循环发生,这时需要使用if(l == r) { break; }退出

public static int binarySearch(){
    //搜索大于i的最小值左边界
    //若为搜索大于等于i的最小值左边界,第二个条件应为list[list.length - 1] < i
    if (list.length == 0||list[list.length - 1] <= i) return -1;
    int l = 0,r = list.length - 1;
    while(l <= r){
        int n = l + (r -l)/2;//同int n = l + (r -l >> 1);
        if(list[n] == i){
            l = n + 1;
            //r = n;    if(l == r) { break; }  //当搜索大于等于i的最小值左边界(一般不这么做)
        }else if (list[n] > i){
            r = n;
            if(l == r) { break; }
        }else if (list[n] < i){
            l = n + 1;
        }
    }
    //寻找左边界,返回左边界
    return l;
}
//---------------------------分割线-------------------------------
public static int binarySearch2(){
    //使用左闭右开区间搜索
    if (list.length == 0||list[list.length - 1] <= i) return -1;
    int l = 0,r = list.size();
    //搜索大于num的左边界
    while(l < r){
        int median = (l + r) >> 1;
        if(list.get(median) == num){
            l = median + 1;
            //r = n;    //当搜索大于等于i的最小值左边界
        }else if(list.get(median) < num){
            l = median + 1;
        }else{
            r = median;
        }
    }
    //寻找左边界,返回左边界
    return l;
}

当要搜索右边界时,方法与左边界类似

不要拘泥于这些模板这只是一种解决办法
每种语言都有对应的库和函数来为我们实现这里二分查找大于等于某个数的第一个位置的功能，比如C++的lower_bound，Java中的Arrays.binarySearch，C#中的Array.BinarySearch，Python中的 bisect.bisect_left

排序

排序算法	时间复杂度(最坏/平均/最好)	空间复杂度	稳定性	特点与适用场景
冒泡排序	$O(n^2)$ / $O(n^2)$ / $O(n)$	$O(1)$	稳定	简单实现，适合小规模数据或数据接近有序的场景
选择排序	$O(n^2)$	$O(1)$	不稳定	简单但效率低，不适合大数据
插入排序	$O(n^2)$ / $O(n^2)$ / $O(n)$	$O(1)$	稳定	适合少量数据或几乎有序的数组
希尔排序	难以分析，肯定小于 $O(n^2)$	$O(1)$	不稳定	适用于数据量较大的场景，是对插入排序的改进
归并排序	$O(n \log n)$	$O(n)$	稳定	适合大数据、需要稳定性的场景
快速排序	$O(n^2)$ / $O(n \log n)$ / $O(n \log n)$	$O(\log n)$	不稳定	高效通用的排序算法，适合大规模数据
堆排序	$O(n \log n)$	$O(1)$	不稳定	用于堆结构的场景，内存使用较少
计数排序	$O(n + k)$	$O(n + k)$	稳定	适用于数据范围较小且整数数据的场景
桶排序	$O(n + k)$	$O(n + k)$	稳定	适合数据均匀分布的场景
基数排序	$O(n * k)$	$O(n + k)$	稳定	适合多位数值或字符串的排序

稳定性实际上依赖实现，表中展示的是基本的算法排序思想下的稳定性

快速排序

作为冒泡排序的改进,不稳定(相等的值,顺序可能发生变化),平均时间复杂度为 $O(nlog_2 n)$ ,空间复杂度 $O(log_2 n)$
基本思想(分治法):在数组中选取一个基准数据(一般选择最左侧的值),使用双指针,使用时,先移动右侧指针,寻找比基准数据小的数,再移动左侧指针,寻找比基准大的数,将二者互换,当两指针相遇时,结束寻找,最后将基准数据放至相遇处,这样就把大于基准数据的数放在了基准右侧,小于基准的数放在了左侧,再对左右同时再进行快速排序,就可以递归完成排序

public Test{
    public static void fastSort(int[] arr,int l,int r){
        if(l >= r){
            return;
        }
        int standard = arr[l];
        int i = l,j = r;
        while(i != j){
            //必须先右指针移动，再左指针移动，这样在最终更改基准位置时，i一定比基准小
            while(arr[j] >= standard && i < j){
                j--;
            }
            while(arr[i] <= standard &&i < j){
                i++;
            }
            if(i < j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        arr[l] = arr[i];
        arr[i] = standard;
        fastSort(arr,l,i - 1);
        fastSort(arr,i + 1,r);
    }
}

希尔排序

希尔排序是对直接插入排序的优化，使用了分组插入的方法，让数组更接近有序，速度比直接插入排序快
- 基本思想是缩小增量，先选定一个整数 $gap$ ，把待排序文件中所有记录分成个组，所有距离为 $gap$ 的记录分在同一组内，并对每一组内的记录进行插入排序。然后，修改 $gap$ ，重复上述分组和排序的工作。当到达 $gap=1$ 时，所有记录在统一组内排好序
步骤
- 选择一个初始的 $gap$ ，将所有间隔为 $gap$ 的看作一组，实际上有 $gap$ 个组
- 对每个分组执行直接插入排序
- 修改 $gap$ ，修改方法有不同，一般是使用除法，比如 $gap = gap / 3 + 1$ (确保最后为1)
- 对新的 $gap$ 继续执行上述步骤，直到 $gap = 1$ 都执行完毕
$gap = 1$ 时实际上就是直接插入排序，只是因为之前的预排序，顺序基本是有序的，所以效率更高
效率远高于直接插入排序，可以接近快速排序和堆排序，时间复杂度因为 $gap$ $g a p$ 的修改方法不同，难以统计，具体的修改方法应该如何选取更好也难以证明，有数据显示，最终的复杂度应该在 $O(n^s)$ $O (n^{s})$ ，其中的 $s$ $s$ 介于1和2之间
- 原始希尔序列修改方法是 $gap = gap / 2$ ，最坏复杂度是 $O(n^2)$
- 其他序列修改方法的复杂度一般优于这个值，甚至有方法在实践中得到的数据接近 $O(n^{1.3})$

计数排序

概念:计数排序是一种基于计数的排序算法，它基于以下假设：数组中元素的范围是固定的，并且元素范围是 $S\in [0, k)$ ，其中 $k$ 为元素的最大值
计数排序分类数据，使用一个能存储所有待排序数据的计数空间，接下来遍历序列，将元素放入代表对应数值的计数空间中，最后将计数空间中的数据按顺序输出
- 计数空间可以使用长数组实现，每个下标对应一个数值S，当数据满足条件后存入对应下标空间
- 最后遍历每个下标，将序列变为有序
- 是使用空间换时间的快速排序方法，只要元素范围不大，速度快于其他的算法
- 如果待排序列长度为n，可以得出时间复杂度为 $O(n + k)$ ，空间复杂度为 $O(n + k)$

桶排序

桶排序利用映射的方法，将元素分类放入不同的优先级桶中，然后对每个桶进行排序，最后将所有桶中的数据合并为有序序列
- 初始化桶：确定桶的数量和具体的桶内数据范围，尽可能让每个桶中数据量均匀
- 分配元素：为元素分配桶，对数据做初步的划分和聚集
- 桶内排序：在桶中可以使用其他的排序算法进行排序，确保桶内有序
- 合并桶：根据桶的排序优先级，将桶的元素合并，得到有序序列
桶排序适合数据分布均匀且范围明确的场景，可以使用高效的内部排序算法，提升效率，但在数据量分布不均匀时，效率可能下降，假设待排序列长度为n，桶数量为k
- 如果内部使用计数排序这样的线性时间排序算法，最终时间复杂度为 $O(n + k)$
- 在空间上需要额外的桶空间，空间复杂度为 $O(n + k)$

基数排序

基数排序(Radix Sort)是一种非比较型整数排序算法，它通过逐位比较数字来实现排序，每轮处理一位数字，确保本位的数字是稳定的
- 基数排序可以是稳定的排序算法，稳定性依赖每轮排序算法的稳定性
- 对于 $n$ $n$ 个数，已知其中最大数字是 $d$ $d$ 位 $k$ $k$ 进制的情况，其中 $0, ..., k-1$ $0, ..., k - 1$ 是数字的每一位的可能值(基数)
  - 时间复杂度为 $O(d * O_i)$ ： $O_i$ 是内部的排序时间复杂度，一般使用线性排序时间的算法，比如计数排序或桶排序时间复杂度为 $O_i = O(n + k)$
  - 空间复杂度为 $O(n + k)$ ：需要额外的 $k$ 个空间存储每轮排序信息，并使用 $n$ 个空间存储每轮排序结果
- 有从最低位开始排序(LSD)和从最高位开始排序(MSD)两种方法
- 期望获取到全为正整数的序列，如果存在负数可以为所有数字同时加上最小数的绝对值，变为全正数处理

基数排序可以使用 $k$ 个基数桶完成，基数桶用于存储有相同本位

获取序列中元素最大值，得到进制 $k$ 和位数 $d$ 信息
初始化 $k$ 个桶，如果期望稳定需要使用队列实现

进行 $d$ 轮操作，每次对第 $d$ 位基数大小进行排序

遍历数组，根据当前位的基数将元素放入对应的基数桶中
遍历桶，将桶中的元素依次放入原数组中
重置桶

public static void radixSort2(int[] arr) {
    // 查找数组中最大的数字
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if(arr[i] > max) {
            max = arr[i];
        }
    }

    // 基数
    LinkedList<Integer>[] bucket = new LinkedList[10];
    for (int i = 0; i < bucket.length; i++) {
        bucket[i] = new LinkedList<>();
    }

    // 从低位到高位逐位处理
    for (int exp = 1; max / exp > 0; exp *= 10) {
        // 逐个将元素放入基数桶中
        for (int i : arr) {
            bucket[i / exp % 10].add(i);
        }

        int index = 0;
        // 收集排序结果
        for (int i = 0; i < bucket.length; i++) {
            while(!bucket[i].isEmpty()) {
                arr[index++] = bucket[i].remove();
            }
        }
    }
}

如果数字很多并期望更大效率时，可以考虑使用针对基数的计数排序实现，不开辟动态队列

查找数组中数字最大值，得到进制 $k$ 和位数 $d$ 信息

进行 $d$ 轮操作，每次对第 $d$ 位基数大小进行排序

创建一个长度为 $k$ 的数组，用于记录每个基数出现的次数
统计每个基数出现的次数
对基数数组使用前缀和统计，现在每个基数数组中的元素表明了最后一个有此基数的数字应该处于的索引位置(从 $1$ 开始)
开辟临时数组，存储排序结果
从后向前遍历原数组，根据基数数组将数字放入临时数组对应位置，同时使对应基数数组的元素减一
拷贝临时数组到原数组

public static void radixSort2(int[] arr) {
    // 查找数组中最大的数字
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if(arr[i] > max) {
            max = arr[i];
        }
    }

    // 从低位到高位逐位处理
    for (int exp = 1; max / exp > 0; exp *= 10) {
        // System.out.println("exp=" + exp);
        // 基数数组，相当于桶
        int[] bucket = new int[10];

        // 逐个将数组元素放入桶中
        for (int i : arr) {
            bucket[i / exp % 10]++;
        }
        // System.out.println("bucket1: " + Arrays.toString(bucket));

        // 计算排序后的位置
        for (int i = 1; i < bucket.length; i++) {
            bucket[i] += bucket[i - 1];
        }
        // System.out.println("bucket2: " + Arrays.toString(bucket));

        // 临时数组，存储此轮排序后的结果
        int[] temp = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int j = arr[i] / exp % 10;
            temp[bucket[j] - 1] = arr[i];
            bucket[j] --;
        }
        // System.out.println("temp: " + Arrays.toString(temp));
        
        // 收集排序结果
        System.arraycopy(temp, 0, arr, 0, temp.length);
    }
}

字符串匹配

KMP算法：利用需要寻找匹配的字符串的字符关系，减少匹配次数
- 利用匹配失败时的前i个字符和字符串开头i个字符的相同关系，不用回到第一个位置重新匹配，而是在第i+1个字符尝试匹配(i+1相对于是匹配的前缀长度)
- 计算前利用相同前后缀的关系(最近的n个字符和开头的n个字符相同)构建next数组，作为匹配失败需要跳转匹配的下标数组，next[0]初始化为0
- 再优化，由于构建next数组时没有考虑跳转之后的字符是否和原字符相同，当需要匹配的字符串字符重复较多时会带来许多无异议的跳转，因此设置nextval数组，如果next数组跳转后字符和当前字符相同，则继续向前跳转，直到找到字符不相同的跳转地址或0
- 匹配时，如果未匹配此字符，就找前一个index的对应next结果，跳转对应下标匹配，直到匹配或已经和第一个字符比较过了结束
有代码第一个next数组元素初始化为-1，是希望避免每次和前一个索引的next比较，将结果都后移一个位置，第一个位置补-1，-1处理不方便计算回退时也要next+1，又有整体+1的方案
- 这里代码选择计算next数组时不右移也不+1的方案
代码详解，使用的是伪代码，数组第一个下标为1
- next数组通过代码构建的关键在于利用之前已经求得的前一个字符的next结果求下一个字符的结果。假设当前需要求的next数组下标为j，由于之前说过下标为0的初始化为0，因此这里的j>0，若next[j - 1] = i则可知，需要匹配的字符串[0, i - 1]和[j - i, j - 1]是相同的，此时需要做的就是查看j和i对应的字符是否相同，如果相同，就是找到了等长的前后缀
- 如果不同，需要继续通过next[i - 1]查找之前匹配的下标k，此时就有四部分的子串相同，这样第一部分和最后一部分又构成了相同前后缀，又继续查看j和k对应的字符是否相同
- 下图中j=17，i=8，k=4，展示了相同前后缀的重合关系
关键细节：
求next数组
- 由于next数组在初始化时将第一位初始化为0，因此后续遍历从1开始
- 求next的过程应该从索引小的开始向索引大的遍历并利用之前计算的结果
- 对于每个索引i而言，都是先查看接下来需要匹配的字符与当前字符是否相等，不相等再通过上一个匹配字符的next进行回退(使用next数组进行自身匹配回退)
- 回退将在找到匹配或直到第一个元素依旧不匹配终止
- 如果找到了匹配而终止，应该后移匹配指针j到下一个位置，未找到指针已经重置到0，即开头
- 重复匹配，直到每个索引都求得next
进行匹配
- 每次查看当前索引i对应字符和要匹配索引j对应字符是否相等，不相等根据next[j - 1]回退，在找到匹配或直到第一个元素依旧不匹配终止
- 如果找到匹配，应该后移匹配指针j到下一个位置
- 如果此时下一个需要匹配的索引已经超出目标字符串范围，已经匹配完毕，进行匹配时的处理
使用nextval数组优化
- nextval数组的构建与next不同在于回退不会在匹配时结束，而是在确认回退之后元素和当前元素不相同时结束
- 可以直接在next之后对当前索引i对应元素和索引next[i - 1]对应元素进行比较，如果相同，提前回退next[i - 1] = next[next[i - 1] - 1]，即对应匹配时第一次不成功，j=next[j - 1]，再匹配还是和同一字符(虽然不同位置)匹配再回退的情况
- 此时下标i应该从2开始，因为每次修改第i - 1个next结果，第1号不用修改，此时最后一个next结果也没有修改，不过最后一个结果也未被使用过
- 要注意，由于存在对next[i - 1] - 1的索引，需要判断next[i - 1]大于0，才进行赋值操作，如果该值不大于0，实际上就是回退到初始0索引
代码模板

c++

void get_Next(string s, int next[])  //这个函数对字符串s进行预处理得到next数组
{
    int j = 0;
    next[0] = 0; //初始化
    for(int i = 1; i<s.size(); i++){ //i指针指向的是后缀末尾，j指针指向的是前缀末尾
        while(j>0&&s[i]!=s[j]) j = next[j-1]; //前后缀不相同，去找j前一位的最长相等前后缀
        if(s[i]==s[j]) j++; //前后缀相同，j指针后移
        next[i] = j; //更新next数组
    }

    // 计算nextval
    for (int i = 2; i < s.size(); i++) {
        if (s[i] == s[next[i - 1]]) {
            next[i - 1] = next[next[i - 1] - 1];  // 跳过重复前缀
        }
    }
}

int strSTR(string s, string t) //这个函数是从s中找到t，如果存在返回t出现的位置，如果不存在返回-1
{
    if(t.size()==0) return 0;
    // 由于使用的是int数组，无法动态创建，需在函数外部创建足够大的数组
    get_Next(t, next);
    int j = 0;
    for(int i = 0; i < s.size(); i++){
        while(j>0&&s[i]!= t[j]) j = next[j-1]; 
        if(s[i]==t[j]) j++;
        if(j==t.size()) return i - t.size() + 1;
    }
    return -1;
}

int strSTR(string s, string t) //这个函数是从s中统计t出现的次数，如果不存在返回0
{
    int ans = 0;
    if(t.size()==0) return ans;
    // 由于使用的是int数组，无法动态创建，需在函数外部创建足够大的数组
    get_Next(t, next);
    int j = 0;
    for(int i = 0; i < s.size(); i++){
        while(j>0&&s[i]!= t[j]) j = next[j-1]; 
        if(s[i]==t[j]) j++;
        if(j==t.size()) {
            ++ans;
            j = next[j - 1];
        }
    }
    return ans;
}

java

public static int[] getNext(String target) {
    int n = target.length();
    int[] next = new int[n];
    int j = 0;
    for(int i = 1; i < n; ++i) {
        while(j > 0&&target.charAt(i) != target.charAt(j)) j = next[j - 1];
        if(target.charAt(j) == target.charAt(i)) {
            ++j;
        }

        next[i] = j;
    }

    // 计算nextval
    for (int i = 2; i < n; i++) {
        if (target.charAt(i) == target.charAt(next[i - 1]) && next[i - 1] > 0) {
            next[i - 1] = next[next[i - 1] - 1];  // 跳过重复前缀
        }
    }

    return next;
}

public static int kmp(String d, String t) {
    int m = d.length(), n = t.length();
    if(n == 0) return 0;
    int[] next = getNext(t);
    int j = 0;
    for(int i = 0; i < m; ++i) {
        while(j > 0 && d.charAt(i) != t.charAt(j)) {
            j = next[j - 1];
        }
        if(t.charAt(j) == d.charAt(i)) ++j;
        if(j == n) return i - n + 1;
    }

    return -1;
}

回溯

位运算

获得比一个正数大一点的第一个 $2^n$ 的值
- 使用位运算可以方便得出结果,通过将这个数二进制表示中从第一个1开始全部变成1,再对结果加一可以方便得出这个幂值
- 由于我们已知,这个数是正数,所以,可以使用int或其他能存下取值范围的数据类型存下它,我们假设使用的是四个字节的int类型,也就是有31个非符号位,也可以得到能存放的二次幂最大值为 $2^{31}$ ,因此,我们无法处理大于 $2^{31}$ 的数字,出现大于该数的数或一个非正数字返回一个正常情况不可能返回的数字,作为警示
- 接下来处理完特殊情况后,就进入位运算处理过程了,我们已经知道,这个正数必定有一个为1的最高非符号位,设这一位为第n位,对n位上使用>>1运算符,就会得到一个数至少在n位上为0,n - 1位上为1
- 在将上述两个数合并后,就得到一个在n和n - 1位上都确定为1的数,即两个位上为1,再使用>>2后取或就可以得到四个位上为1的数...
- 在经过与>>1 >>2 >>4 >>8 >>16的数字或运算后,就可以得到从n位开始都为1的数,加1,就得到了这个幂
```
public static int findBinary(int num){
    int max = 1 <<31; 
    if(num >= max||num <= 0){ return -1;}
    num |= num>>1;
    num |= num>>2;
    num |= num>>4;
    num |= num>>8;
    num |= num>>16;
    num += 1;
    return num;
}
```
x&(-x)可以用来获取某个二进制数的最后一个的1
x/=x&(-x)得到的最后一个1，可以用于消除尾部0
x&=x-1可以消去某个二进制数的最后一个的1
x∣(x+1)的本质是把二进制最右边的0置为1
~x会将每个数位都取反

二叉树的遍历方法主要有四种，大多数问题都通过遍历方式获取树的相关信息

先序、中序、后序遍历：这里的先中后指的是根节点的访问次序是在前面、中间还是后面，实际上三种遍历方式只是写法的区别

先序遍历：先访问根节点，再访问左子树，最后访问右子树
中序遍历：先访问左子树，再访问根节点，最后访问右子树

后序遍历：先访问左子树，再访问右子树，最后访问根节点

java递归

// 先序遍历
public static void bfs(TreeNode root) {
    if (root == null) return;
    System.out.println(root.val);
    bfs(root.left);
    bfs(root.right);
}

java栈模拟

public static void perOder(TreeNode root) {
    if(root == null) return;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.println(node.val);
        // 先将右节点入栈，右节点自然地更后被访问
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
}

层序遍历：层序遍历就是按树的层次遍历，即从上到下，从左到右依次遍历

public boolean isPrime(int n) {
    for(int i = 2; i * i <= n; ++i) {
        if(n % i == 0) {
            return false;
        }
    }

    return n >= 2; // 1 不是质数
}

概率素性检测，比如Miller-Rabin算法
- 算法基于引理：如果 $p$ 为大于2的素数，则方程 $x^2\equiv1\mod p$ 的解只有 $x\equiv1$ 和 $x\equiv-1$ ，也就是x的解在 $[0,p]$ 范围内只有 $1$ 和 $p-1$ ，通过不断尝试 $k$ 次，如果找到其他解则不是素数，如果未找到至少有 $1-2^k$ 的可能性是素数
- 对于素数 $p$ 而言， $p-1$ 为偶数，可以把 $p-1$ 写成 $2^k*m$ 的形式， $m$ 为不断除2后出现的奇数
- 然后随机选择一个在 $[2,n-1]$ 之间的 $a$ ，则根据费尔马定理有 $a^{n-1}=a^{m*2^k}=(a^m)^{2^k}\equiv1$ ，此过程中如果
  - $a^{m}\equiv1$ 且 $(a^{m})^{2^k}\equiv n-1$ 情况存在，则认为很可能是素数
  - $a^{m}\not\equiv1$ 或直到k已经很大 $(a^{m})^{2^k}\equiv n-1$ 还不存在，则认为是合数
  其中的 $\equiv$ 都表示对n取模后相等
- 判断是合数是确定的，实际上被判定为素数只说明通过了当前选取的 $a$ 的测试，一个素数能够通过所有的底数的测试，可以测试不同的 $a$ 提高正确率
```
// https://www.jianshu.com/p/ce5319a7639e
// 时间复杂度为O(k*(logn)^3)，k为测试使用的随机数a的数量
#define ll long long
#define i128 __int128
int primes[19]={2,3,5,7,11,13,17,19,23,29,31,37};
ll poww(ll a,ll b,ll c){
    ll ans=1;i128 base=a;
    while(b){
        if(b&1)ans=ans*base%c;
        base=base*base%c;
        b>>=1;
    }
    return ans;
}
bool miller_rabin(ll n){
    for(int i=0;i<=8;i++){
        if(primes[i]==n)return 1;
        else if(primes[i]>n)return 0;
        ll t=poww(primes[i],n-1,n),x=n-1;
        if(t!=1)return 0;
        while(t==1&&x%2==0){
            x/=2;
            t=poww(primes[i],x,n);
            if(t!=1&&t!=n-1)return 0;
        }
    }
    return 1;
}
```

互素判断

裴蜀定理
欧几里得算法(辗转相除法)常用于求解两个数是否是互素的

int gcd(int a, int b) {
    while(b != 0) {
        int t = a % b;
        a = b; b = t;
    }
    return a;
}

扩展欧几里得算法用于求解已知 $ax+by=gcd(a,b)$ ，求 $x$ , $y$ 的问题，扩展欧几里得应用
- $a,b,x,y$ 只需是实数整数，当 $a,b$ 一正一负时， $x,y$ 一定异号
- 在进行欧几里得算法时，修改x和y的值，重点在于利用最终状态回溯，根据裴蜀定理，这个式子是一定成立的，并且最终状态为 $b=0,x=1,y=0$ ，最终 $gcd(a,b)=a$
- 对于 $gcd(b,a\%b)=b*x+(a\%b)*y=b*x+(a-b*\lfloor a/b\rfloor)*y=a*y+b*(x-\lfloor a/b\rfloor*y)$ ，将 $x'=y,y'=x-\lfloor a/b\rfloor*y$ ，就得到上一次的状态 $ax'+by'=gcd(a,b)$
- 反过来往上回溯时，a和b也会相应发生变化，算法和欧几里得算法一样不需要保证输入 $a>b$ 成立， $x$ 和 $y$ 的输入值会被覆盖，返回值为 $gcd(a,b)$
- 扩展欧几里得算法的时间复杂度为 $O(\log max(a,b))$
- 常见应用：
  - 求解不定方程 $ax+by=c$ ，如果 $gcd(a,b)|c$ 即这两个数同余，则有整数解，将方程修改为 $ax+by=c*gcd(a,b)/gcd(a,b)$ ，然后两边同时除 $t=c/gcd(a,b)$ ，即可进行计算，结果要记得乘 $t$
  - 求同余方程 $ax\equiv b\mod n$ ，通过同余 $ax-b=kn$ 将问题转换为等式 $ax+(-k)n=b$ ，可以令 $y=-k$
  - 求乘法逆元 $ax\equiv 1\mod n$ 实际上就是同余方程的特殊情况
```
int e_gcd(int a,int b,int &x,int &y){
    if(!b){
        x=1;y=0;
        return a;
    }
    int gcd=e_gcd(b,a%b,y,x);
    y-=a/b*x;
    return gcd;
}
```
  手算
  扩展欧几里得的算法只看原理和代码不方便理解和手算结果，实际上计算扩展欧几里得只是在计算gcd(a, b)时添加了额外的商和余数，从最底轮开始每轮对一个x或y进行计算(计算在上一轮不变的系数)，比如计算79在模3220的情况下乘法逆元的结果
  - 第一轮时，式子转化为 $79x+3220y=1$
  - 第二轮时，根据欧几里得算法 $3220\%79=60$ ，式子变成 $79x+60y=1$
  - 重复这个过程， $19x+60y=1$
  - $19x+3y=1$
  - $x+3y=1$ ，已经有系数为1了，正常的gcd过程已经终止了，设此时系数为1的 $x=1$ ， $y=0$
  $\begin{split} 79x+3220y=1\\ 79x+60y=1\\ 19x+60y=1\\ 19x+3y=1\\ x+3y=1 \end{split}$
  - 向上推，最终轮计算的 $x=1$ 是不会被修改的， $19x+3y=1$ 得到 $y=-6$
  - $y=-6$ 不会被修改，向上推得 $19x+60y=1$ 对应的 $x=19$
  - $x=19$ 不会被修改，向上推得 $79x+60y=1$ 对应的 $y=-25$
  - $y=-25$ 不会被修改，向上推得 $79x+3220y=1$ 对应的 $x=1019$
  $\begin{array}{r c} 79x+3220y=1&(y=-25)\rightarrow(x=1019)\\ 79x+60y=1&(x=19)\rightarrow(y=-25)\\ 19x+60y=1&(y=-6)\rightarrow(x=19)\\ 19x+3y=1&(x=1)\rightarrow(y=-6)\\ x+3y=1&(x=1,y=0) \end{array}$
费尔马定理：也称为费马小定理，如果p是一个质数，而整数a不是p的倍数， $a^{p-1} \equiv 1 \mod p$ ，我们可以使用这个方法求乘法逆元，只需要在两边同时乘一个 $a$ 的逆元 $a^{-1}$ ，有 $a^{p-2} \equiv a^{-1} \mod p$ ，接下来就是求 $a^{p-2}$ ，可以使用快速幂算法，时间复杂度为 $O(log p)$
- 因为大多数情况下使用的模数都是质数，这个方法比扩展欧几里得算法写起来要简单，更常用
```
// 手写快速幂
private long pow(long x, int n) {
    long res = 1;
    for (; n > 0; n /= 2) {
        if (n % 2 > 0) {      // 如果当前二进制位是 1，就乘上当前的 x
            res = res * x % MOD;
        }
        x = x * x % MOD;      // x 平方，对应二进制位的左移
    }
    return res;
}

// 调用
pow(a, MOD - 2)
```

大量连续数字素性检测

欧拉筛

随机数

洗牌算法(knuth shuffle)

洗牌算法是一种打乱序列的方法，可以保证对于最终的序列，每个元素能等概率出现在每一个位置
- 算法的常见应用是打乱顺序，比如在简易扫雷中随机得到地雷位置，只需要使用洗牌算法分散元素

步骤：算法遍历序列中的每个位置，对一个位置而言，设下标是 $i$

随机选择一个还未被遍历的位置(可能选中当前位置)，设下标是 $x$

将下标 $x$ 和 $cur$ 的元素交换位置

// java 中有对应方法：Collections.shuffle(list);
public static void shuffle(int[] a) {
    Random random = new Random();
    int n = a.length;
    for (int i = n - 1; i > 0; i--) {
        int x = random.nextInt(i + 1);
        int t = a[i];
        a[i] = a[x];
        a[x] = t;
    }
}

方法证明
- 对于一个从0-n的序列，第一次选择时，每个元素被选中的概率都为1/n
- 第二次选择时，被选中的元素首先不可能被之前选中(概率为(n-1)/n)，而且需要被本次选中(概率为1/(n-1))，因此每个元素被选中的概率为(n-1)/n*1/(n-1)=1/n
- 依次可得，每个元素出现在每个位置的概率都为1/n
方法的时间复杂度为 $O(n)$ ，和序列长度有关
- 可以发现洗牌后的每个元素分布理论是均匀的，方法可以作为从 $n$ 个元素中选择 $m$ 个元素的可选方法
- 如果需要从长序列中选择少量元素，最好考虑专门的随机采样算法

随机抽样

可以想到，对于在 $1-n$ $1 - n$ 的范围中选择 $m$ $m$ 个随机数，可以在每次选择时判断是否被选择过，如果被选择过则重新选择，直到得到没有被选择的数，这被称为算法 $S$ $S$ ，后续许多方法都在这个基础上改进的
- 如果使用普通的数组存储，需要遍历整个数组，判断是否被选择过；如果使用哈希结构，可以方便查看是否被选择过
- 此方法在选择数时需要判断是否被选择过，越到后面被选择过的概率越大，选择一个数的时间也越长
```
public static int[] sample(int n, int m) {
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < m; i++) {
        int x;
        do {
            x = (int) (Math.random() * n);
        }
        while (set.contains(x));
        set.add(x);
    }
    return set.stream().mapToInt(Integer::intValue).toArray();
}
```

蓄水池抽样Reservoir Sampling

先选中第1到k个元素，作为被选中的元素
然后依次对第k+1至第N个元素处理，每次下标为 $i$
- 选择 $[1,i]$ 的随机数 $r$
- 如果 $r<=k$ ，则将第 $i$ 个元素加入被选元素中，即交换 $r$ 和第 $i$ 个元素

每个元素都有k/i的概率被选中，然后等概率的（1/k）替换掉被选中的元素

public int[] sample(int[] nums, int k) {
    for (int i = k; i < nums.length; i++) {
        int r = (int) (Math.random() * i);
        if (r < k) {
            int temp = nums[r];
            nums[r] = nums[i];
            nums[i] = temp;
        }
    }

    return Arrays.copyOfRange(nums, 0, k);
}

Floyd's Algorithm：类似之前的洗牌算法思想，Floyd抽样考虑等概率地获取 $m$ 个数字

基本思想是：

将序列下标为 $0, ..., n-1$ 的数组分成两部分，最后 $m$ 个元素作为待选样本
创建一个最终集合
接下来对最后 $m$ 个元素从下标 $n - m$ 向后遍历
- 每次对下标 $i$ ，选择一个随机数 $T$ ，在 $[0, i]$ 之间
- 如果 $T$ 下标对应元素被选中过，将当前样本加入最终集合
- 否则，将下标 $i$ 的元素加入最终集合

将集合返回

public List<Integer> sample(List<Integer> nums, int m) {
    int n = nums.size();
    Set<Integer> selectedIndex = new HashSet<>();
    Random rand = new Random();

    for (int j = n - m; j < n; j++) {
        int t = rand.nextInt(j + 1); // [0, j]

        if (selectedIndex.contains(t)) {
            selectedIndex.add(j);
        } else {
            selectedIndex.add(t);
        }
    }

    List<Integer> res = new ArrayList<>();
    for (int index: selectedIndex) {
        res.add(nums.get(index));
    }

    return res;
}

implicit hash sampling

拒绝采样

矩阵

矩阵对角线遍历

对于 $m * n$ 的矩阵，应该有 $m + n - 1$ 条主对角线，可以通过对每个对角线单独遍历，减少因为存储所有对角线的状态使用的空间

int m = array.length, n = array[0].length;
// 实际上是从右上角的第一条对角线遍历起的
// 对角线上的元素满足i-j值相同，规定 i - j = k - n
for (int k = 1; k < m + n; ++k) {
    int minJ = Math.max(0, n - k);
    int maxJ = Math.min(m + n - 1 - k, n - 1);
    for (int j = minJ; j <= maxJ; ++j) {
        int i = k + j - n;
        System.out.println(array[i][j]);
    }
}