2025/7/12 学习内容

发表于2025-07-12更新于2025-07-28

2025/7/12 学习内容

今天主要对数据结构在算法中的应用，以及对应的STL库进行了复习训练

一共刷了九道题，在下面会给出一部分我认为适合练习的题的题单（虽然在思路上不算难，但是代码细节还是还是需要非常细心的）：

1812. 判断国际象棋棋盘中一个格子的颜色

119. 杨辉三角 II

[士兵队列训练问题](Problem - 1276)

[NOIP2017]图书管理员

[Team Queue](Problem - 1387)

[!CAUTION]

我按照个人感受由易到难排序，感兴趣的可以练一下，题解在文章后面

由于今天临时有点事，所以大部分题都是来自于英雄编程课程中的，后续会多找一些其他的题

接下来是一些知识点，都是基础，可以根据需求选择性阅读

重要的事情再说一遍 题解代码在文章后面

一、语法

vector <数据类型>

类比于顺序表

n.push_back(元素)：将元素插入到顺序表尾部

n.size()：顺序表长度

stack<数据类型>

栈的c++库函数，适用于进制转换，匹配算法等问题

n.push(元素)：入栈

n.empty()：判空

n.pop()：栈顶元素出栈

n.top()：访问栈顶元素

下面是使用栈进行十进制转二进制的代码示例以及模板练习题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
    stack <int> s;
    while (cin>>n) {
        while (n) {
            s.push(n%2);
            n/=2;
        }
        while (!s.empty()) {
            cout<<s.top();
            s.pop();
        }
        cout<<"\n";
    }
    return 0;
}

模板练习：[Bitset](Problem - 2051)

queue<数据类型>

队列的c++库函数，与栈十分相似，适用于模拟，广度优先搜索等问题

n.push(元素)：入队

n.empty()：判空

n.pop()：队首元素出队

n.front()：访问队首元素

二、刷题题解

1.力扣 1812. 判断国际象棋棋盘中一个格子的颜色

给一个国际象棋棋盘，输入横纵坐标，输出棋格颜色（黑/白）

横坐标：1-8 纵坐标：a-h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool squareIsWhite(string coordinates) {
        int ans1=0,ans2=0;
        if(coordinates[0]>='a'&&coordinates[0]<='h') ans1=1;
        if(coordinates[1]>='1'&&coordinates[1]<='8') ans2=1;
        //上面这个判定加不加都行，但是建议加上
        if(ans1&&ans2){
            int abc=coordinates[0]-96;
            int ott=coordinates[1]-31;//输入是字符转化为对应ASCLL码的1-8数字
            if(abc%2==1&&ott%2==1) return true;
            else if(abc%2==0&&ott%2==0) return true;//如果同为奇数或偶数就为黑
            //这个判定怎么写都行这里是方便理解
            else return false;
        }
        return  false;
    }
};

2.力扣 119. 杨辉三角 II

题意大概是给一个整数，输出对应行的数据

杨辉三角就是其中的每个数是它左上方和右上方的数的和

1
2
输入: rowIndex = 3
输出: [1,3,3,1]

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

整理可得就是两个边界都是1，其他是对应上一行元素加上一行前一个元素

下面是代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> getRow(int rowIndex) {
      int f[44][44];//存杨辉三角
      for(int i=0;i<=33;i++){
          for(int j=0;j<=i;j++){
              if(j==0||j==i){
                  f[i][j]=1;//处理边界
              }
              else{
                  f[i][j]=f[i-1][j-1]+f[i-1][j];//除边界外元素处理
              }
          }
      }
      vector<int> n;//建立顺序表储存输出元素
      for(int j=0;j<=rowIndex;j++){
          n.push_back(f[rowIndex][j]);
      }
      return n;
  }

3.杭电 [士兵队列训练问题](Problem - 1276)

题意是给出一个队伍先1-2报数，报到2的人出列，然后1-3报数报到3的人出列，循环往复直至只剩三个人以下

由于原题内容太模糊不清，导致可能很多人理解错题意，这里要注意数到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
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
#include<bits/stdc++.h>

using namespace std;

