SnowDawn'Home
0%

发表于 更新于 分类于

分治算法 - 棋盘覆盖问题

棋盘覆盖问题：有一个残缺的棋盘，由$2^k * 2^k$ 个方格组成，只能用以下四种残缺的方块组成（蓝色的部分表示残缺），成为三格板，两个三格板之间不能重叠，不能覆盖最终图形中的残缺方格。

​ 1号2号3号4号

因为棋盘的组成满足 $2^k*2^k$ ,因此可以将这个问题根据分治的思想，将棋盘不断分为四块，那么每一块都是由$2^{k-1}*2^{k-1}$ 格子组成的，将一个大的棋盘不断分为四份的小棋盘。

为了保证满足覆盖要求和条件，将其中三块的缺口放在中间，这样就可以把缺口覆盖，只留下题目中要求的唯一缺口。

首先考虑k=1的情况，若把某一格放空，方案是唯一的。已知某个正方形和空格，我们按照上下面的办法，可输出方案。首先延中心，将边长为$2^k*2^k$的矩形分成4个边长为$2^{k-1}*2^{k−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
/*
 * @Description: 算法分析与设计
 * @Autor: 赵晗
 * @Date: 2022-10-08 21:45:09
 * @LastEditors: 赵晗
 * @LastEditTime: 2022-10-09 22:05:51
 */

#include <iostream>
using namespace std;
int count = 0;
int boardsize = 1;
int Board[8][8];
void Cover(int tr, int tc, int dr, int dc, int size); //填充棋盘的函数
void OutputBoard(int size);
int main()
{
    int x, y;
    int i;
    int k;
    //输入棋盘规模
    cout << "请确认棋盘规模，输入k大小（2k×2k）:" << endl;
    cin >> k;
    for (i = 1; i <= k; i++)
        boardsize *= 2;
    cout << "请输入残缺棋子位置（行号，列号）:" << endl;
    cin >> x >> y;
    Cover(0, 0, x, y, boardsize);
    OutputBoard(boardsize);
}
void Cover(int tr, int tc, int dr, int dc, int size)
{
    if (size < 2)
        return;
    int t = count++;
    int s = size / 2;
    //如果残缺在左上角
    if (dr < tr + s && dc < tc + s)
    {
        Cover(tr, tc, dr, dc, s);
        Board[tr + s - 1][tc + s] = t;
        Board[tr + s][tc + s - 1] = t;
        Board[tr + s][tc + s] = t;
        //返回，填充其他部分
        Cover(tr, tc + s, tr + s - 1, tc + s, s);
        Cover(tr + s, tc, tr + s, tc + s - 1, s);
        Cover(tr + s, tc + s, tr + s, tc + s, s);
    }
    //右上角
    else if (dr < tr + s && dc >= tc + s)
    {
        Cover(tr, tc + s, dr, dc, s);
        Board[tr + s - 1][tc + s - 1] = t;
        Board[tr + s][tc + s - 1] = t;
        Board[tr + s][tc + s] = t;
        //返回，填充其他部分
        Cover(tr, tc, tr + s - 1, tc + s - 1, s);
        Cover(tr + s, tc, tr + s, tc + s - 1, s);
        Cover(tr + s, tc + s, tr + s, tc + s, s);
    }
    else if (dr >= tr + s && dc < tc + s)
    {
        Cover(tr + s, tc, dr, dc, s);
        Board[tr + s - 1][tc + s - 1] = t;
        Board[tr + s - 1][tc + s] = t;
        Board[tr + s][tc + s] = t;
        //返回，填充其他部分
        Cover(tr, tc, tr + s - 1, tc + s - 1, s);
        Cover(tr, tc + s, tr + s - 1, tc + s, s);
        Cover(tr + s, tc + s, tr + s, tc + s, s);
    }
    else if (dr >= tr + s && dc >= tc + s)
    {
        Cover(tr + s, tc + s, dr, dc, s);
        Board[tr + s - 1][tc + s - 1] = t;
        Board[tr + s - 1][tc + s] = t;
        Board[tr + s][tc + s - 1] = t;
        //返回，填充其他部分
        Cover(tr, tc, tr + s - 1, tc + s - 1, s);
        Cover(tr, tc + s, tr + s - 1, tc + s, s);
        Cover(tr + s, tc, tr + s, tc + s - 1, s);
    }
}
void OutputBoard(int size)
{ //输出棋盘的内容
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            cout.width(5);
            cout << Board[i][j];
        }
        cout << endl;
    }
}

