算法基础

GPT摘要

这篇文章是算法与数据结构学习的大纲，涵盖了从基础算法到高级算法的多个领域。主要内容包括基础算法（排序、二分、高精度计算、前缀和、双指针等）、数据结构（链表、栈、队列、树、Trie树、并查集、堆等）、图论算法（深度优先搜索、广度优先搜索、最短路、最小生成树等）、数学算法（质数筛选、约数、快速幂、逆元、组合数学等）、动态规划（背包问题、线性动态规划、状态动态规划、记忆化搜索）以及贪心算法。文章还列出了LeetCode的Hot 100题单和按类别分类的刷题建议，包括找规律题、基础算法题、数据结构应用题、搜索算法题和动态规划题等。此外，还提到了一些高级算法和数据结构的实现，如马拉车算法、非递归快速排序、非递归中序遍历等。整体来看，这是一份较为全面的算法与数据结构学习路线图，适合系统性学习和刷题准备。

0.特殊

leetcode 10^7^

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n<=12      n!

n<=30      2^n           dfs+剪枝

100~300  n^3            floyd

10^3        n^2            dp dij 二分  

10^4        n*根号n      块状链表

10^5~6    nlogn         排序 线段树 树状数组 set/map heap dij+heap spfa 二分 求凸包 求半平面交

10^6         n               hash 双指针  kmp ac自动机  
	小常nlogn   sort 树状数组 heap+dij spfa

10^7         n                hash 双指针  kmp ac自动机  线性筛质素

10^9         根号n         判断质素

10^18        logn          欧几里得  快速幂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<utility> map
#include<cstring> memset(h,-1,sizeof h); memset(dis,0x3f,sizeof dis);
// 小于x的第一个元素
int idx = lower_bound(alls.begin(), alls.end(), x)-alls.begin();

// 优先队列
    priority_queue<int, vector<int>, less<int> > q;  //大根堆 priority_queue<int> q; 
	priority_queue<int,vector<int>,greater<int> >q;  //小根堆
	// 自定义比较函数：STL构造时放入 https://www.cnblogs.com/lengbingshy/p/3491192.html
    static bool mycmp(ListNode* l1, ListNode* l2)  return l1->val>l2->val;
    priority_queue<ListNode*,vector<ListNode*>,function<bool(ListNode*, ListNode*)>> pq(mycmp);
	// 或者
    struct comp {
        bool operator()(ListNode* a, ListNode* b) {
            return a->val > b->val;
        }
    };
    priority_queue<ListNode*, vector<ListNode*>, comp> q;
	
// 保留小数
	setiosflags(ios::fixed)<<setprecision(6)
//排序 去重  algorithm
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

// vector
    vector<int> a(b) 	vector<int> a = {1，2，3}初始化
    
	a.swap(b)			交换
	add.push_back({x,c})  //vector中 pair插入:
        
// 优先队列 栈  top()   pop() push()
// 队列        front() pop() push()
        
//set map multiset multimap 平衡二叉树（红黑树） 动态维护有序序列 增删改查:O(logN)
	size() empty() clear() begin() end()
set 无重复有序 multiset 有重复
    insert()
    find()
    count() // 0 1
    erase(x)删除所有x  k+logn
    erase(迭代器)删除当前
    lower_bound(x) 删除大于等于x最小的  
    upper_bound(x) 删除大于x中最小的

map multimap
    insert({'a',1}) erase() 参数pair
    添加M["str"]=1 ,如果没有该key，默认值为0
    auto遍历时first,second取数，和pair遍历一样
    multimap可以用map<x,vector<y> >代替

unordered_set unordered_map unoerder_multiset unoerder_multimap 哈希表
    增删改查O(1) 不支持 lower_bound upper_bound

//二分返回第一个大于等于x的数
	lower_bound(a,a+n,x)-a;
	lower_bound(v.begin(),v.end(),x)-v.begin();  

// 随机数
	srand((int)time(0));
	cout << rand()%100<< " ";

// 自定义比较函数
	static bool cmp(int a,int b){return a>b;}
	sort(a,a+n,cmp);
// greater比较
	sort(a,a+n,greater<int>());

1.基础

1.0排序

快速排序

​ 选取中点为划分，左边<=，右边>=。再分别排序两边 空间O(logn) 不稳定 边界选择

1
2
3
4
5
6
7
8
9
10
11
int i=l-1 ,j=r+1 mid=a[l + r >> 1];
while(i<j){
    i++;while(a[i]<mid) i ++;
    j--;while(a[j]>mid) j --;
    if(i<j)swap(a[i], a[j]);
}
quickSort(l, j);        // j会停留在<=mid的位置，且j右边一定满足>=mid
quickSort(j+1, r);

// 如果以i-1  i分解 mid要加一  否则死循环  [1, 2]
return ;

​ partition: l的左边小于key，r的右边大于key。[l:i)的数等于key

l为下一个放小于key的地方，r为下一个放大于key的地方

最后0l-1小于key ， lr等于key ， r+1到n-1大于key

1
2
3
4
5
6
7
8
9
10
11
12
l=0,r=n-1,i=l
while(i<=r){
    if(nums[i]<key){
    	swap(nums[i],nums[l]);
    	i++,l++;//换过来的数一定等于key，i直接增加
    }else if(nums[i]>key){
    	swap(nums[i],nums[r]);
    	r--;   // 换过来的数不知道大小，i不增加
    }else{
    	i++;
    }
}

归并排序

​ 先排好中点左边，再排中点右边，然后merge两边, 空间O(n) 稳定

1
2
3
4
int mid = l+r >> 1;
merge_sort(l,mid);
merge_sort(mid+1,r);
// merge  merge时tmp数组只申请需要的大小，或者全局申请

其他

1
2
3
4
5
6
7
8
冒泡 每次交换出一个最大
插入 
选择  不稳定

堆排序 不稳定

计数排序
桶排序  ：桶内排序，桶外计数排序
1
2
3
4
5
6
7
8
9
10
11
12
排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
QuickSort	O(n log n)	O(n^2)		O(log n)不稳定
Merge Sort	O(n log n)	O(n log n)	O(n)稳定
Heap Sort	O(n log n)	O(n log n)	O(1)不稳定
Timsort		O(n log n)	O(n log n)	O(n)稳定  归并+插入
Dual-Pivot 	O(n log n)	O(n^2)		O(log n)不稳定  java int char long[]
Insertion 	O(n^2)	O(n^2)			O(1)稳定   每次向有序中插入一个元素 常数小！
Bubble Sort	O(n^2)	O(n^2)			O(1)稳定   冒泡 每次交换出一个最大
Selection 	O(n^2)	O(n^2)			O(1)不稳定  每次在无序中，选出一个最小的
Counting 	O(n + k)	O(n + k)	O(k)稳定  	0~k个桶 统计数量，适用于小范围整数。
Radix 		O(d(n + k))	O(d(n + k))	O(n + k)稳定 	按位排序，适用于整数和固定长度字符串。
Bucket 		O(n + k)	O(n^2)		O(n + k)稳定	数据分桶[0, 0.1), [0.1, 0.2),后排序，再合并所有桶。

TimSort 的过程：

  1. 分块: TimSort 首先将数组分成若干个小的子数组，这些子数组称为 Run。每个 Run 的大小通常在 32 到 64 之间，具体取决于数组的大小和实现。
  2. 对每个 Run 进行排序: 对每个 Run 使用插入排序进行排序，因为插入排序在小规模数据上效率高。
  3. 合并 Run: 将这些有序的 Run 通过归并排序的方式合并在一起，形成一个更大的有序数组。TimSort 会根据实际情况决定何时合并哪些 Run，以保持整体效率。

1.1二分

分界点右边都满足一种性质，左边都不满足

1
2
3
4
5
6
7
8
9
10
l=0 ,r=n-1;
//寻找满足条件的最左边的数        大于等于aim      不会用到a[r]的值     
while(l<r){
    mid=l+r>>1;
    if(a[mid]>=aim){
        r=mid;
    }else{
        l=mid+1;
    }
}
1
2
3
4
5
6
7
8
9
//寻找满足条件的最右边的数        小于等于aim      不会用到a[l]的值
 while(l<r){
    mid=l+r+1>>1;        //不加一 会死循环
    if(a[mid]<=aim){
        l=mid;
    }else{
        r=mid-1;
    }
}
1
2
3
4
5
6
//浮点数二分，结束条件要多两位
while(r-l>0.00000001){        //多两位
    double mid=(l+r)/2;
    if(mid*mid*mid<=n) l=mid;
    else r=mid;
}

0.旋转数组找旋转点

1.机器人跳跃 1e5 n a[i]，从起点跳到终点 

1
2
每次跳跃res= res*2-a[i];   res始终要大于零，求最小的起始res。
检测一个数要1e5，遍历[1,1e5]个数超时，二分遍历即可解决

2.分巧克力

1
2
对于每一种大小的切法，1e5时间能求出是否满足数量
二分求出这个大小即可。

3.炸弹问题：矩阵和

4.四平方和 四个数的平方和为x，求出序列最小的 x< 5*1e6

1
2
3
4
求出三个数，就能得出最后一个，但是时间上最多求出两个
	枚举前面两个数c d，并存下来 按照sum排序 如果相同就按照c排序
		（或者把和扔到hash中，只放入第一次遇到的）
	枚举a b，查看x-a^2-b^2是否在存下的数中（二分，hash）

5.k倍区间 一个数组中子串为给定数k的倍数，求共有多少个这样的区间 1e5

1
2
3
4
5
6
7
8
9
两个循环加前缀和 但依旧会超时

s[r]-s[l]  % k == 0 相当于  s[r]与s[l]余数相同，所以每次是在找余数为固定值的个数
cnt[i] 代表当前余数为i的个数（包括s[r]）
先计算出s[r]全取的情况下，余数为零的个数，再取算s[l]与s[r]同余的个数
遍历右端点
    if(s[r]==0)res ++;
	cnt[s[r]]++;
    res += (cnt[s[r]]-1);

1.2高精度

1
2
3
4
//两个大整数，求和          10^6位
//相减                    10^6位
//一个大整数乘一个小整数    <10^6位 * 1000000
//          除
1
2
//大整数的每一位存到vector中，个位放下标0,输入用字符串,记得-'0'
//t = a[i] + b[i] + t
  • 除了加法都要去除前面的零 while(C.size()>1&&C.back()==0)C.pop_back();
  • 乘法每一位直接拿小的数乘
  • 除法从高位开始除，最后反转 reverse(C.begin(),C.end());
1
2
3
4
5
6
7
8
9
10
11
// 乘法直接一位一位乘, 最后再一次性进位
for(int i=0;i<a1.size();i++){
    for(int j=0;j<a2.size();j++){
    	res[i+j] += a1.get(i) * a2.get(j);
    }
}

for(int i=0;i<res.length-1;i++){
    res[i+1] += res[i]/10;
    res[i] %= 10;
}

