grant's Blog

记录生活中的点点滴滴

考研算法辅导课笔记（三）

发表于 更新于 分类于 ， ，   阅读次数： Valine：
本文字数： 5.2k 阅读时长 ≈ 5 分钟

1.2日期问题

3607. 打印日期（华中科技大学）

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
给出年份 y 和一年中的第 d 天，算出第 d 天是几月几号。

输入格式
输入包含多组测试数据。
每组数据占一行，包含两个整数 y 和 d。

输出格式
每组数据输出一行一个结果，格式为 yyyy-mm-dd。

数据范围
输入最多包含 100 组数据,
1≤y≤3000,
1≤d≤366,
数据保证合法。

输入样例：
2000 3
2000 31
2000 40
2000 60
2000 61
2001 60
输出样例：
2000-01-03
2000-01-31
2000-02-09
2000-02-29
2000-03-01
2001-03-01

简单的日期问题模板题。

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

bool is_Leap(int y) {return (y % 4 == 0 && y % 100 != 0) || y % 400 == 0; }

int get_days(int y,int m){ 
    // 得到y年m月的天数
    bool add = is_Leap(y);
    if (m == 2) return month[m] + add;
    else return month[m];
}

// 以上内容基本是日期问题的固定格式

int main(){
    int Y,D;
    
    while (cin >> Y >> D){
        int d = 1,m = 1;
        -- D;
        while (D--){
            
            int n = get_days(Y,m);
            if ( ++d > n){
                d = 1;
                ++ m;
            }
            
            if ( m > 12){
                m = 1;
                ++ Y;
            }
        }
        
        printf("%04d-%02d-%02d\n",Y,m,d);
    }
    
    return 0;
}

3573. 日期累加（北京理工大学）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
设计一个程序能计算一个日期加上若干天后是什么日期。

输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据占一行，包含四个整数 y,m,d,a，分别表示给定日期的年、月、日和累加的天数。

输出格式
每组数据输出一行，一个结果，每行按 yyyy-mm-dd 的格式输出。

数据范围
1≤T≤1000
1000≤y≤3000,
1≤m≤12,
1≤d≤31,
1≤a≤10^6,
保证输入日期合法。

输入样例：
1
2008 2 3 100
输出样例：
2008-05-13

也是一个经典的日期问题的模板题。

