Please enable Javascript to view the contents

算法笔记（基于C++的考研机试）

 ·  ☕ 22 分钟  ·  ✍️ Calvin Haynes · 👀... 阅读

前言

本文主要是记录作为备考考研复试机试过程中的笔记，目前考虑按照题目类型分类进行思路总结和相关的题目代码实现。

C++机试刷题技巧&基础知识

Tips

  • 对机试而言链表不重要，因为可以用数据结构把链表内容转而用数组存储来解决，但是要明白链表处理的流程，用于应付复试中面试可能问到的问题。

map 映射

  • 想用字符串映射成 int 类型则可以考虑用 map 这种数据结构：map<string,int>
  • 具体可看：map

迭代器是什么？

机试中字符串的处理

  1. 在输入输出时采用 C 风格的字符串，即通过字符数组的方式来实现字符串 （char arr[MAX]），因为 ‘\0’ 是字符串结束的标志，所以申请字符数组空间的时候需要至少比题目要求空间多一位，用 scanf 和 printf 函数来进行字符串输入和输出。
  2. 在进行诸如查找字符串中的一些字符，比较两个字符串，插入/移除字符串中的某些字符等高级字符串操作（更改字符串内容的操作）时则采用 C++ 风格的字符串最佳。
  3. C 风格字符串的 case：
    1. char buff[100] scanf("%d",buff) ==> 缺点：只能读取一个单词，例如输入 how are you，scanf 只能读取 how。
    2. char buff[100] fgets(buff,100,stdin) ==> 读取一整行，包括换行符。
    3. 如何用 fgets 并且删掉换行符（C++操作）：char buff[100] fgets(buff,100,stdin) string cplusplus = buff cplusplus.erase(cplusplus.size() - 1)
  4. C++风格字符串常用的一些 example：
    1. 引入 string：#include <string> using namespace std;
    2. C 风格字符串转为 C++ 风格：char str[101] string cplusplus = str
    3. C++ 风格字符串转为 C 风格（通常用于 printf 打印时）：cplusplus.c_str()
    4. 求字符串长度：cplusplus.size() 或 cplusplus.length()
    5. 访问字符的语法：cplusplus[i] ==> 访问第 i 个字符 ==> 打印？printf("%c",cplusplus[i])
    6. 连接字符串语法：cplusplus = cplusplus + "world"
    7. 删除字符串中某个字符：cplusplus.erase(5) ==> 把下标为 5 的字符删掉
    8. 清空字符串：cplusplus.clear()
    9. 查找：寻找某字符（串）第一次出现的位置

Vector 向量（动态数组）

  • 数组的缺点
    • 数组在定义时，就要指定大小（常量），不能再改变。
    • 函数内部的数组不能定义太长，因为栈（放局部变量）溢出，所以定义数组尽量定义为全局变量（数据段，不会内存自动回收）。
  • Vector–序列式容器
    image.png

stack 栈

queue 队列

struct

  • 尽管在 C 和 C++ 中都有 struct 的概念，但是他们对应的东西是不能混用的！
  • C 中的 struct 用来描述一种固定的内存组织结构，而 C++ 中的 struct 就是一种类，它与类唯一的区别就是它的成员和继承行为默认是 public 的，而一般类的默认成员是 private 的。这一点在写 C/C++ 混合代码时尤其致命。另外，声明 struct 时 C++ 也不需要像 C 那么繁琐。
    1. C 版本：
      image.png
    2. C++ 版本：
      image.png

模拟问题

  1. 模拟问题主要是对一些实际问题进行数学抽象，难度在读题和理解题目本身，属于送分题。
  2. 模拟问题主要分为图形打印，日期问题以及其他模拟题，其中图形打印和日期问题相对较难，下面会分类进行总结。

图形打印问题

  • 通用的图形打印思路如下：（二维数组+找规律+分析循环的边界条件）
  1. 申请固定大小的二维数组 arr[M][N]，最好放在全局变量位置。本质问题就是需要确定两个维度的下标
  2. 根据条件，从任意方向开始，设置二维数组（设计并存储图形）
  3. 把图案每一行边界的后一个位置使用’\0’赋值
  4. 使用 fori 循环加上 printf("%s",arr[i])打印每一行（画出图形）

梯形打印问题（清华复试上机）

8749D8A25FFEB11FF67A1A8FC83D0FE5

  • 解题代码和思路：
 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 <cstdio>

int main() {
    int h = 0;
    printf("请输入h：（用ctrl+d键结束输入，否则可以一直输入h）\n");
    while (scanf("%d",&h) != EOF) {
        char TuAn[h][3*h-2];

        for (int i = 0; i < h; ++i) {   //初始化二维数组
            for (int j = 0; j < 3*h-2; ++j) {
                TuAn[i][j] = ' ';
            }
        }

        for (int i = h-1; i >= 0; --i) {    //画梯形
            for (int j = 3*h-3; j >= 2*(h-1-i); --j) {
                TuAn[i][j] = '*';
            }
        }

        for (int i = 0; i < h; ++i) {     //打印梯形
            for (int j = 0; j < 3*h-2; ++j) {
                printf("%c",TuAn[i][j]);
            }
            printf("\n");
        }
    }
}

叠筐问题（杭电 OJ）

image.png

  • 解题代码和思路