java中，string到List<Integer>需要-‘0’，而sb.append 可以直接append数字

1.3前缀和 差分

==前缀和==：前缀和一个值代表着一个区间的性质

  1. 普通前缀和 询问区间
  2. 矩阵和 求出每个到0，0点的矩阵的和 询问矩阵
  3. 前缀积 2438. 二的幂数组中查询范围内的乘积 - 力扣（LeetCode） 需要结合逆元

==差分==：差分数组一个值的改变影响一个区间

  1. 差分数组 多次区间操作后，询问结果
  2. 差分矩阵b求和等于a，不用考虑b如何出来的，只需要考虑b如何改变a的
    • 当b增加时，改变的时全部右下角的数

1.4双指针

双指针
快排 归并排序

将i j 两种枚举n^2的情况，优化为O(n);
找到i j 之间存在的单调性

将一个英文句子的每个单词输出。

1
2
3
4
5
for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;
    // 具体问题的逻辑
}

  • 连续最长不重复子串

  • 两个升序数组，求和为x的两个数组的下标

  • 判断是否是字串

1.5位运算

1
2
3
4
5
#define lowbit(x) x&-x
//lowbit:返回最后一位1以及后面的零 110100 -> 100

n>>k&1
//二进制中第k位是几
  • 求一个数中二进制1的个数，两种方法都可以

1.6离散化

原来的下标太大了，将大数，转为排序数组的下标

  • 操作无限长坐标上的元素后，询问区间和

将大的数保存到vector中后，排序，去重

1
2
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());

将大值和下标映射用二分查找或unordered_map映射

询问上的点也要先加入到alls中

如果只想将大数映射到小数，也可也不去重，同一个数每次查找时会获取出同一个idx

1
2
3
4
// sorted 所有的大数 并且已经排序 可能重复
Arrays.sort(sorted);

idx = Arrays.binarySearch(sorted, nums[i]);   //或者用map

2.数据结构

单链表

int h=-1, e[], ne[], idx

栈

s[], t=-1

单调栈

单调增：栈内元素单调递增，遍历到i时，导致某元素出栈，则i是右边第一个比该元素小的，新栈顶为左边第一个比该元素小的。

  1. 最大矩阵面积

队列

q[], t=-1, h=0; t进h出 q[++t]=x; h++;

  • 单调队列：把最小的始终保存在队头，实现滑动窗口求最小

树遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
297 树的序列化与反序列化
void middle_order(Node Node):
	if(Node == NULL)
        return;
    // printf("%d ", Node->data);前
    middle_order(Node->left);
    // printf("%d ", Node->data);中
    middle_order(Node->right);
    // printf("%d ", Node->data);后

非递归实现：颜色标记法
def inorderTraversal(self, root: TreeNode) -> List[int]:
    WHITE, GRAY = 0, 1
    res = []
    stack = [(WHITE, root)]
    while stack:
        color, node = stack.pop()
        if node is None: continue
        if color == WHITE:
            stack.append((WHITE, node.right)) # 先输出的后入栈
            stack.append((GRAY, node))
            stack.append((WHITE, node.left))
        else:
            res.append(node.val)
    return res

搜索树

树：边的个数加+ 1 = ∑节点*度 + 1 = 节点个数

https://www.bilibili.com/video/BV1Tb4y197Fe

Binary Search Tree: BST ->退化-> AVL （左右高度差不超过1）>频繁增删> RBT

如果失去平衡, 找到第一个失去平衡的点左右旋转使得平衡 LL，RR（直接旋转） LR（先左旋）

RBT：根是黑色（空结点也是黑色）、红节点不连续、黑节点到达空指针进过的黑点个数相同

B树（数据库）：一个节最多m-1个值（连续，访问磁盘次数就会更少），m个孩子节点。m为树的阶

​ 非叶子节点最少有(m+1)/2子树，最多m

​ 叶子节点为空节点，都在同一层

​ 查找：和BST类似 范围查询：中序遍历

​ 插入：当节点个数多于(m+1)/2时，进行分裂

​ 删除：终端节点：大于(m+1)/2-1个节点：直接删

​ 等于(m+1)/2-1，去兄弟节点借，借不到就合并：上一层挪下来一个

​ 非终端：和相邻关键字（前驱、后驱）互换，就变成了终端节点

B+树：

​ n个节点n个子树

​ 非叶子节点只能索引，叶子节点才指向记录。

​ 叶子节点被串成了一个单链表，可以线性访问，头指针被保存。

KMP

p 在 s中所有的起始位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
ne:p当前匹配失败后，j跳转的位置（j-1的最大匹配长度） ababc ne[3]=1  ne[4]=2
void get(){
    int i=0,j=-1;
    ne[0]=-1;
    while(i<n){
        if(j==-1||p[i]==p[j]){
            i++,j++;
            ne[i]=j;
        }
        else{
            j = ne[j];
        }
    }
}
void kmp(){
    int i=0,j=0;
    while(i<m){
        if(j==-1||s[i]==p[j]){
            i++,j++;
            if(j==n){
                cout<<i-n<<" ";
                j=ne[j];  // 这里不可以从头开始，不然会少很多  如 aba  ababa
            }
        }
        else{
            j = ne[j];
        }
    }
}
cin>>n>>s>>m>>p;
get();
kmp();

Trie树

字符串出现次数

1
2
3
4
5
6
7
8
9
10
11
int son[N][26],cnt[N],idx;   //son 保存下标
void insert(char str[]){
    int p=0;
    for(int i=0;str[i];i++){
        int u=str[i]-'a';
        if(!son[p][u])son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;
    return ;
}

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//返回根节点编号 路径压缩
int find(int x){
    if(x!=p[x]){
        p[x]=find(p[x]);
    }
    return p[x];
}
void merge(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx!=fy){     //在不同的情况下才相加
        p[fx]=fy;
        cnt[fy]+=cnt[fx];
    }
    return ;
}

堆

用数列保存，从1开始存 儿子（2u，2u+1）

down: 左右儿子已经是堆，加上直接再构成堆 n/2开始down

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void down(int u){
    int t=u;
    if(u*2<=si&&h[u*2]<h[t])t=u*2;
    if(u*2+1<=si&&h[u*2+1]<h[t])t=u*2+1;
    if(u!=t){
        swap(h[u],h[t]);
        down(t);
    }
}
void up(int i){
    if(i!=1 && heap[i]<heap[i/2]){
        swap(heap[i],heap[i/2]);
        up(i/2);
    }
}
// 插入到最后一个元素，然后up
void insert(int p){
    now++;
    heap[now] = p;
    up(now);
}
// 最后一个元素放到第一个位置，然后down
void pop(){
    heap[1]=heap[now];
    now--;
    down(1);
}

无扩容java堆，0开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class MyPriorityQueue<E>{
    private int size;
    private Object[] queue;
    private final Comparator<? super E> comparator;

    public MyPriorityQueue(int initialCapacity, Comparator<? super E> comparator){
        this.queue = new Object[initialCapacity+1];
        size = 0;
        this.comparator = comparator;
    }

    public void offer(E e){
        queue[size] = e;
        size ++;
        up(size-1);
    }

    public E peek(){
        return size == 0 ? null: (E)queue[0];
    }

    public E poll(){
        if(size == 0){
            return null;
        }
        E res = (E)queue[0];
        queue[0] = queue[size-1];
        size--;
        down(0);
        return res;
    }

    private void down(int i){
        int u = i;
        if(i*2+1<size && comparator.compare((E)queue[u], (E)queue[i*2+1]) > 0){
            u = i*2+1;
        }
        if(i*2+2<size && comparator.compare((E)queue[u], (E)queue[i*2+2]) > 0){
            u = i*2+2;
        }
        if(u != i){
            Object t = queue[i];
            queue[i] = queue[u];
            queue[u] = t;
            down(u);
        }
    }

    private void up(int i){
        if(i == 0) return ;
        int p = (i-1) / 2;

        if(comparator.compare((E)queue[i], (E)queue[p]) < 0){
            Object t = queue[i];
            queue[i] = queue[p];
            queue[p] = t;
            up(p);
        }
    }


    public int size(){
        return size;
    }
}

Hash

方法1：线性探测表，开两倍地址空间 null=0x3f3f3f3f

//返回x对应下标,没有x就返回应该放的地方

1
2
3
4
5
6
7
8
int find(int x){
    int k=(x%N+N)%N;
    while(a[k]!=null&&a[k]!=x){
        k++;
        if(k==N)k=0;
    }
    return k;
}

方法2：链地址法，也是存图的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int h[N],e[N],ne[N],idx;
int mod=100003;
void insert(int x){
    int k=(x%N+N)%N; //保证都映射到正数上
    e[idx]=x;
    ne[idx]=h[k];
    h[k]=idx++;
}
bool query(int x){
    int k=(x%N+N)%N;
    for(int i=h[k];i!=-1;i=ne[i])
        if(e[i]==x)
            return true;
    return false;
}

字符串hash

将一段字符串用一个数字表示，字符串低位为数字高位 左高右低

hash值用ULL保存typedef unsigned long long ULL;

1
2
3
const int P=131;//131进制，字符串中下标小的为高位
ULL p[N];  // 进制的i次方
ULL h[N];  // hash值   下标1~i

存入时,计算字符串hash

1
2
3
4
for(int i=1;i<=n;i++){
    h[i]=h[i-1]*P+s[i];
    p[i]=p[i-1]*P;
}

计算式，L到R之间的字符串的hash值为

1
ULL t=h[R]-h[L-1]*p[R-L+1];

java：214. 最短回文串 前添加字符使得字符串回文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int base = 131;
int mod = (int)1e9+7;
int mul = 1;

int prefix = 0, suffix = 0;
int idx = 0;
int n = s.length();
// abcde
for(int i=0;i<n;i++){
    int c = s.charAt(i) - 'a' + 1;
    prefix = (int)(((long) prefix * base + c)%mod); //a ab abc  正常字符串写法
    suffix = (int)(((long) mul * c + suffix)%); //a ba cba
    mul = (int)(((long) mul * base) % mod);

    if(prefix == suffix){
        idx = i;
    }

}

if(idx==n-1 || n==0){
    return s;
}

return new StringBuilder(s.substring(idx+1)).reverse().toString() + s;

回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        StringBuffer t = new StringBuffer("$#");
        for (int i = 0; i < n; ++i) {
            t.append(s.charAt(i));
            t.append('#');
        }
        n = t.length();
        t.append('!');

        int[] f = new int[n];
        int iMax = 0, rMax = 0, ans = 0;
        for (int i = 1; i < n; ++i) {
            // 初始化 f[i]
            f[i] = i <= rMax ? Math.min(rMax - i + 1, f[2 * iMax - i]) : 1;
            // 中心拓展
            while (t.charAt(i + f[i]) == t.charAt(i - f[i])) {
                ++f[i];
            }
            // 动态维护 iMax 和 rMax
            if (i + f[i] - 1 > rMax) {
                iMax = i;
                rMax = i + f[i] - 1;
            }
            // 回文串数量
            ans += f[i] / 2;
            // 回文串长度
            ans  = Math.max(ans, f[i] -1);
        }

        return ans;
    }
}