分治算法的复杂度分析

分治算法将一个规模为$n$ 的问题分解为k个规模为$\frac{n}{m}$的问题，整个问题的复杂度计算分为三个部分

  • 将问题分解的时间$f(n)$

  • k个小规模问题的时间之和$kT(\frac{n}{m})$

  • 将结果合并的时间$f(n)$

    所以在问题规模$n\neq1$ 的前提下,分治算法的时间复杂度计算公式为
    $$
    T(n) =kT(\frac{n}{m})+f(n)
    $$

    其中，m为将问题分解为了多少个子问题，k是这些子问题中有多少是需要进行计算和解决的，在棋盘覆盖问题中，将问题分为了4份，全部都要解决，所以
    $$
    k = m = 4
    $$

    很简单的可以得到，将这些子问题的结果合并的时间复杂度是$O(1)$

    接下里由master定理可以计算得到
    $$
    T(n) = O(n)
    $$
    时间复杂度求解完成。

发表于 更新于 分类于

Git原理和基础

在过去几个学期的期末大作业合作中，我们常常花费了大量的时间和精力去将各人的工作整合在一起成为一个完整的项目。通常我们分配完成任务，完成各自的编码任务，最后再汇总在一个人那里，完成最后的调试。

在这样的前提下，我开始系统地学习和了解版本管理工具，其中Git是使用最广泛的。

Git工作原理

Git 将顶级目录中的文件和文件夹作为集合，并通过一系列快照来管理其历史记录。在Git的术语里，文件被称作Blob对象（数据对象），也就是一组数据。目录则被称之为“树”，它将名字与 Blob 对象或树对象进行映射（使得目录中可以包含其他目录）。快照则是被追踪的最顶层的树。一个最简单的文件结构树例子：

image-20240108104233560

这个顶层的树包含了两个元素，一个名为 “foo” 的树（它本身包含了一个blob对象 “bar.txt”），以及一个 blob 对象 “baz.txt”

Git的历史记录是一个由快照的有向无环图，图中的每一个节点都是一个快照，每个快照都包括一个文件结构状态。所以每一个快照都有一系列父辈，也就是其之前的一系列快照。

在 Git 中，这些快照被称为“提交”。通过可视化的方式来表示这些历史提交记录时，看起来差不多是这样的：

image-20240108110306552

图中的每个o表示一次commit，即快照。箭头指向了当前提交的父辈在第三次提交之后，历史记录分岔成了两条独立的分支。这可能因为此时需要同时开发两个不同的特性，它们之间是相互独立的。开发完成后，这些分支可能会被合并并创建一个新的提交，这个新的提交会同时包含这些特性。新的提交会创建一个新的历史记录，看上去像这样（最新的合并提交用粗体标记）：

image-20240108110746951

Git 中的提交是不可改变的。但这并不代表错误不能被修改，只不过这种“修改”实际上是创建了一个全新的提交记录。

数据模型和伪代码表示

使用伪代码表示Git的数据模型：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 文件就是一组数据
type blob = array<byte>

// 一个包含文件和目录的目录
type tree = map<string, tree | blob>

// 每个提交都包含一个父辈，元数据和顶层树
type commit = struct {
    parent: array<commit>
    author: string
    message: string
    snapshot: tree
}

对象和内存寻址

Git 中的对象可以是 blob、树或提交：

type object = blob | tree | commit

