算法基础

Ray Lv1
  2025-03-13 19:04:19 2025-03-13 19:04:19 Created   2025-03-19 20:24:38 2025-03-19 20:24:38 Updated    7.3k Words  35 Mins  

1. 基础算法

快速排序—分治

时间复杂度：nlogn 期望是n/2

  1. 确定分界点：
    • 左边界
    • 右边界
    • 中点
    • 随机
  2. 调整区间(已选择一个点x)
    • 让<=x的数在x的左边,让>=x的数在x的右边
  3. 递归处理左右两段
  4. 代码实现

c++版本

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
#include<iostream>

using namespace std;

const int N = 1e6+10;

int n;
int q[N];
void quick_sort(int q[],int l,int r){
  if(l >= r) return;
  int x = q[l],i = l-1, j = r+1;//不能用q[r] 会有边界问题 递归死循环
  while( i < j){
    do i++;	while(q[i] < x);
    do j--;	while(q[j] > x);
    if (i < j) swap(q[i],q[j]);
  }
  quick_sort(q,l,j);
  quick_sort(q,j+1,r);
}
int main(){
  scanf("%d",&n);
  for (int i = 0;	i < n; i ++) scanf("%d",&q[i]);
  quick_sort(q,0,n-1);
  for	(int i = 0; i < n; i ++) printf("%d",q[i]);
  return 0;
}

java版本

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{
    
    static int N = 100010;
    static int[] q = new int[N];
    
    public static void main(String[] args)throws IOException{
      	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
      	String [] line = in.readLine().split(" ");
        for(int i = 0; i < n;i ++) q[i] = Integer.parseInt(line[i]);
        quick_sort(q,0,n-1);
        for(int i = 0; i < n;i ++) System.out.print(q[i] + " ");
    }
    public static void quick_sort(int[] q, int l, int r){
        if (l >= r ) return;
        int x = q[l], i = l - 1, j = r + 1;
        while( i < j ){
           do{
               i++;
           }while(q[i] < x);
           do{
               j--;
           }while(q[j] > x);
           if(i < j){
               int t = q[i];
               q[i] = q[j];
               q[j] = t;
           }
        }
        quick_sort(q, l, j);
        quick_sort(q, j+1, r);
    }
}

归并排序—分治