树状数组

  1. 逆序对数量

  2. 单点更新 update(x, delta)： 把序列 x 位置的数加上一个值 delta； logn

  3. 前缀和查询 query(x)：查询序列 [1,...x] 区间的区间和，即位置 x 的前缀和。logn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n;
int a[1005],c[1005]; //对应原数组和树状数组

int lowbit(int x){
    return x&(-x);
}

void updata(int i,int k){    //在i位置加上k
    while(i <= n){
        c[i] += k;
        i += lowbit(i);
    }
}

int getsum(int i){        //求A[1 - i]的和
    int res = 0;
    while(i > 0){
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}

建树规则：c[i] 管理着 从i开始的前lowbit(i)个数的和

  • 求前 10010010的和 只需要拿出c[10010010] (最后两个数) + [sum(10010000) = c[10010000] + c[10000000] ]

  • 当一个数修改后 1010，会影响管理者他的c：c[1010] c[1100] c[10000] c[100000] …

  • 单点修改+区间查询 （单纯前缀和不能在这两种操作混合时发挥作用）

  • 区间修改+单点查询 维护差分数组 （单纯差分数组在这两种操作混合时发挥作用）

3.图

建图

1
2
3
4
5
6
7
8
9
10
11
12
13
int h[N],ne[N],e[N],w[N];
int idx;
memset(h,-1,sizeof h);

void add(int a,int b,int c){
    w[idx]=c;
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

for(int i=h[a];i!=-1;i=ne[i]){
    int j=e[i];

dfs:

1
2
3
4
5
6
7
8
9
10
11
// 需要标记数组st[N],  遍历节点的每个相邻的边
void dfs(int u) {
    st[u] = true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            dfs(j);
        }
    }
}
实践：求树的重心 acwing846

bfs：

st[] 和 queue

求距离，先进距离短 先出

d[]保存距离，同时判断是否访问过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
d[1]=0;
queue<int> q;
q.push(1);

while(q.size()){
    int x=q.front();q.pop();

    for(int i=h[x];~i;i=ne[i]){
        int j=e[i];
        if(d[j]==-1){
            d[j]=d[x]+1;
            q.push(j);
        }
    }
}

最短路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
无负边 （从顶点角度出发每次取出最近顶点）
                                 			                 都需要dis[N]
   dij稠密 	         n*n      二维数组           st[N] //判断是否已经求出来了
   dij稀疏  堆优化      m*logn     邻接表              优先队列存<PII>  st[N]


有负边  (从边的角度出发)

   有负环 bellmanford      n*m               struct存边       backup[N]//防止串联更新
   无负环 spfa             m -> n*m          邻接表            q  st[N]//是否在队列中
      判负环：不用设置dis，所有点都加入队列                        +cnt[N]  连了多少条边

floyd 动态规划             n^3                 二维数组


二维数组处理重边g[a][b]=min(g[a][b],c); dij初始化可以全为0x3f3f3f3f但floyd不行。
邻接表、struct存边不需要额外处理，松弛时自动选择小的边

存在负边会导致正无穷变小（bellmanford 和 floyd）所以判断改成：dis[n]>0x3f3f3f3f /2

dij

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
dis[1]=0;
priority_queue<PII,vector<PII>,greater<PII> > p;
p.push({0,1});

while(p.size()){
    PII tmp = p.top();
    p.pop();
    if(st[tmp.second])continue;

    int x = tmp.second;
    st[x] = 1;

    for(int i=h[x];i!=-1;i=ne[i]){
        int j = e[i];
        if(dis[j]>dis[x]+w[i]){  // 这里及时更新距离，并通过距离剪枝
            dis[j] = dis[x]+w[i];
            p.push({dis[j],j});
        }
    }
}

bellmanford

1
2
3
4
5
6
7
8
9
dis[1]=0;
// 最多k条边,对所有点的出边进行更新
for(int i=0;i<k;i++){
    memcpy(backup,dis,sizeof dis); //防止串联更新
    for(int j=0;j<m;j++){
        int a=edges[j].a,b=edges[j].b,c=edges[j].c;
        dis[b]=min(dis[b],backup[a]+c);
    }
}

如果k=n时还更新了，就是存在包含点1的负环

spfa

当一个点距离变小后，所有以该点的出边才可能更新。st数组防止重复添加(不用也能过)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
dis[1]=0;
q.push(1);
st[1]=1;
while(q.size()){
    int t=q.front();
    q.pop();
    st[t]=0;

    for(int i=h[t];i!=-1;i=ne[i]){
        int j=e[i];
        if(dis[j]>dis[t]+w[i]){
            dis[j]=dis[t]+w[i];
            if(st[j]==0){
                q.push(j);
                st[j]=1;
            }
        }
    }
}

判负环

最短路包含边数大于n-1

设置一个虚拟源节点，到所有阶段距离都为0，原图有负环等价于现在的图有负环，

第一次spfa等价于所以开始时所有点都加入

最小生成树

1
2
普里姆：	 加最近点，有点像dij    n^2
克鲁斯卡尔： 加最小的边     		E^2     并查集

4.数学

筛质素

诶氏筛法 O(nloglogn):小于等于 n 的质数的倒数和大约是 loglogn

1
2
3
4
5
6
7
8
void get_primes1(){
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
            for(int j=i;j<=n;j+=i) st[j]=true;//可以用质数就把所有的合数都筛掉；
        }
    }
}

线性筛法 O(n)：每个数只被最小的质素筛 https://www.acwing.com/solution/content/2559/

i=15 会筛掉 15* 2 15* 3 ，但15*5不会被15筛，而是被25 * 3筛, 所以primes[j]只到 i 的最小因子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i;
        //假设primes[0]为n最小的质因子,i为最大的因数，
        //易知若primes[i]中i>0,则会进入循环后产生多余的标记。
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            //标记;primes[j]一定是primes[j]*i的最小质因子
            st[primes[j]*i] = true;
            //表明primes[j]一定是i的最小质因子,没有必要再遍历,primes要小于等于i的最小质因子
            //这样能保证每个数遍历一遍,而没有重复
            if(i % primes[j] == 0) break;
        }
    }
}

约数

n 个正整数 ai，请你输出这些数的乘积的约数个数

求出所有质因子p以及个数x：N = (p1^x1^)(p2^x2^)(p3^x3^)…(pk^xk^)

约数个数： (x1+1)(x2+1)(x3+1)…(xk+1)

约数和=(1+p1^1^+p1^2^+…+p1^x1^)×(1+p2^1^+p2^2^+…+p2^x2^)…×(1+pk^1^+pk^2^+…+pk^xk^) 每一个括号里取出一个数相乘就得到一个约数，最后求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
unordered_map<int, int> primes;
while (n -- )
{
    int x;
    cin >> x;

    for (int i = 2; i <= x / i; i ++ )
        while (x % i == 0)
        {
            x /= i;
            primes[i] ++ ;
        }

    if (x > 1) primes[x] ++ ;
}

LL res = 1;
for (auto p : primes)
{
    LL a = p.first, b = p.second;
    LL t = 1;
    while (b -- ) t = (t * a + 1) % mod;
    res = res * t % mod;
}

cout << res << endl;

秦九韶算法: 计算多项式朴素方法需要2n乘法（xn-1 * x * a）n次加法，秦九韶只需要n次乘n次加
$$
f(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0= (((a_nx + a_{n-1})x + \cdots )x + a_1)x + a_0
$$

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
求 m^k mod p，时间复杂度 O(logk)。
int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

矩阵快速幂

将递推式写成矩阵形式：斐波那契数列 O（n）-> O（m^3*logn）

矩阵快速幂 - Virtual Judge (vjudge.net)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
const int N=6;                  //题目中可能出现的最大大小
const int n=6;                  //实际常数矩阵的大小
const int mod=123456789;        // const int 和int 作为模数还运算速度不一样
long long int t[N][N];          //常数矩阵

long long int tmp[N][N];         //相乘时的temp  辅助
void multi(long long int a[][N],long long int b[][N],long long int n)
{
    memset(tmp,0,sizeof tmp);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            for(int k=0;k<n;k++)
                tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%mod;

    for(int i=0;i<n;i++)
    	for(int j=0;j<n;j++)
    		a[i][j]=tmp[i][j];

}

long long int result[N][N];                     //保存求幂后的值

void Pow(long long int a[][N],long long int x)
{
    memset(result,0,sizeof result);             //N是矩阵大小
    for(int i=0;i<N;i++) result[i][i]=1;

    while(x){
        if(x&1)
            multi(result,a,n);              //result=result*a;复制直接在multi里面实现了；
        multi(a,a,N);                       //a=a*a
        x>>=1;
    }
}

int main()
{
    int x;
    while(cin>>x&&x!=-1){
        t[0][0]=t[0][1]=t[1][0]=1;
        t[1][1]=0;
        pow(t,x);
        cout<<result[0][1]<<endl;
    }
}

逆元

  • (ab)modp=(amodp)∗(bmodp)modp
  • (a+b)modp=((amodp)+(bmodp))modp
  • (a−b)modp=((amodp)−(bmodp)+p)modp
  • 注意(a/b)modp≠((amodp)/(bmodp))modp 这也是为什么需要求乘法逆元

若整数 b，m互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 a/b≡a×x(modm)，则称 x为 b的模 m 乘法逆元，记为 b−1(modm)。

b存在乘法逆元的充要条件是 b与模数 m互质：

  • 当模数 m为质数时，b^m−2^即为 b 的乘法逆元。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    LL qmi(int a, int b, int p)
    {
        LL res = 1;
        while(b){
            if(b & 1) res = res * a % p;
            a = (LL)a * a % p;
            b >>= 1;
        }
        return res;
    }
    qmi(a, p - 2, p)

  • 否者用扩展欧几里得

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int exgcd(int a, int b, int &x, int &y)
    {
        if (!b) {
            x = 1, y = 0;
            return a;
        }
        int d = exgcd(b, a % b, y, x);
        y -= a / b * x;
        return d;
    }
    int d = exgcd(a, p, x, y);
    if (d == 1) cout << ((LL)x + p) % p << endl;//保证x是正数
    else puts("impossible");
1
2
3
4
5
6
7
8
a / b ≡ a * x (mod n)
两边同乘b可得 a ≡ a * b * x (mod n)
即 1 ≡ b * x (mod n)
同 b * x ≡ 1 (mod n)
由费马小定理可知，当n为质数时 且b n 互质
b ^ (n - 1) ≡ 1 (mod n)
拆一个b出来可得 b * b ^ (n - 2) ≡ 1 (mod n)
故当n为质数时，b的乘法逆元 x = b ^ (n - 2)

逆元可拆分：（a!)-1 =（a-1! * a)-1 = ( a-1! )-1 * ( a )-1