思路：

  1. 从内到外一层一层画(for循环：外框尺寸每次增长2)
  2. 画外筐（4个边 == 4个for循环）
  3. 终止条件由输入的三元组中的外筐尺寸确定，并且最后要删去四个角
  4. 注意输入时题目要求输入一个个三元组要用while+scanf的方法，输出则采用行输出二维数组的字符串的方法 
 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 <cstdio>  
  
int main() {  
    int n; //外筐尺寸  
    char inner,outer; //内外筐花色字符  
    bool flag = true;  
    printf("请输入三元组（外筐尺寸，中心花色字符，外筐花色字符）：");  
    while(scanf("%d %c %c",&n,&inner,&outer) != EOF) {  //输入一个个三元组  
  
        if(flag) {  //目的是实现题目说的除第一个筐外要空一格再输出  
            flag = false;  
        } else {  
            printf("\n");  
        }  
  
        int length,x,y;  
        char kuangImg[80][80] = {0};  
        char curColor = inner;  
        for (length = 1,x = n/2,y = n/2; length <= n; length+=2,x--,y--) {   //最外层循环：外筐尺寸由1增长到输入值n  
  
            //顶边  
            for (int i = x,j = y; j <= y+length-1; ++j) {  
                kuangImg[i][j] = curColor;  
            }  
  
            //左边  
            for (int i = x,j = y; i <= x+length-1; ++i) {  
                kuangImg[i][j] = curColor;  
            }  
  
            //底边  
            for (int i = x+length-1,j = y; j <= y+length-1; ++j) {  
                kuangImg[i][j] = curColor;  
            }  
  
            //右边  
            for (int i = x,j = y+length-1; i <= x+length-1; ++i) {  
                kuangImg[i][j] = curColor;  
            }  
  
            //每一层筐变花色  
            if(curColor == inner) {  
                curColor = outer;  
            } else {  
                curColor = inner;  
            }  
        }  
        //除掉最外层筐的四个角  
        if(n != 1) {  
            kuangImg[0][0] = ' ';  
            kuangImg[n-1][n-1] = ' ';  
            kuangImg[n-1][0] = ' ';  
            kuangImg[0][n-1] = ' ';  
        }  
  
        for (int i = 0; i < n; ++i) {  
            printf("%s\n",kuangImg[i]);  
        }  
    }
}

日期问题

  1. 能被4整除但不能被100整除，或能被400整除的年份即为闰年。
    bool isLeap = year%400 == 0 || year%100 != 0 && year%4 == 0;
  2. 机试中如何使用字符串（输入输出 C 风格，其他复杂的比较情况 C++风格）: image.png
  3. 日期问题有时会要求格式(例如 yyyy-mm-dd 的日期打印格式)，用 printf 来打印,格式有下面两种:
    1. %4d:表示至少四个位置宽,不足四个位置的话则用空格填充
    2. %04d:表示至少四个位置宽，不足四个位置则用0来填充
  4. 日期问题万能解决方案：nextDay() code-snapshot.png

今年的第几天？（牛客网）

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

// 空间换时间思路    
int main() {  
    int year,month,day;  
    int MonTable[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};  
    int totalDay[13] = {0};  
    for (int mon = 2; mon <= 12; ++mon) {  
        //计算从年初到mon月1日的天数 = 到（mon-1）月1日的天数 + 第（mon-1）月的天数  
        totalDay[mon] = totalDay[mon - 1] + MonTable[mon - 1];  
    }  
    while(scanf("%d%d%d",&year,&month,&day) != EOF) {  
        //判断是否是闰年  
        bool isLeap = year%400==0 || year%100!=0 && year%4==0;  
        if(isLeap && month >= 3) {  
            printf("%d\n",totalDay[month] + day + 1);  
        } else {  
            printf("%d\n",totalDay[month] + day);  
        }  
    }}

打印日期（牛客网）

 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 <cstdio>  
  
int main() {  
    int year,n;   //year：年份，n：第n天  
    int monthTable[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};  
    while (scanf("%d %d",&year,&n) != EOF) {  
        int month = 1,day = 1; // 默认从1月1号开始算起  
        //nextDay万能方法如下：
        for (int i = 0; i < n-1; ++i) {  
            //判断闰年  
            bool isLeap = year%400==0 || year%100!=0 && year%4==0;  
            if(isLeap) {  
                monthTable[2] = 29;  
            } else {  
                monthTable[2] = 28;  
            }  
            day++;  
            if(day > monthTable[month]) {   //日期加超过month了  
                day = 1;  
                month++;  
            }  
            if(month > 12) {    //月份超过12月重置为1月  
                month = 1;  
                year++;  
            }  
        }
        printf("%04d-%02d-%02d\n",year,month,day);          
    }  
}

Day of Week（牛客网）

主体思路:
image.png

  1. 以当前日期作为基准，输入一个日期，此日期有可能在当前日期之前或之后，所以要分类讨论
  2. 在当前日期之前，则需要统计{相隔的天数 - x（当前日期星期 x）}%7得到输入的日期是星期几
  3. 在当前日期之后，则需要统计{相隔的天数 + x（当前日期星期x）}%7得到输入的日期是星期几

Tips:

  1. 因为题中要求月份输入为字符串,但是后续算法处理时要用数字最好,所以要用 map 做月份(string)和数字(int)之间的一一映射
  2. 题目中要求输出字符串,不妨直接用数组做数字 int 和月份 string 之间的映射 
 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

