数据结构算法笔试

如何备考数据结构大题

  • 数据结构的小题最好的复习方法是把王道书的课后习题二刷
  • 多做题少听课
  • 主动发现自己不足的地方，去查缺补漏而不是遍历课本

大题的题型

  • 应用题侧重于算法的逻辑而不是算法代码的实现
  • 大纲里面应用相关即大题要考的考点
  • 应用题备考思路：
    • 画数据结构和算法运行过程
    • 训练数据结构定义的简单代码
    • 基本操作的简单代码

八大考点

①线性表的应用

②栈的应用

③队列的应用

④数组的应用

⑤树与二叉树的应用

  • 二叉树基本考的就是哈夫曼树和哈夫曼编码，并查集及其应用。其他的题型通常是定义数据结构或者实现基本操作

⑥图的基本应用

  • 比较基本的应用
  • 应用题一般不用写代码但是要手算，能够懂这些算法运行的逻辑
最小（代价）生成树
  • 最小生成树考察的是一个图中包含多个点的总路线代价最短
    • 而单源最短路径只考虑两点之间最短距离的路径
最短路径
拓扑排序
关键路径
其他
  • 数据结构定义
  • 画图

⑦查找算法的分析及应用

  • 二叉搜索树、平衡二叉树和红黑树可能和树与二叉树考点进行比较深度的结合

    • 比如给出一个关键字序列，从一个空的二叉树开始插入这些关键字，然后画出插入以后的平衡二叉树的形态，同时给出这个平衡二叉树的数据结构定义
    • 大概率应用题而不是代码
    • 尤其是平衡二叉树和红黑树

  • 散列（哈希）表

    • 大概率应用题而不是代码

  • B树及其基本操作

    • 不太可能在应用题当中考察，只考基本概念，不用管基本操作，b树小题里面一般可能考

  • 分块查找

    • 应用题

  • 字符串模式匹配

    • 大概率应用题而不是代码

  • 查找算法的性能分析，分析平均查找长度，成功的ASL和失败的ASL

⑧排序算法的分析及应用

  • 希尔排序
    • 更容易考小题而不是应用题
  • 堆排序
  • 基数排序
  • 外部排序

七大考法

①画图作答

  • （1）画数据结构的状态示意图
    • 重中之重
    • 一般是考察比较复杂的数据结构的图示

②代码作答

  • （1）写数据结构定义、基本操作代码
    • 简单的代码
    • 基本操作/功能的代码片段，比如判断队空或者插入
    • 比较复杂的数据结构不会考很复杂的算法题，但可能考数据结构的代码定义以及基本操作的代码实现

③文字简答

  • （1）手算分析算法运行过程/结果
  • （2）数据结构、算法的选择
    • 基于应用场景选择一种合适的数据结构
    • 基于应用场景选择一种性能比较好的算法
  • （3）算法性质分析
    • 分析算法的时间复杂度和空间复杂度
      • 所有算法都有可能考
    • 查找算法
      • 分析平均查找长度
      • 成功ASL和失败ASL
    • 排序算法
      • 分析关键字的对比次数
        • 某一趟排序当中关键字的对比次数是多少
        • 排完序关键字的总对比次数是多少
      • 稳定性
  • （4）文字描述算法思想/过程
    • 可以通过示意图去解释算法的运行过程，用文字描述也可以解和画图去做
    • 将画数据结构的状态示意图和手算分析算法运行过程/结果结合起来，从这两个角度去把各个算法的运行过程和数据结构的示意图捋清楚
  • （5）数据结构性质推演
    • 树和图的性质推演
      • 主要根据王道书的课后小题来复习

应用题

  • 先找到题目中的线索，然后遍历一下这类问题的做法

排序类应用题

  • 插入类排序：直接插入排序、折半插入排序、希尔排序
    • 能够保证相对升序的序列（有可能是跳跃的，也有可能是前面的i+1个
  • 选择类排序：简单选择排序、堆排序
    • 堆排序：（大根堆）每次选择堆顶元素放在最后（和堆底元素交换），每次将最大的元素放在最后面
      • 第一趟排序是先顺序存进一个二叉树，调整成为一个大根堆，再把它那个最大的元素换到最后面，再次调整为大根堆的结果
    • 每次都有一个元素被放在最终位置
  • 交换类排序：冒泡排序、快速排序
    • 每次根据逆序对进行交换
    • 快速排序：
      • 枢值一般选取序列的第一个元素
  • 不稳定排序算法的特点
    • 对于一种排序算法，我们要交换前两个位置的时候，如果它看不到前面有一个和他相同的元素，就有可能出现不稳定

查找类应用题

  • 折半查找
    • 元素有序，顺序表
  • 散列查找查找失败的情况
    • 线性探测法，查找到空位的时候说明查找失败，比较空的数组元素会计入一次比较次数
    • 链地址法，比较到一个空指针的位置才是查找失败，但是该比较空指针不会算进比较次数
    • 装填因子在链地址法中可以大于1，但是存储效率一定是小于等于100%的
    • 查找成功的时候分母是元素数量，查找失败的时候分母是取模后面的那个数字（因为无法映射到其他更大的数字）

  • 链式存储，考虑二叉搜索树
  • 顺序存储，顺序查找和折半查找（注意排序）比较常见

树类应用题

图类应用题

线性表类应用题

算法题

  • 算法题
    • 一题多解，分数高中低三档
    • 可以先写第二小问再写第一小问
    • 顺序表和链表一般情况下要考察时间复杂度
    • 树和图一般不考时间复杂度和空间复杂度，分析要求低一点，但依旧要记得
      • 树和图能解决问题比高效解决问题最重要，只要能解决问题笨方法也可以，只要能掌握常规代码即可
  • 备考方法
    • 阶段一：完成历年真题
    • 阶段二：分模块训练
    • 阶段三：少食多餐，增加做题量
    • 阶段四：考前保持手感，再刷历年真题

排序

顺序表

  • 快排和堆排是所有排序算法中效率最高的，但是快排代码简单，堆排代码复杂，所以快排最优

  • 考试按照时间复杂度给分

    • 通常来说，408算法题不会限制具体使用哪种算法
    • 408算法题通常按照复杂度给分，复杂度越低，给分越高
    • 若题目没有特别要求，答题时回答“平均复杂度”即可

  • 套路型算法：

    • 快速排序
      • 能快排就快排，不能用快排的再考虑用其他排序
      • 快排只能在顺序表和数组（静态链表）中使用，链表当中不能用快排，因此当涉及顺序表（数组）的题目，考虑能否使用到快速排序。
      • 如果题目中给的是一个乱序数组的话，如果把这个乱序数组变成有序，我们用快排的套路，先把它变成有序，能否更加轻松的解决这个问题，从这个角度思考
      • 时间复杂度O(nlogn)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void quick_sort(int q[], int l, int r)
    {
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
     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);
    }
    • 归并排序
      • 时间复杂度O(nlogn)
      • 如果我们在考题当中遇到排序类的题目，要求把一个乱序的数组排成一个更大的数组，如果这个数组本身部分有序，那么我们采用归并排序比快速排序更加优秀
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    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];

    }
    • 快速排序更擅长将一个原本乱序的数组排成有序
      • 二路归并排序更擅长将两个原本有序的数组合并为一个，时间复杂度仅为O(n)
      • 通常来说，对乱序数组的排序，用归并不如用快排
      • 如果题目中给的是两个有序表，并且需要将两个有序表合并为一个，可以考虑用归并思想

链表

  • 不支持随机访问，算法较少
  • 考察偏向于考基本功
    • 按位序查找
    • 按关键字条件查找+删除某个节点
    • 按关键字条件查找+插入某个节点
    • 头插法（可实现原地逆置）
    • 尾插法（保持原序）

树

  • 掌握前中后序遍历、层序遍历、递归算法
    • 非递归算法不用掌握
    • 基于这些算法解决思维导图中列出的问题，然后做一下王道书的剩余算法题

图

  • 数据结构层面

    • 邻接矩阵和邻接表的遍历
      • 邻接矩阵可以for循环遍历
    • 但是邻接表只能bfs或者dfs
    • 邻接多重表和十字链表的定义

  • 算法备考

    • 栈、队列的数组表示（用来理解下面的代码）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // tt表示栈顶
    int stk[N], tt = 0;//stk表示栈，tt表示栈顶下标

    // 向栈顶插入一个数
    stk[ ++ tt] = x;

    // 从栈顶弹出一个数
    tt -- ;

    // 栈顶的值
    stk[tt];

// 判断栈是否为空，如果 tt > 0，则表示不为空
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
18
19
20
21