组合数

组合数.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 100010, p = (int) 1e9 + 7;
    static int[] fact = new int[N], infact = new int[N];

    public static int qmi(int a, int k, int p){
        long res = 1;
        while( k > 0){
            if( (k & 1) != 0 ) res = res * a % p;
            a =(int) ((long) a * a % p);
            k >>= 1;
        }
        return (int) res;
    }

    public static void main(String[] args) throws Exception{
        int t = Integer.valueOf(read.readLine());
        fact[0] = infact[0] = 1;
        for(int i = 1; i < N; i++){
            fact[i] =(int) ((long)fact[i - 1] * i % p);
            infact[i] = (int) ((long) infact[i - 1] * qmi(i, p - 2, p ) % p);
        }

        while(t -- > 0){
            String[] ss = read.readLine().split(" ");
            int a = Integer.valueOf(ss[0]);
            int b = Integer.valueOf(ss[1]);
            int res = (int) ((long) fact[a] * infact[a - b] % p * infact[b] % p);
            System.out.println(res);
        }
    }

}

容斥原理

https://www.acwing.com/solution/content/29702/

1
2
n = 10, p1=2,p2=3
求1-10中能满足能整除p1或p2的个数, 即2，3，4，6，8，9，10,共7个

image-20240330222536954

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
using namespace std;
typedef long long LL;

const int N = 20;
int p[N], n, m;

int main() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) cin >> p[i];

    int res = 0;
    //枚举从1 到 1111...(m个1)的每一个集合状态, (至少选中一个集合)
    for(int i = 1; i < 1 << m; i++) {
        int t = 1;             //选中集合对应质数的乘积
        int s = 0;             //选中的集合数量

        //枚举当前状态的每一位
        for(int j = 0; j < m; j++){
            //选中一个集合
            if(i >> j & 1){
                //乘积大于n, 则n/t = 0, 跳出这轮循环
                if((LL)t * p[j] > n){    
                    t = -1;
                    break;
                }
                s++;                  //有一个1，集合数量+1
                t *= p[j];
            }
        }

        if(t == -1) continue;  

        if(s & 1) res += n / t;              //选中奇数个集合, 则系数应该是1, n/t为当前这种状态的集合数量
        else res -= n / t;                      //反之则为 -1
    }

    cout << res << endl;
    return 0;
}

高斯消元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
n元1次方程组

初等行列变换：1.某一行乘非零的数   2.交换某2行   3.把某一行的k倍加到另外一行取

高斯消元：每一次消去每行第一个，把方程边成上三角，再逆推求xn xn-1...

完美阶梯型(第一行n个数 第二行n-1...最后一行1个) 唯一解             r(A)=r(A,b)=n
左边没有未知数，右边不为零                    无解                r(A)<r(A,b)
方程没有n个                                无穷多组           r(A)=r(A,b)<n

（矩阵的秩r：矩阵中所有行向量中极大线性代无关组的元素个数。有效方程数量, 阶梯矩阵非零行数）
https://www.zhihu.com/question/21605094

化阶梯型：
int r=0,c=0;
枚举每一列c 0~n-1
	1.选出r~n-1行中，第c列的数最大的那一行(为零就continue),移到第r行上去（最上面）
	2.将该数a[r][c]化成1
	3.将r+1~n-1行，如果第c列不是零，将第c列化为零
	成功消除一列r++
r==n 有解  有解逆推 i=n-1 ~0，
			j= i+1~n-1 
				a[i][n]-=a[i][j]*a[j][n];
r<n 
	for i in r~n-1
		如果存在b不为零，无解 否则无穷解

5.dp

1
2
3
4
5
6
1.每一个状态为一个集合，分集合思想后，求转移方程是通过大的划分出小的(不重不漏)
2.代码实现时，是从小的推导出大的，一定要保证转移方程中小的项已经求出来了。自底向上逐步填充数组
	因此有的循环顺序可以交换：背包、整数划分      有的一定不行：哈密顿
3.初始化，按题意给出有效的初始值
	计数时有效：1，无效为0
	最值时有效：0  负无穷或正无穷

5.1背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
https://blog.csdn.net/yandaoqiusheng/article/details/84782655
01背包    每种只有一个             
完全背包 可以无限重复        
    1000 *1000 * 1000 暴力tle，f[i][j]=max(f[i-1][j],f[i][j-v[i]] +w[i]) 用本层求出来的值优化
多重背包 限制单种数量              
    1000* 2000* 2000 暴力tle，二进制优化（像快速幂），打包后1000* 2000* 12转化为01背包  
分组背包 每一组最多选一个       
    100* 100* 100直接暴力
限制总数量                                
    额外一个sum[][]记录当前数量

1.一维数组存储，用上一层的值j就从大到小，用本层的j从小到大

2.完全背包 和 01背包 的区别仅在于状态更新时的遍历顺序。（即01是逆序，完全是顺序）

3.不超过容量 和 恰好装满 的区别仅在于二者的初始化~
- 前者全0；也就是全有效
- 后者，f[i][0] = 0（第一列），其余全为负无穷，一维：除f[0]为0外，其余f[j]都是负无穷）

5.2线性dp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1.三角形
2.a最长上升子序列 f[i] 以i结尾的长度     优化：f[i]长度为i的序列结尾的数字
3.a、b最长公共子序列 f[i][j] a[i],b[j]结尾的最大长度   以a[i],b[j]是否出现四次划分11 10 01 00
4.编辑距离       f[i][j]a前i个变成b前j个的最小操作次数	 只操作i的最后一个字母（3种）
5.最短编辑距离 		同上
6.石头合并最小代价（最优矩阵相乘）  f[i][j] i到j的代价  最后一次的分界线为分类（因为该区间最后一定是某两个区间合并出来的）
	(!!!!!!区间问题：先枚举区间长度，再枚举起点，最后再根据决策计算。)
    长度 -> 起点 -> 拆分点

7.整数划分1. 转化为体积为1~n的！恰好 ！为n的完全背包物体 计数问题
        	    f[i][j]只取i个数，体积恰好为j的种类

 	2. f[i][j] 总和为i，总数为j   分成有无1两类 f[i][j]=(f[i-1][j-1]+f[i-j][j])%mod;

8.计数问题

5.3状态dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
AcWing 291
只考虑放水平的方格，列方格自动补全（前提不能有连续奇数个零，不然补全不了）
用二进制表示状态，0表示无1表示有

横向放置第i列结尾方格时  1.满足与第i-1列不冲突     (j&k)==0
		        	 2.i-1列剩下的格子，没有连续奇数个格子   st[ j|k ]==1
当n不同时，st数组也不同

//棋盘为0~m-1列，需要计算到m列
memset(f,0,sizeof f);
f[0][0]=1;
for(int i=1;i<=m;i++)     //放以i列结尾的方块
    for(int j=0;j< 1<<n ;j++)      //i-1列结尾的方块状态
        for(int k=0;k< 1<<n ;k++)     //尝试i列结尾的方块状态
            if((j&k)==0 && st[j|k])
                f[i][k]+=f[i-1][j];

11* 2^11 *2^11 =4 * 10^7
1
2
3
4
5
6
7
acwing 91 最短hamilton哈密顿距离
1≤n≤20 
用二进制保存进过点的状态 
int f[1<<N][N];//i状态 j结尾的最小长度
for 状态
	for 终点
		for 倒数第二个点

5.4记忆化搜索

dfs的同时，返回前记录下当前状态值。

没有上司的舞会、最长滑雪长度 零钱兑换(需要注意什么情况下是无解 什么条件是还没求 什么时候是中止)

1
2
3
4
5
6
int get(int x){
    if(f[x])return f[x];
    // 中止条件 
    ... 求解f[x]的最优解res
    f[x] = res;
    return f[x];

题目

1
2
3
4
5
6
7
322Coin Change：给定无数个定值硬币，最少数量凑出amount。
	dp：恰好、完全背包
	记忆化搜索：凑x需要的个数 me[x], 画出求解树,存在重叠，需要记忆优化

矩阵左上角到右下角传纸条，穿两次路径和最大

栈的出栈入栈序列

6.贪心

0.合并区间

1.区间选点使得每个区间至少一个点。

1
右端点排序，每次更新最右边的点

2.安排课表，使得上的课最多[区间不重叠]

3.区间分组，组内互不相交 优先队列+左端点排序

4.选择区间覆盖指定区间。 左端点+贪心

5.排序

6.牛的最大忍耐度最小 对两头牛交换，会导致结果变大还是变小

leetcode

Hot 100

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
1 两数之和 hash  双指针
4  二分
5 最长回文 dp || 马拉车
10 正则表达式匹配 ！ dp  处理边界以及情况列举
11 盛水容器  每次移动是丢弃了一些状态 
15 三数和为零 hash+set去重  |  排序+双指针 注意去重 
19 一次遍历删除链表第n个元素  快慢指针
23 合并k个有序列表  分治！类似归并、维护优先队列
31 下一个排序 找规律
33 旋转过的有序数组 二分寻找一个数
34 二分模板
39 组合总和 dfs   引用更快，但需要回溯回状态
42 接雨水
	求出每个i能够接到的雨水数
	单调栈
46 全排列
48 旋转矩阵

49. 字母异位词分组 输入vector<string> 将所含字母相同放入一个vector中输出
	1.map<string,[s1,s2]> string为排序后 s1,s2为原来
	2.将字母映射一个质素double a[26]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};
		将string转为质素相乘，其他与1一样，少一个排序时间
		小心溢出，用long long后取余(余数要大)或者用double
	3.如果是string需要完全相同，可以字符串哈希映射为一个数字
	4.统计个数后，map<string,[s1,s2]> string是每一个元素的个数 'a:x b:y'

53* 最大子数组和 字串的最大连续和  【dp】  二分分治维护区间关系，可以求解任意[l，r]区间最大值  -> 线段树
	后续题目：2321. 拼接数组的最大分数  或者转为状态dp 

55 从数组第一个位置能否跳到最后一位置，数组上值为最大跳跃距离  dp优化成【贪心】

56 区间合并 【贪心】

62. 【dp】或者 记忆化搜索 或者 排列组合

63 【dp】可以优化空间到

64 【dp】可以直接原数组上dp

70 【dp】或找规律

72 最短编辑距离 【dp】    边界条件(如何初始化方便)

75 将数组分为0 1 2 【partition】 L:下一个放0的位置   R：下一个放2   有等号

76 【滑动窗口】求最小覆盖串
	滑动窗口的套路
	先找到一个可行解，再优化这个可行解。
	优化到不能优化，产生出一个可能的最优解。
	继续找新的可行解，再优化这个可行解。

	直接用数组代替map映射需要的字母的数量，用额外count记下还需要匹配多少个，免去遍历过程

78  求无重复数组的子集   直接每层选出一个，下一层接着这个数选，有重复的话剪枝，排序后只拿第一个

79  普通回溯，记得找到后【提前结束】寻找，不然超时