时间复杂度：nlogn

  1. 确定分界点：mid = (l+r)/2

  2. 递归排序左边和右边

  3. 归并—把有序的两个序列合二为一

  4. 代码实现

    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
    #include<iostream>

    using namespace std;

    const int N = 1000010;
    int n;
    int q[N];

    void merge_sort(int q[], int l, int r){
      if(l >= r)	return;
      int mid = l + r >> 1;
      
      merge_sort(q, l, mid),merge_sort(q, mid + 1,r);//递归这里排序的原理还是不太懂
      
      int k = 0,i = l,j = mid + 1;
      while(i <= mid && j <= r)
        if(q[i] <= q[j]) tmp[k++] = q[i++];
      	else tmp[k++] = q[j++];
      while (i <= mid) tmp[k++] = q[i++];
      while (j <= r)	tmp[k++] = q[j++];
      
      for (i = l,j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
    }
    int main(){
      scanf("%d",&n);
      for(int i = 0;i < n; i ++) scanf("%d",&q[i]);
      
      merge_sort(q, 0, n - 1);
      
      for(int i = 0; i < n;i ++) printf("%d",q[i]);
      
      return 0;            
    }

整数二分法（一定有解，需要处理边界）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//区间[l,r]被划分成[l,mid]和[mid+1,r]时使用
int bsearch_1(int l, int r){
  while(l < r){
    int mid = l + r >> 1;
    if (check(mid)) r = mid;//check()判断mid是否满足性质
    else l = mid +1;
  }
  return l;
}

//区间[l,r]被划分成[l,mid-1]和[mid,r]时使用
int bsearch_2(int l, int r){
  while(l < r){
    int mid = l + r + 1>> 1;
    if (check(mid)) l = mid;//check()判断mid是否满足性质 此处为一个表达式
    else r = mid -1 ;
  }
  return l;
}

浮点数二分法(不需要处理边界)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//此处开平方为例
#include<iostream>

using namespace std;

int main(){
  double x;
  cin >> x;
  
  double l = 0, r = x;
  while(r - l > 1e-8){
    double mid = (l + r) / 2;
    if (mid * mid >= x) r = mid;
    else l = mid;
  }
 	printf("%lf\n",l);
  return 0;
}

2. 数据结构

链表与邻接表

单链表（邻接表：存储图和树）

  • 数组模拟链表（开多个数组，代表val和next 用下标来进行关联 空节点用下标-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
    const int N = 100010;

    // head 表示头节点的下标
    // e[i] 表示节点i的值
    // ne[i] 表示节点i的next指针是多少
    // idx 存储当前已经用到了哪个点
    int head,e[N],ne[N],idx;

    //初始化
    void init(){
      head = - 1;
      idx = 0;
    }

    //将x插到头节点
    void add_to_head(int x){
      e[idx] = x, ne[idx] = head, head = idx ++;
    }

    //将x插到下标是k的点后面
    void add(int k, int x){
    	e[idx] = x;
      ne[idx] = ne[k];
      ne[k] = idx;
      idx ++;
    }

    //将下标是k的点后面的点删掉
    void remove(int k){
      ne[k] = ne[ne[k]];
    }

双链表（优化某些问题）

  • 让下标是0为链表的头节点 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
    const int N = 100010;

    int e[N],l[N],r[N],idx;

    //初始化
    void init(){
      // 0表示左端点，1表示右端点
      r[0] = 1, l[1] = 0;
      idx = 2;
    }

    //在下标是k的点的右边插入x
    void add(int k, int x){
    	e[idx] = x;
      r[idx] = r[k];
      l[idx] = k;
      l[r[k]] = idx;
      r[k] = idx;
    }

    //在左边插入l[k]

    //删除第k个点
    void remove(int k){
    	r[l[k]] = r[k];
      l[r[k]] = l[k];
    }

  • 邻接表 （单链表 头节点成数组）

栈与队列

栈 先进后出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int N = 100010;
int stk[N],tt;

//插入
stk[++tt] = x;

//弹出
tt --;
//判断栈是否为空
if(tt > 0) not empty
  else empty
    
//栈顶
stk[tt];

队列 先进先出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int N = 100010;

//在队尾插入元素,在队头弹出元素
int q[N],hh,tt = -1;

//插入
q[++ tt] = x;

//弹出
hh ++;

//判断队列是否为空
if(hh <= tt) not empty
else empty

//取出队头元素
q[hh]

单调栈

给一个序列 求序列中每个数左边离它最近的数在什么地方

通常我们会使用暴力来解 再考虑优化

1
2
3
4
5
6
7
8
9
10
//暴力
//假定为求比 q[i] 小的数且离 q[i] 最近的数 q[j]
for(int i = 0; i < n; i ++ ){//枚举每一个数
  for(int j = i - 1; j >= 0; j -- ){//从i的左边开始往左边枚举
  	if(q[i] > q[j]){
    	cout<<q[j]<<endl;
      break;
    }  
  }
}

如果考虑用栈来存储这个序列 考虑栈顶的元素 每次入栈的时候和栈顶比较如果栈顶大于要插入的元素 此时栈顶的元素出栈 最后插入入栈的元素

1
2
3
4
5
6
7
8
9
10
int n;
cin >> n;
for(int i = 0; i < n; i ++ ){
  int x;
  scanf("%d",&x);
 	while(tt && stk[tt] >= x) tt --;
  if(tt) printf("%d",stk[tt]);
  else printf("-1");
  stk[++tt] = x;
}

单调队列

用数组模拟的栈和队列 比stl快一些

求滑动窗口里的最大值或者最小值 例题：滑动窗口

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
#include <iostream>

using namespace std;

const int N = 1000010;

int n,k;
int a[N],q[N];//此处的q[N]存的是队列的下标

int main(){
  scanf("%d%d",&n,&k);
  for(int i = 0; i < n; i ++ ) scanf("%d",&a[i]);
  
  int hh = 0, tt = -1;
  for(int i = 0; i < n; i ++ ){
    //判断队头是否滑出窗口
    if(hh <= tt && i - k + 1 > q[hh]) hh ++;   //不止一次的时候要写while
    while(hh <= tt && a[q[hh]] >= a[i]) tt --;
    q[++tt] = i;
    if(i >= k - 1) printf("%d ",a[q[hh]]);
  }
  puts("");
  
  hh = 0, tt = -1;
  for(int i = 0; i < n; i ++ ){
    //判断队头是否滑出窗口
    if(hh <= tt && i - k + 1 > q[hh]) hh ++;
    while(hh <= tt && a[q[hh]] <= a[i]) tt --;
    q[++tt] = i;
    if(i >= k - 1) printf("%d ",a[q[hh]]);
  }
  puts("");
}

kmp

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
#include <iostream>

using namespace std;
//画图辅助理解
int n,m;
char p[N],s[N];
int ne[N];

int main(){
	cin >> n >> p + 1 >> m >> s + 1;
  
  //求next的过程
  for(int i = 2, j = 0; i <= n; i ++ ){
    while(j && p[i] != p[j+1]) j = ne[j];
    if(s[i] == p[j+1]) j++;
    ne[i] = j;
  }
  //kmp匹配过程
  for(int i = 1, j = 0; i <= m; i ++ ){
     while(j && p[i] != p[j+1]) j = ne[j];
   	 if(s[i] == p[j+1]) j++;
     if(j == n){
       printf("%d",i - n);
       j = ne[j];
     } 
  }
}

求next数组：

image-20231016171349040

j为模式串子串的长度

image-20231016171506180

Trie树

高效存储和查找字符串的数据结构

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
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
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] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