#include <cstdio>  
#include <map>  
#include <string>  
using namespace std;  
  
int main() {  
   int year,month,day;  
   char str[100];  
   string mon;  
   bool isBefore;  
   int MonthTable[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};  
   string IntToWeekend[7] = {"Sunday","Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};  
   map<string,int> MonthStringToInt = {  
           {"January",1},  
           {"February",2},  
           {"March",3},  
           {"April",4},  
           {"May",5},  
           {"June",6},  
           {"July",7},  
           {"August",8},  
           {"September",9},  
           {"October",10},  
           {"November",11},  
           {"December",12},  
   };  
   while(scanf("%d %s %d",&day,str,&year) != EOF) { //C风格处理输入输出  
        mon = str; // C风格转C++便于后续处理  
        month = MonthStringToInt[mon]; // 字符串转数字便于后续处理  
        //判断输入的日期在今天之前还是之后  
        if(year < 2023 || 2023 == year && month < 3 || 2023 == year && month == 3 && day < 3) {  
            isBefore = true;  
        } else {  
            isBefore = false;  
        }  
  
        //从begin走到end  
        int begYear,begMon,begDay,endYear,endMon,endDay;  
        if(isBefore) {  
            begYear = year;  
            begMon = month;  
            begDay = day;  
            endYear = 2023;  
            endMon = 3;  
            endDay = 3;  
        } else {  
            begYear = 2023;  
            begMon = 3;  
            begDay = 3;  
            endYear = year;  
            endMon = month;  
            endDay = day;  
        }  
  
        int totalDay = 0;   //begDay到endDay中间经历了多少天  
        while(true) {  
            if(begYear == endYear && begMon == endMon && begDay == endDay) {  
                break;  
            }  
            //判断从beg移动到end过程中此时是否是闰年  
            bool isLeap = begYear%400 == 0 || begYear%4 == 0 && begYear%100 != 0;  
            if(isLeap) {  
                MonthTable[2] = 29;  
            } else {  
                MonthTable[2] = 28;  
            }  
  
            totalDay++;  
            //nextDay()  
            begDay++;  
            if(begDay > MonthTable[begMon]) {   //日期加超过当月了  
                begDay = 1;  
                begMon++;  
                if(begMon > 12) {    //月份超过12月重置为1月  
                    begMon = 1;  
                    begYear++;  
                }  
            }        }  
        //分类处理  
        if(isBefore) {  //2023-3-3之前  
            //(x+totalDay)%7 = 5 --> x = (12 - totalDay % 7) % 7  
            printf("%s\n", IntToWeekend[(12 - totalDay % 7) % 7].c_str());  
        } else {    //2023-3-3之后  
            printf("%s\n", IntToWeekend[(totalDay + 5) % 7].c_str()); //2023-3-3是星期五  
        }  
   }}

剩下的树（牛客网）

思路如下：

  1. 用一个很大的 bool 类型数组表示马路上的一排树，用 true 和 false 表示树的死活
  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

#include <cstdio>  
  
int main() {  
    bool Trees[10000];   //true表示树活，false表示树死  
    int M,L;  
    while(scanf("%d%d",&L,&M) != EOF) {  
        int left,right;  
        for (int i = 0; i <= L; ++i) {  
            Trees[i] = true;  
        }  
        for (int i = 0; i < M; ++i) {  
            scanf("%d%d",&left,&right);  
            for (int j = left; j <= right; ++j) {  
                Trees[j] = false;  
            }  
        }        
        int restTrees = 0;  
        for (int i = 0; i <= L; ++i) {  
            if(Trees[i]) {  
                restTrees++;  
            }  
        }        printf("%d",restTrees);  
    }  
}

手机键盘九宫格（牛客网）

思路如下：

  1. 九宫格布局图如下：
    image.png
  2. 需要解决的两个关键问题：（用 map 进行映射）
    ① 手机数字按键和其对应字母的关系（从而判断等待与否）。
    ② 输入某一个字母需要按几次对应的数字按键。 
 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 <cstdio>  
#include <map>  
using namespace std;  
  
int main() {  
    char str[101];  
    map<char,int> PushTimes = {     //记录输入某字母需要按几次按键  
            {'a',1},{'b',2},{'c',3},  
            {'d',1},{'e',2},{'f',3},  
            {'g',1},{'h',2},{'i',3},  
            {'j',1},{'k',2},{'l',3},  
            {'m',1},{'n',2},{'o',3},  
            {'p',1},{'q',2},{'r',3},{'s',4},  
            {'t',1},{'u',2},{'v',3},  
            {'w',1},{'x',2},{'y',3},{'z',4},  
    };  
    map<char,int> WordToInt = {     //记录某字母属于哪个数字按键  
            {'a',2},{'b',2},{'c',2},  
            {'d',3},{'e',3},{'f',3},  
            {'g',4},{'h',4},{'i',4},  
            {'j',5},{'k',5},{'l',5},  
            {'m',6},{'n',6},{'o',6},  
            {'p',7},{'q',7},{'r',7},{'s',7},  
            {'t',8},{'u',8},{'v',8},  
            {'w',9},{'x',9},{'y',9},{'z',9},  
    };  
    while(scanf("%s",str) != EOF) {  
        int time = 0;  
        int buttonBefore = 1;   //上一次按下的数字按键  
        for (int i = 0; str[i] != '\0'; ++i) {  
            if(buttonBefore == WordToInt[str[i]]) {   //等待用时  
                time += 2;  
            }  
            time += PushTimes[str[i]];  //按下此按键用时  
            buttonBefore = WordToInt[str[i]]; //记录每次按下的按键作为下一次的上一次按键参考  
        }  
        printf("%d\n",time);  
    }  
}

其他模拟问题

完数 VS 盈数（牛客网）

 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 <cstdio>  
#include <vector>  
using namespace std;  
  
int sum_index(int x) {    //一个数的各因子(该数本身除外)的和，如：6==>3+2+1  
    int sum = 0;  
    for (int i = 1; i < x ; ++i) {  
        if(x%i == 0) {  
            sum = sum + i;  
        }  
    }    
    return sum;  
}  
  
int main() {  
    vector<int> Enumber;  
    vector<int> Gnumber;  
  
    for (int i = 2; i <= 60 ; ++i) {  
        if(i == sum_index(i)) {  
            Enumber.push_back(i);  
        }  
        else if(sum_index(i) > i){  
            Gnumber.push_back(i);  
        }  
    }  
    printf("E:");  
    for (int i = 0; i < Enumber.size(); ++i) {  
        printf(" %d",Enumber[i]);  
    }  
    printf("\n");  
  
    printf("G:");  
    for (int i = 0; i < Gnumber.size(); ++i) {  
        printf(" %d",Gnumber[i]);  
    }  
}

约瑟夫问题

  • 问题描述
    1. n 个人围坐一圈，并按顺时针编号为 1~n，从编号 p 的人顺时针依次报数，从 1 报到 m，报到 m 的那个人立刻出局，然后这个人的下一个人再从 1 开始报数（顺时针），报到 m 的那个人再次出局，以此类推，直到所有人都出局，要求按出局的先后顺序输出编号。
    2. 输入：（n，p，m）三元组。（例如：8 3 4）
    3. 输出：按出局的顺序输出编号，编号之间以逗号间隔。（例子输出：6,2,7,4,3,5,1,8）
  • 思路&代码
  1. 先初始化队列，编号为 1 ~ n。
  2. 然后把编号 1 ~ p-1 的元素逐个 pop 出队列再 push 回队列末尾。
  3. while 大循环检测队列是否为空，循环内部进行报数 number 变量的计数。
    1. 在 number 未达到输入的 m 时就 pop 队首元素再 push 回队尾（和 2 一样）。
    2. 如果 number 一旦达到 m，则直接 pop 队首元素，打印队首元素，number 重置，进入下一轮循环，直到队列为空（实现了按出局的顺序输出编号）。 
 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 <cstdio>  
#include <queue>  
using namespace std;  
  
int main() {  
    queue<int> q1;  
    int n,m,p;  
    int number = 0; //报的数  
    int temp = 0; //临时变量  
  
    scanf("%d %d %d",&n,&p,&m);  
    for (int i = 1; i <= n; ++i) {  
        q1.push(i);  
    }  
    for(int i = 1; i <= p-1; ++i) {  
        q1.pop();  
        q1.push(i);  
    }  
  
    while(!q1.empty()) {  
        temp = q1.front();  
        q1.pop();  
        number++;   //从1开始报数  
        if(number == m) {  
            printf("%d,",temp);  
            number = 0;  
        } else {  
            q1.push(temp);  
        }  
    }
}

圆圈中最后剩下的数字（剑指 Offer 62）

思路：约瑟夫问题的变种，参考上题思路。

 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

//暴力模拟解法，不通Leetcode，超时，但是OJ应该能通？
#include <cstdio>  
#include <queue>  
using namespace std;  
  
int main() {  
    queue<int> q1;  
    int n,m;  
    int number = 0; //计数  
    int temp;   //临时变量  
  
    scanf("%d%d",&n,&m);  
    for (int i = 0; i < n; ++i) {  
        q1.push(i);  
    }  
  
    while(q1.size() != 1) {  
        temp = q1.front();  
        q1.pop();  
        number++;  
        if(number != m){  
            q1.push(temp);  
        } else {  
            number = 0;  
        }  
    }    printf("%d", q1.front());  
}

猫狗收容所（简单）

  • 题目描述：
    image.png
  • 思路&代码：
  1. 设计数据结构：
    1. Animal 结构体（C++设计方法）==> 其中两个 int 变量，一个动物编号（表示动物类型），一个序号（表示猫&狗进入收养所的先后顺序）。
    2. 两个队列 queue，一个存猫，一个存狗。
  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
74
75
76
77
78
79
80
81
82
83

//猫狗收容所  
#include <cstdio>  
#include <queue>  
using namespace std;  
  
struct Animal{  
    int num;  
    int seq;  
};  
  
int main() {  
    queue<Animal> catQue;  
    queue<Animal> dogQue;  
    int n;  //n：操作序列次数  
    int animalSeq = 0;  
  
    scanf("%d",&n);  
    for (int i = 0; i < n; ++i) {  
        int m,t;    //m：第一个元素 t：第二个元素  
        scanf("%d%d", &m, &t);  
        if(m == 1) {    //有动物进入收容所  
            if(t > 0) {  
                Animal dog{};  
                dog.num = t;  
                dog.seq = animalSeq;  
                dogQue.push(dog);  
                animalSeq++;  
            }  
            else {  
                Animal cat{};  
                cat.num = t;  
                cat.seq = animalSeq;  
                catQue.push(cat);  
                animalSeq++;  
            }  
        }        
        else if(m == 2){  //有人收养动物  
            if(t == 0) {    //第一种收养方式  
                //有猫无狗，有狗无猫，有猫有狗，无狗无猫（不合法操作，啥也不干）  
                if(!dogQue.empty() && !catQue.empty()) {    //有猫有狗  
                    if(dogQue.front().seq > catQue.front().seq) {  
                        printf("%d ", catQue.front().num);  
                        catQue.pop();  
                    }  
                    else {  
                        printf("%d ", dogQue.front().num);  
                        dogQue.pop();  
                    }  
                }                
                else if(dogQue.empty() && !catQue.empty()) {    //有猫无狗  
                    printf("%d ", catQue.front().num);  
                    catQue.pop();  
                }  
                else if(!dogQue.empty() && catQue.empty()) {    //有狗无猫  
                    printf("%d ", dogQue.front().num);  
                    dogQue.pop();  
                }  
                else {  //无狗无猫  
                    continue;  
                }  
            }           
            else if(t == 1){    //指定收养狗  
                if(!dogQue.empty()){  
                    printf("%d ", dogQue.front().num);  
                    dogQue.pop();  
                }  
                else {  
                    continue;  
                }  
            }          
	        else {  //指定收养猫  
                if(!catQue.empty()) {  
                    printf("%d ", catQue.front().num);  
                    catQue.pop();  
                }  
                else {  
                    continue;  
                }  
            }
        }    
    }    
    printf("\n");  
}

Zero-complexity Transposition

排序问题

排序问题可以直接利用 C++的库函数 sort 来解决，方便快捷，不用关注排序本身的算法优化。

  1. sort 函数如何引入？#include<algorithm> using namespace std;
  2. sort 函数如何使用？sort() 函数有 2 种用法如下：（cplusplus网站上的API解释）
    1. void sort (RandomAccessIterator first, RandomAccessIterator last); 对 [first, last) 区域内的元素做默认的升序排序，其中 first 和 last 都是元素的地址（数组名，结构体数组元素前加&取地址）
    2. void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);按照指定的 comp 排序规则，对 [first, last) 区域内的元素进行排序，comp 可以是 C++ STL 标准库提供的排序规则（比如 std:: greater <T>），也可以是自定义的排序规则。
    3. 关于 comp 函数：
    comp 函数往往是我们需要自己定义的 bool 类型的函数 bool comp（RandomAccessIterator lhs，RandomAccessIterator rhs），lhs（left hand side） 是左边的数，rhs （right hand side）是右边的数，其具体实现是 programmer 按照题目要求进行设计，关键的条件是在比较待排数组里面的左边一个数 lhs 和右边一个数 rhs 时不需要交换则返回 true，反之返回 false。