84  柱状图中最大的矩形 暴力：以i为高度两边扩散；     【单调栈】

85  最大矩形 0和1的矩阵，求最大矩形面积 多个84题

96  n个节点二叉搜索数的个数    暴力超时，dp分解求解   卡特兰数

98 	验证二叉搜索树  中序遍历为上升序列，巧用pre保存前一个点   or  dfs

101 对称二叉树  dfs or bfs

102	二叉树层次遍历  需要知道层次，一次性处理一行

104 二叉树的最大深度 dfs

105	前序中序得到树		dfs

114 将树转为链表：右节点转为下一个节点  dfs    解法很巧妙，自己用的最朴素的返回链后头尾节点

121. 买卖股票的最佳时机 直接求

124. 二叉树中的最大路径和  注意dfs的返回值的含义！

128 最长连续序列  数组中的数值，连续的最长序列长度
	1.暴力：计算以每一个数为开头的长度n  2.优化：只计算区间起点的长度 3.并查集  4.dp

136 只出现一次的数字  异或

139. 单词拆分  给wordDict 拼出s，可重复使用
	1.暴力 超时  2.hash优化字符串比较+记忆化（存在重复 所以想到）  3.dp

142. 环形链表 II  并返回入环点

148. 排序链表 1.归并排序 logn空间  2.O1不会

152. 乘积最大子数组 dp

155. 最小栈 栈，但能获取到最小值

160. 相交链表 求相交点 1.hash 2.求多出来的长度 3.相互连接起来

169. 多数元素 删除不同的两个数 还是多数元素

198. 打家劫舍

200. 岛屿数量 DFS||BFS

206. 反转链表

207. 课程表 图是否有环  拓扑图 ||  DFS搜索看是否回来

208. 实现 Trie (前缀树) 

215. 数组中的第K个最大元素

221. 最大正方形  dp || 85. 直接用长方形来解答的，没用答案的正方形性质

235. 二叉搜索树的最近公共祖先  非搜索树236也可也解，递归，函数返回结果为是否包含p或q

238. 除自身以外数组的乘积  不用除法、On时间 On空间  前缀和

240. 搜索二维矩阵 II  在搜索矩阵中高效找一个数

279. 完全平方数  dp | 记忆化

283. 移动零

287. 寻找重复数 有一个数出现两次及以上  二分 | 位运算 | 快慢指针

297. 二叉树的序列化与反序列化 解析时删除元素

300. 最长递增子序列

301. 删除无效的括号  可能的方案？

309. 买卖股票的最佳时机含冷冻期  dp[i][3]

312*. 戳气球 区间dp 以区间最后一个气球为准

322. 零钱兑换  dp  见分类刷题-dp

337. 打家劫舍 III  树上 记忆化搜索  可以不要考虑两种情直接求

338. 比特位计数 dp

347. 前 K 个高频元素 堆

394. 字符串解码 递归

399. 除法求值 构建为图  List<List<Pair<Integer, Double>>> edges  最外层是点，存List<Pair>代表点的每条出边

406. 根据身高重建队列 贪心排序 + 暴力找位置 or  树状数组+二分 （想知道1~x区间和，同时也会增加1，二分找区间和>=k+1的地方  logn * logn）

416. 分割等和子集 选择一些数和等于sum/2 dp 注意顺序，数组在内部循环会导致错误（元素重复使用）  零钱兑换是需要重复使用

437. 路径总和 III 暴力  || 前缀和+hash

438. 找到字符串中所有字母异位词 双指针

448. 找到所有数组中消失的数字  交换到应该的位置 |  +n标记

494. 目标和 添加正负号和为target  dfs -> 记忆化 -> dp  || 转为数组中选取元素，之和等于 target 416.

538. 把二叉搜索树转换为累加树 反中序遍历

543. 二叉树的直径  二叉树任意两个点的最大距离 dfs  定义好dfs的返回值的意义！ 同 二叉树中的最大路径和

560. 和为 K 的子数组 数量  暴力 | 前缀和 + hash（不关心具体下标，只关心等于 k 的前缀和之差出现的次数c）  遍历右维护左

581. 最短无序连续子数组 将数组部分排序后有序 nlogn排序-二分  找规律技巧

617. 合并二叉树 dfs

621. 任务调度器 模拟题

647. 回文子串 中心点暴力

739 每日温度 下一个更大的温度 单调栈
1
2
3
4
5
6
7
24 两两交换链表节点  		递归
26 删除有序vector重复项     双指针	

172 阶层中零的个数
202 将一个数每一位求平方和，判断最后是否收敛到1  19->82->68->100->1  
	判断是否存在循环：快慢指针、hash
o

卡特兰数：n对括号正确匹配数目 (22)，n个节点二叉搜索树(96)，出栈次序，矩阵相乘
C0 = 0 Cn+1 = 2(2n+1) / (n+2) * Cn

$$
C0 = 0 ~~~~~~~~~
Cn+1=
\frac{2(2n+1)}{n+2}Cn
$$

分类刷题

doocs/leetcode: 😏 LeetCode solutions

0.找规律

1. 基础算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
在排序数组中查找元素的第一个和最后一个位置 - 二分查找
准时到达的列车最小时速 - 二分查找  		对速度进行二分
找到需要补充粉笔的学生编号 - 二分查找
可移除字符的最大数目 - 二分查找

排序数组 - 快速排序、归并排序

字符串相加 - 高精度加法
字符串相乘 - 高精度乘法

区域和检索 - 数组不可变 - 前缀和
二维区域和检索 - 矩阵不可变 - 二维前缀和
区间加法 - 前缀和、差分
用邮票贴满网格图 - 二维前缀和、二维差分


位 1 的个数 - 位运算、lowbit
合并区间 - 区间合并

枚举右，维护左

哈希表维护左边全部（找等值关系）, 或者单变量维护最值(买卖股票1) （找最值关系）

前缀和+维护左

二分

分享丨【题单】二分算法（二分答案/最小化最大值/最大化最小值/第K小） - 力扣（LeetCode）

2. 数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
设计链表 - 单链表、指针引用、数组实现
下一个更大元素 I - 单调栈
每日温度 - 单调栈
子数组的最小值之和 - 单调栈
最大宽度坡 - 单调栈
最多能完成排序的块 II - 单调栈   ×
子数组范围和 - 单调栈
子数组最小乘积的最大值 - 单调栈
滑动窗口最大值 - 单调队列
满足不等式的最大值 - 单调队列 ×
和至少为 K 的最短子数组 - 单调队列   尝试单调栈->无单调性？  前缀和+单调队列
带限制的子序列和 - 动态规划、单调队列优化
单词规律 II - 哈希表、回溯 ×
最短回文串 - 字符串哈希
回文对 - 字符串哈希
最长重复子串 - 字符串哈希、二分查找
不同的循环子字符串 - 字符串哈希

滑动窗口（双指针）

查找满足某要求的字串、子序列；解题时看到字串子序列：先考虑所有以i结尾的串，在考虑j的单调

（此外还有一种二分的解法 nlogn：每一个right结尾时，二分寻找left的最优）

基本思想：随着 i的增大，满足 某表达式 的j 值是单调的。

​ 1.我遍历了全部以i结尾的串。确保不遗漏
​ 2.暴力：j需要for一次 -> 如果以i结尾的j~i窗口是一个可行解，i往后移，j不能回头。该单调性可以优化掉O(n^2^)

步骤

  1. 左右指针ji控制窗口，遍历右指针i向右边移动，以获取所有的答案（理解为以i结尾的所有串）
  2. 目前ji是可行解
  3. 当前窗口i++，不是可行解或最优解（窗口大小,字符数量）
  4. j++，直到可行
  5. 更新res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 朴素 N^2
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (check(i, j)) {
            // 具体问题的逻辑 res = max(res, j-i+1)
        }
    }
}

// 双指针 N
for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;
    // 具体问题的逻辑 res = max(res, j-i+1)
}
基础：
  1. 长度最小且sum大于k的子数组：j~i以i结尾长度最小且大于k，j ~ i+1 一定大于但可能不是最短； 除了双指针还可以二分j
  2. 乘积小于 K 的子数组：有多少个子串乘积后严格小于k。j~i < k，j ~ i+1不一定<k, 但j一定要往后走
    1. 拓展：字串加减乘除(不能有负数:反例) 满足 大于小于某个值:长度最小且sum大于k的子数组
  3. 3097. 或值至少为 K 的最短子数组 II 将求和改成了或，需要记录每一位上的数量
  4. 无重复字符的最长子串：j~i以i结尾无重复且最长，j ~ i+1 不一定无重复，但j一定是往后移动缩小窗口，使得无重复
    1. 长度为 K 的无重复字符子串 的个数 多一个长度缩小
  5. 字符串的排列：s2是否存在的某个子串刚好包含s1全部字符 ；新加进来的不能多+直接长度判断是否满足
  6. 438. 找到字符串中所有字母异位词 同上，需要找出所有的
  7. **最小覆盖子串**：s中字串能包含t全部字符，且最小（可以多，所以不能用长度判断 要多一个need记录）。j~i覆盖且最小，j ~ i+1 覆盖但不一定最小，但j一定是往后移动缩小窗口，使得更小；用一个变量记录下一共要多少个字符、一个hash记录每个字符需要多少（也可也直接用长为26字母遍历check）
  8. 统计定界子数组的数目 满足最大为min 最小为max的子数组的数量
    1. 维护两个指针，i是以i结尾的子数组。
    2. 当i不越界时，数量关系取决于最后一个min 和 max的下标
    3. 当i越界时，两指针都跳到i+1
  9. 最大连续1的个数 III：最多存在k个0，求数组连续1的个数
相向：
  1. 167. 两数之和 II - 输入有序数组
  2. 15. 三数之和 三数和为0，并且去重 ； 排序去重 然后双指针（有序）找值，当然也可也hash维护找（空间消耗）
  3. 数组元素的目标和两个升序数组，求和为x的两个数组的下标
    • 一个i指针一直往大了走，说明窗口是变大的，那么j的移动方向就是使得窗口值变小
    • 因此推断i=0 -> n ; j=m-1 -> 0
      • if v(i,j)>x，j一直移动变小，直到满足<=x （v(i,j)>x，那么v(i+1,j)>x，不会遗漏）
      • 如果ij小于x，x变大，并且j
  4. 42. 接雨水 - 力扣（LeetCode）
  5. 11. 盛最多水的容器 - 力扣（LeetCode）
恰好型

恰好为k，拆分成>=k 以及 >=k+1

单调栈

  • 想知道每个元素前后第一个比它大(或小)的元素； 当新来元素很大时，前面比他小的都找到下一个更大了 于是出栈，所以栈中是一个递减的序列

  • pre ~ i ~ next时(两边只包含一个) i 都是最大，就可以知道所有子数组中，i 当了(k-i)(i-j)次老大

  • 经常要求所有子数组的个数或者子数组求和，需要注意越界问题