最大异或对

并查集

1 将两个集合合并 2 询问两个元素是否在一个集合当中 近乎O(1)

基本原理：每个集合用一颗树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点

如何判断树根：if (p[x] == x)

如何求x的集合编号：while(p[x] != x) x = p[x]

如何合并两个集合：px是x的集合编号 py是y的集合编号 p[x] = y

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
(1)朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点 + 路径压缩
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);


(2)维护size的并查集：

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);


(3)维护到祖宗节点距离的并查集：

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量


堆

插入一个数

求集合当中的最小值

删除最小值

删除任意一个元素

修改任意一个元素

完全二叉树 一维数组

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
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

Hash表

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
(1) 拉链法
    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一个数
    void insert(int x)
    {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }

    // 在哈希表中查询某个数是否存在
    bool find(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;
    }

(2) 开放寻址法
    int h[N];

    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }

c++与stl使用技巧

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
vector, 变长数组，倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序

pair<int, int>
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string，字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串
    c_str()  返回字符串所在字符数组的起始地址

queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素

priority_queue, 优先队列，默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

deque, 双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)

    set/multiset
        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反

3. 搜索与图论

深度优先搜索 DFS stack 空间O(h) 不具有最短性

  • 回溯
  • 剪枝

842. 排列数字

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
//842. 排列数字

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 10;

int path[N];
bool st[N];
int n;

void dfs(int u){
    if (n == u){//递归到最后一个位置 此时每个位置上都有了数 输出所有数
        for(int i = 0; i < n; i ++ ) printf("%d ",path[i]);
        puts("");
        return;
    }
    for(int i = 1; i <= n; i ++ ){//此处枚举了1-n个数 判断每个数是否被使用过 
        if(!st[i]){//如果没有被使用
            path[u] = i;//把这个值赋给path[u]
            st[i] = true;//并将其状态设为使用 在下面递归的时候就不会再使用这个数
            dfs(u + 1);
            st[i] = false;//递归回溯后 恢复原来的状态 进行其他分支的递归
        }
        
    }
    
}
int main(){
    cin >> n;
    dfs(0);
    return 0;
}

843. n皇后

image-20231018084205460 
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
import java.util.Scanner;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;

class Main{
    final static int N = 20;
    static int n = 0;
    static char[][] g = new char[N][N];
    static boolean [] col = new boolean[N];
    static boolean [] dg = new boolean[N];
    static boolean [] udg = new boolean[N];
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
  
  
	public static void main(String[] args)throws Exception{
	
        Scanner sc = new Scanner(System.in);
    	  n = sc.nextInt();
        for(int i = 0; i < n; i++)
	        for(int j = 0; j < n; j ++)
	            g[i][j] = '.';
	            
        dfs(0);
        writer.flush();
    
    }  
    public static void dfs(int u)throws Exception{
        if(u == n){
            for(int i = 0; i < n; i++){
	            for(int j = 0; j < n; j ++){
	                  writer.write(g[i][j]);
	                  if(j == n - 1) writer.write("\n");
	                  if(i == n - 1 && j == n - 1) writer.write("\n");
	            }
            }      
        }
        for(int i  = 0; i < n; i ++ ){
            if(col[i] == false && dg[u+i] == false && udg[n-u+i] == false){
                g[u][i] = 'Q';
                col[i] = dg[u+i] = udg[n-u+i] = true;
                dfs(u+1);
                g[u][i] = '.';
                col[i] = dg[u+i] = udg[n-u+i] = false;
            }
        }
    }
}
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