排序问题的通用解决思路

  1. 找到题目中问题的最原子的比较和交换的条件（就是 comp 函数不需要交换的比较条件）。
  2. 根据找到的条件设计 comp 函数。
  3. 用 sort（first，last，comp）进行排序，其中 first 是待排数组的第一个元素的地址，其实就是数组名，last 是待排数组最后一个元素的下一个空位的地址，就是数组名 + 数组长度（数字）。

排序（牛客网）

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

#include <cstdio>  
#include <algorithm>  
using namespace std;  
  
int main() {  
    int n;  //几个整数  
    int arr[100];  
    while(scanf("%d",&n) != EOF) {  
        for(int i = 0;i < n;i++) {  
            scanf("%d",&arr[i]);  
        }  
        sort(arr,arr+n);  
        for(int i = 0;i < n;i++) {  
            printf("%d ",arr[i]);  
        }  
        printf("\n");  
    }  
}

整数奇偶排序（牛客网）

思路如下：

  1. 该问题在 comp 函数中的原子问题可以分为下面三种情况
    1. lhs 是奇数，rhs 也是奇数，则当 lhs > rhs 时返回 true
    2. lhs 是偶数，rhs 也是偶数，则当 lhs < rhs 时返回 true
    3. lhs 是奇数，rhs 是偶数时返回 truw
  2. 设计 comp 函数
  3. 写 sort 逻辑
 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 <cstdio>  