求下一个更大：暴力：每个元素都可能要遍历后面的所有；优化：维护一个栈，当目前元素比栈顶更大时，栈顶就找到了下一个更大。一直pop，最后栈顶是i的前一个更大

模板1：当前元素必须进栈，进栈后影响栈内元素 可以见https://leetcode.cn/problems/sum-of-subarray-ranges/
这里pre next 一个是严格一个不是，可以保证子数组不重不漏！ 如果都想要严格或者非严格就再求一次

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 0; i < nums.length; i++) {
    while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
        nextBig[stack.top()] = i; // 栈顶的下一个非严格大是i，出栈时记录   下面是严格大，去掉等号要反过来
        stack.pop();
    }
    preBig[i] = stack.isEmpty() ? -1 : stack.peek();  // 当前i的前一个严格大是栈顶
    stack.push(i);
}
// 不能忘了最后栈内的
while(!stack.isEmpty()){
    nextBig[stack.pop()] = n;
}

模板2：当前元素可能不进栈，进栈后会影响后面未进栈的。左边小的可以让后面大的都不进栈，相当于从右到左模板1的弹出过程,用的比较少，看题目具体情况（最大宽度坡）

1
2
3
4
5
for (int i = 0; i < n; i++) {
    if (stack.isEmpty() || nums[stack.peek() > nums[i]]) {
    	stack.push(i);
    }
}
  • 模板1从左到右和从右到左得到结果不一样
  • 从左到右模板2的结果和从右到左模板1并反序，栈内元素会一样

例题：

  1. 下一个更大元素 I

  2. 求所有子数组中最小值，并求和 907

    ​ 方法一: dp[i] 以i结尾的所有子数组，最小和：a[i]能影响到上一个比a[i]小数a[j] 单调栈，dp[i] = dp[j] + (i-j)*a[i] 如果这一步不dp记录下来，就会导致超时

    ​ 方法二：每个元素 nums[i] 作为最小值出现在了多少个子数组中：pre j、next k (k-i)(i-j)。单调栈！

    ​ 方法三：排序后，从最小数的下标开始 Arrays.sort(B, (i, j) -> ((Integer) A[i]).compareTo(A[j]));

  3. 最大宽度坡 满足 A[i] <= A[j] 的最大 j - i 值

    ​ 需要从左往右建立一个特殊的栈，小的元素会导致后面大的元素直接不进栈，建立后从右往左找规律求结果

  4. 最多能完成排序的块 II 排序子数组使得整体有序

    ​ 1、找规律 max nums[0:i-1] < min nums[i:n-1] 和单调栈无关

    ​ 2、和排序的对比字符数

    ​ 3、单调栈

  5. 子数组范围和

    ​ 求全部子数组(max-min)，并求和，同2，但多一个最pre nextMax。

  6. 子数组最小乘积的最大值

    ​ 求全部子数组中，min(a) * sum(a)最大的。mina 还是用单调栈，注意这里是越宽越好，所以pre next都用非严格的两次去求(单次同时求出非严格需要跳跃 代码)。（其实一个非严格一个严格也可以，因为第一个元素的nextBig会包裹相同元素，1111相当于以第一个1为代表）。

  7. 柱状图中最大的矩形 模板

单调队列

​ 为什么要引入队列？有的题目前后都要弹出！！元素满足单调性

理解：通过单调性来移出不优的元素，例如在“和至少为 K 的最短子数组”，对于每个点作为左节点j，如果来了一个新值j‘，并且更小，那么左边的旧值j就永远不需要看了；作为左节点j如果j~i满足条件，那么右边的j~i'就不用再看了

可以获取最值的队列 可以在队尾插入，队头取出；并且O1最大值

  1. 维护全局一个最大值，但该元素出队列后找不到下一个最大值 ×
  2. 维护有效最大值列表，使得最大出列后还能找到第二大：
    1. 有效的特点：当队尾来了一个很大的数，最大值列表中的小值都可以被忽略了，所以是一个递减的
    2. 队头也可也删除元素，当普通队列的元素和最大值队列队头相同时，最大值队列需要出队
  3. 类似题目：可以获取最小值的栈 同样是维护一个最小值列表