//对行进行递归 对列进行遍历
//如何保证不在一条线上，那就是依靠截距来判断，当截距相同的时候才是在同一条线上
// i为列号 列号即为y | y = -x + b  b = i + u 
// u为行号 行号就是x | x = y - b  b = i - u b 可能为负数需要偏移量n 即 b = u - i + n  当加了n之后其实u和i谁减谁都一样了
//⚠️坐标系顺时针旋转了90度
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 20;
char g[N][N];
bool col[N],dg[N],udg[N];
int n;
void dfs(int u){
    if( u == n ){
        for(int i = 0; i < n; i ++){
            puts(g[i]);
        }
        puts("");
        return;
    }
    for (int i = 0; i < n; i ++ ){
        if(!col[i] && !dg[u+i] && !udg[n-u+i]){
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = false; 
            g[u][i] = '.';
        }
        
    }
    
}
int main(){
    cin >> n;
    for(int i = 0; i < n; i ++ ){
        for(int j = 0; j < n; j ++ ){
            g[i][j] = '.';
        }
        
    }
    dfs(0);
    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
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
#include<iostream>
using namespace std;
const int N = 10;
int st[N],used[N];
int n ;

//判断函数，因为使用了used记录，所以一定不会在同一列，只需要判断对角线
/*
这里用到了数学知识(abs((u - i)) == abs(st[u] - st[i]))，大家画个图一看就明白了

比如st为{1,3,2,4}，列为1,2,3,4
第3列 减 第 2 列 为 3 - 2 = 1
st[3] - st[1] = 2 - 3 = -1  = abs = 1
所以在同一对角线
*/
bool valid(int u)
{
    for (int i = 1; i < u; i++)
    {
        if ((abs((u - i)) == abs(st[u] - st[i])))
            return false;
    }
    return true;
}

//dfs模板
void dfs(int u){
    //结束条件，按st里的数字决定是Q还是.
    if(u > n){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(j == st[i])
                    cout << 'Q';
                    else{
                    cout << '.';
                    }
            }
            puts("");
        }
        puts("");//答案之间有一个空行
        return ;
    }

    for(int i = 1; i <= n; i++){
        if(used[i] == 0 ){
            st[u] = i;
            if(!valid(u)) {
                st[u] = 0;
                continue;//如果当前数字不行，则跳过该数字，且不用改变used
            }
            used[i] = 1;
            dfs(u + 1);
            used[i] = 0;
            st[u] = 0;
        }
    }
}
int main()
{
    cin >> n;
    dfs(1);
    return 0;
}

宽度优先搜索 BFS queue 空间(2^h^). “最短路”

不是所有的最短路都可以用BFS 当所有边权重相同

844. 走迷宫

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
#include <cstring>
#include <iostream> 
#include <algorithm>

using namespace std;
typedef pair<int,int> PII;
const int N = 110;

int n,m;
int g[N][N]; // 建立直角坐标系，与数学里常用的不同，y轴是垂直向下的
int d[N][N];

PII q[N*N]; // 这是一个模拟队列 N*N表示最长的长度 保证在存储点位的时候不会越界

int bfs(){
    int hh = 0, tt = 0;
    q[0] = {0,0}; //当初的队列头位置是从(0,0)开始
    
    memset(d, -1, sizeof d);
    
    d[0][0] = 0; // -1 表示未走过的路径，0表示已经走过
    
    int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1}; // 定义四个方向的位置偏移量 (左、下、右、上)

    while(hh <= tt){ // 当队列不空
        auto t = q[hh ++]; // 出队先进入的位置点
        for (int i = 0; i < 4; i ++ ){
            int x = t.first + dx[i],y = t.second + dy[i];  // 位置偏移过后 得到了新的坐标
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1 ) {
                // d[x][y]等于-1意味着是第一次走到也就是最短距离，如果是1说明已经走过，不是最短路径
                d[x][y] = d[t.first][t.second] + 1; // 累计移动次数 
                q[++tt] = {x,y};
            }
        }
        
    }
    return d[n-1][m-1];
}
int main(){
    
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            cin >> g[i][j];
    
    cout << bfs() << endl;
    return 0;
}

树与图的存储

树是一种特殊的图 树是无环连通图

  • 有向图 a->b
  • 无向图 a-b <=> a->b b->a

重边：有两条边 自环：一条边自己指向自己

入度：前面的比后面的小是入度

出度：后面的比前面的大是出度

存储：

  • 邻接矩阵

  • 邻接表 （链表数组）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
    int h[N], e[N], ne[N], idx;

    // 添加一条边a->b
    void add(int a, int b)
    {
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
    }

    // 初始化
    idx = 0;
    memset(h, -1, sizeof h);