先一年一年数，再一天一天数。每组数据计算量是：2700 (10^6 / 365) + 365。

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
#include <iostream>
using namespace std;
const int month[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

bool is_leap(int y){ return (y % 4 == 0 && y % 100 != 0) || y % 400 == 0; }

int get_days(int y,int m){
    if (m != 2) return month[m];
    return month[2] + is_leap(y);
}

// 计算从y-m-d到y+1-m-d的天数
int get_year_days(int y,int m){ // 排除m == 2 && d == 29的情况
    if (m <= 2) return 365 + is_leap(y); // 对于2.28及以前，跳转到第二年需要考虑当年有无2.29
    return 365 + is_leap(y+1); // 对于此后，跳转第二年需要考虑第二年有无2.29
}

int main(){
    int t;
    cin >> t;
    
    
    while (t--){
    	int y,m,d,a;
        cin >> y >> m >> d >> a;
        
        if (m == 2 && d == 29) -- a, m = 3, d = 1;
        while (a > get_year_days(y,m)){
            a -= get_year_days(y,m);
            y ++;
        }
        
        while (a -- ){
            if ( ++ d > get_days(y,m)){
                ++ m;
                d = 1;
            }
            
            if (m > 12){
                ++ y;
                m = 1;
            }
        }
        
        printf("%04d-%02d-%02d\n",y,m,d);
    }
    
    return 0;
}

2.第三讲 栈与队列

2.1栈和队列

  1. 栈和队列的基本概念
  2. 栈和队列的顺序存储结构
    (1) 栈：栈顶元素位置：指向最后一个元素、指向最后一个元素的下一个位置
    (2) 队列：一般采用循环队列。
     (a) 队头元素位置：指向第一个元素、指向第一个元素的前一个位置。
 (b) 队尾元素位置：指向队尾元素、指向队尾元素的下一个位置。
  3. 栈和队列的链式存储结构
  4. 栈和队列的应用
    (1) 栈的应用：表达式求值（中缀表达式转后缀表达式、括号匹配）、DFS
    (2) 队列的应用：BFS

栈：后进先出（LIFO），队列：先进先出（FIFO）。

2.1.1顺序栈

在栈顶（top）进行数据的插入和删除。

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
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 211;

int main(){
    // 1.top指向最后一个元素
    int stk1[N],top1 = -1;

    stk1[++ top1] = 1; // 插入元素
    stk1[++ top1] = 2;
    -- top1; // 删除元素
    stk1[top1]; // 返回栈顶元素 
    // if (top1 == -1) 栈空！

    // 2.top指向最后一个元素的下一个位置
    int stk2[N],top2 = 0; // top2 指向的是待放入元素
    stk2[top2 ++] = 3; // 插入元素
    stk2[top2 ++] = 3;
    -- top2; // 删除元素
    stk2[top2 - 1]; // 返回栈顶元素 
    // if (top1 == 0) 栈空！
    
    return 0;
}

2.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
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;
const int N = 211;

int main(){
    //! 搞清楚：front是队头，rear是队尾！
    //! 队尾插入，队头弹出
    // 1.front指向第一个元素，rear指向最后一个元素的下一个位置
    int q[N],front = 0,rear = 0;

    // 考察重点！
    // 队列判空，front == rear
    // 队列判满，front == (rear + 1) % N
    // 为了区别空与满，判定rear转了一圈回到原点的前一个位置时队满，再插入一个就放不下了

    q[rear ++] = 1; // 队尾插入
    rear %= N;

    front = (front + 1) % N; // 队头弹出

    q[front]; // 返回队头
    
    /*--------------*/

    // 2.front指向第一个元素，rear指向最后一个元素
    int q[N],front = 0,rear = -1;


    // 队列判空，front == (rear + 1) % N
    // 队列判满，front == (rear + 2) % N
    // 对比第一种定义方式判空与判满的关系

    q[++ rear] = 1; // 队尾插入
    rear %= N;

    front = (front + 1) % N; // 队头弹出

    q[front]; // 返回队头
    return 0;
}

注意：上面程序的插入和删除操作不够严谨，理论上在插入和删除之前应该先执行判满和判空操作。

为了区分循环队列空与满的两种情况，这里会牺牲一个存储单元。（各种方式都会）

看下面的模拟图就知道了。

约定：队尾在队头的前一个位置时表示队列已满，具体参考王道P74的文字说明和图。

  • 做题时如何确定队空、队满的判定条件呢？

  • 根据题目对两个指针指向位置的描述，模拟只有1个元素的情况，倒推出队空的条件；模拟队满的情况，必须满足队满的条件不能和队空的条件重合，推出队满的条件。

  • 比如：front指向第一个元素，rear指向最后一个元素的下一个位置。

    image-20211119163623080

    注意：上图中情况1到情况2，front指向不需要改变。

2.1.3链栈

对于链栈的插入和弹出操作，也就是对链表的头（栈顶）插和头（栈顶）删。

链栈的定义方式可以分为两种，带头节点和不带头节点。

这里的代码版本是不带头节点的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;

struct Node{
    int val;
    Node *next;

    Node(): next(NULL) {}
    Node(int _val): val(_val),next(NULL) {}
};

void print(Node *head){
    for (auto p = head; p ; p = p->next){
        cout << p->val << '\n';
    }
}

int main(){
    Node *top; // 栈顶指针

    auto a = new Node(1); // 栈顶插入
    a->next = top;
    top = a;

    auto b = new Node(2);
    b->next = top;
    top = b;

    print(top);
    
    return 0;
}

2.1.4链队列

对于链队列的插入和弹出操作，也就是对链队列的尾（队尾）插和头（队头）删。

链队列的定义方式可以分为两种，带头节点和不带头节点。

这里的代码版本是带头节点的：（带不带头节点，解释看王道P75，第一个不带，第二个带）

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

struct Node{
    int val;
    Node *next;

    Node(): val(0),next(NULL){}
    Node(int _val): val(_val),next(NULL){}
};

void print(Node *head){
    for (auto p = head; p->next; p = p->next){
        cout << p->val << '\n';
    }
}

int main(){
    Node *front = new Node(),*rear = front; // 初始时front和rear都指向头节点
	// 之后：front指向队列中第一个元素，rear指向队列中最后一个元素的下一个位置
    
    rear->val = 1;
    rear->next = new Node();
    rear = rear->next;

    rear->val = 2;
    rear = rear->next = new Node(); // 从右往左赋值

    print(front);

    cout << front->val << '\n'; // 输出队头

    auto p = front;
    front = front->next; // 队头弹出元素
    delete p;

    cout << front->val << '\n'; // 输出队头
    return 0;
}

image-20211118230537306

坚持原创技术分享，您的支持将鼓励我继续创作！