Git 在储存数据时，所有的对象都会基于它们的 SHA-1 哈希 进行寻址,Blobs、树和提交都一样，它们都是对象。当它们引用其他对象时，它们并没有真正的在硬盘上保存这些对象，而是仅仅保存了它们的哈希值作为引用。

引用

但是对于用户而言，使用哈希作为快照的名称是不可行的，针对这一问题，Git 的解决方法是给这些哈希值赋予人类可读的名字，也就是引用（references）。引用是指向提交的指针。与对象不同的是，它是可变的（引用可以被更新，指向新的提交）。例如，master 引用通常会指向主分支的最新一次提交。使用HEAD来表示当前所在的位置。

基础操作

Git的命令行接口有许多功能，这里简单记录一套最基本的使用方法：

创建git仓库,创建一个新的 git 仓库，其数据会存放在一个名为 .git 的目录下

1
git init

显示当前仓库状态，下面的状态是没有提交到暂存区的结果

1
git status

image-20240108113553832

添加文件到暂存区,将修改后的文件添加到暂存区，后查看status，显示出等待commit的记录。

1
git add

image-20240108113758913

提交记录,输入后会提示用户添加提交信息记录，成功后显示出简化版本的hash值

1
git commit

image-20240108114129515

查看日志，显示出当前的位置和已经存在的分支，加上参数后会以图的形式表示，更加直观

1
git log --all --graph --decorete

image-20240108114915744

有关Git的多人协作功能还需要进一步学习，在此贴就不进行形象记录，主要体现Git的底层逻辑。

后续学习资料

发表于 分类于

要解决的问题

  • 通过什么方式实现上下文的切换，并且方便测量时间。
  • 如何保证在具有多个CPU的系统中，保证上下文切换的进程处于同一个处理器上

上下文切换的方式

利用两个管道，测量在父子进程之间互相切换的时间成本，具体流程见下图

[管道的介绍](Linux管道通信 | SnowDawn’Home)

3

​ 使用双管道在父子进程之间相互切换

  1. 父进程向管道Pi1 写入获取到的开始时的时间，使用gettimeofday()函数
  2. 父进程从Pi2 读取，但是此时的Pi2 中还没有内容写入，所以父进程陷入等待，系统切换到子进程
  3. 子进程从Pi1 中读取开始的时间，并且记录此时的时间，与开始的时间相减，输出切换的时间
  4. 子进程向Pi2 中写入开始时间，此时切换到等待读取的子进程，再次算出一个切换时间

使切换进程保证在同一个处理器上

使用sched_seaffinity()调用实现，该函数的参数比较复杂，这里只是简单的使用，没有详细的研究与介绍。

测量程序代码(标明在注释中)

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
#define _GNU_SOURCE
#include <sched.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/time.h>

#define errExit(msg)        \
    do                      \
    {                       \
        perror(msg);        \
        exit(EXIT_FAILURE); \
    } while (0)