int T;
int main() {
queue<int> q,q1;//两个队列交替进行
    int n;
cin>>T;
    while(T--) {
        cin>>n;
        for (int i = 1; i <= n; i++) {
            q.push(i);//先把人（编号）入队
        }
        int cnt=0;//计数器
        while(q.size()>3) {
            cnt=0;
            while (!q.empty()) {
                int v=q.front();
                q.pop();
                cnt++;
                if (cnt%2==1) {
                    q1.push(v);//保留非2的人
                }
            }
            if (q1.size()<=3) {//一定要在这里判断一下，这个很重要，如果没有这步会出现漏项
                while (!q1.empty()) {
                    q.push(q1.front());
                    q1.pop();
                }
                break;
            }
            cnt=0;//重置
            while (!q1.empty()) {

                int v=q1.front();
                q1.pop();
                cnt++;
                if (cnt%3==1||cnt%3==2) {
                    q.push(v);//保留非3的人
                }
            }
        }
while (!q.empty()) {
    cout<<q.front()<<" ";
    q.pop();//出队
}
        cout<<endl;
}
    return 0;
}

4.杭电 [Team Queue](Problem - 1387)

这题的思路简单，但是细节比较难处理，我这里自己写了一版代码十分混乱，于是直接按照英雄编程课程中的代码来写的，下面是代码

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<bits/stdc++.h>

using namespace std;

int T;
int hax[1000010];//一个简单哈希表

int main() {
int cnt=0;
    while (cin>>T&&T) {
        cnt++;
        cout<<"Scenario #"<<cnt<<endl;
        memset(hax,0,sizeof(hax));//初始化哈希
        for (int i=1;i<=T;i++) {
            int n;
            cin>>n;
            while (n--) {
                int x;
                cin>>x;
                hax[x]=i;//建立索引，就是以元素为索引，对应的队伍编号为元素，这样方便查找
            }
        }
        queue<int> q[10001];
        int s=0,e=0;//整个队列区间
        string str;
        while (cin>>str) {
            if (str=="STOP") break;
            if (str=="ENQUEUE") {
                int x,i;//x是元素，i是行数
                cin>>x;
                for (i=s;i<e;i++) {
                    if (hax[q[i].front()]==hax[x]) break;
                    //这里是通过访问每个队队首元素带回哈希表，再与元素所在队伍进行比较，判定是否在同一个队伍
                }
                q[i].push(x);//进入对应的队伍
                if (i==e) e++;//如果这个队伍还不存在需要拓展一下队伍
            }
            else {
                int val=q[s].front();
                q[s].pop();
                if (q[s].empty()) s++;//如果已经空了就取消这个队伍
                cout<<val<<endl;

            }

        }
        cout<<endl;
    }
    return 0;
}
5.牛客 [NOIP2017]图书管理员

题目要求就是把用户需要的编码与图书编码对照，判断是否为图书编码的结尾数字，如果有输出最小的图书编码，反之输出-1

这个题目涉及的知识点很广泛，做法也很多，这里给大家分享一下我的做法

首先我们需要保证他是最小，所以要排序，如果你想用int存，那么直接sort即可，但是后期处理稍微麻烦一些

我选用string存，这样很多功能直接调用就可以，但是需要自己写sort的排序函数comp

查找我本来想用二分，但是发现有很多问题，而且排序后线性枚举也不会超时，所以直接写个比较函数就行

下面是代码

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<bits/stdc++.h>
using namespace std;
int n,q;
//判断函数
int Myfind(string str,string qstr){
    if(str.length()<qstr.length()) return 0;//如果图书码小于查找码，直接返回
    int l=str.length()-1,r=qstr.length()-1;//从后向前对比
    while(r>=0&&l>=0){
        if(str[l--]!=qstr[r--]) return 0;//只要不一样直接返回
    }
    return 1;
}
//排序函数
bool comp(string a,string b){
    if(a.length()<b.length()) return true;//由小到大排序
    else if(a.length()==b.length()){
        int l=0,r=0;//如果等长从前向后对比
        while(l<a.length()){
            if(a[l]<b[r]) return true;
            else if(a[l]>b[r]) return false; 
                l++;
                r++;
        }
        return true;
    }
    else return false;
}

int main(){
    cin>>n>>q; 
    string str[1210];
    string qstr;
    for(int i=0;i<n;i++){
        cin>>str[i];       
    }
    sort(str,str+n,comp);
    int m;
    for(int i=0;i<q;i++){
        cin>>m;
        cin>>qstr;
        int p=0,k;
        for( k=0;k<n;k++){
              p=Myfind(str[k],qstr);//线性枚举            
            if(p) break;
        }       
        if(!p) cout<<-1<<endl;
        else cout<<str[k]<<endl;
    }    
    return 0;
}