#include <algorithm>  
using namespace std;  
  
bool comp(int lhs,int rhs){  
    if(lhs%2 == 1 && rhs%2 == 0) {  
        return true;  
    } else if(lhs%2 == 1 && rhs%2 == 1 && lhs > rhs) {  
        return true;  
    } else if(lhs%2 == 0 && rhs%2 == 0 && lhs < rhs) {  
        return true;  
    } else {  
        return false;  
    }  
}  
int main() {  
    int arr[10];  
    while(scanf("%d%d%d%d%d%d%d%d%d%d",  
                arr,arr+1,arr+2,arr+3,arr+4,arr+5,arr+6,arr+7,arr+8,arr+9) != EOF) {  
        sort(arr,arr+10,comp);  
        for (int i = 0; i < 10; ++i) {  
            printf("%d ",arr[i]);  
        }  
        printf("\n");  
    }  
}

成绩排序 1（牛客网）

  1. 自定义符合题目条件的学生结构体。
  2. 注意 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

#include <cstdio>  
#include <algorithm>  
using namespace std;  
  
typedef struct {  
    int num;  
    int score;  
}Student;  
  
bool comp(Student lhs,Student rhs) {  
    if(lhs.score < rhs.score) {  
        return true;  
    }  
    else if(lhs.score == rhs.score && lhs.num < rhs.num) {  
        return true;  
    }  
    else {  
        return false;  
    }  
}  
  