int main()
{
    cpu_set_t set;           // cpu_set_t是一个用来存放CPU的集合的结构体
    int parentCPU, childCPU; //
    parentCPU = 0;
    childCPU = 0; //设置父进程和子进程的CPU核心

    CPU_ZERO(&set); //将CPU核心集合清零
    int pi1[2];     //父进程和子进程的管道
    int pi2[2];
    char buf1[30], buf2[30]; //父进程和子进程的管道缓冲区
    int p1 = pipe(pi1);      //创建父进程和子进程的管道
    int p2 = pipe(pi2);
    long temptime;
    struct timeval start, end; //记录时间
    int i;
    if (p1 < 0 || p2 < 0) //判断管道是否创建成功
        errExit("pipe");
    int rc = fork();         //创建子进程
    for (i = 0; i < 10; ++i) //循环测试十次
    {
        if (rc < 0) //判断子进程是否创建成功
        {
            fprintf(stderr, "fork failed");
            exit(1);
        }
        else if (rc == 0)
        {
            CPU_SET(childCPU, &set); //将子进程的CPU核心设置为childCPU
            if (sched_setaffinity(getpid(), sizeof(set), &set) == -1)
                errExit("sched_setaffinity");         //设置CPU核心
            read(pi1[0], buf1, 25);                   //读取父进程的数据
            gettimeofday(&end, NULL);                 //获取结束时间
            printf("%d\n", end.tv_usec - atol(buf1)); //输出时间差
            gettimeofday(&start, NULL);               //获取开始时间
            sprintf(buf2, "%ld", start.tv_usec);      //将开始时间转换为字符串
            write(pi2[1], buf2, 25);                  // 将开始时间写入管道
        }
        else
        {
            CPU_SET(parentCPU, &set); //将父进程的CPU核心设置为parentCPU
            if (sched_setaffinity(getpid(), sizeof(set), &set) == -1)
                errExit("sched_setaffinity");         //设置CPU核心
            gettimeofday(&start, NULL);               //获取开始时间
            sprintf(buf1, "%ld", start.tv_usec);      //将开始时间转换为字符串
            write(pi1[1], buf1, 25);                  // 将开始时间写入管道
            read(pi2[0], buf2, 25);                   // 读取子进程的数据
            gettimeofday(&end, NULL);                 //获取结束时间
            printf("%d\n", end.tv_usec - atol(buf2)); //输出时间差
        }
    }
    return 0;
}

测试程序的运行结果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
90
15
6
7
5
6
5
6
5
6
5
7
5
6
5
6
5
7
5
398

对测试结果的分析

在十次循环的测量中，开始的一次和最后的一次测量时间较长，具体为何会出现这样的情况有以下猜测：

  • 对于刚创建的子进程，还未进入到系统的缓存，进程之间的切换较慢。
  • 对于最后一次测量上下文切换时间，待解决，择日向老师请教。

另，此测试程序得到的结果并不只是上下文切换的时间，还包括对读和写的系统调用，将字符串转化为数字，设置cpu亲和度的调用等时间，根据之前对系统调用的测量，并且忽略其他细小的时间消耗，该系统的上下文切换时间应该在 4 – 5 微秒。

发表于 分类于

什么是管道

​ 管道， 英文名 pipe 。

​ 在系统操作和执行命令的时候，通常需要将一个程序的输出交给另外一个程序处理，这样的操作虽然可以使用输入输出重定向加文件实现，但是比较麻烦。

​ 管道的概念就是这样诞生，将两个进程的输入和输出通过一个管道相连，以便达到进程之间相互通信的目的。

​ 从本质上来说，管道就是一个文件，前面的的进程以写的方式打开文件，后面的程序以读的方式打开文件，利用这样的方式实现进程间通信。

​ 虽然实现形态上是文件，但是管道本身并不占用磁盘或者其他外部存储的空间。在Linux的实现上，它占用的是内存空间。所以，Linux上的管道就是一个操作方式为文件的内存缓冲区。

管道的分类

  • 匿名管道

  • 命名管道

    匿名管道只能在父进程和子进程之间使用，在父进程产生子进程之前，打开一个管道文件，然后再fork（）

产生一个子进程，由于父子进程共享文件描述符，所以可以通过这个管道文件相互通信。

匿名管道的调用原型：