[滑动窗口最大值](https://github.com/doocs/leetcode/blob/main/solution/0200-0299/0239.Sliding Window Maximum/README.md)

​ 求滑动窗口的最大值，当新来元素很大时，前面比他小的都可以忽略了，所以窗口中是一个递减的序列，最大值就在peekLast （此外还可以维护一个优先队列（堆） O(logn)取出最值）

1
2
3
4
5
6
7
8
9
10
11
12
// 队尾超出窗口大小 pop
while(deque.peekLast().index<i-k+1){
    deque.pollLast();
}

// 队头出pop， 并且新元素入队
while(!deque.isEmpty() && deque.peekFirst().value<nums[i]){
    deque.pollFirst();
}
deque.addFirst(new Pair(nums[i], i));
// 根据队列最大值计算相关值
res[i] = deque.peekLast().value;

和至少为 K 的最短子数组 ：如果全是正数，那么用双指针可以把空间复杂度也降低到O1

  1. 使用前缀和的差来计算子数组的和；

  2. 使用一种数据结构，将当前前缀和i与最前面的前缀和j作差，如果满足>=k的条件，那么j在之后就可以不用看了。【因为即使后面也有满足条件的，长度也会更长，所以需要将j从前面弹出】；

  3. 第2步完成了之后，当前的i也要放入数据结构，那么如果数据结构中有前缀和j比前缀和i大，j也可以不用看了。【因为即使后面有满足条件的，与i作差肯定也满足条件，并且长度更短，所以需要将大于等于i的从后面弹出】。

    ​ 前面后面都要弹出，压入的元素满足单调性，所以使用单调队列。

    数组存在负数，所以不能用二分查找i结尾的起点在哪。

    第二次做：其实是找满足条件的j~i，不能暴力遍历就找规律：对于左起点j以及右终点i，如果j~i当前满足了，那j不需要再去找后面的i了；i以后作为左起点 对于左起点，如果当前比左边的数小，那么左边的数都不可能再作为左起点了

带限制的子序列和 求max ( sum[子序列] ) ， 且子序列中的最大下标间隔不能超过k

  1. dp[i] 代表以i结尾的子序列的最大和，保证不遗漏
  2. dp[i] = max(dp [i-k] ~ dp[i-1]) 如果遍历k的话，超时；分析目前是想得到前k个元素的最大值
  3. 维护一个窗口大小为k的单调队列！

树状数组

3.搜索

BFS：有很多结果，需要最优的，所以需要BFS同时尝试所有的，并且最先遇到的就是最优解
DFS：存在问题，只需要一个；把一种可能的情况尝试到底

BFS

BFS：状态转换 + 最短路/最小步数/最小操作；空间范围有限

  • 有一个全局的visit代表是否访问过，用来保证不走回头路，可以用距离(使用距离的话，入队的点就不用额外保存距离)
  • 入队时标记而不是出队时标记，防止同一个节点入队两次
  • 尽量只将有意义的节点入队，同时入队时判断结束条件最好：转化数字的最小运算数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
grid[n-1][m-1] = -1; // 入队时标记
deque.addLast(new int[]{n-1, m-1, 1});

while(!deque.isEmpty()){
    int[] tmp = deque.pollFirst();
    int x = tmp[0], y = tmp[1], dis = tmp[2];
    
    if(x==0&&y==0)return dis; // 出队时判断全集最优 结束搜索

    int []dx = {-1,0,1,0,-1,-1, 1, 1};
    int []dy = {0,1,0,-1,-1,1,1,-1};
    for(int i=0;i<8;i++){
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(xx>=0&&yy>=0&&xx<n&&yy<m&&grid[xx][yy]==0){ // 入队的条件
            grid[xx][yy] = -1; // 入队标记
            deque.addLast(new int[]{xx, yy, dis+1});
        }
    }
}
https://leetcode.cn/problems/shortest-path-in-a-grid-with-obstacles-elimination/submissions/505710677/

优化：双向DFS，可以节约百倍空间复杂度[模板](1091. 二进制矩阵中的最短路径 - 力扣（LeetCode）) 模板code

1+2+4+8+16+32+64+128+256+512 -> 1+2+4+8+16 + (相遇) 16+8+4+2+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
queue1、queue2 为两个方向的队列
dis1、dis2 为两个方向的距离数组，记录每个节点距离起点的

更新时优先更新小的，并且一次更新一层
二者相遇时即为结果

    while(!deque1.isEmpty() && !deque2.isEmpty()){
        int res=-1;
        // 优先扩展size小的 缩小搜索空间
        if(deque1.size()<deque2.size()){
            res = update(deque1, dis1, dis2);
        }else{
            res = update(deque2, dis2, dis1);
        }

        if(res!=-1)return res;
    }
    return-1

public int update(Deque<Integer> deque, int []dis, int []other){
        int num = deque.size();
        while(num-- != 0){
            int x = deque.pollFirst();

            // 相遇为终结
            if(other[x] != -1){
                return dis[x] + other[x];
            }
            for(int i=0;i<4;i++){
                // 具体业务
                if(...&&dis[now]==-1){
                	deque.addLast(now);
                }
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
图像渲染- BFS、DFS、Flood Fill 算法、连通性模型
岛屿数量 - BFS、DFS、Flood Fill 算法
01 矩阵 - 多源 BFS    					 注意只能多源BFS！！DFS实现失败   还可以dp，但没看
地图中的最高点 - 多源 BFS 和上面一模一样
进击的骑士 - BFS、最短路模型   			暴力或者双向BFS
二进制矩阵中的最短路径 - BFS、最短路模型     模板  如果入队没有标记而是出队标记 会超时
迷宫中离入口最近的出口 - BFS、最短路模型     模板

网格中的最短路径 - BFS、最短路模型           从左上到右下最短路，可以删除k个障碍；这里即便访问过，后来的也可也访问：入队额外记录剩余删除个数，如果比全局的更多（后来的距离一定更大，想要继续走就必须要剩余更多删除），就可以入队

打开转盘锁 - 最小步数模型、双向 BFS、A* IDA*  四位旋转到目标数  看上去题目复杂，但搜索空间只有1e5 直接暴力 dfs第一次遇到的是最优的，set去重。  双向BFS优化模板

单词接龙 - 最小步数模型、双向 BFS   同上 仔细分析搜索空间其实不是特别大  最多也就5k个词
转化数字的最小运算数 - 最小步数模型、双向 BFS
滑动谜题 - BFS、最小步数模型、A* 算法
访问所有节点的最短路径 - BFS、最小步数模型、A* 算法
为高尔夫比赛砍树 - BFS、A* 算法
使网格图至少有一条有效路径的最小代价 - 双端队列 BFS
到达角落需要移除障碍物的最小数目 - 双端队列 BFS

DFS

​ 进入时修改状态，回溯后改回状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 当前状态保存在传参中 now 和 idx
public boolean dfs(int []matchsticks, int target, int idx, int now, int start){
	// 结束条件
    if(idx == 4) return true;
    if(now == target) return dfs(matchsticks, target, idx+1, 0, 0);

    for(int i=start;i<matchsticks.length;i++){
        // 遍历选择列表 过滤不满足的
        if(i>start && matchsticks[i] == matchsticks[i-1]) continue;
        if(matchsticks[i]==-1)continue;
        if(matchsticks[i] + now > target) continue;
        
        // 修改选择状态 并加入下一次
        int t = matchsticks[i];
        matchsticks[i] = -1;
        // 存在类问题提前返回，如果是最优问题需要用最优值剪枝
        if (dfs(matchsticks, target, idx, now + t, i+1)){
            return true;
        }
        matchsticks[i] = t;
    }
    return false;
}

记忆化搜索： 自顶向下，并记录。可以改写dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
迷宫 - DFS、连通性模型、Flood Fill 算法
单词搜索 - DFS、搜索顺序、回溯
黄金矿工 - DFS、搜索顺序、回溯
火柴拼正方形 - DFS、回溯、剪枝 n=15          数组组合成一个正方形，暴力遍历 
	1.从组成边的角度出发：(2^n)^k used标记 在组成某一条边时，是组合问题而不是排列！所以需要起始idx
	2.从使用每一个数字出发： 每个数字可以放4个位置 4^n 剪枝：优先遍历大的数字，这样遍历空间更小 edge一样剪纸
	3.状态压缩 + 动态规划
	
划分为 k 个相等的子集 - DFS、回溯、剪枝  k<=16    同上, 数组从划分4个子数组改为k个
	1.从组成子集角度 n!   对于每一个子集，是组合问题，需要使用begin控制搜索
	2.从使用每一个数字：k^n   超时！  加上edge[i+1] == edge[i]优化可以过

公平分发饼干 - DFS、回溯、剪枝  n=k=8   数组划分为k个，求划分使得最小化：max(sum(子数组)) 同下
	1.无法从组成子集角度 
	2.分配每一个数字即可, n=8不需要剪枝

完成所有工作的最短时间 - DFS、回溯、剪枝  n=k=12   数组划分为k个，求划分使得最小化：max(sum(子数组))
	1.从分配每一个任务角度：k^n   超时！   剪枝：维护一个全局最优  降序排列
		剪枝：默认dfs第一次会把任务全给0号工人，其实是最差情况，我们希望分配平均一点
			 优化1：先用优先队列贪心求取出一个res，缩小dfs范围
			 优化2：edge[i+1] == edge[i]时 二者等价  直接跳过
			 优化3. 优先分配给未分配的工人（和2一样）; 因为未分配都一样，所以就分配给未分配的第一个人
		     			可以快速获得一个全局最优，并且去重。原来第一个任务分配给所有人，现在只给1
			 优化4. 对分配排序，每次取出最小的：问题1 直接排序下一层影响这一层，使用idx
								           问题2 每次都排序复杂度太高了，排序行不通
		     
	2. 状态压缩 dp
	3. 二分+转为存在问题
	
组合总和 组合出target  可重复使用，不考虑顺序   记录下list<>now 进入时add 回溯时remove
	全排列问题需要记录数字是否使用  used
	组合问题需要按照搜索顺序  使用begin  如果可重复begin下次还是i 不可重复i+1
	
	[40. 组合总和 II] 需要去重  set直接去重超时  改成排序后一次处理同一种数


	
	划分为k个相等的子集 问题的组成每个子集角度，整体需要used标记，单个子集是组合问题需要begin标记

矩阵中的最长递增路径 - DFS、记忆化搜索      模板
网格图中递增路径的数目 - DFS、记忆化搜索    模板  上面是最大长度，这里是求和
翻转游戏 II - DFS、状态压缩、记忆化搜索 你和朋友轮流将 连续 的两个 "++" 反转成 "--" 是否存在必胜
	代码特别优雅，使用位运算实现字符串的改变
	String nextState = state.substring(0, i) + "--" + state.substring(i + 2);
	
    // 优化
    if ((mask & (1 << i)) == 0 || (mask & (1 << (i + 1))) == 0) {
    	continue;
    }
    if (dfs(mask ^ (1 << i) ^ (1 << (i + 1)))) {
    	continue;
    }
    
    
统计所有可行路径 - DFS、记忆化搜索    
	模板，记录从 dp[i][fuel]  从 i并且有fuel燃料 到finish 有多少解法 sum dfs(j, fuel-cost(i->j))
	需要注意边界条件，如果i==finish，那么ans += 1 当前立即结束代表一种解法
	
	改写成dp！！！  fuel 有大小关系所以在外层，注意dp的初始化
	
切披萨的方案数 - DFS、记忆化搜索+二维前缀和

4.DP

dp有两种

分享丨【题单】动态规划（入门/背包/状态机/划分/区间/状压/数位/树形/数据结构优化） - 力扣（LeetCode）

  1. 01背包

  2. 完全背包

    • dp：

      • 从使用每一个物品出发，x个 dp[i][j] = 最优 dp[i-1][j-x * [w]] -> 优化为当前层取值 -> 优化为1维
      • 从组成的数出发，可重复使用的物品循环在内。 组合总和 Ⅳ ； 零钱兑换 完全平方数 dp只有一维（不考虑顺序可从完全背包出发， 但组合总数考虑了所有不可以）

    • 记忆化：

      1
      2
      3
      4
      5
      6
      7
      8
      从使用每一个物品出发  选了但idx不变
      dfs(idx-1, target);
      dfs(idx, target-coins[idx]);


      从组成的数出发
      for i in n:
      	dfs(target-nums[i]);

找到所有可能的解决方案一般要dfs 39. 组合总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
杨辉三角 - 线性 DP、数字三角形模型
最小路径和 - 线性 DP、数字三角形模型

摘樱桃 - 线性 DP、数字三角形模型  ×

摘樱桃 II - 线性 DP、数字三角形模型

最长递增子序列 - 线性 DP、最长上升子序列模型
	暴力：查找前面所有的
	优化：如果当前长度为5，并且结尾字符比以前的长度为5的结尾字符小，那么以前的就被忽略了，有点像单调栈
			所以每一个长度只需要保存一个结尾字符最小的就行了。
			长度越长结尾字符肯定越大，用二分查找哪一个长度的字符刚好比现在小

无重叠区间 - 线性 DP、最长上升子序列模型、贪心优化
	dp：以当前区间结尾的 无重复区间数，和上面一样可以用二分优化

删列造序 III - 线性 DP、最长上升子序列模型

俄罗斯套娃信封问题 - 线性 DP、最长上升子序列模型、贪心优化

堆叠长方体的最大高度 - 排序、线性 DP、最长上升子序列模型
无矛盾的最佳球队 - 排序、线性 DP、最长上升子序列模型


最长公共子序列 - 线性 DP、最长公共子序列模型
两个字符串的最小 ASCII 删除和 - 线性 DP、最长公共子序列模型
两个字符串的删除操作 - 线性 DP、最长公共子序列模型

目标和 - 0-1 背包问题
	数组前面添加+ 或 -， 最后凑出目标的方案数
	方法1：dp[i][j]  前i个数凑出j-1000的方案个数
			init: dp[0][1000] = 1; return dp[n][target+1000];
	方法2：负号和为x。sum - 2x = target。 数组中凑出(sum-target)/2的方案数
		   dp[i][j] 前i个数和为j的方案数(可以不选) 
		   	 init: dp[0][0] = 1;  return dp[n][target]
	方案3：dfs暴力 2^n^		   

		   
分割等和子集 - 0-1 背包问题  是否存在使得划分两个集合sum相等  计算方案会溢出

最后一块石头的重量 II - 0-1 背包问题  分成两堆 sum差值最小

零钱兑换 - 完全背包问题 给出零钱面值数组(可重复)，凑出target的最小数量
	1.完全背包 f[i][j] 前i种零钱凑出j
	2.普通背包问题 f[i] 凑出i的硬币数量。从n种状态种选出最优
	3.记忆化搜索 从上到下 定义什么时候终止 什么状态为求出来了 求出来中什么状态无解  同样有两种

组合总和 Ⅳ - 完全背包问题  数组中凑出target方案数  
	不考虑顺序是完全背包问题  
	考虑顺序为f[i]凑出i的方案数，从n种状态种选出最优


从栈中取出 K 个硬币的最大面值和 - 分组背包问题

数字 1 的个数 - 数位 DP、记忆化搜索

统计各位数字都不同的数字个数 - 数位 DP、记忆化搜索、状态压缩

不含连续 1 的非负整数 - 数位 DP、记忆化搜索

旋转数字 - 数位 DP、记忆化搜索
最大为 N 的数字组合 - 数位 DP、记忆化搜索
统计特殊整数 - 数位 DP、记忆化搜索

买卖股票的最佳时机 
	II  无限制次数 ，记忆化idx flag
	III IIII 限制次数，记忆化idx left flag，map记忆化比数组慢快10倍
	冷冻期 idx state(无 持有 冷冻)
1
2
139. 单词拆分 使用给定String[] 拼接出s，能不能拼接出来
2707. 字符串中的额外字符 同上，但目标是剩余字符最少  dp[i]: 0~i  暴力->trie || 字符串hash优化查找字符串

入门

网格

背包

01背包

一些物品 选或者不选；dp[i][j] = Math.max(dp[i][j], dp[i-1][j-nums[i-1]]); -> 优化为逆序1维

1
2
3
4
5
6
7
8
9
取或者不取
前idx个数，拼接出target // 也可也从0开始，dfs含义为idx~n-1个数的结果
dfs(nums, idx-1, target);
dfs(nums, idx-1, target-nums.get(idx));

递归终点 -1  
    方案数  有效 1  无效0
    最值 有效0 无效inf
    能否 有效1 无效0
完全背包
  • 从使用每一个物品出发，x个 dp[i][j] = 最优 dp[i-1][j-x * [w]] -> 优化为当前层取值 -> 优化为1维
  • 从组成的数出发，可重复使用的物品循环在内。

不考虑顺序，完全背包

  • 零钱兑换

    • 前i种零钱凑出j；

      1
      2
      3
      4
      记忆化，前idx个元素，凑出amount的最少数量

      dfs(coins, idx-1, amount);
      1 + dfs(coins, idx, amount-coins[idx]); // 选了但idx不变

    • 也可也从普通dp问题：f[i] 凑出i的硬币数量。从n种状态种选出最优

      1
      2
      3
      4
      for(int i=0;i<n;i++){
          t = Math.min(t, dfs(coins, amount - coins[i]));
      }
      t++;

  • 完全平方数

考虑顺序，从使用的最后一个数出发, 因为考虑顺序，不可以用完全背包解决

线性dp

相邻相关 最长上升子序列 需要多保存一个相邻关系（可以理解为状态）

dp[i][j] 为s[:i] 和t[:j] 的结果， 转移考虑最后一个i j

状态dp

题单刷

分享｜如何科学刷题？ - 力扣（LeetCode）

分享丨【题单】常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树） - 力扣（LeetCode）

其他

周赛补题

3097. 或值至少为 K 的最短子数组 II：长度最小且或后大于k的子数组；和求sum很相似

  • 暴力：以每一个i结尾，往前找left超时；双指针优化，但和求和不同，求和left移动直接减就行，这里需要记录下每一位1的个数
  • 还是暴力每一个结尾i，但以i结尾能筹出来的或最多32个，也就是i -> i+1的转换为O32的，而不是On的，这和求和不同

3098. 求出所有子序列的能量和：

  • 子序列
    • 相邻无关 01背包
    • 相邻相关 最长上升子序列 多一个相邻关系
  • 排序后，dfs -> 记忆化优化 50^5 但有一些系数的减小（变量有大小关系，相当于在求组合数，组合数下面有阶乘系数）
1
2
3
4
5
6
7
8
9
10
给你一个长度为 n < 50 的整数数组 nums 和一个 正 整数 k 。

一个子序列的 能量 定义为子序列中 任意 两个元素的差值绝对值的 最小值 。

请你返回 nums 中长度 等于 k 的 所有 子序列的 能量和 。

由于答案可能会很大，将答案对 109 + 7 取余 后返回。


dfs(idx, pre, minnow, lennow)  n * n * n^2 * k

100244. 带权图里旅途的最小代价: 图中两点距离为 & 值，求x y之间的最小距离，可以重复访问

  • and是越多越小，所以尽量访问x和y之间全部的边，因此一个连通块为一个结果
  • 并查集 or dfs
  • 初始化数组太大会超时，n或者只大max一点

3290. 最高乘法得分 - 力扣（LeetCode）

  • dp，注意溢出，key选择string可以，List作为key会超时

3291. 形成目标字符串需要的最少字符串数 I - 力扣（LeetCode）

  • 记忆化搜索 dfs(i)代表从i~n-1需要多少个字符，但由于每次需要尝试n次，n^2复杂度
  • 改成跳跃游戏；如何求每一个idx可以到达的最长长度？ 二分长度 + 字符串hash（字符串普通hash是On的，字符串hash是O1比较）

Q4. 单调数组对的数目 II：将数组nums[] 拆分成一个递增的 一个递减的

  • 经典子序列题，记忆化解决 可以从当前状态可以推出哪些，也可也从转移，转移才可以改写dp优化
  • 改写成dp后，前缀和优化

3307. 找出第 K 个字符 II - 力扣（LeetCode）

  • 拆分成子问题

非递归快排

用栈模拟递归保存排序区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static void quickSort_no_Recursion(int[] q){
        ArrayDeque<Integer> st = new ArrayDeque<Integer>();
        st.push(0);
        st.push(q.length-1);
        
        int l, r, x, i, j;
        while(st.size() != 0){
            
            r = st.pop();
            l = st.pop();
            if(l>=r) continue;
            
            x = q[(l + r) >> 1];
        
            i = l-1; j = r+1;
            while(i<j){
                i++; while(q[i] < x) i++;
                j--; while(q[j] > x) j--;
                if(i<j){
                    int t = q[i];
                    q[i] = q[j];
                    q[j] = t;
                }
            }
            
            st.push(l);
            st.push(j);
            
            st.push(j+1);
            st.push(r);
            
        }
    }

非递归中序

染色来标记是否是第一次遇到，先序可以不用染色

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<Node> deque = new ArrayDeque<Node>();

    deque.addLast(new Node(root, 0));

    while(deque.size() > 0){
        Node tmp = deque.pollLast();

        TreeNode r = tmp.root;
        int flag = tmp.flag;
        if(r == null)continue;

        if(flag == 0){
            deque.addLast(new Node(r.right, 0));
            deque.addLast(new Node(r, 1)); // 放最上面就是后续  最下面就是先序
            deque.addLast(new Node(r.left, 0));

        }else{
            res.add(r.val);
        }
    }
    return res;
}

补充

https://leetcode.cn/problems/climbing-stairs/solutions/286022/pa-lou-ti-by-leetcode-solution/: 矩阵快速幂

马拉车

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public String longestPalindrome(String s) {
        // 预处理字符串，插入特殊字符以便处理偶数长度回文
        StringBuilder sb = new StringBuilder();
        sb.append('#');
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i));
            sb.append('#');
        }
        // 转换后的字符串
        String str = sb.toString();
        int n = str.length();
        int[] p = new int[n]; // p[i]表示以i为中心的回文半径
        int center = 0, right = 0; // 当前最右的回文的中心和右边界
        int maxLen = 0; // 最大的回文长度
        int maxCenter = 0; // 最大回文中心
        
        for (int i = 0; i < n; i++) {
            // 如果i在当前最右回文的范围内，使用之前的对称性加速
            if (i < right) {
                p[i] = Math.min(right - i, p[2 * center - i]);
            }

            // 尝试扩展以i为中心的回文串
            while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && str.charAt(i - p[i] - 1) == str.charAt(i + p[i] + 1)) {
                p[i]++;
            }

            // 更新右边界和中心
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }

            // 更新最大回文长度和中心
            if (p[i] > maxLen) {
                maxLen = p[i];
                maxCenter = i;
            }
        }

        // 从原始字符串中提取最长回文子串
        int start = (maxCenter - maxLen) / 2; // 起始位置 (注意去掉#号)
        return s.substring(start, start + maxLen);
    }

