一、字符串
1.字符与整数的联系--ASCII表
'0'~'9' :48~57 'A'~'Z':65~90 'a'~'z':97~122
字符与数字之间转换:
1.1字符转数字：
字符转数字：
char c = 'A';
cout << c-'A' << endl; //输出0
cout << (int)c << endl; //输出65 字符数字转数字：
char c = '0';
cout << c-'0' << endl; //输出0
cout << (int)c << endl; //输出481.2数字转字符：
int x = 1;
cout << (char)(x+'0') << endl; //输出'1'2.字符数组
字符串就是字符数组+结束符'\0'
可以用字符串初始化字符数组，但每个字符串结尾会暗含一个'\0'
如：以下等价
char[] s = "hellow"; //长度7
char[] s = {'h', 'e', 'l', 'l', 'o', 'w', '\0'}; //长度7
2.1输入字符串
cin和scanf读入字符串，遇见空格或回车或结束符就会停止
#include <cstdio>
#include <iostream>
using namespace std;
int main(){
char s[10];
//字符串的读入，读到空格或回车停止
scanf("%s", s);
//cin >> s;
printf("%s\n", s);
//cout << s << endl;
return 0;
}2.2读入一行到字符数组 char[]：gets()不安全，改用fgets()或cin.getline()
//读入一行到字符数组
//1.fgets(字符数组，最多读入的字数，从哪个文件读入)
char s[100];
fgets(s, 100, stdin); //"hello word" //2.cin.getline(字符数组，最多读入的字数)
char s[100];
cin.getline(s, 100);
cout << s << endl; // "hello word"2.3读入一行到字符串 string：getline()
//读入一行到字符串string
//getline(cin, 字符串)
string s;
getline(cin, s);
cout << s << endl; // "hello word"3.字符串操作库函数 C++：<string> C：<cstring>或<string.h>
3.1字符串复制
C/C++中函数原型char *strcpy(char *destin，char *source)，将source字符串复制到destin 。
#include <stdio.h>
#include <string.h>
int main(){
char name[10] = {};
char *str = "zhangsan";
strcpy(name, str); //将字符串str复制到name
printf("%s\n", name); //zhangsan
return 0;
}3.2字符串拼接
C/C++中函数char *strcat(char *dest，char *source)，可以将source字符串拼接到dest后面。注意,dest必须有足够的空间来容纳拼接出的字符串。
#include <stdio.h>
#include <string.h>
int main(){
char dest[25] = {};
char *str1 = "Hello", *str2 = " ", *str3 = "zhangsan";
strcat(dest, str1); //"Hello"
strcat(dest, str2); //"Hello "
strcat(dest, str3); //"Hello zhangsan"
printf("%s\n", dest); //Hello zhangsan
return 0;
}3.3字符串比较
C/C++中函数int strcmp(char *str1，char *str2)，从第一个字符开始逐字符比较两个字符串的ASCII码（按字典序比较）。如果下标为i的字符不相等，则函数返回str1[i] - str2[i]。如果两个字符串完全相同，则会返回0。即strcmp(a, b)，a<b返回-1，a>b返回1，a==b返回0
#include <stdio.h>
#include <string.h>
int main(){
char *str1 = "cd", *str2 = "abc";
int res = strcmp(str1, str2); //若下标为i的字符不相等，则返回str1[i]-str2[i]
if (res > 0){
printf("%s is greater than %s\n", str1, str2);
} else if(res == 0){ //字符串完全相同，返回0
printf("%s is same as %s\n", str1, str2);
} else {
printf("%s is less than %s\n", str1, str2);
}
return 0;
}3.4获取字符串长度
strlen(s1);
返回字符串 s1 的长度
3.5 C/C++常用字符串函数
| 1 | strcpy(s1, s2); 复制字符串 s2 到字符串 s1。 |
| 2 | strcat(s1, s2); 连接字符串 s2 到字符串 s1 的末尾。连接字符串也可以用 + 号，例如: string str1 = "runoob"; string str2 = "google"; string str = str1 + str2; |
| 3 | strlen(s1); 返回字符串 s1 的长度。 |
| 4 | strcmp(s1, s2); 如果 s1 和 s2 是相同的，则返回 0；如果 s1<s2 则返回值小于 0；如果 s1>s2 则返回值大于 0。 |
4.日期计算
4.1闰年
闰年比平年(非闰年)在2月份多一天。
- 1.年份非整百且能被4整除的为闰年。(如2004年就是闰年,2005年不是闰年)
- 2.年份能被400整除的是闰年。(如2000年是闰年，1900年不是闰年)
需要特别注意，能被100整除的年份，必须要被400整除才是闰年。
int is_leap_year(int y){
if ((y%100 != 0 && y%4 == 0) || (y%400 == 0)){
return 1;
}
return 0;
}4.2几年几月几日是星期几
题目：
蒜头君的生日快到了，蒜头君希望是在周末，蒜头君请你帮忙算出他生日在星期几。
输入格式
输入三个正整数，分别表示年、月、日。保证输入年份合法。
输出格式输出星期几。
用Monday . Tuesday . Wednesday . Thursday .Friday , Saturday ， Sunday表示星期几。
样例输入11 1 1
样例输出1Monday
样例输入22016 11 29
样例输出2Tuesday
#include <iostream>
#include <string>
using namespace std;
/**
星期几
输入三个正整数,分别表示年、月、日。保证输入年份合法。
样例输入：1 1 1
样例输出：Monday
**/
int whatday(int y, int m, int d){
//返回正确的星期。用0-6表示星期1 -7
int ans = 0;
//遍历年
for (int i = 1; i < y; i++){
if ((i%100!=0&&i%4==0) || (i%400==0)){ //闰年，2月多一天
ans += 366%7;
ans %= 7;
} else {
ans += 365%7;
ans %= 7;
}
}
//遍历月
for (int i = 1; i < m; i++){
if (i==1 || i==3 || i==5 || i==7 || i==8 || i==10 || i==12){ //1,3,5,7,8,10,12 有31天
ans += 31%7;
ans %= 7;
} else if (i==4 || i==6 || i==9 || i==11){ //4,6,9,11 有30天
ans += 30%7;
ans %= 7;
} else if ((y%100!=0&&y%4==0) || (y%400==0)){ //闰年2月有29天
ans += 29%7;
ans %= 7;
} else {
ans += 28%7;
ans %= 7;
}
}
//遍历日
ans += d%7;
ans %= 7;
return ans-1;
}
string weekday[7] = {"Monday", "Tuesday", "Wensday", "Thursday", "Friday", "Saturday", "Sunday"};
int main(){
int y, m, d;
cin >> y >> m >> d;
cout << weekday[whatday(y, m ,d)] << endl;
return 0;
} 4.3节假日
题目：
日历有阳历(公历)和阴历(农历)之分。每年都有法定节假日，这些分成三类——双休、阳历节假日、阴历节假日。
1.双休
1)周六和周日2天2.阳历节假日
1)元旦:阳历每年1月1日，放假1天2)劳动节:阳历每年5月1日，放假1天
3)国庆节:阳历每年10月1日，放假3天
4)圣诞节:阳历每年12月25日，放假1天
3.阴历节假日
1)春节:阴历每年1月1日,放假3天2)清明节:阳历每年4月4-6日之间的某天，放假1天
3端午节:阴历每年5月5日，放假1天4)中秋节:阴历每年8月15日,放假1天
当节假日和双休重合时,双休不延后也不提前,保证节假日之间不会重合。
现在给你某年的所有阴历节假日的阳历日期,以及当年的1月1日是星期几,请你计算出这一年(阳历1月1日到12月31日)放了多少天假(包括双休、阳历节假日和阴历节假日)。
输入格式
第一行输入年份y(1900<y ≤2050)。
接下来4行，每行输入两个整数m, d,依次表示春节、清明节、端午节和中秋节的阳历日期。
最后一行一个整数表示当年1月1号是星期几(—周内的第几天，每周从星期一开始计数，即星期一为第一天)。
输出格式
输出一个整数，表示当年放假的天数。
#include <cstdio>
/**
样例输入
2017
1 28
4 4
5 30
10 4
7
样例输出
113
**/
//表示1-12月的天数
int day[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
//阳历节假日
int mm[10] = {1, 5, 10, 10, 10, 12};
int dd[10] = {1, 1, 1, 2, 3, 25};
//月和日后移处理
int nextday(int &m, int &d){
d++;
if (d == day[m]+1){ //月底
d = 1;
m++;
}
}
int main(){
int y, m ,d, w, sf, ans;
scanf("%d", &y);
if ((y%100!=0&&y%4==0) || (y%400==0)){
day[2] = 29; //闰年2月为29天
}
//输入阴历节假日 依次表示春节、清明节、端午节和中秋节
for (int i = 6; i < 10; i++){
scanf("%d%d", &mm[i], &dd[i]);
}
//输入当年1月1号是星期几
scanf("%d", &w);
//从1月1日开始
m = 1;
d = 1;
//标记是否在春节里，0表示不在，正数表示春节剩余天数 （春节可能会跨年
sf = 0;
ans = 0; //统计放假天数
while (m != 13){
//春节可能会跨年，先做判断
if (m == mm[6] && d == dd[6]){ //当前为春节
ans++;
sf = 2; //春节剩余天数更新为2
} else if (sf){ //在春节期间
ans++;
sf--;
} else if (w == 6 || w == 7){ //双休
ans++;
}
else { //再遍历其他节日
for (int i = 0; i < 10; i++){
if (m == mm[i] && d == dd[i]){
ans++;
break;
}
}
}
//月和日后移处理
nextday(m, d);
//双休后移处理
w++;
if (w == 8){
w = 1;
}
}
printf("%d\n", ans);
return 0;
}5.sort排序
sort是一个C++已经为我们实现好的工具，当我们要用它时，需要先引入一个算法的库——<algorithm>。需要说明的是，sort可以排序任何类型的元素，包括我们自己定义的结构体。
5.1sort(a+i, a+j) 升序
那么被排序的将是arr[i]到arr[j - 1]，其他元素将保持原位置。
int arr[] = {2, 4 ,2 ,1 ,5, 3};
//将arr中从开始的元素到第5个元素按从小到大的顺序排列。
sort(arr, arr+5);
for (int i = 0; i < 6; i++){
cout << arr[i] << " "; //1 2 2 4 5 3
}5.2sort第三个参数—-“排序方法”
如果希望arr中的元素从大到小排列(或按照某一个规则进行排列)，我们可以再为sort传入第三个参数—-“排序方法”:
sort(arr, arr+5, greater<int>()); 其中，greater表示“更大”的意思, <int>表示待排序的数组中的元素类型为int，整个这行代码表示让一个元素类型为整数的数组从大到小排序。
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int x, int y){
return x > y; //x>y成立时，x>y
}
int main(){
int arr[10];
for (int i = 0; i < 10; i++){
cin >> arr[i];
}
sort(arr, arr+10);
for (int i = 0; i < 10; i++){
cout << arr[i] << " ";
}
cout << endl;
//降序
sort(arr, arr+10, cmp);
for (int i = 0; i < 10; i++){
cout << arr[i] << " ";
}
cout << endl;
return 0;
}5.3结构体排序
①成绩排序升级版
题目：
小蒜的老师汇总成绩后列出了成绩单，
其中包括每个同学的姓名和四科的成绩。
现在老师希望表扬一下每门课程考试得分前四名和总分前四名的同学，
同分数的情况下，名字字典序更小的先表扬。
输入格式
第一行为学生人数N(4≤N≤100)。
之后N行依次为每个学生的姓名和语文、数学、英语、科学这四门课程的成绩，之间用一个空格隔开（成绩都大于等于0小于等于100)。
输出格式
输出第一行为语文考试要表扬前四名的同学的姓名、之间用一个空格隔开。
输出第二行为数学考试要表扬前四名的同学的姓名，之间用一个空格隔开。
输出第三行为英语考试要表扬前四名的同学的姓名，之间用一个空格隔开。
输出第四行为科学考试要表扬前四名的同学的姓名，之间用一个空格隔开。
输出第五行为总分要表扬前四名的同学的姓名，之间用一个空格隔开。
样例输入
5
Alice 99 98 97 96
Bob 98 97 96 94
Coy 94 94 95 96
Dan 93 95 96 97
Evan 0 94 95 95
样例输出
Alice Bob Coy Dan
Alice Bob Dan Coy
Alice Bob Dan Coy
Dan Alice Coy Evan
Alice Bob Dan Coy
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
/**
样例输入
5
Alice 99 98 97 96
Bob 98 97 96 94
Coy 94 94 95 96
Dan 93 95 96 97
Evan 0 94 95 95
样例输出
Alice Bob Coy Dan
Alice Bob Dan Coy
Alice Bob Dan Coy
Dan Alice Coy Evan
Alice Bob Dan Coy
**/
struct Student {
char name[50];
int score[4];
};
Student stu[105];
bool cmp1(Student x, Student y){
if (x.score[0] != y.score[0]){
return x.score[0] > y.score[0];
}
return strcmp(x.name, y.name) < 0; //strcmp()<0 即x名字大于y不成立
}
bool cmp2(Student x, Student y){
if (x.score[1] != y.score[1]){
return x.score[1] > y.score[1];
}
return strcmp(x.name, y.name) < 0; //strcmp()<0 即x名字大于y不成立
}
bool cmp3(Student x, Student y){
if (x.score[2] != y.score[2]){
return x.score[2] > y.score[2];
}
return strcmp(x.name, y.name) < 0; //strcmp()<0 即x名字大于y不成立
}
bool cmp4(Student x, Student y){
if (x.score[3] != y.score[3]){
return x.score[3] > y.score[3];
}
return strcmp(x.name, y.name) < 0; //strcmp()<0 即x名字大于y不成立
}
//总分前4名
bool cmp(Student x, Student y){
int xsum = 0,ysum = 0;
for (int i = 0; i < 4; i++){
xsum += x.score[i];
ysum += y.score[i];
}
if (xsum != ysum){
return xsum > ysum;
}
return strcmp(x.name, y.name) < 0; //strcmp()<0 即x名字大于y不成立
}
void print(){
for (int i = 0; i < 3; i++){
printf("%s ", stu[i].name);
}
printf("%s\n", stu[3].name);
}
int main(){
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++){
scanf("%s", stu[i].name);
for (int j = 0; j < 4; j++){
scanf("%d", &stu[i].score[j]);
}
}
//语文排序
sort(stu, stu+n, cmp1);
print();
//数学排序
sort(stu, stu+n, cmp2);
print();
//英语排序
sort(stu, stu+n, cmp3);
print();
//科学排序
sort(stu, stu+n, cmp4);
print();
//总分排序
sort(stu, stu+n, cmp);
print();
return 0;
} ②抢气球升级版
题目：
刚一下课，小朋友们就打算去抢这些气球。每个气球在墙上都有一定的高度，只有当小朋友跳起来时，手能够到的高度大于等于气球的高度，小朋友才能摘到这个气球。为了公平起见，老师让跳的低的小朋友先摘,跳的高的小朋友后摘。小朋友都很贪心，每个小朋友在摘气球的时候都会把自己能摘的气球都摘掉。
很巧的是，小朋友们跳起来手能够着的高度都不一样，这样就不会有跳起来后高度相同的小朋友之间发生争执了。
输入格式
第一行输入两个空格分隔的整数 n, m（1≤n, m ≤ 10^5），其中n表示小朋友的数量，m表示墙上气球的数量。
第二行输入n个正整数(每两个整数之间用空格隔开)，第i个数为ai（1≤ai≤10^9），表示第i个小朋友跳起来手能够着的高度为ai。
第三行输入m个正整数（每两个整数之间用空格隔开)，第i个数为hi（1 ≤ hi≤10^9），表示第i个气球的高度为hi。
输出格式
输出一共n行，每行一个整数。
第i行表示第i个小朋友摘到的气球数量。样例输入1
5 6
3 7 9 6 4
1 2 3 4 5 6
样例输出1
3
0
0
2
1注意：这里的 n, m（1≤n, m ≤ 10^5）范围比较大，若是双重for循环，时间复杂度为O(nm)会超时，所以需要利用p降低时间复杂度为O(n+m)
#include <cstdio>
#include <algorithm>
using namespace std;
/**
样例输入2
10 10
1 2 3 4 5 6 7 8 9 10
3 1 4 6 7 8 9 9 4 12
样例输出2
1
0
1
2
0
1
1
1
2
0
**/
struct Children{
int a; //小朋友能够着的高度
int id;
};
Children ch[1005];
int h[1005]; //气球高度
int ans[1005]; //小朋友摘了多少个气球
bool cmp(Children x, Children y){
return x.a < y.a;
}
int main(){
int n, m; //n:小朋友的数量，m:气球数量
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++){
scanf("%d", &ch[i].a);
ch[i].id = i;
}
for (int i = 0; i < m; i++){
scanf("%d", &h[i]);
}
sort(ch, ch+n, cmp);
sort(h, h+m);
int p = 0; //表示当前摘的是第几个气球
for (int i = 0; i < n; i++){
//判断p<m可以省去重复判断的时间，p之前的气球已经被孩子摘走了不用再判断
//时间复杂度降为O(n+m)
while (p < m && h[p] <= ch[i].a){
p++;
ans[ch[i].id]++; //将数量存在孩子对应的编号
}
}
for (int i = 0; i < n; i++){
printf("%d\n", ans[i]); //从编号0对应的孩子输出
}
return 0;
}6.练习题
6.1机器人
题目：
蒜头君收到了一份礼物，是一个最新版的机器人。这个机器人有4种指令∶
顺时针旋转
1. forward x，前进 x 米。
2. back x，先向后转，然后前进 x 米。
3. left x，先向左转，然后前进 x 米。
4. right x，先向右转，然后前进 x 米。
现在把机器人放在坐标轴原点，起始朝向为x轴正方向。
经过一系列指令以后，你能告诉蒜头君机器人的坐标位置吗。
坐标轴上一个单位长度表示1米。
输入格式
第一行输入一个整数n(1≤n≤ 100)表示指令的个数。
接下里n行，每行输入形如上面的指令，其中-1000<r ≤ 1000。
输出格式
输出两个整数x， y表示机器人最后坐标。用空格隔开。样例输入
10
back -9
left 3
left 8
back 15
right 10
right -7
right -3
left 11
right 17
left 3
样例输出
9 -7
#include <iostream>
using namespace std;
/**
样例输入
10
back -9
left 3
left 8
back 15
right 10
right -7
right -3
left 11
right 17
left 3
样例输出
9 -7
**/
//顺时针旋转
//dx ,dy 表示坐标4个方向 上、左、下、右
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
char option[15]; //指令
int main(){
int n, d, x, nowx, nowy;
cin >> n;
//初始为x轴方向 即当前方向向右
d = 3;
//初始坐标
nowx = 0;
nowy = 0;
for (int i = 0; i < n; i++){
cin >> option >> x; //输入指令及步数
if (option[0] == 'b'){
//向后转
d = (d+2)%4;
} else if (option[0] == 'l'){
//向左转
d = (d+1)%4;
} else if (option[0] == 'r'){
//向右转
d = (d+3)%4;
}
nowx += dx[d]*x;
nowy += dy[d]*x;
}
cout << nowx << " " << nowy << endl;
return 0;
} 7.枚举法
能够用枚举法解决的题目往往是最简单的一类题目。
这种题目具有以下特点：
- 解枚举范围是有穷的。
- 检验条件是确定的。
枚举法的结构就是：枚举范围循环÷条件判断语句
7.1枚举范围循环
8.cmath常用函数
8.1指数和对数函数
- double exp(double x)：计算指数函数。返回x的以e为底的指数函数，它是e的x次方：e^x
- double log10(double x)：计算公对数。返回以10为底x的自然对数。如果参数为负，则会发生域错误。
- double log2(double x); x的二进制对数
8.2幂函数
- double pow(double x, double y)：返回底数的幂指数。pow (7.0, 3.0) ==> 7 ^ 3 = 343.000000
- double sqrt(double x)：返回x的平方根。 如果参数为负，则会发生域错误。sqrt(1024.000000) = 32.000000
- double fmod (double x,double y); 返回两参数相除x/y的余数
8.3绝对值函数
-
int abs(int n); 用于求一个整数的自然数
-
double fabs(double n); 升级版的abs,可以填小数，返回值也可以是小数
8.4舍入函数
- double ceil(double x)：向上取整，返回不小于x的最小整数值。
- double floor(double x)：向下取整，返回不大于x的最大整数值。
- double round(double x)：返回最接近x的整数值，中间情况从零开始四舍五入。
8.5最大值和最小值
- double max(double x, double y); 求 x 和 y 之间的最大值
-
double min(double x, double y); 求 x 和 y 之间的最小值