1
2
#include <unistd.h>
int pipe(int pipefd[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
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 <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <sys/types.h>
#include <sys/wait.h>

#define STRING "hello world!"

int main()
{
    int pipefd[2];              //为pipe准备文件标识符
    pid_t pid;
    char buf[BUFSIZ];

    if (pipe(pipefd) == -1) {	//使用pipe（）系统调用
        perror("pipe()");
        exit(1);
    }

    pid = fork();				//创建子进程
    if (pid == -1) {
        perror("fork()");
        exit(1);
    }

    if (pid == 0) {
        /* this is child. */
        printf("Child pid is: %d\n", getpid());
        if (read(pipefd[0], buf, BUFSIZ) < 0) {   //子进程读管道中父进程写入的信息
            perror("write()");	//没有读到的话就是写出现了问题
            exit(1);
        }

        printf("%s\n", buf);	//将从父进程得到的信息打印

        bzero(buf, BUFSIZ);		//将buf清零
        //将要送给parent的信息写入buf中
        snprintf(buf, BUFSIZ, "Message from child: My pid is: %d", getpid());
        //调用pipe（）的写入实现
        if (write(pipefd[1], buf, strlen(buf)) < 0) {
            perror("write()");
            exit(1);
        }

    } else {
        /* this is parent */
        printf("Parent pid is: %d\n", getpid());
		//将要送给子进程的信息写入buf
        snprintf(buf, BUFSIZ, "Message from parent: My pid is: %d", getpid());
        //调用pipe（）的写入实现
        if (write(pipefd[1], buf, strlen(buf)) < 0) {
            perror("write()");
            exit(1);
        }

        sleep(1);       //父进程写入完成以后，等待子进程完成读取

        bzero(buf, BUFSIZ);
        //读取管道中子进程写入的信息
        if (read(pipefd[0], buf, BUFSIZ) < 0) {
            perror("write()");
            exit(1);
        }

        printf("%s\n", buf);

        wait(NULL);
    }


    exit(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
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <sys/types.h>
#include <sys/wait.h>

#define STRING "hello world!"

int main()
{
    int pipefd[2];
    pid_t pid;
    char buf[BUFSIZ];

    if (pipe(pipefd) == -1) {
        perror("pipe()");
        exit(1);
    }

    pid = fork();
    if (pid == -1) {
        perror("fork()");
        exit(1);
    }

    if (pid == 0) {
        /* this is child. */
        close(pipefd[1]); //子进程只读，所以关闭写入

        printf("Child pid is: %d\n", getpid());
        if (read(pipefd[0], buf, BUFSIZ) < 0) {
            perror("write()");
            exit(1);
        }

        printf("%s\n", buf);

    } else {
        /* this is parent */
        close(pipefd[0]);//父进程只写入，所以关闭读

        printf("Parent pid is: %d\n", getpid());

        snprintf(buf, BUFSIZ, "Message from parent: My pid is: %d", getpid());
        if (write(pipefd[1], buf, strlen(buf)) < 0) {
            perror("write()");
            exit(1);
        }

        wait(NULL);
    }
    exit(0);

​ 命名管道不仅可以在父子进程中实现消息的传递，通过命名可以实现任意进程之间的管道通信，此篇博客不再详细介绍命名管道。

发表于 分类于

测量成本的工具

使用 gettimeofday() 这个典型时钟函数来测量时间成本，返回自1970-01-01 00:00:00到现在所经历的秒数，调用两次该函数通过相减的方式获取时间差。

根据函数的定义：此函数在sys/time.h>中

1
int gettimeofday(struct timeval *, struct timezone *);

定义了两个结构体，分别记录时间和时区

1
2
3
4
5
6
7
8
9
struct timeval {undefined
 time_t tv_sec;
 suseconds_t tv_usec;
};//存储秒和微秒

struct timezone {undefined
 int tz_minuteswest;
 int tz_dsttime;
};//记录时区

使用举例 : 测试其时间精度是否可以达到定义中声明的微秒级别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
	struct timeval start,end;
	int i = 10;  
    gettimeofday(&start, NULL);
	for(i=0;i<10;++i) {	
		gettimeofday(&start, NULL);
		gettimeofday(&end, NULL);
		printf("%ld\n", end.tv_usec - start.tv_usec);
		printf("%ld %ld\n", end.tv_usec, start.tv_usec);
	}
    gettimeofday(&end, NULL);
	return 0;
}

这是在空系统调用测试中连续调用 gettimeofday()函数，如果精确度可以达到微秒 级别，那么两次连续调用获取的时间相减应该近似于0

执行结果如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
0
157238 157238
0
157275 157275
0
157278 157278
1
157282 157281
0
157285 157285
0
157288 157288
0
157291 157291
1
157295 157294
0
157298 157298
0
157301 157301

基本可以确定在微秒级别

注意

一般情况下，系统调用的时间成本是在 ns的级别，所以即使可以达到微秒级别，也要通过多次测量取平均值的办法才可以尽可能的实现准确。

测量系统调用的时间成本

这里使用简单的 read() 函数来测量调用的成本 ， 测试程序的代码如下

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 <stdio.h>
#include <sys/time.h>
#include <unistd.h>
#include <fcntl.h>
#include <stdlib.h>

int main()
{
	int n = 10;
	while (n--)
	{
		int fd = open("./6.2.c", O_RDONLY);
		int i;
		char buf[10];
		struct timeval start, end;
		if (fd == -1)
		{
			fprintf(stderr, "file open failed!\n");
			exit(1);
		}
		gettimeofday(&start, NULL);
		for (i = 0; i < 10000; ++i)
		{
			read(fd, buf, 0); //为了让程序结束，把read的第二个参数改为0，这样就可以尽可能测量纯粹的系统调用耗时
		}
		gettimeofday(&end, NULL);
		printf("%d :万次的平均结果： %lf\n", 10 - n, (1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec) * 1.0 / 10000); //强制转换为double
		close(fd);
	}
	return 0;
}

测试程序的结果如下

1
2
3
4
5
6
7
8
9
10
1 :万次的平均结果： 0.583100
2 :万次的平均结果： 0.598400
3 :万次的平均结果： 0.594100
4 :万次的平均结果： 0.595600
5 :万次的平均结果： 0.601000
6 :万次的平均结果： 0.615700
7 :万次的平均结果： 0.606900
8 :万次的平均结果： 0.589100
9 :万次的平均结果： 0.595500
10 :万次的平均结果： 0.584900

从多次运行万次平均结果看，对于 read 函数，系统调用的时间约为 0. 6 微秒。

发表于 更新于 分类于

单调栈

即栈内的元素是有某种单调性的。

用于求特定问题的解。

作用情景

[求一个数列的每个数的左边第一个比它小的数字](830. 单调栈 - AcWing题库)

要求左边第一个比它小的数，那么在之前每一个数入栈的时候就进行判断，只将满足递减单调性的数据存入，其余的弹出

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

using namespace std;

const int N = 100010;

int stk[N], tt;

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        //如果栈是非空的，且栈顶元素不比要入栈的元素小，将栈顶弹出，以形成单调栈
        while (tt && stk[tt] >= x)
            tt--;
        //形成单调栈以后的栈顶就是要找的第一个比要入栈元素小的值
        if (tt)
            printf("%d ", stk[tt]);
        else
            printf("-1 ");
        //最后将这个元素入栈
        stk[++tt] = x;
    }
    return 0;
}

优先队列

与单调栈的定义类似，优先队列里的元素是按照某种单调性排列的。

使用优先队列可以简化特定要求的与队列有关的问题。

作用情景

[滑动窗口](154. 滑动窗口 - AcWing题库)

一组数据

给定一个大小为 k的窗口，从数组的头开始滑动，窗口里最多只能同时存在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
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>

using namespace std;

const int N = 1000010;

int n, k;
//a[N]数组中存储要处理的数组，q[N]数组中存储队列里的数在a[N]数组里的下标
int a[N], q[N];

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    //定义队头和队尾
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i++)
    {
        //使用 i - k + 1 来控制队列（滑动窗口）中的元素数量，每当队列中的元素超出k， 就把队头元素出队
        if (hh <= tt && q[tt] - k + 1 > q[hh])
            hh++;
        //要入队的元素要比队列中的所有元素都要大
        while (hh <= tt && a[q[tt]] >= a[i])
            tt--;
        q[++tt] = i;
        if (i >= k - 1)
            //队头的元素永远是最小的
            printf("%d ", a[q[hh]]);
    }
    printf("\n");
    //找最大值与最小值方法一样，改变入队的限制即可
    hh = 0, tt = -1;
    for (int i = 0; i < n; i++)
    {
        if (hh <= tt && i - k + 1 > q[hh])
            hh++;
        //要入队的元素要比队列中的所有元素都小
        while (hh <= tt && a[q[tt]] <= a[i])
            tt--;
        q[++tt] = i;
        if (i >= k - 1)
            printf("%d ", a[q[hh]]); //输出队头的最大元素
    }
    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
#include <iostream>

using namespace std;

const int N = 100010;

//将tail设为-1 ， 这样在插入了一个数的时候，队头head 就是 tail 队列长度是1
int queue[N], head, tail = -1;

//在队尾插入元素，在队头弹出元素

void push(int x)
{
    queue[++tail] = x;
}

string ifempty()
{
    if (head > tail)
        return "YES";
    else
        return "NO";
}

void pop()
{
    //指针移动，队头的元素相当于被切掉了
    head++;
}

int query()
{
    return queue[head];
}

int main()
{
    int m;
    cin >> m;
    string op;
    while (m--)
    {
        cin >> op;
        if (op == "push")
        {
            int x;
            cin >> x;
            push(x);
        }
        else if (op == "pop")
        {
            pop();
        }
        else if (op == "empty")
        {
            cout << ifempty() << endl;
        }
        else
            cout << query() << 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
51
52
53
54
55
56
57
58
#include <iostream>

using namespace std;

const int N = 100010;

int stk[N], k;

void push(int x)
{
    stk[++k] = x;
}

string ifempty()
{
    if (k <= 0)
        return "YES";
    else
        return "NO";
}

void pop()
{
    k--;
}

int query()
{
    return stk[k];
}

int main()
{
    int m;
    cin >> m;
    string op;
    while (m--)
    {
        cin >> op;
        if (op == "push")
        {
            int x;
            cin >> x;
            push(x);
        }
        else if (op == "pop")
        {
            pop();
        }
        else if (op == "empty")
        {
            cout << ifempty() << endl;
        }
        else
            cout << query() << endl;
    }
    return 0;
}

挺简单的，随便记录一下。

发表于 分类于

双链表

与单链表相比，区别是：
双链表的每一个节点都有对应的前驱和后继。

可以完成一些单链表无法完成的任务。

[基础的双链表操作](827. 双链表 - AcWing题库)

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

using namespace std;

const int N = 100010;

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

void init()
{
    //将0 ， 1 分别设为头节点和尾部节点
    l[1] = 0;
    r[0] = 1;
    idx = 2;
}

//向插入的第k个数后面插入一个数
//也可以通过将参数k 改为l[k]来实现向k的左边插入一个数
void add(int k, int x)
{
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

//移去第k个插入的数
void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main()
{
    init();
    int m;
    cin >> m;
    string op;
    while (m--)
    {
        cin >> op;
        if (op == "L")
        {
            //向头节点的后面添加一个数，就是在最前面加上一个数
            int x;
            cin >> x;
            add(0, x);
        }
        else if (op == "R")
        {
            //向尾节点前面一个数的后面加一个数，就是在最后加上一个数
            int x;
            cin >> x;
            add(l[1], x);
        }
        else if (op == "D")
        {
            //删去第k个插入的数
            int x;
            cin >> x;
            remove(x + 1);
            //第一个插入的数的下标是2 ，因为将  1 定义为了末尾
        }
        else if (op == "IL")
        {
            //在第k个插入的数前面插入一个数
            int k, x;
            cin >> k >> x;
            add(l[k + 1], x);
            //在第k个左边的右面插入，就是在k的左边插入
        }
        else
        {
            int k, x;
            cin >> k >> x;
            add(k + 1, x);
        }
    }
    for (int i = r[0]; i != 1; i = r[i])
        cout << e[i] << " ";
    return 0;
}