操作

快读

1
2
3
4
5
6
7
8
9
10
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");

n = Integer.parseInt(line[0]);
m = Integer.parseInt(line[1]);


PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
out.println();
out.flush();

stringbuilder删除的时候，从后往前删防止影响，传入整数自动转为字符串

new Integer('0') 得到的是ASCII， char可以自动转integer，反过来不行 new Character((char) 48)

集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
set去重
Set<List<Integer>>  使用里面元素的equal  默认ArrayList 是一个一个对比 但int[]是比较地址

char加上一个int需要强转 char c = (char)('a' + j);


数组初始化，此外对应int，里面默认值为0，如果是object，还需要额外new  left[0][1] = new Person();
    int[][] left = new int[26][2];  // 26 行 2 列的二维数组
	System.out.println(left[0].length);  // 输出 2

    int[][] left = new int[26][]; // 锯齿数组
    System.out.println(left[0]);  // 输出 null，因为还没有为第 0 行分配列
    left[0] = new int[2];  // 手动为第 0 行分配 2 列
    left[1] = new int[3];  // 手动为第 1 行分配 3 列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
数组    .length  
String  .length()
List    .size()

int[][] arr = new int[3][]; // 3行的二维数组，但每行的列数不定  内存不连续


Arrays:
    sort(a);     // 对于非基本类 第二个参数可以传入比较方法，见 后面
	binarySearch(a, key);  binarySearch(a, start, end, key);   不包括end
		Collections.binarySearch(list, key);
	fill(a, value);
	a2 = copyOf(a1, a1.length);
	toString() // 打印
        
	Arrays.stream(a).sum();
	Arrays.stream(a).max().getAsInt();

	object[]转List： new ArrayList<>(Arrays.asList(ints))
        反过来 ints = list.toArray(new int[n][]) //这里是二维的 list中存放 <int[]> 带参方法 56.
	int[] 转List ：  
         Arrays.stream(a).boxed().collect(Collectors.toList());    //需要装箱
		integerList.stream().mapToInt(Integer::intValue).toArray();

隐式强转可以小转大，大转小需要显式并且不能溢出

    
java 包含声明和创建
    变量的声明通常在栈内存中完成
    创建通常为new在堆中完成，返回堆内存地址
    
Object[] arr:申明数组类型变量时，为其分配了（32位）引用空间 栈中，由于未赋值，因此并不指向任何对象
    
arr = new Object[10]  堆中创建一个长度为10的Object 类型数组对象(也是对象)，分配了10个连续的内存空间，各自占用（32位的）Object用空间，但现在默认指向null
    
arr[i] = new Object() 在堆中为 Object 类型的对象分配一段内存空间，将引用存储在arr[i]

排序

重写排序，Array.sorts(a) 排序数组同理。注意int不能重写，需要逆序就先排序再反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
ArrayList：
    方法一：直接传一个函数，原理还是下面 FunctionalInterface
    	    nums.sort( (x, y) -> x - y ); // integer
            nums.sort(persons, (p1, p2) -> p2.getAge() - p1.getAge());  // 方便 
		   nums.sort(intervals, (a, b) -> a[0] - b[0]);  // 数组
	方法二：传一个Comparator类对象，比较时调用Comparator.compare
            nums.sort(new Comparator<Person>() {
                @Override
                public int compare(Person o1, Person o2) {
                    return o1.getAge() - o2.getAge();
                }
            })
    方法三：类重写接口方法
        class MyClass implements Comparable<MyClass>{
			public int compareTo(MyClass other) {
                return Integer.compare(this.priority, other.priority);
            }
		}



或者对于List
Collections.sort(nums, new Comparator<Person>() {
    @Override
    public int compare(Person o1, Person o2) {
        return o1.getAge() - o2.getAge();
    }
});

stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
栈 底层数组，适合两端插入删除；LinkedList是链表
	new ArrayDeque<Integer>();  或 Stack
	.isEmpty() .peek() .pop() .push(num)
	
队列  在栈中pop push都是从First操作，因此我代码也在first加入，但严格来说队列是队尾插入
	.addFirst  .addLast
	.peekFirst .peekLast
	.pollFirst .pollLast
    
map 遍历 for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) map.forEach((key, value) -> sout)
    
优先队列 PriorityQueue<Integer> pq = new PriorityQueue<>(); // 自己的类同sort方法 默认小根堆
		// (a, b) -> a.getValue() - b.getValue() 小根堆
	pq.offer(3); add()
 	pq.peek();
	pq.poll();
1
2
3
4
5
6
7
8
9
10
static class console {
    public static <T> void log(T... input){
        StringBuilder sb = new StringBuilder();
        for (T i: input) {
            sb.append(i.toString());
            sb.append(' ');
        }
        System.out.println(sb.toString());
    }
}

重写hashmap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Node{
    TreeNode t;
    int state;

    public Node(TreeNode t, int state){
        this.t = t;
        this.state = state;
    }

    public boolean equals(Object o) {
        Node x = (Node) o;
        return t == x.t && state == x.state;
    }

    public int hashCode() {
        return Objects.hash(t, state);  // 使用 Objects.hash() 生成基于 t 和 state 的哈希值
    }
}

randomfile

1
2
3
4
5
6
7
8
9
10
randomAccess = new RandomAccessFile(filepath, "rw");
byte[] buffer = ...
randomAccess.seek(pageSize * pageNumber);
randomAccess.write(buffer);

randomAccess = new RandomAccessFile(filepath, "r");
byte[] buffer = new byte[pageSize]
randomAccess.seek(pageSize * pageNumber);
randomAccess.read(buffer);
return new HeapPage((HeapPageId) pid, buffer);