int main() {  
    Student stu[100];  
    int n;//学生的个数  
    while(scanf("%d",&n) != EOF) {  
        for(int i = 0;i < n;i++) {  
            scanf("%d%d",&stu[i].num,&stu[i].score);  
        }  
        sort(&stu[0],&stu[n],comp);  
        for (int i = 0; i < n; ++i) {  
            printf("%d %d\n",stu[i].num,stu[i].score);  
        }  
    }}

成绩排序 2（牛客网）

思路如下：

  1. 设计用户结构体。
  2. 设计 comp 函数，按题意需要设计两个 comp（一个升序，一个降序）。
  3. 题目中还要求相同成绩都按先录入排列在前的规则处理，即要求排序稳定，所以要用 stable_sort ()函数，其用法和 sort 一样。 
 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

#include <cstdio>  
#include <algorithm>  
#include <string>  
using namespace std;  
  
typedef struct {  
    char name[1000];  
    int score;  
}UserInfo;  
  
bool compDown(UserInfo lhs,UserInfo rhs) { //降序comp  
    return lhs.score > rhs.score;  
}  
  
bool compUp(UserInfo lhs,UserInfo rhs) { //升序comp  
    return lhs.score < rhs.score;  
}  
  
int main() {  
    int n; //输入用户个数  
    int way; //排序方法：0表示降序，1表示升序  
    UserInfo user[1000];  
    while(scanf("%d%d",&n,&way) != EOF) {  
        for (int i = 0; i < n; ++i) {  
            scanf("%s %d",user[i].name,&user[i].score);  
        }  
  
        if(way == 0){   //降序  
            stable_sort(&user[0],&user[n],compDown);  
        }else{  //升序  
            stable_sort(&user[0],&user[n],compUp);  
        }  
  
        for (int i = 0; i < n; ++i) {  
            printf("%s %d\n",user[i].name,user[i].score);  
        }  
    }  
}

查找问题

查找问题的解决方法 ：（一般有以下三种）

  1. 顺序查找（最暴力的查找办法）

    1. 直接从头到尾挨个比较查找，但时间复杂度很高。
    2. 如果有 M 个不同的数需要在数组中查找，数组长度为 N 的情况下，则时间复杂度来到了 O（MN）的数量级。
    3. 一般来说电脑的 CPU 频率为 x GHZ，翻译过来就是每秒可以执行 10^9 数量级的指令，那么假如数组长度和输入数据的数量级相乘超过 x GHZ，题目又要求执行时间不能超过 1 s，那就超时了。
    4. 所以顺序查找不适合多组不同数据待查的问题，容易有超时的可能。

  2. 二分查找

    1. 二分查找的前提条件是有序数组，所以一般要把数组先进行排序（用 sort 函数）。
    2. 二分查找非常易错的一点：规避 mid，在 right 前移或者 left 后移时，一定要规避 mid，否则可能会发生死循环的情况。(right = mid - 1 left = mid + 1)
    3. 为什么二分查找的终止条件是left <= right，如果不放这个条件，while遍历就会遍历到之前已经遍历过的区域，为什么要加上=的判断条件，因为将左指针和右指针相同的时候，就是判断指针本身和目标值是否相等。每当这里想不清楚的时候，就拿最简单的例子：1，2，3来做推理。要想知道3在不在他们中间，先比较3和2，然后3比2大，left = mid + 1 = 3，right = right = 3;这时候left 和 right相等，他们的中间也就是3,3=3，于是3在他们中间，如果left < right 就返回，就会返回错误的答案。
    4. 二分查找一个完整的函数实现如下：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

//非递归的二分查找，查到target返回true，反之返回false 
//array:数组    n:数组的大小    target:待查找的数据
bool binarySearch(int array[], int n, int target) {
	int left = 0, right = n, mid = 0;
	while(left <= right) {
		mid = (left + right)/2;
		if(target == array[mid]) {
			return true;
		} else if(target < array[mid]) {
			right = mid - 1;
		} else if(target > array[mid]) {
			left = mid + 1;
		}
	}
	return false;
}
  1. 用 map 解决查找问题（首选推荐，用空间换简单代码）
    1. 通过 map 建立数组元素（键）和数组下标（值）的映射关系。
    2. 用 map 的 find 方法进行键的查找，从而得到值。（迭代器 - OI Wiki (oi-wiki.org)）（关联式容器 - OI Wiki (oi-wiki.org)）
    3. map 的底层实现是二叉查找树（Windows 编译器下是平衡二叉查找树，Linux 编译器下是红黑树），map 内部所有的数据都是有序的，且 map 中的元素是自动按 key 升序排序,所以不能对 map 用 sort 函数。

找 x（牛客网）

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

#include<cstdio>  
  