图的深度优先遍历

1
2
3
4
5
6
7
8
9
10
int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

图的宽度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

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

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

图的宽搜的应用—拓扑排序—有向图

一个有向无环图 至少存在一个入度为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
bool topsort()
{
    int hh = 0, tt = -1;

    // d[i] 存储点i的入度
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}

树与图的深度优先遍历

树与图的宽度优先遍历

拓扑排序

4. 数学知识

1. 数论

1.1 质数

概念

在大于1大整数中，如果只包含1和本身这两个约数，就被称为质数或素数

质数的判定 - 试除法(从定义出发). 

1
2
3
4
5
6
7
// 时间复杂度O(n)
bool is_prime(int n){
  if( n < 2 ) return false;
  for (int i = 2; i< n; i ++ )
    if(n % i == 0) return false;
  return true;
}
1
2
3
4
5
6
7
8
9
10
11
// 时间复杂度O(sqrt(n))
bool is_prime(int n){
  if( n <  2 ) return false;
  for ( int i = 2; i <= n / i; i ++ )
    if (n % i == 0) return false;
  return true;
}
/**
	可能会出现的几种情况，例如： i <= n / i  可能被替换成 i <= sqrt(n) 这个函数会比较慢
	i * i < n  当n接近于int的范围的时候， i * i 会超出 int的范围 会有溢出风险，变成负数 出现死循环
/

分解质因数— 试除法

质因数（素因数或质因子）在数论里是指能整除给定正整数的质数。除了1以外，两个没有其他共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。

合数是指在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。与之相对的是质数，而1既不属于质数也不属于合数。最小的合数是4。其中，完全数与相亲数是以它为基础的。

约数，又称因数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 易证n 最多只有一个大于sqrt(n)的质因子 
// 时间复杂度 O(sqrt(n)) 最好是logn 最坏是根号n
void divide(int n){
  for ( int i = 2; i <= n / i; i ++ ){
    if ( n % i == 0 ){
      int s = 0;
      while (n % i == 0){
        n /= i;
        s ++;
      }
      printf("%d %d\n", i, s);
    }
  }
  // 执行到就是最后一个数了，如果它大于1，就是
  if( n > 1 ) printf("%d %d", n, 1);
  puts("");
}

筛质数

1
2
3
4
5
6
7
8
9
10
11
12
13
const int N = 1000010;

int primes[N], cnt;
bool st[N];

void get_primes( int n ){
  for ( int i = 2; i <= n; i ++ ){
    if (!st[i]){
      primes[ cnt++ ] = n ;
    }
    for ( int j = i + i; j <= n; j += i) st[j] = true;
  }
}

埃及数学家发明定理：埃式筛法 O(nloglogn)

image-20231023193243236 
1
2
3
4
5
6
7
8
void get_primes( int n ){
  for ( int i = 2; i <= n; i ++ ){
    if (!st[i]){ // 如果是质数
      primes[ cnt++ ] = n;
      for ( int j = i + i; j <= n; j += i) st[j] = true;
    }
  }
}

线性筛法 （用质数去筛）

1
2
3
4
5
6
7
8
9
void get_primes(int n){
  for (int i = 2; i <= n / i; i ++ ){
    if(!st[i]) primes[cnt++] = i;
    for(int j = 0; primes[j] <= n / i; j ++ ){
    	st[primes[j]*i] = true;
    	if( i % primes[j] == 0) break;
  	}
  }
}

2. 组合计数

3.高斯消元

4. 简单博弈论

5. 动态规划

背包问题：

0 1 背包

在前i个物品中选择 每个物品只可以被选择一次 在不超过背包体积的情况下 最大价值是多少

朴素：

  • 状态表示 两个维度 用f[i,j]表示

    • 集合

      1 符合条件（ 只从前i个物品中挑选，总体积 <= j ）

      2 所有集合

    • 属性 max min 个数 通常f[i,j]所表示的值就是属性

  • 状态计算 状态转移方程

    集合划分

    不包含i f [ i - 1, j ]

    包含i f[ i - 1, j - $v_{i}$ ] + $w_{i}$

    最终 f [ i , j ] = Max（ f [ i - 1, j ] , f [ i - 1, j - $v_{i}$ ] + $w_{i}$ ）

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    using namespace std;

    const int N = 1010;

    int n,m;//输入 有多少个物品 和 多少体积
    int v[N],w[N];//体积 和 价值
    int f[N][N];

    int main(){
      cin >> n >> m;
      for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
      for(int i = 1; i <= n; i ++ ){
        for(int j = 0; j <= m; j ++ ){
          f[i][j] = f[i - 1][j];
          if( j >= v[i] ) f[i][j] = max(f[i][j] , f[i - 1][j - v[i]] + w[i]);
        }
      }
      cout << f[n][m] << endl;
      return 0;
    }

优化：

​ 关于 f [i] [j] 只使用到了 i - 1,考虑在此处优化 使用滚动数组 f[j] 且f[i] [j]由前一层更新过来 所以必须倒序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

int n,m;//输入 有多少个物品 和 多少体积
int v[N],w[N];//体积 和 价值
int f[N];

int main(){
  cin >> n >> m;
  for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
  for(int i = 1; i <= n; i ++ ){
    for(int j = m; j >= v[i]; j -- ){
      f[j] = max(f[j],f[j - v[i]] + w[i]);
    }
  }
  cout << f[m] << endl;
  return 0;
}

完全背包

从前i个物品中选择 每个物品可被选择无限次 在不超过背包体积的情况下 最大价值是多少

朴素写法
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
import java.util.Scanner;

class Main{
    static int []v;
    static int []w;
    static int [][]f;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        f = new int[n+1][m+1];
        v = new int[n+1];
        w = new int[n+1];
        for(int i = 1; i <= n; i ++ ){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        for(int i = 1; i <= n; i ++ ){
            for(int j = 0; j <= m; j ++ ){
                for(int k = 0; k * v[i] <= j; k ++ ){
                    f[i][j] = Math.max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
                }
            }
        }
        System.out.println(f[n][m]);
    }
}
优化过程

观察第三层循环的内部关系

可以观察到递推关系 f[i] [j]=max(f[i,j-v]+w , f[ i- 1 ] [ j ]) 

1
2
3
4
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w ,  f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max(            f[i-1,j-v]   ,  f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
由上两式，可得出如下递推关系： 
                        f[i][j]=max(f[i,j-v]+w , f[i-1][j])

去掉第三层循环后

1
2
3
4
5
6
7
for(int i = 1 ; i <=n ;i++)
for(int j = 0 ; j <=m ;j++)
{
    f[i][j] = f[i-1][j]; //与前一层的一样 重复可不更新
    if(j-v[i]>=0)
        f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}

则01背包问题与完全背包问题的代码区别如下

1
2
3
f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包

f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题

由于f[i] [j] 都是从第i层更新 所以是从小到大枚举 和01背包问题不一样

优化后的代码

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
import java.util.Scanner;

class Main{
    static int []v;
    static int []w;
    static int []f;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        f = new int[m+1];
        v = new int[n+1];
        w = new int[n+1];
        for(int i = 1; i <= n; i ++ ){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        for(int i = 1; i <= n; i ++ ){
            for(int j = v[i]; j <= m; j ++ ){
                f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
                
            }
        }
        System.out.println(f[m]);
    }
}

多重背包

在前i个物品中选择，每个物品最多可以选择s次 在不超过背包体积的情况下 最大价值是多少

分组背包

6. 贪心

心得

考虑多种边界情况可以检查自己的代码是否有误区

关于递归的思想理解

在提交前注意数据范围

  • Title: 算法基础
  • Author: Ray
  • Created at : 2025-03-13 19:04:19
  • Updated at : 2025-03-19 20:24:38
  • Link: http://rayhub.blog/2025/03/13/算法基础/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
算法基础
  1. 1. 基础算法
    1. 快速排序—分治
    2. 归并排序—分治
    3. 整数二分法（一定有解，需要处理边界）
    4. 浮点数二分法(不需要处理边界)
  2. 2. 数据结构
    1. 链表与邻接表
    2. 栈与队列
    3. kmp
    4. Trie树
    5. 并查集
    6. 堆
    7. Hash表
    8. c++与stl使用技巧
  3. 3. 搜索与图论
    1. 深度优先搜索 DFS stack 空间O(h) 不具有最短性
    2. 宽度优先搜索 BFS queue 空间(2^h^). “最短路”
    3. 树与图的存储
    4. 树与图的深度优先遍历
    5. 树与图的宽度优先遍历
    6. 拓扑排序
  4. 4. 数学知识
    1. 1. 数论
    2. 2. 组合计数
    3. 3.高斯消元
    4. 4. 简单博弈论
  5. 5. 动态规划
    1. 背包问题：
  6. 6. 贪心
  7. 心得