```c++
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

//取出队尾
q[tt];

// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt) not empty;
    else empty;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  //循环队列
  // hh 表示队头，tt表示队尾的后一个位置
  int q[N], hh = 0, tt = 0;
  
  // 向队尾插入一个数
  q[tt ++ ] = x;
  if (tt == N) tt = 0;
  
  // 从队头弹出一个数
  hh ++ ;
  if (hh == N) hh = 0;
  
// 队头的值
  q[hh];

  // 判断队列是否为空，如果hh != tt，则表示不为空
if (hh != tt)
  {
  
  }
  • DFS，BFS
1
2
3
4
5
6
7
8
9
10
11
bool st[N];
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);//j没有被搜到，继续搜
    }
}
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
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);
        }
    }
}

int bfs()
{
	int hh =0,tt=0;//定义队头队尾
    q[0]=1;//q的第一个元素起点
    memset(d,-1,sizeof d);//初始化距离，-1表示没有被遍历过
    d[1]=0;//第一个点遍历
    while(hh<=tt){//队列不空
        int t=q[hh++]//取到队头
            for(int i = h[t];i!=-1;i=e[i])//拓展队头
            {
                int j =e[i];//拓展到队头连接的下一个点
               if(d[j]==-1)//d[j]没有被拓展过
               {
                   d[j]=d[t]+1;
                   q[++tt]=j;
               }
            }
    }
    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
int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];//d[n]表示入度，q[n]是拓扑序列
void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a]=idx++;
    
}
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])//枚举t的所有出边t->j，删掉t->j
        {
            int j = e[i];//找到出边
           d[j]--;
            if ( d[j] == 0)//前面的所有点都已经排好了
                q[ ++ tt] = j;//j入队
         
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 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
    //先序（根→左→右）
    void preorder(btnode *p){
        if(p==NULL){
            return;
            visit(p);//对p结点访问等，这道题真正要写的东西，比如题目要求我们做什么，树的每道题不同的点就在于这个visit
            preorder(p->lchild);
            preorder(p->rchild);
            //这三条语句，visit在先就是先序，在中就是中序，在后就是后序
        }
    }
    //中序（左→根→右）
    void inorder(btnode *p){
        if(p==NULL)
            return ;
       inorder(p->lchild);
        visit(p);
        inorder(p->rchild);
    }
    //后序（左→右→根）
    void postorder(btnode *p){
        if(p==NULL)
            return;
        postorder(p->lchild);
        postorder(p->rchild);
        visit(p);
    }

  • 图

    • 基本遍历
    • 最小生成树
    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
    //普利姆prim算法,时间复杂度O(n^2)
    int n;      // n表示点数
    int g[N][N];        // 邻接矩阵，存储所有边
    int dist[N];        // 存储其他点到当前最小生成树的距离
    bool st[N];     // 存储每个点是否已经在生成树中

    //到集合的距离就是一个点连接集合的所有边中最短的那一条
    // 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
    int prim()
    {
        memset(dist, 0x3f, sizeof dist);//初始化最短距离

        int res = 0;
        for (int i = 0; i < n; i ++ )//n次迭代
        {
            int t = -1;//不在集合当中的距离最小点的编号
            for (int j = 1; j <= n; j ++ )
                if (!st[j] && (t == -1 || dist[t] > dist[j]))
                    t = j;

            if (i && dist[t] == INF) return INF;

            if (i) res += dist[t];//只要不是第一个点
            st[t] = true;

            for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
        }

        return res;
    }
    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
    //克鲁斯卡尔Kruskal算法,时间复杂度O(mlogn)
    int n, m;       // n是点数，m是边数
    int p[N];       // 并查集的父节点数组

    struct Edge     // 存储边
    {
        int a, b, w;

        bool operator< (const Edge &W)const//重载小于号
        {
            return w < W.w;
        }
    }edges[M];

    int find(int x)     // 并查集核心操作
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    int kruskal()
    {
        sort(edges, edges + m);//把所有边排序

        for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

        int res = 0, cnt = 0;
        for (int i = 0; i < m; i ++ )//从小到大枚举所有边
        {
            int a = edges[i].a, b = edges[i].b, w = edges[i].w;

            a = find(a), b = find(b);//让a，b分别等于祖宗节点
            if (a != b)     // 如果两个连通块不连通，则将这两个连通块合并
            {
                p[a] = b;//合并两个连通块
                res += w;//存的是最小生成树中所有树边的权重之和
                cnt ++ ;//存的是当前加入了多时少条边
            }
        }

        if (cnt < n - 1) return INF;//图不是联通的
        return res;//输出所有树边的权重之和
    }
    • 最短路径
    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
    //朴素dijkstra算法，时间复杂度O(n^2)
    int g[N][N];  // 存储每条边
    int dist[N];  // 存储1号点到每个点的最短距离
    bool st[N];   // 存储每个点的最短路是否已经确定

    // 求1号点到n号点的最短路，如果不存在则返回-1
    int dijkstra()
    {
        memset(dist, 0x3f, sizeof dist);//初始化其他距离
        dist[1] = 0;//初始化第一个点的距离

        for (int i = 0; i < n - 1; i ++ )
        {
            int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
            for (int j = 1; j <= n; j ++ )
                if (!st[j] && (t == -1 || dist[t] > dist[j]))//当前点还没有确定最短路；没有赋值或者不是最短的
                    t = j;//赋值
      // if(t==n)break;//优化可以加上
            // 用t更新其他点的距离
            for (int j = 1; j <= n; j ++ )
                dist[j] = min(dist[j], dist[t] + g[t][j]);
    //判断长度，得出最小距离并更新
            st[t] = true;
        }

        if (dist[n] == 0x3f3f3f3f) //不连通
            return -1;
        return dist[n];
    }
    //输入输出
    cin >> n>>m;
    memset(g,0x3f,sizeof g);
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c);
    }
    int t =dijkstra()l
        cout<<t;
    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
    //堆优化版dijkstra算法，时间复杂度O(mlogn)
    typedef pair<int, int> PII;

    int n;      // 点的数量
    int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
    int dist[N];        // 存储所有点到1号点的距离
    bool st[N];     // 存储每个点的最短距离是否已确定

    void add(int a,int b,int c){
        e[idx]=b,w[idx]= c,ne[idx]=h[a],h[a]=idx++;
    }
    // 求1号点到n号点的最短距离，如果不存在，则返回-1
    int dijkstra()
    {
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
        priority_queue<PII, vector<PII>, greater<PII>> heap;//定义小根堆
        heap.push({0, 1});      // first存储距离，second存储节点编号

        while (heap.size())//堆里面非空
        {
            auto t = heap.top();
            heap.pop();

            int ver = t.second, distance = t.first;//编号；距离

            if (st[ver]) continue;//冗余备份
            st[ver] = true;

            for (int i = h[ver]; i != -1; i = ne[i])
            {
                int j = e[i];
                if (dist[j] > distance + w[i])
                {
                    dist[j] = distance + w[i];//更新距离
                    heap.push({dist[j], j});//放入堆
                }
            }
        }

        if (dist[n] == 0x3f3f3f3f) return -1;
        return dist[n];
    }
    int main(){
        cin >> n>>m;
        memset(h,-1,sizeof h);
        while(m--){
            int a,b,c;
            cin >> a >> b>>c;
            add(a,b,c);
        }
        int t = dijkstra();
        cout<<t;
        return 0;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    //Floyd算法,时间复杂度O(n^3)
    cosnt int INF=1e9;
    初始化：
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                if (i == j) d[i][j] = 0;
                else d[i][j] = INF;

    // 算法结束后，d[a][b]表示a到b的最短距离
    void floyd()
    {
        for (int k = 1; k <= n; k ++ )
            for (int i = 1; i <= n; i ++ )
                for (int j = 1; j <= n; j ++ )
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    }

    • 拓扑排序
    • 关键路径
    • 目标：考虑一些细节是否到位

  • 能不能直接调用函数

    • 5行以下的随便调用
    1
    2
    3
    4
    5
    6
    pop();
    push();
    swap(a,b);
    abs();
    pow(x,y);//x的y次幂
    sqrt();//平方根

  • 过程

    • 考前最好复习一遍常用的算法模板
1
2
3
4
5
6
7
8
//先假设所用函数已经设立，然后在主函数那里直接用，用完再回去写该函数
//如假如要用折半查找，先
int binary(){
//先留空，下面的ans函数写完再回来写
}
int ans(int s[],int n ,int k){
//答案
}
  • 空间复杂度的分析
    • 申请了哪些数组
    • 申请了哪些结点
    • 递归的时候有多少层的递归（树的高度，递归的层数）

栈、队列的一些代码模板

数组实现栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//数组实现栈

//初始化栈
int stk[N],tt=0;
//入栈
stk[++tt]=x;
//弹出栈顶元素但是不出栈
x=stk[tt];
//弹出栈顶元素并且出栈
x=stk[tt--];
//判断栈空
if(tt==0)
//判断栈满
if(tt==maxsize)

链表实现栈

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
//链表实现栈

//定义栈结点
struct Lnode{
    int data;
    Lnode* next;
};
using listack=Lnode*;
//初始化链表实现栈
bool initstack(listack &s){
  s=new Lnode;
    s->next=nullptr;
    return true;
}
//栈空
bool isempty(listack s){
    if(s->next==nullptr)
        return true;
    else 
        return false;
    
    
}
//入栈
bool push(listack &s,int x){
    Lnode *p=new Lnode;
    p->data= x;
    p->next=s->next;
    s->next=p;
    return true;
}
//出栈
bool pop(listack &s,int &x){
    if(isempty(s)) return false;
    Lnode *p=s->next;
    x=p->data;
    s->next=p->next;
    delete p;
    return true;
}

双向链表实现栈（栈顶在链尾）

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
//双链表实现栈，栈顶在链尾

//定义双链表结点
struct dnode{
    int data;
    dnode*pre,*next;
};
//定义栈
struct dstack{
    dnode *head,*rear;
};
using stk=dstack*;
//初始化一个链栈（双链表实现，栈顶在链尾）
bool init(stk &s){
    s=new dstack;//初始化一个链栈，双链表实现，栈顶在链尾）
    dnode *p=new dnode;
    p->next=nullptr;
    p->pre=nullptr;
    s->head=p;
    s->rear=p;
    return true;
}
//判断栈是否为空
bool isempty(stk s){
    if(s->head==s->rear)
        return true;
    else 
        return false;
}
//入栈（在双链表链尾插入）
bool push(stk &s,int x){
    dnode *p=new dnode;
    p->data=x;
    p->next=nullptr;
    p->pre=s->rear;
    s->rear->next=p;
    s->rear=p;
    return true;
}
//出栈（删除双链表链尾元素）
bool pop(stk &s,int &x){
    if(isempty(s))
        return false;
    dnode *p=s->rear;
    x=p->data;
    s->rear=p->pre;
    s->rear->next=nullptr;
    delete p;
    return true;
}

数组实现循环队列

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
//数组实现循环队列

//定义队列
const int maxsize =100;
struct queue{
    int data[maxsize];
    int rear,head;
};

//初始化队列
void init(queue &q){
    q.rear=q.head=0;
}

//判断队空
bool isempty(queue q){
    if(q.head==q.rear)
		return true;
    else 
        return false;
    
}
//判断队满
bool isfull(queue q){
    if((q.rear+1)%maxsize==q.head)
        return true;
    else return false;
}
//入队
bool inqueue(queue &q,int x){
    if(isfull(q))return false;
    q.data[q.rear]=x;
    q.rear=(q.rear+1)%maxsize;
    return true;
}
//出队
bool outqueue(queue &q,int &x){
    if(isempty(q)) return false;
    x=q.data[q.head];
    q.head=(q.head+1)%maxsize;
    return true;
}

单链表实现队列

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
//单链表实现队列

//定义链表队列节点
struct qnode{
    int data;
    qnode *next;  
};

//定义队列
struct listqueue{
    qnode*head,*rear;
};
using lq=listqueue*;

//初始化队列
bool init(lq &q){
    q=new listqueue;
    qnode *p=new qnode;
    q->head=p;
    q->rear=p;
    p->next=nullptr;
    return true;
}
//判空
bool isempty(lq q){
    return q->head==q->rear;
}

//入队
bool inqueue(lq &q,int x){
    qnode *p=new qnode;
  	p->data=x;
    p->next=nullptr;
    q->rear->next=p;
    q->rear=p;
    return true;
}

//出队
bool outqueue(lq &q,int &x){
    if(isempty(q))return false;
    qnode *p=q->head->next;
    x=p->data;
    q->head->next=p->next;
    if(q->head->next==nullptr)
        q->rear=q->head;
    delete p;
    return true;
    
}

树的一些代码模板

数组实现二叉树

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
//数组实现二叉树(下标从1开始)

//定义树结点
struct treenode{
	int data;
    bool empty;
};
//初始化二叉树
void init(treenode t[],int length){
    for(int i = 0;i<length;i++)
        t[i].empty=true;
}
int main(){
    treenode t[100];
    init(t,100);
}
//判空树结点
bool isempty(treenode t[],int length,int x){
    if(x>=length || x<1) return true;
    return t[x].empty;
}
//找到结点的左孩子
int findlkid(treenode t[],int length,int x){
    int lkid = x*2;
    if(isempty(t,length,lkid))return -1;
    return lkid;
    
}
//找到结点的右孩子
int findrkid(treenode t[],int length,int x){
    int rkid = x*2+1;
    if(isempty(t,length,rkid))return -1;
    return rkid;
}

//找到结点的家长结点
int findparent(treenode t[],int length,int x){
    if(x==1)return -1;
    int parent=x/2;
    if(isempty(t,length,parent))return -1;
    return parent;
}
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
//数组实现二叉树（下标从0开始）

//定义树结点
struct treenode{
	int data;
	bool empty;
};
//初始化
void init(treenode t[],int length){
	for(int i= 0;i<length;i++)
		t[i].empty=true;
}
int main(){
	treenode t[100];
	init(t,100);
    return 0;
}
//判空
bool isempty(treenode t[],int length,int x){
	if(x<0 || x>=length) return true;
	return t[x].empty;
}
//寻找家长节点
int findparent(treenode t[],int length,int x){
	if(x==0)return -1;
	int parent=(x-1)>>1;
	if(isempty(t,length,parent))return -1;
	return parent;
}
//寻找左孩子
int findlkid(treenode t[],int length,int x){
	int lkid = x*2+1;
	if(isempty(t,length,lkid))return -1;
	return lkid;
}

//寻找右孩子
int findrkid(treenode t[],int length,int x){
	int rkid=x*2+2;
	if(isempty(t,length,rkid))return -1;
	return rkid;
}

二叉树的先中后序遍历

先序遍历
1
2
3
4
5
6
7
void visitnode(treenode &x);
void preorder(treenode t[],int length,int x){
        if(isempty(t,lengt,x))return;   
            visitnode(t[x]);
            preorder(t,length,getlkid(t,length,x));
            preorder(t,length,getrkid(t,length,x));
}
中序遍历
1
2
3
4
5
6
7
void visitnode(treenode &x);
void inorder(treenode t[],int length,int x){
    if(isempty(t,length,x)) return;
    inorder(t,length,getlkid(t,length,x));
    visitnode(t[x]);
    inorder(t,length,getrkid(t,length,x));
}
后序遍历
1
2
3
4
5
6
7
void visitnode(treenode &x);
void postorder(treenode t[],int length,int x){
  if(isempty(t,length,x)) return;
  postorder(t,length,getlkid(t,length,x));
  postorder(t,length,getrkid(t,length,x));
  visitnode(t[x]);
}

树的存储结构

双亲表示法
1
2
3
4
5
6
7
8
9
10
11
//定义树结点
const int maxsize=100;
struct ptnode{
    int data;
    int parent;
};
//定义树
struct ptree{
    ptnode nodes[maxsize];
    int n;
};
孩子表示法
1
2
3
4
5
6
7
8
9
10
11
//定义孩子结点
const int maxsize=100;
struct kidnode{
    int index;
    kidnode *next;
};
//定义家长结点
struct parentnode{
	int data;
    kidnoe *firstkid;
}tree[maxsize];
孩子兄弟表示法
1
2
3
4
5
6
//定义结点
struct node{
    int data;
    node*firstkid,*nextbrother;
};
using tree=node*;

并查集

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
//定义并查集
const int N=100;
int size[N],p[N];
//初始化并查集
void init(int size[],int p[],int length){
    for(int i= 1;i<=length;i++)
    {
        size[i]=1;
        p[i]=i;
    }
}
//查
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
//并
void merge(int a,int b){
    int r1=find(a);
    int r2=find(b);
    if(r1==r2)return;
    if(size[r1]>=size[r2]){
        p[r2]=r1;
        size[r1]+=size[r2];
    }
    else{
        p[r1]=r2;
        size[r2]+=size[r1];
    }
}

图的一些代码模板

邻接矩阵实现图的顺序存储

1
2
3
4
5
6
7
//定义邻接矩阵
const int N =100;
struct graph{
    int n,e;
    char vex[N];
    int weight[N][N];
};

邻接表实现图的链式存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int N=100;
//定义弧结点
struct arcnode{
    int adjvex;//弧头结点的编号
    arcnode*nextarc;//指向下一条边的指针
    int info;//用来记录边的权值等信息
};
//定义顶点结点
struct vnode{
    char data;//结点所存储的字母
    arcnode *firstarc;//结点指向的第一条边
}
//定义邻接表
struct graph{
    vnode adjlist[N];//顶点结点数组
    int n,e;//边和顶点的数量
};

dijkstra算法的文字过程描述

1
2
3
4
5
/*
从顶点x1出发，运行dijkstra算法的过程如下：
第一轮：顶点x1到x2的最短路径为1→2，距离为a
第n论：不存在顶点x1到顶点x2的路径，距离为∞
*/

bfs算法的文字过程描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    A
   / \
  B - C
  |   |
  D - E
       \
        F
//图的结构
/*
文字描述：用BFS算法求单源最短路径的过程
初始化：设置一个队列queue，用来存储要访问的结点，以A为起点，起点A入队，visit[A]=1,dist[A]=0

第一轮：队头是A，出队，将A的相邻结点B和C入队，更新dist[B]=1,dist[C]=1,visit[B]=1,visit[C]=1

第二轮：队头是B，出队，将B的相邻未访问节点D入队，dist[D]=2;visit[D]=1

第三轮：队头是C，出队，将C的相邻未访问结点E入队，dist[E]=2；visit[E]=1

第四轮：队头是D，出队，D无相邻未访问节点

第五轮：队头是E，出队，将E的相邻未访问节点F入队，dist[F]=3;visit[F]=1;
*/

拓扑排序的文字过程描述

1
2
3
4
5
6
7
8
9
10
11
/*
拓扑排序：
1、从AOV网中选择任意一个入度为0的点，并将其加入拓扑序列
2、在AOV网中删除该点和以该点为起点的有向边
3、重复上述过程直到AOV网为空

逆拓扑排序：
1、从AOV网中选择任意一个出度为0的点，并将其加入拓扑序列
2、在AOV网中删除该点和以该点为起点的有向边
3、重复上述过程直到AOV网为空
*/

关键长度的意义

1
2
/*AOE网的顶点代表时间，带权边代表活动，关键路径的长度代表的是
一个项目从开始到结束至少需要多长时间

朴素版prim算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//
const int N=1000;
int n;
int g[N][N];
int dist[N];
bool st[N];
int prim(){
    int res=0;
    memset(dist,0x3f,sizeof(dist));
    for(int i = 0;i<n;i++){
        int t=-1;
        for(int j = 1;j<=n;j++)
            if(!st[j]&&(t==-1 || dist[t]>dist[j]))
                t=j;
        if(i && dist[t]==INF)return INF;
        if(i) res+=dist[t];
        st[t]=true;
        for(int j  = 1;j<=n;j++)
            dist[j]=min(dist[j],g[t][j]);
    }
    return res;
}

408图论算法复杂度+适用场景（含负权边/负环）

算法 / 存储结构 时间复杂度 空间复杂度 适用场景 说明
邻接矩阵 —— O(V²) 稠密图 查询边是否存在快 O(1)，遍历慢 O(V)
邻接表 —— O(V+E) 稀疏图 遍历快 O(V+E)，查询边是否存在慢 O(deg(v))
十字链表（有向图） —— O(V+E) 需要同时高效处理出度和入度的有向图 每条边存两次引用
邻接多重表（无向图） —— O(V+E) 需要避免无向边重复存储 每条边只存一次结点
DFS（邻接表） O(V+E) O(V+E) 遍历所有顶点与边；拓扑排序；连通分量；检测环 深度优先搜索
DFS（邻接矩阵） O(V²) O(V²) 小规模稠密图遍历 遍历邻接点需扫一行
BFS（邻接表） O(V+E) O(V+E) 无权图最短路径；分层遍历；连通分量 广度优先搜索
BFS（邻接矩阵） O(V²) O(V²) 小规模稠密图遍历
Prim 算法（朴素版，邻接矩阵） O(V²) O(V²) 稠密图最小生成树 每次扫描所有顶点选最小边
Prim 算法（堆优化版，邻接表） O(E log V) O(V+E) 稀疏图最小生成树 用优先队列维护候选边
Kruskal 算法 O(E log E)≈O(E log V) O(V+E) 稀疏图最小生成树 边排序 + 并查集
Dijkstra（朴素版，邻接矩阵） O(V²) O(V²) 稠密图，单源最短路径（不允许负权边） 每次找最近点 O(V)
Dijkstra（堆优化，邻接表） O(E log V) O(V+E) 稀疏图，单源最短路径（不允许负权边） 用堆维护最短距离
Floyd 算法 O(V³) O(V²) 多源最短路径，小规模稠密图，允许负权边；可检测负环（dist[i][i]<0） 若有负环则无解
Bellman-Ford 算法 O(VE) O(V+E) 单源最短路径，允许负权边；可检测负环（松弛 V 次后仍变化） 若有负环则无解
SPFA 算法 平均 O(E)，最坏 O(VE) O(V+E) 单源最短路径，允许负权边；可检测负环（某点入队 ≥ V 次） 若有负环则无解
算法 / 存储结构 时间复杂度 空间复杂度 适用场景 说明
邻接矩阵 —— O(V²) 稠密图 查询边是否存在快 O(1)，遍历慢 O(V)
邻接表 —— O(V+E) 稀疏图 遍历快 O(V+E)，查询边是否存在慢 O(deg(v))
十字链表（有向图） —— O(V+E) 需要同时高效处理出度和入度的有向图 每条边存两次引用
邻接多重表（无向图） —— O(V+E) 需要避免无向边重复存储 每条边只存一次结点
DFS（邻接表） O(V+E) O(V+E) 遍历所有顶点与边；拓扑排序；连通分量；检测环 深度优先搜索
DFS（邻接矩阵） O(V²) O(V²) 小规模稠密图遍历 遍历邻接点需扫一行
BFS（邻接表） O(V+E) O(V+E) 无权图最短路径；分层遍历；连通分量 队列实现
BFS（邻接矩阵） O(V²) O(V²) 小规模稠密图遍历
拓扑排序（邻接表） O(V+E) O(V+E) DAG 的线性序；任务调度；编译依赖 常用 Kahn 算法（队列）或 DFS
拓扑排序（邻接矩阵） O(V²) O(V²) 小规模稠密图 每次找入度=0 需扫一列
Prim 算法（朴素版，邻接矩阵） O(V²) O(V²) 稠密图最小生成树 每次扫描所有顶点选最小边
Prim 算法（堆优化版，邻接表） O(E log V) O(V+E) 稀疏图最小生成树 用优先队列维护候选边
Kruskal 算法 O(E log E)≈O(E log V) O(V+E) 稀疏图最小生成树 边排序 + 并查集
Dijkstra（朴素版，邻接矩阵） O(V²) O(V²) 稠密图，单源最短路径（不允许负权边） 每次找最近点 O(V)
Dijkstra（堆优化，邻接表） O(E log V) O(V+E) 稀疏图，单源最短路径（不允许负权边） 用堆维护最短距离
Floyd 算法 O(V³) O(V²) 多源最短路径，小规模稠密图，允许负权边；可检测负环（dist[i][i]<0） 若有负环则无解
Bellman-Ford 算法 O(VE) O(V+E) 单源最短路径，允许负权边；可检测负环（松弛 V 次后仍变化） 若有负环则无解
SPFA 算法 平均 O(E)，最坏 O(VE) O(V+E) 单源最短路径，允许负权边；可检测负环（某点入队 ≥ V 次） 若有负环则无解

排序的一些代码模板

快速排序

1
2
3
4
5
6
7
8
9
10
void quick_sort(int q[],int l,int r){
    if(l>=r)return ;
    int i  =  l-1,j=r+1,x=q[l+r>>1]
    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);
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void merge_sort(int q[],int l,int r){
	if(l>=r)return ;
    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(j = 0,i=l;i<=r;i++,j++)
        q[i]=tmp[j];
    
}

错题本

2010 线性表 三次翻转

1
2
3
4
5
6
7
8
9
10
//自己的
void moveleft(int q[],int p,int n){
    int tmp[n];
    for(int i = 0;i<n;i++)
        tmp[(i+n-p)%n]=q[i];
    for(int i = 0 ;i<n;i++)
        q[i]=tmp[i];
    
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//标答
void reverse(int q[],int l,int r){
    if(l>=r)return;
    while(l<r){
        swap(q[l],q[r]);
        l++,r--;
    }
}
void moveleft(int q[],int n,int p){
    reverse(q,0,p-1);
    reverse(q,p,n-1);
    reverse(q,0,n-1);
}

2011 线性表 二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
//自己的
/*算法的基本设计思想：
中位数的位置是可以计算出的，也就是两个数列合并后处于L/2位置的数，利用两个指针ij分别指向数组A,B，然后找到第L/2大的数即中位数*/
int findmid(int a[],int b[],int l){
    int i = 0,j=0;
    while(i+j<l-1){
        if(a[i]>=b[j])j++;
        else i++;
    }
    return min(a[i],b[j]);
}
//14分
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
//标答
int findMid(int a[], int b[], int n) {
    int l = 0, r = n;
    
    // 二分查找
    while (l < r) {
        int i = (l + r) / 2;  // 计算数组 a 中的分割点
        int j = n - i;  // 计算数组 b 中的分割点

        // 进行二分查找
        if (i < n && b[j - 1] > a[i]) l = i + 1;  // a[i] 还小，扩大左边界
        else if (i > 0 && a[i - 1] > b[j]) r = i - 1;  // b[j] 还小，缩小右边界
        else {
            // 找到合适的分割点，开始返回中位数
            int leftMax = 0;
            if (i == 0) leftMax = b[j - 1];  // 如果 i = 0，取 b[j-1]
            else if (j == 0) leftMax = a[i - 1];  // 如果 j = 0，取 a[i-1]
            else leftMax = max(a[i - 1], b[j - 1]);  // 否则取左右两边的最大值

            return leftMax;  // 返回合并后中位数的值
        }
    }
    return -1;  // 如果未找到中位数，返回 -1
}

//15分

2013 线性表 摩尔投票法

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
//自己的
//设计思想：如果一个数的出现次数大于n/2，那么他一定是这一组数顺序序列的中位数，然后找到比它小的第一个数和比他大的第一个数，两者的位置差就是该数出现的次数。
void quick_sort(int q[],int l,int r){
    if(l>=r)return ;
    int x=q[l+r>>1],i=l-1,j=r+1;
    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 bsl(int l,int r,int x,int q[]){
    while(l<r){
        int mid=l+r+1>>1;
        if(q[mid]<x)l=mid;
        else r=mid-1;
    }
    return l;
}
int bsh(int l,int r,int x,int q[]){
    while(l<r){
        int mid = l+r>>1;
        if(q[mid]>x)r=mid;
        else l  = mid+1;
    }
    return l;
}
int findmain(int a[],int n){
    quick_sort(a,0,n-1);
    int result = a[n-1>>1];
    int left=bsl(0,n-1,result,a);
    int right=bsh(0,n-1,result,a);
    if(right-left-1>(n>>1))return result;
    else return -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
//摩尔投票法，时间复杂度O(n)，空间复杂度O(1)
int find_main(int a[], int n) {
    int candidate = -1, count = 0;

    // 第一轮：找出可能的主元素
    for (int i = 0; i < n; i++) {
        if (count == 0) {
            candidate = a[i]; // 换人
            count = 1;
        } else if (a[i] == candidate) {
            count++; // 同类+1
        } else {
            count--; // 异类-1
        }
    }

    // 第二轮：验证是否真的是主元素（必须超过一半）
    count = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == candidate) count++;
    }

    return (count > n / 2) ? candidate : -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cnt = 0, val;
        for (auto x: nums) {
            if (!cnt) val = x, cnt ++ ;
            else if (x == val) cnt ++ ;
            else cnt -- ;
        }

        return val;
    }
};

🎭 这个算法其实是在模拟“投票大战”！

想象你现在有一群人，每人代表一个数。你的目标是找出 有没有某个数在这群人里占多数（超过一半）。

🥊 摩尔投票的逻辑是：

  • 你一开始不知道谁是主角，所以从第一个人开始猜；
  • 如果后来遇到和当前猜测一样的人（站你这边），你就信心 +1；
  • 如果遇到和你猜的不一样的人（反对你），你就信心 -1；
  • 如果信心掉到 0，就说明你现在这个候选人支持和反对打平了，需要换人重新开始；
  • 最后剩下来的“赢家”有可能是主角，但得再数一遍确认一下它是不是真的超过一半。

🎯 那为什么 count-- 是必要的？

因为每遇到一个“不同”的数，就是“主元素”的一个反对票。

如果主元素真的超过一半，那其他所有数都不够把它抵消掉，它一定能撑到最后！

比如数组：

1
2
3
4
5
csharp


复制编辑
[5, 5, 3, 5, 7, 5, 5, 1]
  • 主元素是 5，它有 5 票；
  • 剩下的 3、7、1 只有 3 票；
  • 即使这 3 票全都拿来反对 5，5 还是赢了！

所以你在每遇到一个“异类”时，就等于主角被反对了一次，要 count--。

✅ 总结一句话：

count-- 是为了让反对的声音抵消掉主元素的票数，看它能不能最终剩下来。

2018 线性表 原地哈希法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//自己的
//设计思路：将数组变为有序数组，从最小的正整数1开始判断数组中是否出现，然后递增找到最小的未出现正整数
void quick_sort(int a[],int l,int r){
    if(l>=r)return;
    int x=a[l+r>>1],i=l-1,j=r+1;
    while(i<j){
        do i++ ;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j)swap(a[i],a[j]);
    }
    quick_sort(a,l,j),quick_sort(a,j+1,r);
}
int findmin(int a[],int n){
    int mini = 1;
    quick_sort(a,0,n-1);
    for(int i = 0 ; i<n;i++){
        if(a[i]==mini) mini++;
    }
    return mini;
}
//时间复杂度O(nlogn)空间复杂度O(logn)

1
2
3
4
5
6
7
8
9
10
11
//课本上的答案 时间复杂度O(n),空间复杂度O(n)
int findmin(int a[],int n){
    int tmp[n];
    memset(tmp,0,sizeof(tmp));
    for(int i = 0;i<n;i++){
        if(a[i]>0&&a[i]<=n)tmp[a[i]-1]=1;

    }
    for(int i = 0;i<n;i++)
        if(!tmp[i])return i+1;
}
1
2
3
4
5
6
7
8
//更好的答案（原地哈希法）时间复杂度O(n)，空间复杂度O(1)
int findmin(int a[],int n){
    for(int i = 0 ;i<n;i++)
        while(a[i]>0 && a[i]<=n &&a[a[i]-1]!=a[i])
          swap(a[a[i]-1],a[i]);
    for(int i = 0;i<n;i++)
        if(a[i]!=i+1)return i+1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
//y总版本
int findmissmin(vector<int>&nums){
		int n = nums.size();
		vector<bool>hash(n+1);
		for(int x:nums)
			if(x>=1 && x<=n)
				hash[x]=true;
    	for(int i = 1;i<=n;i++)
            if(!hash[i])
                return i;
    	return n+1;
                
}

2020 线性表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//答案
const int maxint = 0x3f3f3f3f
bool ismin(int a,int b,int c){
    return a<=b&&a<=c;
}
int distance(int a[],int n1,int b[],int n2,int c[],int n3){
    int i = 0 ,j=0,k = 0,dmin = maxint;
     	while(i<n1  && j<n2&& k <n3 &&d>0){
            int d = abs(a[i]-b[j])+abs(a[i]-c[k])+abs(b[j]-c[k]);
            if(d<dmin) dmin=d;
            if(ismin(a[i],b[j],c[k]))i++;
            else if(b[j],a[i],c[k]) j++;
            else k++;
        }
    return  dmin;
}

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

using namespace std;

typedef long long LL;

const int N = 100010;

int l, m, n;
int a[N], b[N], c[N];

int main()
{
    scanf("%d%d%d", &l, &m, &n);
    for (int i = 0; i < l; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);
    for (int i = 0; i < n; i ++ ) scanf("%d", &c[i]);
//读入数据
    LL res = 1e18;
    for (int i = 0, j = 0, k = 0; i < l && j < m && k < n;)//遍历三个
    {
        int x = a[i], y = b[j], z = c[k];
        res = min(res, (LL)max(max(x, y), z) - min(min(x, y), z));//三个数中的最大值-最小值
        //因为最短距离=最大-最小，且都是升序数组，所以最小值所在的那个数组指针向后移，相当于向其他两个数靠近
        if (x <= y && x <= z) i ++ ;
        else if (y <= x && y <= z) j ++ ;
        else k ++ ;
    }

    printf("%lld\n", res * 2);
    return 0;
}

2009 单链表

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
//自己的
#include <iostream>
using namespace std;
struct lnode{
    int data;
    lnode *next;
};
using linklist = lnode*;
int getlength(lnode* head){
    int length=0;
    lnode *p=head->next;
    while(p){
        length++;
        p=p->next;
    }
    return length;
}
int findnum(lnode *head,int k){
        int length=getlength(head);
        int n=length-k+1;
        lnode *p=head->next;
        for(int i = 1;i<n;i++){
                p=p->next;
                if(!p)return 0;
        }
        cout<<p->data<<endl;
        return 1;
}
    //描述算法的基本设计思想：第一遍顺序查找遍历一遍链表，获取链表长度，然后计算倒数k个位置对应的是正数第n-k+1个位置，第二遍顺序查找到第n-k+1个节点，如果存在，输出对应的值并返回1，如果不存在则返回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
//答案的
/*思路
1)算法的基本设计思想：
问题的关键是设计一个尽可能高效的算法，通过链表的一次遍历，找到倒数第k个结点的位置。定义两个指针变量p和q,初始时均指向头结点的下一个结点(链表的第一个结点),p指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到最后一个结点时，q指针所指示结点为倒数第k个结点。以上过程对链表仅进行一遍扫描。
2)算法的详细实现步骤如下：
1、count=0,p和q指向链表表头结点的下一个结点。
2、若p为空，转5。
3、若count等于k,则q指向下一个结点；否则，count=count+1。
4、p指向下一个结点，转2。
5、若count等于k,则查找成功，输出该结点的data域的值，返回1;否则，说明k值超过了线性表的长度，查找失败，返回0。算法结束。
*/
#include <iostream>
using namespace std;
struct lnode
{
    int data;
    lnode *next;
};
int findnum(lnode *list,int k){
    lnode *p=list->next;
    lnode *q=list->next;
    int count = k;
    while(count--){
        if(p==nullptr)return 0;
        p=p->next;

    }
    while(p){
        p=p->next;
        q=q->next;
    }
    if(q==nullptr) return 0;
       
    cout<<q->data<<endl;
    return 1;

}

2012 单链表

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;
struct lnode
{
    char data;
    lnode *next;
    bool ispass=0;
};
using linklist=lnode *;
linklist findpoint(lnode *str1,lnode *str2){
    while(str1){
        str1->ispass=1;
        str1=str1->next;    
    }
    while(str2){
        if(!(str2->ispass)){
            str2->ispass=1;
            str2=str2->next;
        }
        else break;
    }
    lnode *p=str2;
    return p;
}
//思路：先遍历一遍str1，标记已经遍历过的节点，然后再遍历一遍str2，当str2遍历到已经标记过的节点，说明其是二者共同后缀的起始位置。时间复杂度为O(n)

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
//答案
#include <iostream>
using namespace std;
struct node
{
    char data;
    node *next;
};
int listlen(node *head){
    int len=0;
    while(head->next!=nullptr){
        len++;
        head=head->next;
    }
    return len;
}
//找出共同后缀的起始地址
node * findlist(node *str1,node *str2){
    int m,n;
    node *p,*q;
    m=listlen(str1);
    n=listlen(str2);
    for(p=str1;m>n;m--)p=p->next;
    for(q=str2;m<n;n--)q=q->next;
    while (p->next!=nullptr&&p->next!=q->next)
    {
        p=p->next;
        q=q->next;
    }
    return p->next;
}

顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长k个结点，我们先在长链表上遍历k个结点，之后同步遍历两个链表，这样就能够保证它们同时到达最后一个结点。因为两个链表从第一个公共结点到链表的尾结点都是重合的，所以它们肯定同时到达第一个公共结点。
1)算法的基本设计思想：
①分别求出str1和str2所指的两个链表的长度m和n。
②将两个链表以表尾对齐：令指针p、q分别指向str1和str2的头结点，若m≥n,则指针p先走，使p指向链表中的第m-n+1个结点；若m<n,则使q指向链表中的第n-m+1个结点，即使指针p和q所指的结点到表尾的长度相等。
③反复将指针p和q同步向后移动，并判断它们是否指向同一结点。当p、q指向同一结点，则该点即所求的共同后缀的起始位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//yxc
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        auto p = headA, q = headB;
        while (p != q) {
            p = p ? p->next : headB;//p是否是空指针？如果非空，往下走，如果空，开始走另一个链表
            q = q ? q->next : headA;//q是否是空指针？如果非空，往下走，如果空，开始走另一个链表
        }
        return p;
    }
};
时间复杂度O(n+m)
//思路，由两个链表，分别对应str1和str2，假设这两个后缀前的长度分别是a，b，两个链表分别从自己的头指针开始走，走完自己的开始走一个链表，那么两个如果有公共交点，那么他们一个走了a+c+b，一个走了b+c+a，也就是最终他们会相遇，如果没有公共交点，最终他们会同时指向null

2015 单链表

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
//自己的
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
struct node
{
    int data;
    node*link;  
};
void delnode(node *p){//删除该节点的下一个节点
        node *q=p->link;
        p->link=q->link;
        free(q);
}
void nosame(node *head,int m,int n){
    bool ispass[n+1];
    memset(ispass,0,sizeof(ispass));
    node *p=head->link;
    while (p)//同时保存两个点，一个是当前节点的上一个节点即head所指向的，一个是当前节点即p
    {
        if(!(ispass[abs(p->data)])){
            ispass[abs(p->data)]=1;
            p=p->link;
            head=head->link;
        }
        else{
            delnode(head);
            p=head->link;
        }
    }
    
}
/*思路：用一个bool数组记录某个数曾经出现过，
如果遍历到某个点的时候发现他的绝对值出现过，则删除该点。时间复杂度为O(m)*/
1
2
//答案
同样
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
//YXC
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* filterList(ListNode* head) {
        bool st[10001] = {};
        st[abs(head->val)] = true;
        for (auto p = head; p->next;) {
            int x = abs(p->next->val);
            if (st[x]) {
                auto q = p->next;
                p->next = q->next;
                delete q;
            } else {
                p = p->next;
                st[x] = true;
            }
        }
        return head;
    }
};

2019 单链表 快慢指针找链表中点

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
//自己的
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;


/*
思路：根据题目可知，会被插入的节点有n-1/2（下取整）个，即从n-(n-1/2)后面都是要插入前面序列的节点
从该点开始对后面的采用头插法二次插入，形成一个后部逆序，然后从头开始隔次插入，即可得到题目要求的结果
*/
struct node
{
    int data;
    node *next;
};
int getlength(node *head){
    node *p=head->next;
    int length=0;
    while(p){
        length++;
        p=p->next;
    }
    return length;
}

void insertlist(node *head){
    int n=getlength(head);
    int k = n-(n-1>>1);
    node *h=head->next;
    for(int i = 1;i<k;i++){
            h=h->next;//跳出循环后p指向的是第k个节点，也就是不需要倒插的最后一个节点,相当于倒置链表的头结点
    }
    int m = n-1>>1;
    node *p=h->next;
    node *tmp=p->next;
    p->next=nullptr;
    p=tmp;
    //从第一个点开始头插，用一个指针保存剩下的链表的开头
    for(int i = 1;i<=m;i++){
        node *tmp=p->next;//剩下待插入的链表的起点
        p->next=h->next;
        h->next=p;
        p=tmp;     
    }//形成倒插序列
    node *p=h->next;
        node *q=head->next;
        int count= n;
        node *rear=head;
    while (count)
    {//n个数重组
       //顺序链表取数
       node *tmp=q->next;
       rear->next=q;
       rear=q;
       q=tmp;
       count--;
       //逆序链表取数
        node *tmp=p->next;
        rear->next=p;
        rear=p;
        p=tmp;
        count--;
    }
    rear->next=nullptr;
}
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
//答案
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;


/*
思路：根据题目可知，会被插入的节点有n-1/2（下取整）个，即从n-(n-1/2)后面都是要插入前面序列的节点
从该点开始对后面的采用头插法二次插入，形成一个后部逆序，然后从头开始隔次插入，即可得到题目要求的结果
*/
struct node
{
    int data;
    node *next;
};
void changelist(node *h){
    node *p,*q,*r,*s;
    p=q=h;
    while (q->next!=nullptr)//寻找中间节点
    {
        p=p->next;
        q=q->next;
        if(q->next!=nullptr) q=q->next;
    }
    q=p->next;//p所指节点为中间节点，q为后半段链表的首节点
    p->next=nullptr;//p为中间节点，将中间节点指向的节点变为nullptr
    while (q!=nullptr)
    {
        //将链表后半段逆置,p(中间节点)充当了头结点的地位，q成为了待插入链表的起点
        r=q->next;//r用来存储下一个要插入的节点
        q->next=p->next;//头插法，q指向原头结点指向的节点
        p->next=q;//q成为头结点指向的节点
        q=r;//q成为下一个要插入的节点
    }
    s=h->next;//s指向前半段的第一个数据节点，即插入点
    q=p->next;//q指向后半段的第一个数据节点
    p->next=nullptr;//p要成为链表的
    while (q!=nullptr)//将链表后半段的节点插入到指定位置
    {
        r=q->next;//r指向后半段的下一个节点
        q->next=s->next;//将q所直接点插入到s所指结点之后
        s->next=q;
        s=q->next;//s指向前半段的下一个插入点
        q=r;//q变为后半段要插入的点
    }
    

    
}

你问：“为什么快指针 q 走两步，慢指针 p 走一步，最后 q 到达链尾时 p 正好在链表中间？”

这个其实是快慢指针（龟兔赛跑）找链表中点的经典原理，我给你详细解释一下：

原理说明

  • 设链表长度为 n。
  • 慢指针 p 每次走一步，快指针 q每次走两步。
  • 当快指针 q 到达链表末尾（或越过末尾）时，慢指针 p 所指节点就是链表的中点。

为什么成立？

  • 由于 q速度是 p的两倍，假设 p走了 k 步，那么 q走了 2k2k 步。

  • 当 q 到链尾时，链表总长度是 n，因此：

    2k≈n  ⟹  k≈n22k \approx n \implies k \approx \frac{n}{2}

  • 即慢指针 p 走了链表长度一半的步数，停在中点。

直观示例

链表长度 q走的步数 p 走的步数 p 位置
5 4~5 2~3 第3个节点（中间）
6 6 3 第4个节点（中间）

代码示例

1
2
3
4
5
6
7
8
9
node* findMiddle(node* head) {
    node* p = head;
    node* q = head;
    while (q != nullptr && q->next != nullptr) {
        p = p->next;
        q = q->next->next;
    }
    return p; // p 指向中点
}

总结

  • 快指针两步，慢指针一步。
  • 快指针到末尾时，慢指针刚好走一半，指向中点。
  • 这是链表中点查找的最常用技巧。

形象文字图

1
2
3
4
5
6
7
less复制编辑节点： 1 → 2 → 3 → 4 → 5 → 6 → 7 → nullptr

p:        ↑     ↑     ↑     ↑
         1     2     3     4

q:        ↑           ↑           ↑
         1           3           5           7
  • 每次循环，p向右走一个节点，q向右走两个节点。
  • 当q到达链尾或超出链尾时，p所在的位置就是中点。
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
//YXC
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void rearrangedList(ListNode* head) {
        if (!head->next) return;
        int n = 0;
        for (auto p = head; p; p = p->next) n ++ ;
        int left = (n + 1) / 2;  // 前半段的节点数
        auto a = head;
        for (int i = 0; i < left - 1; i ++ ) a = a->next;
        auto b = a->next, c = b->next;

        a->next = b->next = NULL;
        while (c) {
            auto p = c->next;
            c->next = b;
            b = c, c = p;
        }

        for (auto p = head, q = b; q;) {
            auto o = q->next;
            q->next = p->next;
            p->next = q;
            p = p->next->next;
            q = o;
        }
    }
};

2022 二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//自己的
#include <iostream>
using namespace std;
/*
思路：遍历数组的每个点，判断各点是否符合二叉搜索树的情况，时间复杂度为O(n)
*/
const int max_size =10000;
struct sqbitree{
    int sqbitnode[max_size];
    int Elenum;
};
bool isbst(sqbitree a){
        int n = a.Elenum;
        for(int i = 0;i<n;i++){
            int x=a.sqbitnode[i];
            int lk=a.sqbitnode[i*2+1];
            int rk=a.sqbitnode[i*2+2];
            if(x==-1)continue;
            if(x>=lk &&x<=rk)continue;
            else return false;
        }
        return true;
}
1
//答案

2023 邻接矩阵

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
//我的
#include <iostream>
#include <cstring>
using namespace std;
const int MAXV=1000;
struct MGraph
{
    int numVertices,numEdges;
    char VerticesList[MAXV];
    int Edge[MAXV][MAXV];
};
/*
思路：遍历邻接矩阵，当Edge[a][b]有值的时候说明存在一条a->b的边，也就是a的出度+1，b的入度+1，
遍历完整个邻接矩阵后即可得到所有点的入度和出度，时间复杂度为O(V²)
*/

int printVertices(MGraph G){
    int n = G.numVertices;//点的数量
    int m = G.numEdges;//边的数量
    int innum[n];//记录每个顶点的入度
    int outnum[n];//记录每个顶点的出度
    memset(innum,0,sizeof(innum));
    memset(outnum,0,sizeof(outnum));
    for(int i = 0;i<n;i++){
        for(int j = 0 ;j<n;j++)
          {
            if(m<=0) break;//剪枝
            if(G.Edge[i][j]) {
                innum[j]++;//j为终点，入度+1
                outnum[i]++;//i为起点，出度+1
                m--;//遍历完一条边
            } 
          }
    }
    int count=0;
    for(int i= 0;i<n;i++){
        if(outnum[i]>innum[i]){
            cout<<char(i+97);
            count++;
        }
    }
    return count;
}

2021 邻接矩阵

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
//自己的
#include <iostream>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXV=1000;
struct MGraph
{
    int numVertices,numEdges;
    char VerticesList[MAXV];
    int Edge[MAXV][MAXV];
};
/*
思路：不大于2的偶数，即0或者2，我们可以遍历整个数组，计算每个顶点的度，然后再遍历一遍存储度的数组，
当度为奇数的顶点个数超过2就return 0，如果最后结果是2或者0就break；同时由于是无向图，数组为对称矩阵，
可以采用压缩存储的思路减少遍历的数组元素
时间复杂度O(v²)空间复杂度O(V);
*/
int IsExistEL(MGraph G){//假设不存在
        int n = G.numVertices,m=G.numEdges;//用n存储顶点数，m存储边数
        int dexnum[n];
        memset(dexnum,0,sizeof dexnum);
        for(int i = 0;i<n;i++){
            for(int j = 0 ;j<i+1;j++){
                if(m == 0) break;
                if(G.Edge[i][j] && G.Edge[i][j]!=INF) {
                    dexnum[i]++;
                    dexnum[j]++;
                    m--;
                }
            }
        }
        int count = 0;
        for(int i = 0;i<n;i++){
                if(count >2) return 0;
                if(dexnum[i]%2) count++;
        }
        if(count ==0 || count == 2)return 1;
        else 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
//答案
#include <iostream>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXV=1000;
struct MGraph
{
    int numVertices,numEdges;
    char VerticesList[MAXV];
    int Edge[MAXV][MAXV];
};
int IsExistEL(MGraph G){//假设不存在
        int degree;
        int count = 0;
        for(int i = 0;i<G.numVertices;i++){
            degree =0;
            for(int j = 0;j<G.numVertices;j++)
                degree+=G.Edge[i][j];
            if(degree%2) count ++;
        }
        if(count==0 ||count==2)return 1;
        else return 0;
        
}

2024 拓扑序列

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
//自己的
时间复杂度O(n²)空间复杂度O(1)
#include <iostream>
#include <cstring>
using namespace std;
const int MAXV=1000;
struct MGraph
{
    int numVertices,numEdges;//图的顶点数和有向边数
    char VerticesList  [MAXV];//顶点表
    int Edge[MAXV][MAXV];//邻接矩阵，无权图
};
/*
思路：拓扑序列唯一，说明每次可以加入拓扑序列的入度为0的点是唯一的，然后同时说明拓扑序列存在，
因此只需要判断每次入度为0的点是否唯一，且当入度为0的点为0的时候，是否还有顶点没有加入拓扑序列，如果全部加入，
则存在唯一的拓扑序列
*/
int uniquely(MGraph G){
    int n =G.numVertices;
    int d[n];//存储每个顶点的入度
    memset(d,0,sizeof d);
    for(int j = 0;j<n;j++)//遍历每个顶点
        for(int i = 0;i<n;i++)//每个顶点和其他顶点是否有入边
            d[j]+=G.Edge[i][j]; 
        //找到入度为0的点
    int hh=-1;
    for(int k = 0;k<n;k++){//n个点循环n次
        int dot ;
        for(int i = 0;i<n;i++){//找到入度为0的点加入拓扑序列
            if(!d[i])
            {
                ++hh;//加入拓扑序列
                dot = i;
                d[i]=-1;//从图中删除点i
            }
           } 
            if(hh!=k) return 0;//按理来说一次加入一个入度为0的点，从而拓扑序列唯一，如果加入两个，说明不唯一
        for(int j = 0;j<n;j++)
            if(G.Edge[dot][j]) d[j]--;//从图中删除该点为起点的边
    }
    if(hh==(n-1)) return 1;//每个点都加入了拓扑序列
    else return 0;//有点没有加入拓扑序列


}

2016 排序

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
//自己的
#include <iostream>
using namespace std;
/*
思路：将集合排序，然后将较小的一半当作A1，较大的一般当作A2，即符合题目的要求,时间复杂度O(nlogn)，空间复杂度O(n)
*/
void quick_sort(int a[],int l,int r){
    if(l>=r)return ;
    int i = l-1,j=r+1;
    int x = a[l+r>>1];
    while (i<j)
    {
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j)swap(a[i],a[j]);
    }
    quick_sort(a,l,j),quick_sort(a,j+1,r);
    
}
void grouping(int n,int a[]){
        quick_sort(a,0,n-1);
        int n1=n>>1;//小半边
        int n2=n-n1;//大半边
        int a1[n1];//小
        int a2[n2];//大
        for(int i = 0;i<n1;i++) a1[i]=a[i];//小
        for(int i = n1,j=0;i<n;i++,j++)a2[j]=a[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
28
29
30
31
32
33
34
35
36
37
38
39
40
//答案
#include <iostream>
using namespace std;
/*
思路：将集合排序，然后将较小的一半当作A1，较大的一般当作A2，即符合题目的要求,时间复杂度O(nlogn)，空间复杂度O(n)
*/
int setPartition(int a[],int n){
    int pivot,low = 0,low1=0,high=n-1,high1=n-1,flag=1,k=n>>1,i;
    //枢纽值，第一组的起点和终点，第二组的起点和终点，判断是否退出循环，中间值的位置
    int s1=0,s2=0;//大小两个组的和
    while (flag)
    {
        pivot=a[low];//第一个值为枢纽
        while(low<high){//双指针分组
            while(low<high && a[high]>=pivot) --high;
            if(low!=high) a[low]=a[high];
            while(low<high && a[low]<=pivot) ++low;
            if(low!=high) a[high]=a[low];
        }
        a[low]=pivot;//把枢轴值放到正确位置
        if(low == k-1)//如果数周是第n/2小的位置，划分成功
            flag =0;
        else{
            if(low <k-1)//说明该枢纽值属于较小的一边,继续划分右半部分
               {
                 low1=++low;//右半部分从枢轴右端开始（参考二分）
                high=high1;//右半部分的右端是n
               }
            else{//说明枢轴属于较大的一边，继续划分左半部分
                low = low1;
                high1=--high;
            }
            
        }
    }
    for(int i = 0;i<k;i++)s1+=a[i];
    for(int i = k;i<n;i++)s2+=a[i];
    return s2-s1;    

}

YXC版强化

时间复杂度、矩阵展开；排序、进位制

时间、空间复杂度

  • 只考虑次数不考虑常数
  • 常见复杂度
    • O(1)
    • O(n)
    • O(n^k)
    • O(logn)
    • O(nlogn)
    • O(根号n)

特殊矩阵的展开

  • 给出展开方式，求下标位置

  • 可以先列出每行的元素个数，然后求和，是第几个元素，然后从0开始就-1

线性表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//定义链表结点
struct Node{
    int val;
    Node *next;//双链表还要加*pre
}
//创建链表
Node * head = new Node();
//遍历链表
void print(Node * head)
{
    for(auto p = head;p;p=p->next)
        cout<<p->val <<' ';
    cout<<endl;
}
//head不是一个结点，head存的是第一个结点的地址

栈与队列

  • 栈的链式存储

    • 头结点当栈顶，尾结点当栈底，头插法，头删

  • 队列的链式存储

    1
    2
    3
    4
    5
    //队尾指针指向下一个要存的位置
    node *front = new Node(),*rear=front;
    rear->val=1;
    rear->next=new node();
    rear=rear->next;

  • 只有需要回到上一层才需要用到栈，尾递归不涉及栈

  • 栈dfs，队列bfs

  • 表达式求值

    • 两个栈，一个用来存操作数，一个存操作符
    • 数栈遇到数则压栈
      • 运算符栈遇到（压栈，遇到）操作到（
      • ±*/操作到遇到（或者栈顶优先级<当前
      • 操作完运算符栈，数栈栈顶就是答案
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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <stack>

using namespace std;

stack<char> op;
stack<int> num;

void eval()
{
    auto b = num.top(); num.pop();
    auto a = num.top(); num.pop();
    auto c = op.top(); op.pop();

    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);
}

int main()
{
    string s;
    cin >> s;

    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    for (int i = 0; i < s.size(); i ++ )
    {
        if (isdigit(s[i]))
        {
            int j = i, x = 0;
            while (j < s.size() && isdigit(s[j]))
                x = x * 10 + s[j ++ ] - '0';//把连续的数字字符转成整数
            num.push(x);
            i = j - 1;
        }
        else if (s[i] == '(') op.push(s[i]);
        else if (s[i] == ')')
        {
            while (op.top() != '(') eval();
            op.pop();
        }
        else
        {
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[s[i]])
                eval();
            op.push(s[i]);
        }
    }

    while (op.size()) eval();
    cout << num.top() << endl;

    return 0;
}

树

  • 二叉树节点计算的常用方法：

    • 数学归纳法

    • 递推

    • 解方程/等式代换

      • 先求点数再求边数
      • 边数=点数-1

  • 前驱：中序遍历的前一个点

  • 后继：中序遍历的后一个点

  • 树与二叉树的转换：原树中叶子节点数=转换后的树中有右孩子的结点数+1

    • 原树中叶子节点个数 = 转换后的树中有右儿子的节点数 + 1

    • 原树中分支节点个数 = 转换后的树中无右儿子的节点数 - 1

    • 转换后的树中有右儿子的节点数 = 原树中有右兄弟的节点数

    • 节点总数 = 原树中原树中叶子节点个数 + 原树中原树中分

      支节点个数 = 转换后的树中有右儿子的节点数 + 转换后的树中无右儿子的节点数

  • 森林与二叉树的转换

    • 森林中的叶节点个数=转换后二叉树中有右孩子的结点数+森林的颗树

  • 森林的前序遍历就是树二叉树的前序遍历

  • 森林的后序遍历就是二叉树的中序遍历

    • 因为只有二叉树能找到左右，森林分不出左右只能分子树和根

  • 所有节点都有0个孩子或者2个孩子的时候，前序遍历和后序遍历可以唯一确定一个二叉树，但是当有结点只有1个孩子的时候，前序遍历和后序遍历不可以唯一确定一个二叉树

  • 二叉搜索树(BST)：中序遍历有序的二叉树

    • 插入
      • O(logn)
      • 每次插入必然插入到叶子节点
    • 删除
      • O(logn)
      • 叶子节点直接删除
      • 只有左子树或者右子树，用左子树或者右子树的根节点替换掉删除的结点
      • 左右子树皆有，用中序遍历前驱替代删除的点
    • 查找
      • O(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
68
69
70
71
72
73
74
//二叉搜索树
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int INF = 1e8;

struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(int _val): val(_val), left(NULL), right(NULL) {}
}*root;

void insert(TreeNode* &root, int x)
{
    if (!root) root = new TreeNode(x);
    else if (x < root->val) insert(root->left, x);
    else insert(root->right, x);
}

void remove(TreeNode* &root, int x)
{
    if (!root) return;
    if (x < root->val) remove(root->left, x);
    else if (x > root->val) remove(root->right, x);
    else
    {
        if (!root->left && !root->right) root = NULL;
        else if (!root->left) root = root->right;
        else if (!root->right) root = root->left;
        else
        {
            auto p = root->left;
            while (p->right) p = p->right;
            root->val = p->val;
            remove(root->left, p->val);
        }
    }
}

int get_pre(TreeNode* root, int x)
{
    if (!root) return -INF;
    if (root->val >= x) return get_pre(root->left, x);
    return max(root->val, get_pre(root->right, x));
}

int get_suc(TreeNode* root, int x)
{
    if (!root) return INF;
    if (root->val <= x) return get_suc(root->right, x);
    return min(root->val, get_suc(root->left, x));
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int t, x;
        cin >> t >> x;
        if (t == 1) insert(root, x);
        else if (t == 2) remove(root, x);
        else if (t == 3) cout << get_pre(root, x) << endl;
        else cout << get_suc(root, x) << endl;
    }

    return 0;
}

  • 平衡二叉树

    • 平衡因子：左-右
    • 左旋右旋只改变高度不改变中序遍历顺序

  • 表达式树是二叉树，分支节点都是运算符，叶子节点都是数字/字符

    • 从左到右，按照顺序构造
    • 前缀表达式：表达式树的前序遍历
    • 后缀表达式：表达式树的后序遍历

  • 如何判断关键字序列能否构成二叉排序树中的查找路径

    • 画出序列构成的二叉树，然后进行中序遍历看是否有序

  • 哈夫曼树

    • 前缀编码→所有编码均对应叶节点
    • 从下往上构造一棵树，每次合并根节点值最小的子树
    • 所有点的度数不为1
    • 一定有一个最优解，使得权值最小的两个点互为兄弟

  • 并查集

    • 按秩合并就是按照大小，小树合到大树

图

  • 邻接多重表理论上找无向图的反向边比邻接表方便
  • 十字链表是对邻接矩阵的优化，实际上也可以存无向图
  • 邻接矩阵和十字链表无法存重边，邻接表和邻接多重表可以存重边
  • 三元组表也能存重边
  • 判断dijkstra算法最短路径的快捷方法
    • 直接看每个点到起点的距离，然后从小到大排序
  • 判断连通性

查找

有序线性表的查找

二分查找

  • (low+high)/2下取整
  • (low+high+1)/2上取整
    • 二分要保持一致，上取整就一直上取整，下取整就一直下取整
    • 小于则右端点=mid-1，大于则右端点=mid+1
    • 平均成功查找长度=log(n+1)-1
  • 折半查找中序遍历有序
  • 判定折半查找判定树：看上下取整是否一致，也就是说上取整要一直上取整，下取整要一直下取整
    • 快速判定：要么左边一直比右边节点多，要么右子树一直比左子树结点多

分块查找

B树和B+树

  • 主要用于硬盘或者文件系统管理、数据库
    • 读写慢
    • 文件大
  • B树中间的点有信息
  • 而B+树中间的点仅作区分分类用，不保留信息，信息全部存储在根节点
    • 全部放在叶节点，局部性很好，方便一块读，全在同一层
  • 上取整（m/2）-1=m/2下取整

  • B树向上分裂的时候，中间节点存在上一层的结点，但是B+树向上分裂的时候，由于所有信息存储在叶节点，所以上面分离出去的只是索引节点，而分裂出来的两组叶节点中，双亲结点的信息存储在右边那一组
    • 如果分裂的是索引节点，则直接分裂不用存多次
    • 索引节点不需要重复
    • B+树每次数据查询的次数都一样，因为都是查找到叶节点
  • B树的删除情况
    • 兄弟够借
      • 删左左旋
      • 删右右旋
    • 兄弟不够借
      • 删左，合并双亲节点一起左旋
      • 删右，合并双亲结点一起右旋
  • B树和B+树的区别：
    • B树的关键字和子树个数差1，而B+树关键字个数=子树个数

哈希表

  • 拉链法又称为开散列法
  • 开放寻址法又称为闭散列法
  • 负载因子=已有元素数/数组长度
    • 负载因子越低，效率越高
  • 哈希函数
    • 乘余取整法：n*(A * x的小数部分)，A是0-1之间的数
    • 平方取中法：先平方，然后取中间几位
    • 基数转换法：换成其他进制，然后取其中几位
  • 线性探测法、二次探查法、随机探查法，都容易产生二级聚集问题
  • 查找效率指的是时间，存储效率指的是空间
  • 哈希表的查找失败长度是针对整数域来讲的，也就是说key%M，分母就是1/M，分子0~M-1的对应失败查找次数，要查到空才停止

红黑树

  • 所有根节点都是黑色不是指的实结点，而是指的空黑叶节点
  • 黑路同，值得也是从任意节点出发，到达任一空叶节点的路径上经过的黑节点数量相同（包括黑空叶节点）
  • 所有操作的时间复杂度都是log(n)
  • 红黑树的删除：单子树直接删，双子树用后继替代，接着递归调整直到符合红黑树的性质

查找算法时间复杂度表

排序

排序算法对比表

算法 最好时间复杂度 平均时间复杂度 最坏时间复杂度 空间复杂度 稳定性 适用
直接插入排序 O(n)（表中元素有序） O(n²)（表中元素逆序） O(n²) O(1) 稳定 顺序存储和链式存储的线性表
基本有序的排序表和数据量不大的排序表
链式存储结构上无需移动元素
折半插入排序 先比较左右两边大小：O(n)
不比较直接二分查找：O(logn)		 O(n²) O(n²) O(1) 稳定 顺序存储的线性表
数据量不算很大的排序表
冒泡排序 O(n) O(n²) O(n²) O(1) 稳定 顺序存储和链式存储的线性表
简单选择排序 O(n²) O(n²) O(n²) O(1) 不稳定 顺序存储和链式存储的线性表
关键字较少的情况
希尔排序 — O(n^1.5) O(n²) O(1) 不稳定 顺序存储的线性表
代码量小，在内存非常宝贵的情况下很有用
快速排序 O(n log n) O(n log n) O(n²) O(log n)
最好O(log n)
最坏O(n)		 不稳定 顺序存储的线性表
不适用于对原本有序的记录序列进行排序
堆排序 O(n log n) O(n log n) O(n log n) O(1) 不稳定 顺序存储的线性表
适用于关键字较大的情况，关键字较少，不建议使用堆排序
适用于求解top-k问题
找maxk，建立小根堆，找mink，建立大根堆
二路归并排序 O(n log n) O(n log n) O(n log n) O(n) 稳定 顺序存储的线性表和链式存储的线性表
归并排序的递归顺序与二叉树的后序遍历相同
桶排序 O(n + m) O(n + m) O(n + m) O(n + m) 稳定 按桶分区域，区域间有序，再对区域内进行排序，参考分块查找，只不过要对块内进行排序
适用于数据量很大的情况
比如可以将100w个数据分成1000个桶，然后分别对每个桶进行排序，然后将结果合并
基数排序 O(d(n + r)) O(d(n + r)) O(d(n + r)) 顺序基数排序O(n + r)
链式基数排序O®		 稳定 顺序存储和链式存储的线性表
如果关键字的取值范围很大，采用最高位优先
计数排序 O(n+k) O(n+k) O(n+k) O(n+k)数组给定的情况下O(n) 稳定 顺序存储的线性表
适用于序列中的元素是整数且元素范围不能太大，否则会造成辅助空间的浪费
排序算法 平均时间复杂度 最好时间复杂度 最坏时间复杂度 空间复杂度 稳定性 就地性 适用数据对象 比较次数与初始状态关系 移动次数与初始状态关系 排序趟数与初始状态关系
插入排序 O(n²) O(n) O(n²) O(1) ✔ 稳定 原地 数组/链表 有关 有关 无关
折半插入 O(n²) O(n²) O(n²) O(1) ✔ 稳定 原地 数组 无关 有关 无关
希尔排序 O(n^1.3) O(n log n) O(n²) O(1) ✘ 不稳定 原地 数组 有关 有关 无关
冒泡排序 O(n²) O(n) O(n²) O(1) ✔ 稳定 原地 数组/链表 有关 有关 有关
快速排序 O(n log n) O(n log n) O(n²) O(log n) ✘ 不稳定 原地 数组 有关 有关 有关
选择排序 O(n²) O(n²) O(n²) O(1) ✘ 不稳定 原地 数组/链表 无关 有关 无关
堆排序 O(n log n) O(n log n) O(n log n) O(1) ✘ 不稳定 原地 数组 有关 有关 无关
归并排序 O(n log n) O(n log n) O(n log n) O(n) ✔ 稳定 非原地 数组/链表 有关 无关(非原地算法，在辅助空间进行排序，而非在原始数组上直接进行交换) 无关
计数排序 O(n+k) O(n+k) O(n+k) O(n+k) ✔ 稳定 非原地 数组 无关 无关 无关
基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) 顺序基数排序O(n + r)
链式基数排序O®		 ✔ 稳定 非原地 数组 无关 无关 无关
桶排序 O(n+k) O(n+k) O(n²) O(n+k) ✔ 稳定 非原地 数组 无关 无关 无关

快排

  • 第一层分界点不是端点，第二层必然存在左右半边，因此必然至少有三个点在正确的位置上
  • 第一层分界点是端点，第二层只有一个区间，因此该区间内只有一个分界点，因此至少有两个点在正确的位置上，且其中一个点为端点

堆排

  • 堆排只要求子树范围内，根结点最大，二叉排序树要求严格左中右递增

外部排序

  • ①预处理
    • 置换选择排序生成尽量长的串（内存里操作）
  • ②归并（k路归并）
  • 流程
    • ①置换选择排序生成初始串
    • ②哈夫曼树选择要进行归并的k路
    • ③败者树进行k路归并

算法题刷题

题表：

散题：

算法积累

从无序顺序表中删除所有值为x的元素

  • 时间复杂度O(n)，空间复杂度O(1)

1
2
3
4
5
6
7
8
9
10
void delete_x(vector<int>&nums,int x){
    int i;
    int j;
    for(i = 0;i<num.size();i++){
        if(nums[i]!=x){
            nums[j]=nums[i];
            j++;
        }
    }
}

无序表删除值为s到t之间的所有元素

  • 思路：快慢指针

1
2
3
4
5
6
7
void delte_s_t(seqlist & l,int s,int t){
	for(int i = 0,j=0;i<l.length;i++){
        if(l.data[i]<s ||l.data[i]>t)
            l.data[j++]=l.data[i];
    }
    l.length=j;
}

有序表中删除值为s到t之间的所有元素

  • 思路：找到第一个和最后一个值处于该区间的元素下标，然后将该区间的后面的元素依次前移即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void delete(seqlist &l,int s,int t){
    int i =0;
    int j = length-1;
    while(l.data[i]<s &&i<length)
        	i++;
    while(l.data[j]>t &&j>=0)
        	j--;
    if(i<j){
        int d= j-i+1;
        j++;
        while(j<nums.size()){
			l.data[i++]=l.data[j];
            j++;
        }
        l.length -=d;
    }
    else{
        return;
    }
}

删除重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
int remove(seqlist &l){
    if(l.length == 0)return 0;
    int fast = 1,slow =1;
    while(fast<length){
        if(l.data[fast]!=l.data[fast-1]){
            l.data[slow]=l.data[fast];
        ++slow;
        }
        ++fast;
    }
    length =slow;
    return length;
}

数组逆置

1
2
3
4
5
6
7
8
9
void reverse(vector<int> &nums){
    int i =0,j=nums.size()-1,tmp;
    while(i<j){
        tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
        ++i,--j;
    }
}

删除倒数第k个数

  • 快慢指针，快指针先运行k步
1
2
3
4
5
6
7
8
9
10
11
12
13
listnode* remove(listnode *head,int n)
{
    listnode *left=head,*right=head;
    while(n--){
        right=right->next;
    }
    while(right->next){
        left=left->next;
        right=right->next;
    }
    left->next=left->next->next;
    return head;
}

带有头结点的链表逆序输出每个节点的值

1
2
3
4
5
6
7
8
9
void print(Lnode *L){
    if(L->next=nullptr){
        cout<<L->data<<" ";//递归出口
    }
    print(L->next);
}
void printlist(Lnode *head){
    print(head->next);
}

反转链表

  • 头插法
1
2
3
4
5
6
7
8
9
10
11
Lnode* reverse(Lnode *&L){
    Lnode *p=L->next,*r;
    L->next=nullptr;
    while(p){
        r=p->next;
        p->next=L->next;
        L->next=p;
        p=r;
    }
    return L;
}//时间复杂度O(n)，空间复杂度O(1)
  • 迭代法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Lnode* reverse(Lnode *&L){
    Lnode *pre=nullptr,*cur = L;
    while(cur){
        Lnode *next=cur->next;
        cur->next=pre;
        pre=cur;
        cur=next;
    }
    return pre;
}
Lnode *reverselist(Lnode *&L){
    L->next=reverse(L->next);
    return L;
}//时间复杂度O(n),空间复杂度O(1)
//反转结束后，从原链表上看，pre指向反转这一段的最后一个节点，cur指向反转这一段后序的下一个结点。

反转部分链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Lnode* reverselist(Lnode *&head,int left,int right){
    Lnode *p0=head;
    for(int i = 0;i<left-1;++i){
        p0=p0->next;//找到链表中待反转部分的前一个结点
    }
    Lnode *pre =nullptr,*cur = p0->next;
    for(int i = 0;i<right-left+1;i++){
        Lnode *next = cur->next;
        cur->next=re;
        pre=cur;
        cur=next;
    }
    //中间反转完毕，和原链表连接
    p0->next->next=cur;//中间部分反转完毕后cur指向中间部分的最后一个结点，此处进行最后一次反转
    p0->next=pre;//反转完之后从原链表视角看，pre指向待反转链表的最后一个结点，也就是反转后的第一个结点
    return head;
}

快慢指针应用

链表中间结点

1
2
3
4
5
6
7
8
9
10
Lnode* middlenode(Lnode *head){
  Lnode *fast,*slow;
    fast=slow=head->next;
    while(fast && fast->next){
        fast = fast ->next->next;
        slow = slow->next;
        
    }
    return slow;
}

删除链表中间结点

1
2
3
4
5
6
7
8
9
10
11
12
Lnode * deletemiddle(Lnode *head){
    if(head->next)return nullptr;
    Lnode *fast=head->next,*slow=head->next,*pre=head->next;
    while(fast &&fast->next){
        pre=slow;
        slow=slow->next;
        fast=fast->next->next;
    }
    pre->next=slow->next;
    delete(slow);
    return head;
}

判断链表中是否存在环

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
//单纯判断链表中是否存在环
bool hascycle(Lnode *head){
    Lnode *fast=head->next,*slow =head->next;
    while(fast && fast->next){
        fast=fast->next->next;
        slow =slow->next;
        if(fast==slow){
            return true;
        }
    }
    return false;
}
//返回开始进入环的第一个结点
Lnode *detectcycle(Lnode *head){
    Lnode *fast=head->next,*slow=head->next;
    while(fast && fast->next){
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow){
            Lnode *p=head->next;
            while(p!=slow){//如果p指针和慢指针相遇，说明次数二者都到了环的入口处
                p=p->next;
                slow=slow->next;
            }
            return slow;
        }
    }
    return nullptr;
}
//求解环的长度
int lengthcycle(Lnode *head){
    Lnode *fast=head->next,*slow=head->next;
    while(fast && fast->next){
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow){//第一次相遇       
            slow=slow->next;
            int length =1;
            while(fast!=slow){
                slow=slow->next;
                length++;
            }
            return length;//第二次相遇，跳出循环
            
        }
    }
}

从无序数组中删除所有值为x某元素

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int k = 0; // 下一个要写入的位置
        for (int x : nums) {
            if (x != val) nums[k++] = x;
        }
        return k;
    }
};

重排链表（快慢指针找中间节点/反转链表/链表的交叉连接）

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
Lnode* findmiddle(Lnode *&head){
    Lnode *fast=head->next;
    Lnode *slow=head->next;
    while(fast&&fast->next){
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}
Lnode* reverse(Lnode *&head){
    Lnode * pre=nullptr;
    Lnode * cur=head;
    while(cur){
        Lnode* next=cur->next;
        cur->next=pre;
        pre=cur;
        cur=next;
    }
    return pre;
}

void reverselist(Lnode *&head){
    Lnode* middle=findmiddle(head);
    Lnode* head2=reverse(middle);
    Lnode*head1=head->next;
    while(head2){
        Lnode*tmp1=head1->next;
        Lnode*tmp2=head2->next;
        head1->next=head2;
        head2->next=tmp1;
        head1=tmp1;
        head2=tmp2;
    }
}

回文链表

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
lnode *findmiddle(lnode *head){
    lnode*fast=head->next;
    lnode*slow=head->next;
    while(fast &&fast->next){
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}//找中间节点模板
lnode *reverselist(lnode *&head){
    lnode *pre=nullptr;
    lnode *cur=head;
    while(cur){
        lnode *next=cur->next;
        cur->next=pre;
        pre=cur;
        cur=next;
    }
    return pre;
}

bool isloop(lnode *head){
    lnode *mid=findmiddle(head);
    lnode *p=reverselist(mid);
    lnode*head1=head->next;
    while(p){
        if(p->data!=head1->data)
            return false;
        p=p->next;
        head1=head1->next;
    }
    return true;
}

链表排序

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
lnode *sortlist(listnode *head){
    return mergesort(head);
}
lnode *mergesort(lnode *head){
    if(head==nullptr||head->next==nullptr)return head;
    lnode*fast=head,*slow=head;
    while(fast &&fast->next){
        fast=fast->next->next;
        slow=slow->next;
        pre=slow;
    }
    r=mergesort(slow);
    pre->next=nullptr;
    l=mergesort(head);
    return mergetwolist(l,r);
}
lnode*mergetwolist(lnode * list1,lnode* list2){
    lnode*dummy =new lnode(0,nullptr);
    lnode *p=list1,*q=list2,*cur=dummy;
    while(p&&q){
        if(p->val<q->val){
            cur->next=p;
            cur=cur->next;
            p=p->next;
        }
        else{
            cur->next=q;
            cur=cur->next;
            q=q->next;
        }
    }
    if(q==nullptr) cur->next=q;
    else{
        cur->next=q;
    }
    return dummy->next;
}

合并升序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
lnode *mergelist(lnode*list1,lnode*list2){
	if(list1->next==nullptr)return list2;
    if(list2->next==nullptr)return list1;
    lnode *l=new lnode(0,nullptr);//创建一个新链表
    lnode *head1=list1->next;lnode*head2=list2->next;
    lnode*tail=l;
    while(head1&&head2){
        if(head1->data<head2->data){
            tail->next=head1;
            tail=head1;
            head1=head1->next;
        }
        else{
            tail->next=head2;
            tail=head2;
            head2=head2->next;
            
            
        }
    }
	tail->next=(head1==nullptr)? head2:head1;//耳目运算符，如果跳出循环后list1为空，将list2剩余部分接到cur后面，否则接另一条的剩余部分；
    return L;
}

表达式求值

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

using namespace std;

stack<char> op;
stack<int> num;

void eval()
{
    auto b = num.top(); num.pop();
    auto a = num.top(); num.pop();
    auto c = op.top(); op.pop();

    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);
}

int main()
{
    string s;
    cin >> s;

    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    for (int i = 0; i < s.size(); i ++ )
    {
        if (isdigit(s[i]))
        {
            int j = i, x = 0;
            while (j < s.size() && isdigit(s[j]))
                x = x * 10 + s[j ++ ] - '0';//把连续的数字字符转成整数
            num.push(x);
            i = j - 1;
        }
        else if (s[i] == '(') op.push(s[i]);
        else if (s[i] == ')')
        {
            while (op.top() != '(') eval();
            op.pop();
        }
        else
        {
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[s[i]])
                eval();
            op.push(s[i]);
        }
    }

    while (op.size()) eval();
    cout << num.top() << 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <stack>

using namespace std;

stack<char> op;

void eval()
{
    auto c = op.top(); op.pop();
    cout << c << ' ';
}

int main()
{
    string s;
    cin >> s;

    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    for (int i = 0; i < s.size(); i ++ )
    {
        if (isdigit(s[i]))
        {
            int j = i, x = 0;
            while (j < s.size() && isdigit(s[j]))
                x = x * 10 + s[j ++ ] - '0';
            cout << x << ' ';
            i = j - 1;
        }
        else if (s[i] == '(') op.push(s[i]);
        else if (s[i] == ')')
        {
            while (op.top() != '(') eval();
            op.pop();
        }
        else
        {
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[s[i]])
                eval();
            op.push(s[i]);
        }
    }

    while (op.size()) eval();

    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
//O(n²)
//
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     string val；
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 */
class Solution {
public:
    string dfs(TreeNode* root) {
        if (!root) return "";
        if (!root->left && !root->right) return root->val;
        return '(' + dfs(root->left) + root->val + dfs(root->right) + ')';
    }

    string expressionTree(TreeNode* root) {
        return dfs(root->left) + root->val + dfs(root->right);
    }
};

//O(n)
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     string val；
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 */
class Solution {
public:
    string ans;

    void dfs(TreeNode* root) {
        if (!root) return;
        if (!root->left && !root->right) ans += root->val;
        else
        {
            ans += '(';
            dfs(root->left);
            ans += root->val;
            dfs(root->right);
            ans += ')';
        }
    }

    string expressionTree(TreeNode* root) {
        dfs(root->left), ans += root->val, dfs(root->right);
        return ans;
    }
};

哈夫曼树

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
//O(nlogn)
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);

    priority_queue<int, vector<int>, greater<int>> heap;
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        heap.push(x);
    }

    int res = 0;
    while (heap.size() > 1)
    {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        res += a + b;
        heap.push(a + b);
    }

    printf("%d\n", res);
    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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head==nullptr)return head;
            ListNode* odd = head;
            ListNode* evenhead=head->next;
            ListNode* even=evenhead;
            while(even && even->next){
                    odd->next=even->next;
                    odd=odd->next;
                    even->next=odd->next;
                    even=even->next;

            }
            odd->next=evenhead;
            return head;
    }
};

定义和基本操作模板

单链表

单链表结点的定义

1
2
3
4
struct Lnode{
    int data;
    Lnode *next;
};

单链表的初始化

1
2
3
4
5
6
7
8
9
10
11
12
//有头结点的单链表的初始化
Lnode init(){
    Lnode *head = new Lnode;
    head->next=nullptr;
    head->data=0;
    return head;
}
//无头结点的单链表的初始化
Lnode init(){
    Lnode *head =nullptr;
    return head;
}

单链表求表长（不含头结点）

1
2
3
4
5
6
7
8
9
int listlength(Lnode *l){
    Lnode p = l->next;//指向第一个结点
    int length = 0;
    while(p!=nullptr){
        ++length;
        p=p->next;
    }
    return length;
}//时间复杂度O(n)

单链表的按位查找

1
2
3
4
5
6
7
8
9
10
11
12
Lnode* getElem(Lnode *L,int i){
    Lnode p = L->next;
    if(i==0)return L;
    else if(i<0)return nullptr;
    else{
        while(p!=nullptr &&i!=0){
            p=p->next;
            i--;
        }
        return p;
    }
}

单链表的按值查找

1
2
3
4
5
6
Lnode * locateElem(Lnode *l,int target){
    Lnode p=l->next;
    while(p!=nullptr &&p->data !=target)
        p=p->next;
    return p;
}

头插法建立单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Lnode *list_head_insert(Lnode *&l){
    Lnode *newnode;
    int x;
    L = new Lnode;
    L->next=nullptr;
    cin>>x;
    while(x!=-1){
        newnode = new Lnode;
        newnode ->data=x;
        newnode->next=l->next;
        l->next=newnode;
    }
    return L;
}//时间复杂度O(n)

尾插法建立单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Lnode * list_tail_insert(Lnode *&L){
    Lnode *newnode,tail=L;
    int x;
    L =new Lnode;
    L->next=nullptr;
    cin >>x;
    while(x!=1){
        newnode = new Lnode;
        newnode ->data=x;
        newnode ->next=nullptr;
        tail->next=newnode;
        tail=tail->next;
    }
    return L;
}//时间复杂度为O(n)

插入节点操作

1
2
3
4
5
6
7
8
9
10
11
12
13
bool insertnode(Lnode *&L){
    Lnode *newnode,*prenode,*curnode;
    int x;
    if(i<=0)return false;
    prenode =getElem(L,i-1);
    if(prenode ==nullptr)return false;
    curnode =prenode->next;
    newnode =new Lnode;
    newnode->data=x;
    newnode ->next=curnode;
    prenode->next=newnode;
    return true;
}//时间复杂度O(n)

删除节点操作

1
2
3
4
5
6
void deletenode(Lnode *p){
	p->data=p->next->data;
    Lnode *q=p->next;
    p->next=q->next;
    delete q;
}

双链表

双链表的数据结构定义

1
2
3
4
5
6
struct dnode{
    int data;
    dnode *pre,*next;
    
};

双链表的插入

1
2
3
4
q->next=p->next;
p->next->pre=q;
p->next=q;
q->pre=p;

双向链表的删除操作

1
2
3
p->next=q->next;
q->next->pre=p;
delete q;

循环单链表

循环单链表的初始化

1
2
3
4
5
6
7
bool init(Lnode *&head){
    head= new Lnode;
    if(L==nullptr)
        return false;
    head->next=head;
    return true;
}

循环双链表

循环双链表初始化

1
2
3
4
5
6
7
8
bool init(dnode *&head){
    head = new dnode;
    if(l==nullptr)
        return false;
    head->pre=head;
    head->next=head;
    return true;
}

静态链表

静态链表的定义

1
2
3
4
5
#define maxsize 50
struct slinklist{
    int data;
    int next;
}list[maxsize];

二叉树

二叉树的顺序存储

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
//定义与初始化
struct treenode{
    int data;
    bool isempty;
};
//初始化顺序存储的二叉树，所有节点标记为空
void init(treenode t[],int length){
    for(int i = 0;i<length;i++)
        t[i].isempty=true;
    
}
int main(){
    treenode t[100];
    init(t,100);
}
//判空
bool isempty(treenode t[],int length,int index){
    if(index>=length ||index <1)return true;
    return t[index].isempty;
}
//找左孩子
int getlkid(treenode t[],int lenght,int index){
    int lkid=index*2;
    if(isempty(t,length,lkid))return -1;
    return lkid;
}
//找右孩子
int getrkid(treenode t[],int lenght,int index){
    int rkid=index*2+1;
    if(isempty(t,length,rkid))return -1;
    return rkid;
}
//找双亲
int getparent(treenode t[],int lenght,int index){
    if(index==1)return -1
    int parent=index/2;
    if(isempty(t,length,parent))return -1;
    return parent;
}
//先序遍历
void pre(treenode *t,int length,int index){
    if(isempty(t,length,index))
        return;
    visit(t[index]);
    pre(t,length,getlkid(t,length,index));
    pre(t,length,getrkid(t,length,index));
}
//中序遍历
void mid(treenode *t,int length,int index){
    if(isempty(t,length,index))
        return;
    mid(t,length,getlkid(t,length,index));
    
    visit(t[index]);
   
    mid(t,length,getrkid(t,length,index));
}
//后序遍历
void post(treenode *t,int length,int index){
    if(isempty(t,length,index))
        return;
    post(t,length,getlkid(t,length,index));
    post(t,length,getrkid(t,length,index));
    visit(t[index]);
   
    
}

二叉树的链式存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct treenode{
    int data;
    treenode *lkid,*rkid;
};
//定义一颗空树
treenode * root =nullptr;
//插入根节点
root= new treenode;
root->data=1;
root->lkid=nullptr;
root->rkid=nullptr;

//插入新节点
treenode *p=new treenode(2);
p->lkid=nullptr;
p->rkid=nullptr;
root->lkid=p;

迭代法先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> pre(treenode* root){
    stack<treenode*> st;
    vector<int>result;//用于返回遍历序列
    if(root=nullptr)return result;
    st.push(root);
    while(!st.empty()){
        treenode *node=st.top();//中
            st.pop();//取出根节点然后弹出
       if(node!=nullptr){
        result.push_back(node->val);//访问并处理当前节点，本层递归处理，将结点加入先序序列
        if(node->right)st.push(node->right);//右孩子入栈（空节点不入栈），后递归处理右子树
        if(node->left)st.push(node->left);//左孩子入栈，先递归处理左子树（栈的特性是后进先出）
       }
    }
    return result;
}

迭代法中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> inorder(treenode *root){
    vector<int>result;//定义一个结果数组用于存放中序遍历序列
    stack<treenode*>st;
    treenode* cur=root;//cur为遍历指针
	while(cur!=nullptr ||!st.empty()){//遍历指针不为0且栈不为空
        if(cur!=nullptr){//指针来访问节点，访问到最底层
            st.push(cur);//将访问的结点放进栈
            cur=cur->left;//左
        }
        else{//当前结点为空，说明上一个结点没有左子树
            cur=st.top();//此时栈里面保存着从跟根节点沿着左子树一直走的结点，从栈里面弹出的数据，就是最左的结点，即要处理的数据（放进result数组里的数据）
            st.pop();
            result.push_back(cur->val);//往中序遍历序列中加入栈顶元素。此时由于栈顶为没有左子树的最左结点，弹出后cur=cur->right不存在，第二次弹出的是根节点，其实就相当于中结点
            cur=cur->right;//左中遍历完，遍历右
        }
        
    }
    return result;
}
1
2
//迭代法后序遍历的静态链表写法

迭代法后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> postorder(treenode *root){
    stack<treenode*>st;
    vector<int> result;
    if(root=nullptr)return result;
    st.push(root);
    while(!st.empty()){
        treenode *node=st.top();
        st.pop();
        result.push_back(node->val);
        if(node->left)st.push(node->left);//相对于前序遍历，左右子树遍历顺序互换（空节点不入栈）
        if(node->right)st.push(node->right);//空节点不入栈
    }
    reverse(result.begin(),reguslt.end());//将结果反转之后就是左右中的顺序了
    return result;
}

二叉树的层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> levelorder(treenode *root){
    vector<int>res;
    queue<treenode*>que;
    if(root==nullptr)return res;
    que.push(root);//将根节点入队
    while(!que.empty()){//队列非空
        treenode *cur=que.front();//取出队头
        que.pop();
        res.push_back(cur->val);
        if(cur->left!=nullptr)que.push(cur->left);
        if(cur->right!=nullptr)que.push(cur->right);
    }
    return res;
}

重建二叉树

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    unordered_map<int,int> pos;

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for (int i = 0; i < n; i ++ )
            pos[inorder[i]] = i;
        return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    TreeNode* dfs(vector<int>&pre, vector<int>&in, int pl, int pr, int il, int ir)
    {
        if (pl > pr) return NULL;
        int k = pos[pre[pl]] - il;
        TreeNode* root = new TreeNode(pre[pl]);
        root->left = dfs(pre, in, pl + 1, pl + k, il, il + k - 1);
        root->right = dfs(pre, in, pl + k + 1, pr, il + k + 1, ir);
        return root;
    }
};//上机题

二叉排序树

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

using namespace std;

const int INF = 1e8;

struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(int _val): val(_val), left(NULL), right(NULL) {}
}*root;

void insert(TreeNode* &root, int x)
{
    if (!root) root = new TreeNode(x);
    else if (x < root->val) insert(root->left, x);
    else insert(root->right, x);
}

void remove(TreeNode* &root, int x)
{
    if (!root) return;
    if (x < root->val) remove(root->left, x);
    else if (x > root->val) remove(root->right, x);
    else
    {
        if (!root->left && !root->right) root = NULL;
        else if (!root->left) root = root->right;
        else if (!root->right) root = root->left;
        else
        {
            auto p = root->left;
            while (p->right) p = p->right;
            root->val = p->val;
            remove(root->left, p->val);
        }
    }
}

int get_pre(TreeNode* root, int x)
{
    if (!root) return -INF;
    if (root->val >= x) return get_pre(root->left, x);
    return max(root->val, get_pre(root->right, x));
}

int get_suc(TreeNode* root, int x)
{
    if (!root) return INF;
    if (root->val <= x) return get_suc(root->right, x);
    return min(root->val, get_suc(root->left, x));
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int t, x;
        cin >> t >> x;
        if (t == 1) insert(root, x);
        else if (t == 2) remove(root, x);
        else if (t == 3) cout << get_pre(root, x) << endl;
        else cout << get_suc(root, x) << endl;
    }

    return 0;
}

线索二叉树的结构体定义

1
2
3
4
5
struct threadnode{
    int data;
    struct threadnode*lkid,*rkid;
    int ltag,rtag;
};

中序线索二叉树的构造

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
void inthread(threadnode*p,threadnode*pre){
    if(p!=nullptr){
        inthread(p->lkid,pre);//递归线索化左子树
        if(p->lkid==nullptr){//如果p没有左孩子，即左孩子指针为空，建立前驱线索
            p->lkid=pre;//将其指向前驱节点
            p->ltag=1;
            
        }
        else{
            p->ltag=0;
        }
        if(pre!=nullptr&&pre->rkid=nullptr){//如果pre没有右孩子，即右孩子指向空
        	pre->rkid=p;//将其右孩子指针指向p;
            pre->rtag=1;//修改标识;
        }
        else{
            pre->rtag=0;
        }
        pre=p;//左右处理完毕，更新遍历结点；表示当前节点成为刚刚访问过的结点
        inthread(p->rkid,pre);//递归线索化右子树
    }
}
void creatinthread(treadtree* root){
    threadnode *pre = nullptr;
    if(root){//非空二叉树线索化;
        inthread(root,pre);//线索化二叉树
        pre->rkid=nullptr;//处理遍历的最后一个结点，将其后继指向空;
        pre->rtag=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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//找到以p为根的子树中，第一个被中序遍历访问到的结点;
threadnode *firstnode(threadnode *p){
    //循环找到最左下结点（不一定是叶节点）
    while(p->ltag==0){
        p=p->lkid;
    }
    return p;
}
//在中序线索二叉树中找到结点p的后继节点
threadnode *nextnode(threadnode *p){
    if(p->rtag==0){//代表有右孩子
        return firstnode(p->rkid);//后继为右子树的最左下结点      
    }
    else{//rtag=1表示p结点没有右孩子，则其右孩子指针指向其后继
        return p->rkid;//直接返回后继结点
    }
}
//对中序线索二叉树进行中序遍历（利用线索化实现的非递归，空间复杂度为O(1)
void inorder(threadnode *root){
    for(threadnode *p=firstnode(root);p!=null;p=nextnode(p))
        visit(p);
}
//在中序线索二叉树里面找结点p的前驱
//找到以p为根的子树中，最后一个被中序遍历访问到的结点；
treadnode*lastnode(thread*p){
    //循环找到最右下结点（不一定是叶节点）
    while(p->rtag==0){
        p=p->rkid;
    }
    return p;
}
//在中序线索二叉树中找到结点p的前驱节点；
threadnode *prenode(threadnode *p){
    if(p->ltag==0){//表示p结点有左孩子
    	p=p->rkid;
    }
    return p;
}
//在中序线索二叉树中找到结点p的前驱节点
threadnode *prenode(threadnode *p){
    if(p->ltag==0){//表示p结点有左孩子
        return lastnode(p->lkid);//则其前驱为左子树的最右下结点; 
    }
    else{
        return p->lkid;
    }
}
void revorder(threadnode *root){
    for(threadnode *p = lastnode(root);p!=nullptr;p=prenode(p))
        visit(p);
}

先序线索化

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
// 前序线索化
void PreThread(ThreadNode* p, ThreadNode* pre) {
    if (p != NULL) {
        if (p->lchild == NULL) {  // 如果p没有左孩子，建立前驱线索
            p->lchild = pre;
            p->ltag = 1; // 修改标识，表示线索化
        } else {
            p->ltag = 0;
        }

        if (pre != NULL && pre->rchild == NULL) {  // 如果pre没有右孩子，则建立前驱结点的后继线索
            pre->rchild = p;
            pre->rtag = 1;  // 修改标识
        } else {
            pre->rtag = 0;
        }

        pre = p;  // 更新遍历结点，表示当前结点成为刚刚访问过的结点

        if (p->ltag == 0)  // 避免线索化左子树
            PreThread(p->lchild, pre);
        if (p->rtag == 0)  // 必须判断后再递归，否则会陷入死循环
            PreThread(p->rchild, pre);  // 避免线索化右子树
    }
}

void CreatePreThread(ThreadTree root) {
    ThreadNode* pre = NULL;
    if (root) {
        PreThread(root, pre);  // 线索化二叉树
        if (pre->rchild == NULL)  // 处理遍历的最后一个结点
            pre->rtag = 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
// 后序线索化
void PostThread(ThreadNode* p, ThreadNode* pre) {
    if (p != NULL) {
        PostThread(p->lchild, pre);  // 避免线索化左子树
        PostThread(p->rchild, pre);  // 避免线索化右子树

        if (p->lchild == NULL) {  // 如果p没有左孩子，建立前驱线索
            p->lchild = pre;
            p->ltag = 1;  // 修改标识，表示线索化
        } else {
            p->ltag = 0;
        }

        if (pre != NULL && pre->rchild == NULL) {  // 如果pre没有右孩子，则建立前驱结点的后继线索
            pre->rchild = p;
            pre->rtag = 1;  // 修改标识
        } else {
            pre->rtag = 0;
        }

        pre = p;  // 更新遍历结点，表示当前结点成为刚刚访问过的结点
    }
}

void CreatePostThread(ThreadTree root) {
    ThreadNode* pre = NULL;
    if (root) {
        PostThread(root, pre);  // 线索化二叉树
        if (pre->rchild == NULL)  // 处理遍历的最后一个结点
            pre->rtag = 1;
    }
}

二叉树的带权路径长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int dfs(TreeNode* root, int depth) {
        if (!root) return 0;
        if (!root->left && !root->right) return root->val * depth;
        return dfs(root->left, depth + 1) + dfs(root->right, depth + 1);
    }

    int pathSum(TreeNode* root) {
        return dfs(root, 0);
    }
};

二叉树的最大深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        return root?max(maxDepth(root->left),maxDepth(root->right))+1 : 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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     string val；
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 */
class Solution {
public:
    string ans;

    void dfs(TreeNode* root) {
        if (!root) return;
        if (!root->left && !root->right) ans += root->val;
        else
        {
            ans += '(';
            dfs(root->left);
            ans += root->val;
            dfs(root->right);
            ans += ')';
        }
    }

    string expressionTree(TreeNode* root) {
        dfs(root->left), ans += root->val, dfs(root->right);
        return ans;
    }
};

树与森林的存储

双亲表示法

1
2
3
4
5
6
7
8
9
10
11
12
#define maxsize 100

struct ptnode {
    int data;
    int parent;
};

struct ptree {
    ptnode nodes[maxsize];
    int n;
};

孩子表示法

1
2
3
4
5
6
7
8
9
10
11
12
13
struct kid{
    int index;//孩子结点
    kid*next;//下一个孩子；
};

struct treenode
{
    int data;//节点信息
    kid *firstkid;//指向第一个孩子
};

treenode tree[10];

孩子兄弟表示法

1
2
3
4
struct csnode{
    int data;
    csnode*firstchild ,*rightbro;
};

并查集

  • 朴素版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define size 13
int s[size];
//初始化并查集
void init(int s[]){
    for(int i = 0;i<size;i++){
        s[i]=-1;
    }
}
//查操作，找x所属集合（返回x所属树的根节点）
int find(int s[],int x){//x是该元素在数组中存储的值，即其父节点的数组下标
    while(s[x]>=0){//只要数组中该元素值>0，说明还未找到其所属集合根节点，继续循环寻找
        x=s[x];    
    }    
    return x;//找到所属集合根节点，此时x值为根节点下标
}
//并操作
void Union(int s[],int root1,int root2){
    if(root1==root2)
        return;//要求是不同集合才合并
    s[root2]=root1;//将根root作为根root1的自主，即合并
}
  • 路径压缩版
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
(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);//让a的祖宗节点的父节点等于b的祖宗节点，即将a插入b中

    //判断a和b是不是在同一个集合中
      if(find(a)==find(b)) puts("yes");
		else puts("no"); 

(2)维护size的并查集：

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量，只保证根节点的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所在的两个集合：
      if(find(a)==find(b))continue;//a和b在一个集合当中
    size[find(b)] += size[find(a)];//把a集合中点的个数加到b集合中
    p[find(a)] = find(b);//将a插入b
    //找到某点所在的集合的点的个数
      cout<<size[find(a)];

(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
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
#define MAX 100
struct mgraph
{
    int numvertex;//图中实际的顶点数
    int numedges;//图中实际的边数
    char vertexlist[MAX];//顶点表
    int edges[MAX][MAX];
};
//计算某个顶点的入度
int indegree(mgraph graph,char v){
    int index=-1;
    int count=0;
    //查找顶点v在定点表中的索引
    for(int i = 0;i<graph.numvertex;i++){
        if(graph.vertexlist[i]==v){
            index=i;
            break;
        }
    }
    if(index==-1){
        return -1;

    }
    for (int i = 0; i < graph.numvertex; i++)
    {
        if (graph.edges[i][index]!=0)
        {
            count++;
        }
        
    }
    return count;
    

}
//计算某个顶点的出度
int outdegree(mgraph graph,char v){
    int index=-1;
    int count=0;
    //查找顶点v在顶点表中的索引
    for (int i = 0; i < graph.numvertex; i++)
    {
        if (graph.vertexlist[i]==v)
        {
            index=i;
            break;  
        }
        
    }
    //如果没有找到顶点v，返回-1表示错误
    if (index==-1)
    {
        return -1;
    }
    //遍历邻接矩阵的该顶点对应的行，检查是否有从该顶点出发的边
    for (int i = 0; i < graph.numvertex; i++)
    {
        if (graph.edges[index][i]!=0)
        {
            count++;
        }
        
    }
    return count;
    
}

图的邻接表存储结构体

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
struct arcnode//边表节点
{
    int adjvex;//该弧指向的顶点位置
    arcnode* next;//指向下一条弧的指针
};
struct vnode//顶点表结点
{
    char data;//顶点信息
    arcnode *first;//指向第一条依附该顶点的弧的指针
}*graph[10];//定义一个拥有10个顶点的图（邻接表法）
//书上定义方式
#define MAX 1000
struct arcnode//边表节点
{
    int adjvex;//该弧指向的顶点位置
    arcnode* next;//指向下一条弧的指针
};
struct vnode//顶点表结点
{
    char data;//顶点信息
    arcnode *first;//指向第一条依附该顶点的弧的指针
};
struct graph
{
    int numvertex;
    int numedge;
    vnode vertex[MAX];  
};
//计算某个顶点的入度
int indegree(graph graph,char v){
    int index=-1;
    int count=0;
    //找到v在顺序表中的下标
    for (int i = 0; i < graph.numvertex; i++)
    {
       if (graph.vertex[i].data==v)
       {
        index=i;
        break;
       }
       
    }
    //如果未找到顶点v，返回-1表示错误
    if (index==-1)
    {
        return -1;

    }
    //遍历每个单链表，找到指向v的边，并计数
    for (int i = 0; i < graph.numvertex; i++)
    {
        arcnode*p=graph.vertex[i].first;
        while (p)
        {
            if(p->adjvex==index){
                count++;
            }
            p=p->next;
        }
        return count;
    }
    
}
//计算某个顶点的出度
int outdegree(graph graph,char v){
    //查找顶点v对应的出度
    for (int i = 0; i < graph.numvertex; i++)
    {
        if (graph.vertex[i].data==v)
        {
            int count =0;
            arcnode*p=graph.vertex[i].first;
            while (p)
            {
                count++;
                p=p->next;
            }
            return count;
        }
        
    }
    //如果查找失败，返回-1表示计算失败
    return -1;
}

十字链表存储结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define MAXV 1000
struct arcnode
{
    int tailvex;
    int headvex;
    arcnode* hlink,*tlink;
    int weight; 
};
struct vnode
{
    char data;
    arcnode * firstin,*firstout;
};
struct graph
{
    int numvertex;
    int numedge;
    vnode vertex[MAXV];
};




邻接多重表存储结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define MAXV 1000
struct arcnode
{
    int i,j;
    arcnode*ilink,*jlink;
};
struct vnode
{
    char data;
    arcnode* first;
};
struct graph
{
    int vertexnum;
    int edgenum;
    vnode vertex[MAXV];
};



基于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
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
//BFS
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 100010;

int n, m;
struct Node
{
    int id;
    Node* next;
    Node(int _id): id(_id), next(NULL) {}
}*head[N];
int d[N], q[N];

void add(int a, int b)
{
    auto p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

bool topsort()
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (auto p = head[t]; p; p = p->next)
            if ( -- d[p->id] == 0)
                q[ ++ tt] = p->id;
    }

    return tt == n - 1;
}

int main()
{
    scanf("%d%d", &n, &m);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        d[b] ++ ;
        add(a, b);
    }

    if (!topsort()) puts("-1");
    else
    {
        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
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
//DFS
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 100010;

int n, m;
struct Node
{
    int id;
    Node* next;
    Node(int _id): id(_id), next(NULL) {}
}*head[N];
int st[N], q[N], top;

void add(int a, int b)
{
    auto p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

bool dfs(int u)
{
    st[u] = 1;

    for (auto p = head[u]; p; p = p->next)
    {
        int j = p->id;
        if (!st[j])
        {
            if (!dfs(j)) return false;
        }
        else if (st[j] == 1) return false;
    }

    q[top ++ ] = u;

    st[u] = 2;
    return true;
}

bool topsort()
{
    for (int i = 1; i <= n; i ++ )
        if (!st[i] && !dfs(i))
            return false;
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    if (!topsort()) puts("-1");
    else
    {
        for (int i = n - 1; i >= 0; i -- )
            printf("%d ", q[i]);
    }

    return 0;
}

朴素版prim算法

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

using namespace std;

const int N = 510, M = 100010, INF = 0x3f3f3f3f;

int n, m;
int g[N][N], dist[N];
bool st[N];

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;//距离
    int res = 0;//总代价
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                 t = j;//找到距离最近的一个点
        if (dist[t] == INF) return INF;//如果这个点不存在，报错
        st[t] = true;//加入这个点
        res += dist[t];//计算最小生成树代价
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], g[t][j]);//更新距离
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int res = prim();
    if (res == INF) puts("impossible");
    else printf("%d\n", res);
    return 0;
}

kruskal算法

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

using namespace std;

const int N = 510, M = 100010;

int n, m;
struct Edge
{
    int a, b, c;
    bool operator< (const Edge& t) const
    {
        return c < t.c;
    }
}e[M];
int p[N];

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

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i ++ )
        scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
    sort(e, e + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    int res = 0, cnt = n;
    for (int i = 0; i < m; i ++ )
    {
        int a = e[i].a, b = e[i].b, c = e[i].c;
        if (find(a) != find(b))
        {
            res += c;
            cnt -- ;
            p[find(a)] = find(b);
        }
    }

    if (cnt > 1) puts("impossible");
    else printf("%d\n", res);

    return 0;
}

BFS算法(邻接矩阵)

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
#include <queue>
#include <iostream>
#define MAX 100
using namespace std;
struct graph
{
    int vertexnum;
    int edgenum;
    char vertexlist[MAX];
    int edge[MAX][MAX];
};
bool visited[MAX];
//对于数组下标为v的顶点，找到第一个和他相邻的顶点，并返回该顶点的数组下标
int firstneighbor(graph G,int v){
    for (int i = 0; i < G.vertexnum; i++)
    {
        if (G.edge[v][i])//如果存在边
        {
            return i;
        }
       
    
    }
      return-1;   
}
//对于数组下标为v的顶点，从位置w开始查找和它相邻的顶点，并返回该点的数组下标
int nextneighbor(graph g,int v,int w){
    for(int i = w+1;i<g.vertexnum;i++){
        if (g.edge[v][i])
        {
            return i;
        }
        
    }
    return -1;
}
//广度优先遍历
void bfstraverse(graph g){
    for (int i = 0; i < g.vertexnum; i++)
    {
        visited[i]=0;//将访问标记数组初始化
    }
    for(int i = 0;i<g.vertexnum;i++){
        if(!visited[i])
            bfs(g,i);
    }
    
}
//从顶点v出发，广度优先遍历图G
void bfs(graph g,int v){
    queue<int>que;//设置一个队列，用来存储顶点的索引
    visit(g.vertexlist[v]);//访问初始顶点v
    visited[v]=1;
    que.push(v);//初始顶点入队
    while (!que.empty())
    {
        int cur=que.front();//用cur来接收队头弹出的顶点索引
        que.pop();//队头元素出队
        //检测当前顶点cur的所有邻接点
        for(int w = firstneighbor(g,cur);w>=0;w=nextneighbor(g,cur,w)){
            if(!visited[w]){//w为当前顶点cur的尚未访问过的邻接顶点
                visit(g.vertexlist[w]);//访问w顶点
                visited[w]=1;//标记访问
                que.push(w);//访问完将其入队

            }
        }
    }
    
}
//实例的visit函数，可以根据需要修改
void visit(char vertex){
    cout<<vertex<<" ";
}

BFS算法（邻接表）

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 <queue>
#include <iostream>
#define MAX 100
using namespace std;
struct arcnode//边表节点
{
    int adjvex;//该弧指向的顶点位置
    arcnode* next;//指向下一条弧的指针
};
struct vnode//顶点表结点
{
    char data;//顶点信息
    arcnode *first;//指向第一条依附该顶点的弧的指针
};
struct graph
{
    int numvertex;
    int numedge;
    vnode vertex[MAX];  
};
bool visited[MAX];
//广度优先遍历
void bfstraverse(graph g){
    for (int i = 0; i < g.numvertex; i++)
    {
        visited[i]=0;//将访问标记数组初始化
    }
    for(int i = 0;i<g.numvertex;i++){
        if(!visited[i])
            bfs(g,i);
    }
    
}
//从顶点v出发，广度优先遍历图G
void bfs(graph g,int v){
    queue<int>que;//设置一个队列，用来存储顶点的索引
    visit(g.vertex[v].data);//访问初始顶点v
    visited[v]=1;
    que.push(v);//初始顶点入队
    while (!que.empty())
    {
        int cur=que.front();//用cur来接收队头弹出的顶点索引
        que.pop();//队头元素出队
       arcnode*p=g.vertex[cur].first;//获取当前顶点的次一个邻接点
       //遍历当前顶点cur的所有邻接点
       while (p!=nullptr)
       {
        int adjindex=p->adjvex;//获取邻接顶点的索引
        if (!visited[adjindex])
        {
            visit(g.vertex[adjindex].data);//访问邻接顶点
            visited[adjindex]=1;
            que.push(adjindex);
        }
        p=p->next;
       }
       
    }
    
}
//实例的visit函数，可以根据需要修改
void visit(char vertex){
    cout<<vertex<<" ";
}

DFS算法（邻接矩阵）

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 <iostream>
using namespace std;
#define maxv 100

struct graph
{
    int vertexnum;
    int edgenum;
    char vertex[maxv];
    int edge[maxv][maxv];
};
bool visited[maxv];
//对于数组下标为v的顶点，找到第一个和他相邻的顶点，并返回该顶点的数组下标
int firstneighbor(graph G,int v){
    for (int i = 0; i < G.edgenum; i++)
    {
        if (G.edge[v][i])//如果存在边
        {
            return i;
        }
       
    
    }
      return-1;   
}
//对于数组下标为v的顶点，从位置w开始查找和它相邻的顶点，并返回该点的数组下标
int nextneighbor(graph g,int v,int w){
    for(int i = w+1;i<g.vertexnum;i++){
        if (g.edge[v][i])
        {
            return i;
        }
        
    }
    return -1;
}
void dfstraverse(graph g){
    //初始化访问数组
    for (int  i = 0; i < g.vertexnum; i++)
    {
        visited[i]=0;
    }
    //对每个顶点进行DFS，防止非连通图未遍历完全
    for (int i = 0; i < g.vertexnum; i++)
    {
        if(!visited[i])
            dfs(g,i);
    }
    
    
}
void dfs(graph g,int v){
    visit(g.vertex[v]);//访问顶点v
    visited[v]=1;
    //对顶点v的每个邻接顶点进行递归dfs
    for(int w=firstneighbor(g,v);w>=0;w=nextneighbor(g,v,w)){
        if(!visited[w]){
            dfs(g,w);
        }
    }
    
}
void visit(char vertex){
    cout<<vertex<<" ";
}


DFS算法（邻接表）

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
#include <queue>
#include <iostream>
#define MAX 100
using namespace std;
struct arcnode//边表节点
{
    int adjvex;//该弧指向的顶点位置
    arcnode* next;//指向下一条弧的指针
};
struct vnode//顶点表结点
{
    char data;//顶点信息
    arcnode *first;//指向第一条依附该顶点的弧的指针
};
struct graph
{
    int numvertex;
    int numedge;
    vnode vertex[MAX];  
};
bool visited[MAX];
//广度优先遍历
void dfstraverse(graph g){
    for (int i = 0; i < g.numvertex; i++)
    {
        visited[i]=0;//将访问标记数组初始化
    }
    for(int i = 0;i<g.numvertex;i++){
        if(!visited[i])
            dfs(g,i);
    }
    
}
//从顶点v出发，广度优先遍历图G
void dfs(graph g,int v){
    visit(g.vertex[v].data);//访问初始顶点v
    visited[v]=1;
   //遍历顶点v的所有邻接顶点
   arcnode*p=g.vertex[v].first;
   while (p!=nullptr)
   {
    if(!visited[p->adjvex]){
        dfs(g,p->adjvex);
    }
    p=p->next;
   }
   
    
}
//实例的visit函数，可以根据需要修改
void visit(char vertex){
    cout<<vertex<<" ";
}

朴素版dijkstra算法

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
int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f3f3f3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

拓扑排序

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
//邻接表情况
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N =100010;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N];
int q[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool topsort(){
    int hh=0,tt=-1;
    for(int i = 1;i<=n;i++)
        if(!d[i])//入度为0，入队
            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);//消去t结点为弧尾的边，如果消去后入度为0，入队
            q[++tt]=j：
        }
    }
    return tt=n-1;//如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列
}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i = 0;i<m;i++){
        int a,b;
        cin >> a >>b;
        add(a,b);
        d[b]++;
    }
    if(!topsort())cout<<"-1";
    else
    {
        cout<< "1";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
//这里用的邻接表
// 对于每个点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
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//邻接矩阵法
bool topsort(int course[][n]){
    int in[n]={0};
    int q[n];
    int tt=-1,hh=0;
    for(int i=0;i<n;i++)
        for(int j = 0;j<n;j++)
            if(course[i][j])
                	in[j]++;//统计入度
    for(int i= 0;i<n;i++)
        if(!in[i])q[++tt]=i;
        while(hh<=tt){
            int t = q[hh++];
           for(int i =0;i<n;i++){
               if(course[t][i])
               {
                   --in[i];
                   if(!in[i])q[++tt]=i;
               }
           }
            
            
        }
    
    return tt==n-1;
}

查找

一般线性表的顺序查找

1
2
3
4
5
6
7
8
9
struct sstable{
    int *data;//动态数组基址
    int tablelen;//表长
};
int seq_search(sstable st,int target){
    st.data[st.tablelen]=target;//设置哨兵
    for(int i = 0 ;st.data[i]!=target;i++)
        return i;//查找成功则返回下标，查找失败则返回表长
}

有序表的顺序查找

1
2
3
4
5
6
7
8
9
int seq_search(SSTable ST, int target) {
    for (int i = 0; i < ST.tablelen && ST.elem[i] <= target; ++i) {
        if (ST.elem[i] == target) {
            return i;   // 找到了
        }
    }
    return -1;  // 循环结束还没找到 -> 失败
}

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//不区分开闭，左闭右闭
#include <bits/stdc++.h>
using namespace std;
int binary_search(vector<int> nums,int target){
    int l = 0,r=nums.size()-1,mid;
    while (l<=r)
    {
        mid=l+(r-1)/2;
        if(nums[mid]==target)return mid;//查找成功返回坐标
        else if(nums[mid]>target) r=mid-1;//从前半部分继续查找
        else l = mid+1;//从后半部分继续查找
    }
    return -1;//查找失败，返回-1；
}

二分不用考虑有没有解

整数二分
  • 有单调性的题目可以二分，但可以二分不一定有单调性，二分的本质不是单调性
  • 二分的本质是性质，使得一部分满足红色性质，一部分满足绿色性质，整个区间可以一分为二，二分可以寻找性质的边界

①红点

  • mid=l+r+1>>1;

    if(check(mid)) true ->[mid,r] l = mid;//mid满足红色性质

    ​ false->[l,mid-1] r = mid-1;//mid不满足红色性质，在绿色性质区域

②绿点

  • mid = l+r>>1;

    if(check(mid)) true->[l,mid] r = mid;//mid满足绿色性质

    ​ false->[mid+1,r] l = mid+1;//mid满足红色性质，不满足绿色性质

1
2
3
4
5
6
7
8
9
10
11
12
13
//mid属于绿色区域
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用，即如果更新方式是r=mid,l=mid+1;
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
//mid属于红色区域
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用,即如果更新方式是l=mid,r=mid-1;
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;//判断mid是否满足红色性质
        else r = mid - 1;
    }
    return l;
}
浮点数二分

注：判断是否满足绿色性质

1
2
3
4
5
6
7
8
9
10
11
12
13
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求，比要求的位数多2
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

二叉搜索树

查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
struct treenode
{
    int val;
    treenode *left,*right;
    treenode(int x) : val(x),left(nullptr),right(nullptr){}
};
treenode *bstsearch(treenode *root,int num){
    treenode* cur =root;
    while (cur!=nullptr)
    {
        if(cur->val<num)
            cur=cur->right;//目标结点在cur的右子树
        else if(cur->val>num)
            cur=cur->left;//目标节点在cur的左子树
            else break;    
    }
    return cur;
    
}
插入
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
#include <bits/stdc++.h>
using namespace std;
struct treenode
{
    int val;
    treenode *left,*right;
    treenode(int x):val(x),left(nullptr),right(nullptr){}
};
void insert(treenode *&root,int num){
    if(root=nullptr)return;//如果根节点为空，直接返回
    treenode* cur =root,*pre=nullptr;
    while (cur!=nullptr)
    {
        if(cur->val==num)return;//如果找到了与待插入值相等的结点，则直接返回；
        pre=cur;
        if(cur->val<num)
            cur=cur->right;//目标结点在cur的右子树
        else if(cur->val>num)
            cur=cur->left;//目标节点在cur的左子树
        
    }
    //找到位置后开始执行插入操作
    treenode *node=new treenode(num);
    if(pre->val<num)pre->right=node;
    else pre->left=node;

    
}

二叉搜索树的构造
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
#include <bits/stdc++.h>
using namespace std;
struct treenode
{
    int val;
    treenode *left,*right;
    treenode(int x):val(x),left(nullptr),right(nullptr){}
};
void insert(treenode *&root,int num){
    if(root=nullptr)return;//如果根节点为空，直接返回
    treenode* cur =root,*pre=nullptr;
    while (cur!=nullptr)
    {
        if(cur->val==num)return;//如果找到了与待插入值相等的结点，则直接返回；
        pre=cur;
        if(cur->val<num)
            cur=cur->right;//目标结点在cur的右子树
        else if(cur->val>num)
            cur=cur->left;//目标节点在cur的左子树
        
    }
    //找到位置后开始执行插入操作
    treenode *node=new treenode(num);
    if(pre->val<num)pre->right=node;
    else pre->left=node;

    
}
void create_bst(treenode *&root,vector<int> str){
    root=nullptr;//初始时root为空树
    int n = str.size();
    //调用插入节点函数依次将关键字插入BST中
    for(int i = 0;i<n;i++){
        insert(root,str[i]);
    }
}

Hash表

  • 存储结构

    • 开放寻址法

    • 拉链法

  • 字符串哈希

  • 作用：把一个比较庞大的空间（值域）映射到比较小的空间，映射后的函数叫做哈希函数

    • x %10^5 ∈(0,10^5)
      • 模的数一般要取成质数，所以一般要遍历寻找最小的质数
    • 冲突：两个不一样的数映射成了同一个数，处理冲突的方式可以分为开放寻址法和拉链法
拉链法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(1) 拉链法
    int h[N], e[N], ne[N], idx;//h[N]是槽，e[N]（值）、ne[N]（下一个位置）是链表
//memset(h,-1,sizeof h)把槽先清空
    // 向哈希表中插入一个数
    void insert(int x)
    {
        int k = (x % N + N) % N;//把余数变成正数，k就是x的哈希值，将x插到k槽的单链表中
        e[idx] = x;//存下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)//判断该槽链表中是否存在x
                return true;

        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//寻找质数
for(int i =  ; ;i++){
bool flag =true;
for(int j = 2;j*j<=i;j++)
	if(i%j==0){
	flag =false ;
	break;
	}
	if(flag)
	{
	cout<<i<<endl
	break;
	}
}
开放寻址法
  • 只开一个数组，但是开的长度一般是输入数据的2-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
(2) 开放寻址法
    int h[N];
//需要定义一个不在数据范围内的null，如0x3f3f3f3f，一般设置最大值,INT_MAX也还是0x3f3f3f3f

memset(h,0x3f,sizeof h);//初始化哈希表
    //由于x是int类型，一个int四个字节，相当于4个3f，即0x3f3f3f3f

// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;//求哈希值，即映射
        while (h[t] != null && h[t] != x)//t位置上面有人，并且位置上的值不等于x
        {
            t ++ ;//看下一个位置
            if (t == N) t = 0;//看完了最后一个位置，需要循环看第一个位置
        }
        return t;//如果x在哈希表中，返回的就是x的下标，如果x不在哈希表中，返回的就是x应该插入的位置
    }

//插入一个数字
h[find(x)]=x;
//判断数字是否在哈希表中
if(h[find(x)])== null cout<<"No";
else cout<<"Yes";
字符串哈希

字符串前缀哈希法

  • 先预处理出所有前缀的哈希

    把字符串看成是p进制的数字，每一位上的字母就表示p进制上的每一位数字，然后再取模，就可以把字符串映射到从0到Q-1

  • A-Z不能映射成0，一般从1开始

  • 字符串哈希假定不存在冲突，因此不考虑冲突

  • 好处是可以利用前缀哈希算出来任意一个子串的哈希值

  • 作用：

    快速判断两个字符串是否相同，哈希值相同，两个字符串相同，如果哈希值不同，则两个字符串不同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
const int P=131 or 13331 //P进制
// 初始化
p[0] = 1;//p的零次方等于1
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;//位数对应的数字，类似于024816
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 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
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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int q[N], sz, w[N];

void insert_sort()  // 直接插入排序
{
    for (int i = 1; i < n; i ++ )
    {
        int t = q[i], j = i;
        while (j && q[j - 1] > t)
        {
            q[j] = q[j - 1];
            j -- ;
        }
        q[j] = t;
    }
}

void binary_search_insert_sort()  // 折半插入排序
{
    for (int i = 1; i < n; i ++ )
    {
        if (q[i - 1] <= q[i]) continue;
        int t = q[i];
        int l = 0, r = i - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] > t) r = mid;
            else l = mid + 1;
        }
        for (int j = i - 1; j >= r; j -- )
            q[j + 1] = q[j];
        q[r] = t;
    }
}

void bubble_sort()  // 冒泡排序
{
    for (int i = 0; i < n - 1; i ++ )
    {
        bool has_swap = false;
        for (int j = n - 1; j > i; j -- )
            if (q[j] < q[j - 1])
            {
                swap(q[j], q[j - 1]);
                has_swap = true;
            }
        if (!has_swap) break;
    }
}

void select_sort()  // 简单选择排序
{
    for (int i = 0; i < n - 1; i ++ )
    {
        int k = i;
        for (int j = i + 1; j < n; j ++ )
            if (q[j] < q[k])
                k = j;
        swap(q[i], q[k]);
    }
}

void shell_sort()  // 希尔排序
{
    for (int d = n / 3; d; d = d == 2 ? 1 : d / 3)
    {
        for (int start = 0; start < d; start ++ )
        {
            for (int i = start + d; i < n; i += d)
            {
                int t = q[i], j = i;
                while (j > start && q[j - d] > t)
                {
                    q[j] = q[j - d];
                    j -= d;
                }
                q[j] = t;
            }
        }
    }
}

void quick_sort(int l, int r)  // 快速排序
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[(l + r) / 2];
    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(l, j);
    quick_sort(j + 1, r);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= sz && q[u * 2] > q[t]) t = u * 2;
    if (u * 2 + 1 <= sz && q[u * 2 + 1] > q[t]) t = u * 2 + 1;

    if (u != t)
    {
        swap(q[u], q[t]);
        down(t);
    }
}

void heap_sort()  // 堆排序，下标一定要从1开始
{
    sz = n;
    for (int i = n / 2; i; i -- ) down(i);

    for (int i = 0; i < n - 1; i ++ )
    {
        swap(q[1], q[sz]);
        sz -- ;
        down(1);
    }
}

void merge_sort(int l, int r)
{
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) w[k ++ ] = q[i ++ ];
        else w[k ++ ] = q[j ++ ];
    while (i <= mid) w[k ++ ] = q[i ++ ];
    while (j <= r) w[k ++ ] = q[j ++ ];
    for (i = l, j = 0; j < k; i ++, j ++ ) q[i] = w[j];
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    // insert_sort();
    // binary_search_insert_sort();
    // bubble_sort();
    // select_sort();
    // shell_sort();
    // quick_sort(0, n - 1);
    // heap_sort();
    merge_sort(0, n - 1);


    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
    return 0;
}
/*
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/1588694/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

快排

1
2
3
4
5
6
7
8
9
10
void quick_sort(int q[],int l,int r){
    if(l>=r)return ;
    int i  =  l-1,j=r+1,x=q[l+r>>1]
    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);
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
void insert_sort(int n,int q[]){
    for(int i = 1;i<n;i++){
        int t = q[i],j=i;
        while(j&&q[j-1]>t)
        {
            q[j]=q[j-1];
            j--;
        }
        q[j]=t;
    }
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void merge_sort(int q[],int l,int r){
	if(l>=r)return ;
    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(j = 0,i=l;i<=r;i++,j++)
        q[i]=tmp[j];
    
}

堆排序

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100010;
int n;
int q[N], sz; // q 存储堆，sz 表示堆的当前大小

// 向下调整操作，保证堆的性质（大根堆）
void down(int u){
    int t = u; // 初始设定当前节点为 t
    if(u * 2 <= sz && q[u * 2] > q[t])  // 如果左子树存在且左子树的值大于当前节点的值
        t = u * 2; // 更新 t 为左子树
    if(u * 2 + 1 <= sz && q[u * 2 + 1] > q[t]) // 如果右子树存在且右子树的值大于当前节点的值
        t = u * 2 + 1; // 更新 t 为右子树
    if(u != t){ // 如果当前节点 t 不是最优节点（即左或右子树较大）
        swap(q[u], q[t]); // 交换当前节点和较大的子节点
        down(t); // 递归继续向下调整，保证堆的性质
    }
}

// 堆排序函数
void heap_sort() // 大根堆排序，下标从 1 开始
{
    sz = n; // 初始化堆的大小为 n
    // 1. 构建初始堆：从最后一个非叶子节点开始，进行向下调整
    for(int i = n / 2; i; i--)  // 从最后一个非叶子节点开始（n/2）
        down(i); // 调用 down 函数，向下调整每个节点，确保堆的性质
    // 2. 排序：每次将堆顶元素（最大元素）和堆的最后一个元素交换，并减少堆的大小，然后调整堆
    for(int i = 0; i < n - 1; i++){ 
        swap(q[1], q[sz]); // 将堆顶元素与堆的最后一个元素交换
        sz--; // 减少堆的大小
        down(1); // 调整堆，重新恢复堆的性质
    }
}

计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
void countsort(int a[],int b[],int n,int k){
    int i,c[k];
    for(i=0;i<k;i++)
        c[i]=0;
        for(i = 0;i<n;i++)
            c[a[i]]++;
    for(i=1;i<k;i++)
        c[i]=c[i]+c[i-1];
        for(i=n-1;i>=0;i--){
            b[c[a[i]]-1]=a[i];
            c[a[i]]=c[a[i]]-1;
        }
}

408中c++stl可用的情况

栈

1
2
3
4
5
6
7
stack<int>stk;
stk.push();
stk.pop();
int top=stk.top();
int size=stk.size();
bool empty=stk.empty();

队列

1
2
3
4
5
6
7
8
#inlude <queue>
queue<int> q;
q.push();
q.pop();
int a =q.front();//
int b= q.back();
int c=q.size();
#include <deque>

代码每日一题

Day1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//个人答题卡
/*1、算法的基本思想
    最次方法:按照正常的排序做，快排，时间复杂度Ologn，空间复杂度O1
    思考后的方法：利用计数排序，统计0，1，2的数量，然后通过循环放置0，1，2的数量，时间复杂度O(n),空间复杂度O(n)
2、代码
void sort(int a[],int n){//n表示数组长度
    int count[3];
    for(int i = 0;i<n;i++)
    	count[a[i]]++;//统计正整数序列中0，1，2各自的数量
    	int j = 0;
    for(int i = 0;i<count[0];i++)
    	a[j++]=0;
    for(int i =0;i<count[1];i++)
    	a[j++]=1;
    for(int i =0;i<count[2];i++)
    	a[j++]=2;
}
3、
	时间复杂度O(n),空间复杂度O(1)；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*最优解
三向切分快速排序or荷兰旗算法
定义三个指针，low,mid,high
初始化：
low=mid=0,high=n-1
移动mid
①a[mid]==0,交换Low和mid指向的元素，low++，mid++
②a[mid]==1，mid++
③a[mid]==2,交换mid和high指向的元素，high--
④mid>high👉break
代码：
void flag(int a[],int n){
	int low=mid=0;
	int high=n-1;
	while(mid<=high){
	if(a[mid]==0)swap(a[mid],a[low]),low++,mid++;
	else if(a[mid]==1)mid++;
	else swap(a[mid],a[high])high--;
	}
}时间复杂度O(n),空间复杂度O(1)

Day2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*个人答题卡
1、基本思想
三个指针各自指向每个数组开头，如果不等，最小的往后走，大的不变。直到相等为止
2、
bool ismin(int a,int b,int c){
	if(a<b && a<c)
		return true;
}
void thesame(int a[],int b[],int c[],int n){
	int i =0,j=0;k=0;
	int cnt=n;
 while(i<n && j<n&&k<n){
	while(a[i]!=b[j]&&b[j]!=c[k]){
			if(ismin(a[i],b[j],c[k])) i++;
			if(ismin(a[j],b[i],c[k]))j++;
			if(ismin(a[k],b[i],c[j]))k++;
			
	}
		cout<<a[i]<<' ';
		i++,j++,k++;
	}

}
时间复杂度O(n),空间复杂度O(1);

Day3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*个人答题卡
1、算法的基本思想
由于是两个等长的升序序列，说明中位数一定是在两个序列合在一起的第L个数，那么我们只需要找到第L个数，我们同时找到两个数组的中位数，对比这两个中位数的大小，两个序列的中位数一定是大于小的中位数，小于大的中位数，递归直到两个数组各自只剩下一个数，对比两个数大小，大的是结果
2、代码
int getmid(int a[],int b[],int l){
	int i  = 0,j=0,n=l-1,m=l-1;
	int mid1=0,mid2=0;
	while(i!n && j!=m){
			if(a[(i+n+1)>>1]>=b[(j+m+1)>>1])
					n=((i+n+1)>>1)-1,j=((j+m+1)>>1)+1;
			else
				i = ((i+n+1)>>1)+1,m=((j+m+1)>>1)-1;
	}
	if(a[i]>b[j]) return a[i];
}
时间复杂度O(logn)，空间复杂度O(1)；

Day4

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
/*个人答题卡
1、思路：快慢指针，慢指针指向重复出现的数第一次出现的位置，快指针指向第一个与慢指针指向的数不一样的数，让慢指针next指向快指针，然后慢指针和快指针指向同一个点
2、代码
struct listnode{
	int val;
	listnode *next;
}
listnode deleterepeat(listnode *head){
		listnode*fast=head;
		listnode*slow=head;
	while(slow){
		fast=slow->next;
         while(fast->val==slow->val && fast)
            fast=fast->next;
		slow->next=fast;
		slow=fast;
		
	
	}


}
3、
时间复杂度O(n)，空间复杂度O（1）


Day5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
1、基本思想：快慢指针，快指针先走n步，然后慢指针从头开始，快指针指向null，则慢指针恰好指到倒数第n个结点，然后运用链表原地删除删除结点
2、代码
listnode deletenode(lisntode* head,int n){
	listnode* fast=head;
	listnode* slow=head;
	while(n){
			fast=fast->next;
			n--;
	}
	while(fast){
		fast=fast->next;
		slow=slow->next;
	}
	//此时slow指向要删除的结点
	listnode * p=slow->next;
	slow->val=p->val;
	slow->next=p->next;
	free(p);
}
3、时间复杂度O(n),空间复杂度O(1);

Day6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*答题卡
1、思路：数组模拟队列，hh指向队头，tt指向队尾，根节点入队，弹出根节点，访问结点，有子结点则子结点入队，重复上述过程直到所有点都访问完毕
2、代码
#define N 5010
struct treenode{
	int val;
	treenode * left,*right;
};
void traverse(treenode * root){
		treenode* q[N];
		int hh=0,tt=0;
		if(root) q[tt++]=root;
		while(hh!=tt){
			treenode * tmp= q[hh++];
			cout<<tmp->val<<" ";
			if(tmp->left)q[tt++]=tmp->left;
			if(tmp->right)q[tt++]=tmp->right;
		}
	

}

Day7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
1、思路： 整体倒置，之后以xp为基准，前半部分倒置，后半部分倒置，就可以得到图中所要求的数组，时间复杂度O(N)，空间复杂度O（1）
2、逆序用双指针
void reverse(int a[],int l,int r){
for(int i = l,j=r;i<j;i++,j--)
	swap(a[i],a[j])
}
void leftmove(int a[],int n,int p){
	reverse(a,0,n-1);
	reverse(a,0,p-1);
	reverse(a,p,n-1);


}

Day8

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
/*个人答题卡
1、算法的基本思想
中序遍历二叉搜索树，能够得到一个升序数组，然后a[k]即为低k个小的元素
2、
int a(int a[],int n,int k){//a[]是二叉搜索树的存储数组，n是结点数，k是第k小的元素
	int	result[n];//存储中序遍历的结果
	int stk[n];
	int tt=0;
	//模拟栈
	int cur= 1;
	int count=0;
	while(int a[cur]!=0 || tt>0 ){//遍历指针不为0且栈不为空
		if(int a[cur]!=0){//遍历左子树
			stk[++tt]=cur;
			cur=cur>>1;
		
		}
		else{//说明上一个结点没有左子树
			cur=stk[tt--];
			result[count++]=a[cur];
			cur=cur*2+1;
		}
	
	}
	return result[k-1];

}
3、
时间复杂度：O(n)，空间复杂度O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*答案
int tt=0;
int t[n];
struct treenode{
	inta data;
	treenode * left,*right;
};
int num(treenode * root,int n ,int k){
	midtraverse(root);
	return t[k-1];
}
void midtraverse(treenode * root){
	if(root->left) find(root->left);
	t[cnt++]=root->data;
	if(root->right)find(root->right);
}

Day9 重要，连通性问题

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
/*个人答题卡
1、算法的基本思想
遍历邻接矩阵，找到一个陆地，然后寻找它上边，如果有陆地，则将这个陆地划到上边陆地一组，然后看它右边是否还有陆地，如果有的话，则分到和他同一组，直到碰到水为止，最后分出n块陆地，则岛屿的数量为n
2、代码
int group[n][m];
int num(int a[][],int n,int m){
	int cnt=0;
	for(int i = 0 ;i<n;i++){
		int j = 0;
	while(j<m){
			if(a[i][j]==1){//是一块陆地
				if(i==0)//如果是第一排陆地，不需要往上找
				{
                    cnt++;
					group[i][j++]=cnt;
					while(j<m&&a[i][j]==1){//右边也是陆地
                            group[i][j]=cnt;
							j++;
					}
					
				}
                else{//如果不是第一排陆地
                        if(group[i-1][j])//上面也是一块陆地
                            {group[i][j++]=group[i-1][j];
                                
                                while(j<m&&a[i][j]==1){
                                        group[i][j]=group[i][j-1];//标记为同一块陆地
                                        j++;
                                    }

                            }
                        else{//上面不是一块陆地，说明这是一块新的陆地
                                cnt++;
                                group[i][j]=cnt;

                        }
                }
			}
            j++;
		}
	
	}
	return cnt;
}
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
/*连通性问题
char g[n][m];
bool visit[n][m];
int cnt;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int numislands(int n ,int m){
	for(int i = 0;i<n;i++)
		for(int j  =0;j<m;j++)
			if(!visit[i][j] && g[i][j]=='1'){
				dfs(i,j);
				count++;
			}
			return cnt;
}
void dfs(int x,int j){
		if(x<0 || x>=n-1 || y<0 || y>=m-1)return;
			if(g[x][y]='0') return;
				if(visit[x][y])return;
                visit[x][y]=1;
                for(int i =0;i<4;i++){
                int nx=x+dx[i];
                int ny=y+dy[i];
                dfs(nx,ny);
                }
}

Day10 重点，树的后序遍历

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
/*个人答题卡
1、算法的基本思想：
统计每个结点的树高，然后再次遍历一遍检查是否符合平衡二叉树的要求
2、
struct treenode {
	int val;
	treenode * left,*right;
};
int imax(int a,int b){
	return a>b? a : b;
}
int heightorneg(treenode * root){
	if(root==0) return 0;
	int hl= heightorneg(t->left);
	if(hl<0) return -1;
	int hr= heightorneg(t-right);
	if(hr<0) return -1;
	if(hl-hr>1 || hr-hl>1)return -1;
	return imax(hl,hr)+1;
}
int isavl(treenode * root)
{
	return heightorneg(root)>=0?1:0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*答案
node {
	int data;
	node *left,*right;
	
};
bool flag=true;
bool isval(treenode *root){
	int t =check (root);
	return flag;
}
int check(treenode t){
	int l = -1;
	int r=-1;
	if(t->left) l = check(t->left);
	if(t->right) r= check (r->right);
	if(abs(l-r)>1) flag=false;
	return max(l,r)+1;
}
//时间复杂度O（n）

Day11 重点图的遍历

1
2
3
4
/*个人答题卡
1、
用DFS遍历每个点，求出每个点最深的结点。
2、
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*答案
struct graph{
	int a[n+10][n+10];
};
int res=0;bool visit[n];
void find(graph g,int n,int m){
		for(int i = 1;i<=n;i++){
			res=0;
			memset(visit,false ,sizeof visit);
			dfs(i,g);
			cout<<res<<" ";
		}
}
void dfs(int x,graph g){
		res=max(res,x);
		visit[x]=true;
		for(int i = 1;i<=n;i++)
			if(g.a[x][i]&&visit[i])
			dfs(i,g);
}

Day12

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
/*个人答题卡
1、邻接矩阵，使用dijkstra算法，计算单源最短路径
2、
#include <bits/stdc++.h>
#define N 100010
int dist[N];
int g[N][N];
bool st[N];
int min(int a,int b){
        return a<b? a:b;


}
int dijkstra(int k,int n){
    memset(dist,0x3f3f3f3f,sizeof dist);
    dist[k]=0;
    for(int i = 0;i<n-1;i++){
            int t=-1;
            for(int j = 1;j<=n;j++)//找到尚未访问的节点中距离最近的点
                    if(!st[j]&&(t==-1 || dist[t]>dist[j]))
                        t=j;
            for(int j = 1;j<=n;j++)//用该点更新其他点的距离
                dist[j]=min(dist[j],dist[t]+g[t][j]);

            st[t]=1;

            




    }
    if(dist[n]==0x3f3f3f3f)return -1;
    return dist[N];



}
3、时间复杂度O(n²)空间复杂度O(n²)
1
/*答案

Day13

1
2
3
/*个人答题卡
1、利用拓扑排序生成一个序列
2、答案见拓扑排序模板
1
/*答案

Day14

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
/*个人答题卡
1、利用BFS求连通分量的数量，调用BFS的次数就是连通分量的个数
2、
const int N=1000010;
int n;
bool visit[N];
int g[N][N];
int count(int g[][N])
{   
    int cnt=0;
    for(int i = 0;i<n;i++)
    {
        if(!visit[i]) {
            cnt++;
            dfs(i);


        }



    }
return cnt;

}
void dfs(int a){
    visit[a]=true;
    for(int i = 0;i<n;i++){
        if(g[a][i] && !visit[i])
            dfs(i);

    }
    return;


}
1
/*答案

Day15

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
/*个人答题卡
1、染色法，从某个一个结点开始，把邻接的且没有染过的点染成预期相反的颜色，如果失败，则说明不是二分图
2、
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;  // 小规模数据
int g[N][N];
int color[N];
int n;

bool dfs(int u, int c) {
    color[u] = c;
    for (int i = 1; i <= n; i++) {
        if (g[u][i]) {  // 只有存在边时才处理
            if (color[i] == -1) {
                if (!dfs(i, !c)) return false;
            } else if (color[i] == c) {
                return false;
            }
        }
    }
    return true;
}

bool check() {
    memset(color, -1, sizeof color);
    for (int i = 1; i <= n; i++) {
        if (color[i] == -1) {
            if (!dfs(i, 0)) {
                return false;
            }
        }
    }
    return true;
}
1
/*答案

Day16

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*个人答题卡
1、双指针算法，i指针指向插入的位置，j指针往后遍历直到找到第一个非0元素，找到后交换两个指针所指的值，然后i指针和j指针都往后+1，重复上述过程，直到遍历完毕
2、
void swap(int &a,int &b){
		int tmp=a;
		a=b;
		b=tmp;

}
void movezero(int a[],int n){
		int i = 0,j=0;//i前面的都会是非0元素
		while(j<n){//
			while(!a[j])j++;//j一直往后直到找到第一个非零元素
			swap(a[i],a[j]);//交换元素
			i++,j++;
		}

}
1
/*答案

Day17

1
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
/*答案
#include <bits/stdc++.h>
using namespace std;
int sta[26]={0};
int stb[26]={0};
bool check(int l,int r,string a,string b){
    for(int i =l;i<=r;i++){
          stb[(int)b[i]-65]++;


    }
    for(int i = 0;i<26;i++)
      if(sta[i]!=stb[i])return false;


}
bool issubstring(string a,string b,int n,int m){
    for(int i =0;i<n;i++)
      sta[i]=(int)a[i]-65;
    for(int i = 0;i<m-n+1;i++){
      memset(stb,0,sizeof stb);
          int l = i;
          int r=i+n-1;
          if(check(l,r,a,b)) return true;


    }
    return false;

  
      




}

Day18

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
/*个人答题卡
1、利用深度优先遍历，遍历找能走过的路
2、
const int N=1010;
int dx[4]={0,0,-1,1}//上下左右
int dy[4]={1,-1,0,0}//上下左右
bool visit[N][N];
int cnt;
int count(int g[N][N],int n,int x,int y){
	dfs(x,y);
	return cnt;
}
void dfs(int g[N][N],int x,int y){
if(visit[x][y]|| x<0 || y<0 || x>=n|| y >=n) return;
		visit[x][y]=true;
		cnt++;
		int c=g[x][y];//取出该点的数字
		for(int i = 0;i<n;i++){
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(g[nx][ny]!=c && (!visit[nx][ny]))//如果没有访问过，而且邻接点与当前结点值相反，可以走
			dfs(nx,ny);
		}
}

1
/*答案

Day19

1
2
/*个人答题卡
1、找到l左边的结点，保存为h1，然后把中间l-r的部分用迭代法反转，连上即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*答案
Lnode* reverselist(Lnode *&head,int left,int right){
    Lnode *p0=head;
    for(int i = 0;i<left-1;++i){
        p0=p0->next;//找到链表中待反转部分的前一个结点
    }
    Lnode *pre =nullptr,*cur = p0->next;
    for(int i = 0;i<right-left+1;i++){
        Lnode *next = cur->next;
        cur->next=re;
        pre=cur;
        cur=next;
    }
    //中间反转完毕，和原链表连接
    p0->next->next=cur;//中间部分反转完毕后cur指向中间部分的最后一个结点，此处进行最后一次反转
    p0->next=pre;//反转完之后从原链表视角看，pre指向待反转链表的最后一个结点，也就是反转后的第一个结点
    return head;
}

Day20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*个人答题卡
1、找到倒数第（k+1）%n个结点，然后找到最后一个结点，（k+1）%n个结点指向nulptr，最后一个结点next指向头节点，右移完成
2、void reverse(node * root,int k){
	node * head->next=root;
	int len=0;
	node * tmp=head->next;
	node * newhead=head;
	while(tmp){
		len++;
		newhead=newhead->next;
		tmp=tmp->next;
	}
	int kk=k%len;
	if(kk==0)return ;
	node *tail=head
	for(int i = 0;i<len-kk;i++){
				tail=tail->next;
	}
	tail->next=nullptr;
	newhead->next=head->next;



}
1
/*答案

Day21

1
2
3
4
/*个人答题卡
1、快排，遍历
	
			
1
/*答案

Day22

1
2
/*个人答题卡
1、倒转后分两区间，两个区间分别用二分查找
1
/*答案

Day23

1
2
/*个人答题卡

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
/*答案
class Solution {
public:
    int findMissMin(vector<int>& nums) {
        int n = nums.size();
        vector<bool> hash(n + 1);
        for (int x: nums)
            if (x >= 1 && x <= n)
                hash[x] = true;
        for (int i = 1; i <= n; i ++ )
            if (!hash[i])
                return i;
        return n + 1;
    }
};

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/1566876/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//解法2
int find(int a[],int n){
	for(int i = 0;i<n;i++){
		while(a[i]<=n && a[i]>=1 && a[i]!=a[a[i]-1])
			swap(a[i],a[a[i]-1]);
	}
	for(int i = 0;i<n;i++)
		if(a[i]!=i+1)return i+1;
    return i+1;
}
空间复杂度O（1）,时间复杂度O(n)

Day24

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
/*个人答题卡
1、双指针，一个指针指向当前结点，另个指针指向下一个结点，因为是升序，不用考虑后续还有重复的元素，只用删除非重复元素即可
2、void deleterepeate(node * head){
	node *hh;
	hh->next=head;
	node *i=hh;//负责删除
	node *j=hh->next;//j和k一起负责找到重复数字
	node *k=hh->next->next;
	while(j->next){
		while(j->val!=k->val)
			{
				i=i->next;
				j=j->next;
				k=k->next;
			}//找到第一个相同的起点
		while(j->val==k->val && k) k=k->next;//找到第一个不相同的点
		if(k==nullptr){//如果k到最后都没找到不相同的点，说明后面全一样，全删除
				i->next==nullptr;
				return;
		}
		i->next=k;
		j=k;
		k=k->next;
	
	}


}
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
/*答案
struct node {
		int val;
		node * next;
}
node * delete(node * head){
			node * p =new node();
			p->next=head;
			head=p;
			node * pre=p;
			node* cur=p->next;
			while(cur && cur->next){
				if(cur->data==cur->next->data){
					while(cur->data==cur->next->data) cur=cur->next;
      				pre->next=cur->next;
                    cur=pre->next;
				
				}
				else {
				pre=pre->next;
				cur=cur->next;
				}
			
			}
			
			return head->next;
			
	

}

Day25

1
2
/*个人答题卡

1
/*答案

Day26

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*个人答题卡
1、三个指针，同时指向三个数组的元素，因为D是绝对值相加，实际上三个数的D就是三个数中，数轴上最左边到最右边数的距离的两倍，所以只需要求三个数最大值-最小值最小的一个组合，通过三个指针，让左和右端不断靠近，即能找出结果
2、
void sanyuanzu(int s1[],int s2[],int s3[],int a,int b,int c)//a,b,c为长度
{       
		int d=0x3f3f3f3f;
		int i = 0,j=0,k=0;
		while(i<a && j<b && k <c){
				int x=s1[i];
				int y=s2[j];
				int z=s3[k];
				res=min(res,abs(max(max(x,y),z)-min(min(x,y),z)));
				if(x<=y && x<=z) i++;
				else if(y<=x && y<=z)j++;
				else k++;
		}
		return res*2;
}
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
/*答案
//yxc
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int l, m, n;
int a[N], b[N], c[N];

int main()
{
    scanf("%d%d%d", &l, &m, &n);
    for (int i = 0; i < l; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);
    for (int i = 0; i < n; i ++ ) scanf("%d", &c[i]);
//读入数据
    LL res = 1e18;
    for (int i = 0, j = 0, k = 0; i < l && j < m && k < n;)//遍历三个
    {
        int x = a[i], y = b[j], z = c[k];
        res = min(res, (LL)max(max(x, y), z) - min(min(x, y), z));//三个数中的最大值-最小值
        //因为最短距离=最大-最小，且都是升序数组，所以最小值所在的那个数组指针向后移，相当于向其他两个数靠近
        if (x <= y && x <= z) i ++ ;
        else if (y <= x && y <= z) j ++ ;
        else k ++ ;
    }

    printf("%lld\n", res * 2);
    return 0;
}

Day27

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*个人答题卡
1、思路：层序遍历，记录每个结点的高度，然后每个高度的第一个结点就是每层最左边的结点，用一个min值记录，如果层次更高，更新，直到遍历完毕，最终的就是结果
2、
struct treenode {
	int val;
	treenode * left;
	treenode * right;
};
int height=-1;
int leftval(treenode *root){
				


}
void cengxubianli(treenode *root,int h){


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*答案
struct node {
	int data;
	node *left;
	node *right;
}
int res;
int height=-1;
int find(treenode* root){
		
    dfs(root,0);
	return res;
}
void dfs(treenode * t,int depth){
	if(depth>height){
		height=depth;
		res=t->data;
		}
        if(t->left==nullptr && t->right==nullptr)return;
        if(t->left)dfs(t->left,depth+1);
        if(t->right) dfs(t->right,depth+1);

}

Day28

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*个人答题卡
1、用一个结果栈保存操作数和结果，遇到操作符号弹出栈顶的两个元素进行计算，并且将结果保存回栈顶
2、
int stack[n];
bool isnum(char a){
	if(a!='+' && a!='-'&& a!='*' && a!='/')return true;
	return false;
}
int result(string s,int n){
			int top=-1;
		for(int i = 0;i<n;i++){
				if(isnum(s[i])) stack[++top]=s[i];//操作数压栈保存
				else{
					int y= stack[top--];
					int x= stack[top--];
					if(s[i]=='+')stack[++top]=x+y;
                    if(s[i]=='-')stack[++top]=x-y;
					if(s[i]=='*')stack[++top]=x*y;
					if(s[i]=='/')stack[++top]=x/y;
				}
		}
		return stack[top];
}
1
/*答案

Day29

1
2
/*个人答题卡

1
/*答案

Day30

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*个人答题卡
1、思想：利用快慢指针，如果快慢指针会相遇，说明存在环
2、
struct node{
	int val;
	node *next;
}
bool haveornot(node * head){
		node * p = new node(-1,head);
		head=p;
		node * fast=head;
		node * slow=head;
		while(fast && fast->next){
				fast=fast->next->next;
				slow=slow->next;
				if(slow == fast)
					return true;
		}
		return false;
}
3、时间复杂度On，空间复杂度O1
1
/*答案

Day31

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
/*个人答题卡
1、思路：两个二分
2、
int binary_searchleft(int a[],int l ,int r,int target){//开始位置
	while(l<r){
		int mid = l+r+1>>1;
		if(mid<=target) l = mid ;
		else r=mid-1;
	}
	return l;

}
int binary_searchright(int a[],int l,int r){//结束位置
		while(l<r){
			int mid = l+r>>1;
			if(mid>=target) r = mid;
			else l = mid+1;
		}
return l;
}
void result(int a[],int n){
	int x=binary_searchleft(a,0,n-1);
	int y=binary_searchright(a,0,n-1);
		cout << x << " "<<y;
}
3、时间复杂度Ologn，空间复杂度O1
1
/*答案

Day32 统计回溯

1
2
/*个人答题卡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*答案
int g[100][100];
int n;
vector<vector<int>>res;
vector<vector<int>> allpathssourcetarget(vector<vector<int>>&graph){
		n=graph.size();
		for(int i = 0;i<n;i++){
			int m = graph[i].size();
			for(int j =0;j<m;j++){
					g[i][graph[i][j]]=1;
			
			
			}
		
		
		}

		vector<int> t;
		t.push_back(0);
		dfs(0,t);
		return res;


}

Day33

1
2
/*个人答题卡

1
/*答案

Day34

1
2
/*个人答题卡

1
/*答案

Day35

1
2
/*个人答题卡

1
/*答案

Day36

1
2
/*个人答题卡

1
/*答案

Day37

1
2
/*个人答题卡

1
/*答案

Day38

1
2
/*个人答题卡

1
/*答案

Day39

1
2
/*个人答题卡

1
/*答案
#408日常
数据结构算法笔试
http://example.com/2025/04/02/数据结构算法笔试/
作者
Kugeln
发布于
2025年4月2日
许可协议