int main() {  
    int n,x;  
    int arr[201];   
    while(scanf("%d",&n) != EOF) {  
        for (int i = 0; i < n; ++i) {  
            scanf("%d",&arr[i]);  
        }  
        scanf("%d",&x);  
        int j;  
        for (j = 0; j < n; ++j) {  
            if(x == arr[j]) {  
                printf("%d",j);  
                break;  
            }  
        }       
        if(j == n) {    //不在数组中则输出-1  
            printf("-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

//方法一：二分查找
#include <cstdio>  
#include <algorithm>  
using namespace std;  
  
int arr[101]; //全局数组方便函数共享  

//n：数组长度  target：待查找的目标数字
bool binaryResearch(int n,int target) {  
    int low = 0,high = n-1,mid = 0;  
    while(low <= high) {  
        mid = (low + high)/2;  
        if(arr[mid] == target){  
            return true;  
        }  
        else if(arr[mid] < target) {  
            low = mid + 1;  
        }  
        else {  
            high = mid - 1;  
        }  
    }    
    return false;  
}  
  
int main() {  
    int n,m;  
    int curResearch;      
    while(scanf("%d",&n) != EOF) {  
        for (int i = 0; i < n; ++i) {  
            scanf("%d",arr+i);  
        }  
        sort(arr,arr+n);  //排序  
        scanf("%d",&m);  
        for (int i = 0; i < m; ++i) {  
            scanf("%d",&curResearch);  
            bool flag = binaryResearch(n, curResearch);  
            if(flag) {  
                printf("YES\n");  
            } else {  
                printf("NO\n");  
            }  
        }    }}

方法二：map 方法

  1. 用 map 数据结构存储数组元素（键） ==> 数组元素下标（值）的映射。
  2. 利用 map 的 find 方法进行查找（find(x): 若容器内存在键为 x 的元素，会返回该元素的迭代器；否则返回 end()）。 
 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 <cstdio>  
#include <map>  
using namespace std;  
  
int main() {  
    int arr[101];  
    int n,m;  
    map<int,int> findIndex;  
    while(scanf("%d",&n) != EOF) {  
        for (int i = 0; i < n; ++i) {  
            scanf("%d",arr+i);  
            //map存储：数组元素（键） ==> 数组元素下标（值）的映射  
            findIndex[arr[i]] = i;  
        }  
        scanf("%d", &m);  
        for (int i = 0; i < m; ++i) {  
            int curFind; //待查元素  
            scanf("%d",&curFind);  
            //find方法查找成功时会返回键对应的迭代器  
            if(findIndex.find(curFind) == findIndex.end()) {  
                //find方法在没找到键时返回的是end迭代器  
                printf("NO\n");  
            } else {  
                printf("YES\n");  
            }  
        }    
    }
}

搜索问题

搜索问题本质上是一个有限制的枚举问题，枚举是列出所有状态，然后每个状态都可以随意的转移到另一种状态，而搜索问题往往对应着图/网的数据结构，从一个节点出发没法任意转移到其余各个节点。

广度优先搜索（BFS）

  1. 广度优先搜索算法（英语：Breadth-First Search，缩写为 BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索演算法。简单的说，BFS 是从[根节点]( https://zh.wikipedia.org/wiki/%E6%A0%91_ (%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84)#%E6%9C%AF%E8%AF%AD “树 (数据结构)")开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。
  2. BFS 是一种暴力搜索算法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止
  3. BFS 的具体实现：
    1. 创建一个辅助队列（用于不断插入每一层的 BFS，然后和目标待搜元素比对）&一个辅助集合（bool isVisited[MAX]，表示某一节点是否被访问过）
    2. 将起始节点（初始状态）加入队列。
    3. while 大循环（队列非空）
    1. pop 取出队首元素 front，修改 isVisited[front] = true（比对代搜元素）
    2. 将 front 的所有邻居加入队列（同时排除已经访问过的节点，即 isVisited == true 的节点）
    3. pop 取出队首元素 front，修改 isVisited[front] = true（比对代搜元素）
    4. 只要搜到就 break 退出 while 大循环（或者加上按照题目要求打印 blabla 的代码）
  4. 往往在题目中求什么最优解，最优路径等等问题上要考虑 BFS。

Catch That Cow（北大 OJ）

用 BFS 的思路解决：其实就是对一个三叉树做上述的 BFS 算法，每个节点 x 延展出去的三个叉都对应着 x+1、x-1、x* 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

//Catch That Cow  
#include <cstdio>  
#include <queue>  
using namespace std;  
  
struct Farmer{  
    int pos;    //Farmer当前位置  
    int time;   //Farmer目前已用时几分钟  
};  
  
int main() {  
    int n,k;  
    queue<Farmer> farmerQue;    //队列  
    bool isVisited[100001]; //表示某一节点是否被访问  
    for (int i = 0; i < 100001; ++i) {  //初始化  
        isVisited[i] = false;  
    }  
  
    scanf("%d%d", &n, &k);  
  
    //存入第一个节点  
    Farmer first;  
    first.pos = n;  
    first.time = 0;  
    farmerQue.push(first);  
  
    while(!farmerQue.empty()) {  
  
        Farmer temp = farmerQue.front();  
        farmerQue.pop();  
        isVisited[temp.pos] = true;  
  
        if(temp.pos == k){  
            printf("%d",temp.time);  
            break;  
        }  
  
        Farmer neighbor;  //邻居节点（临时）  
        if(temp.pos-1 >= 0 && temp.pos-1 <= 100000 && !isVisited[temp.pos-1]) {  
            neighbor.pos = temp.pos - 1;  
            neighbor.time = temp.time + 1;  
            farmerQue.push(neighbor);  
        }  
        if(temp.pos+1 >= 0 && temp.pos+1 <= 100000 && !isVisited[temp.pos+1]) {  
            neighbor.pos = temp.pos + 1;  
            neighbor.time = temp.time + 1;  
            farmerQue.push(neighbor);  
        }  
        if(temp.pos*2 >= 0 && temp.pos*2 <= 100000 && !isVisited[temp.pos*2]) {  
            neighbor.pos = temp.pos * 2;  
            neighbor.time = temp.time + 1;  
            farmerQue.push(neighbor);  
        }  
    }
}

Find The Multiple

思路：

  1. 用 BFS 生成所有由 0 和 1 构成的正整数。
    IMG_0609(20230309-211959).PNG
  2. 用 BFS 搜索上面生成的树，当搜到的数字%n == 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

#include <cstdio>  
#include <queue>  
using namespace std;  
  
int main() {  
    int n;  
  
    while (true) {  
        scanf("%d", &n);  
        queue<long long> mulQue;  
        mulQue.push(1);  
        if(n == 0) {  
            break;  
        }  
  
        while (!mulQue.empty()) {  
            long long temp = mulQue.front();  
            mulQue.pop();  
  
            if(temp % n == 0) {  
                printf("%lld\n", temp);  
                break;  
            }  
  
            mulQue.push(temp*10);  
            mulQue.push(temp*10 + 1);  
        }  
    }}

动态规划问题（DP 问题，Dynamic Programming）

动态规划（英語：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。

  1. 动态规划问题一般形式就是求最值（比如求最长递增子序列）。
  2. 动态规划的核心问题是穷举（分析问题初步要用穷举的思想，将问题原规模减小，然后穷举，寻找规律）。计算机可以暴力穷举（递归），也可以利用“备忘录”（存储递归过程中已经形成的一些状态值，从而给递归树剪枝，减小时间复杂度）或DP Table（常用这种办法，本质上就是利用一个数组存储穷举的各种状态的对应值形成的表，此时是自底向下的迭代思想，设置边界条件初值 dp【0 或 1】，然后代入状态转移方程，从而迭代求出 dp【i】）。
  3. 动态规划三要素：重叠子问题、最优子结构、状态转移方程
  • 重叠子问题：如果暴力穷举（递归）的话，就会出现重叠子问题。（画递归树，只要存在重复节点，就说明存在重叠子问题）
    image.png
  • 最优子结构：「最优子结构」是某些问题的一种特定性质，并不是动态规划问题专有的。也就是说，很多问题其实都具有最优子结构，只是其中大部分不具有重叠子问题，所以我们不把它们归为动态规划系列问题而已。我先举个很容易理解的例子：假设你们学校有 10 个班，你已经计算出了每个班的最高考试成绩。那么现在我要求你计算全校最高的成绩，你会不会算？当然会，而且你不用重新遍历全校学生的分数进行比较，而是只要在这 10 个最高成绩中取最大的就是全校的最高成绩。我给你提出的这个问题就符合最优子结构：可以从子问题的最优结果推出更大规模问题的最优结果。让你算每个班的最优成绩就是子问题，你知道所有子问题的答案后，就可以借此推出全校学生的最优成绩这个规模更大的问题的答案。
  • 状态转移方程：一个状态 = 该状态之前的状态进行运算 就是状态转移方程。
  1. DP Table：边界条件 + 状态转移方程 自底向上迭代求出所有结果。

爬楼梯（Leetcode 70 题 简单）

  1. 将大规模问题拆解为小规模问题先行思考，比如这题先假设从 0 楼爬到 3 楼（一共要爬 4 层楼）的情况，那么可以推出爬到 4 楼的方法种数 = 爬到 3 楼的方法种数 ＋ 爬到 2 楼的方法种数 = 5 种。
  2. 不难推出该 dp 问题的状态转移方程：dp【i】 = dp【i-1] + dp【i-2】。
  3. 设置边界条件 dp【0】 = dp【1】 = 1，利用状态转移方程自底向上迭代求出所有情况。
  • 代码实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

//DP Table迭代法
class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n+1);
		for(int i = 0;i <= n;i++){
			dp[i] = 0;
		}
		dp[0] = 1; //边界条件，爬0层楼就一种方法
		dp[1] = 1; //爬一层楼也就一种方法
		for(int i = 2;i <= n;i++){
			dp[i] = dp[i-1] + dp[i-2]; //状态转移方程
		}
		return dp[n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

//状态压缩，减小空间复杂度，该题不需要用一个大的数组存储所有的状态值
class Solution {
public:
    int climbStairs(int n) {
       int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }
};
-------他日江湖相逢 再当杯酒言欢-------
分享
Calvin Haynes
❉ 作者: Calvin Haynes ❉
Life is a journey, not a destination.
总访客 ...
总浏览 ...

©2023, All Rights Reserved自由转载-非商用-非衍生-保持署名

Powered by Hugo on Github | 吉ICP备2021002455号

构建工具Hugo v0.111.0 托管于阿里云 图床阿里云OSS 主题Zzo theme
目录