数组和字符串(浙邮院)解题报告

数组和字符串(浙邮院)-by lin1278303011



ps:此解题报告内所有代码均为AC代码,并且会列出多种思路,但不一定是最优解法


A:C语言实验题――数组逆序


tips:这道题还是比较简单的,这里列出两种方法,一种是将原数组逆序存入新数组,一种是直接在原数组内部调换。


1.将原数组num数组逆序存入ans数组中

#include "iostream"
using namespace std;
int main() {
	int num[10],ans[10];
	for (int i = 0; i < 10; i++) cin >> num[i];
	for (int i = 0; i < 10; i++) ans[10 - i - 1] = num[i];      //直接将第i位放在第10-i-1位
	for (int i = 0; i < 10; i++) {
		if (i == 0) cout << ans[i];                    //格式控制
		else cout << " " << ans[i];
	}
	return 0;
}


2.在num数组内部直接调换

#include "iostream"
using namespace std;
void change(int& a, int& b) {                    //调换函数,使用地址符直接修改实参的值
	int t = a;
	a = b;
	b = t;
}
int main() {
	int num[10];
	for (int i = 0; i < 10; i++) cin >> num[i];
	for (int i = 0; i < 5; i++) change(num[i], num[10 - i - 1]);       //调换第i位和第10-i-1位
	for (int i = 0; i < 10; i++) {
		if (i == 0) cout << num[i];            //格式控制
		else cout << " " << num[i];
	}
	return 0;
}


B:C语言实验题――大小写转换


tips:这道题是一个基本的字符判断,同样列出两种方法,一种是输入一整串字符串,再进行判断,一种是边输入边判断。


1.先输入字符串,再逐位判断

#include "cstdio"
#include "cstring"
using namespace std;
int main() {
	char str[100];
	gets(str);
	int len = strlen(str);                //储存str字符串的长度
	for (int i = 0; i < len; i++) {
		if (str[i] >= 'a' && str[i] <= 'z') str[i] -= 32;       //判断小写
		else if (str[i] >= 'A' && str[i] <= 'Z') str[i] += 32;    //判断大写
	}
	puts(str);
	return 0;
}


2.边输入边判断,可以省略开数组的空间

#include "cstdio"
#include "cstring"
using namespace std;
int main() {
	char c;
	while (true) {
		c = getchar();                    //获取字符
		if (c == '\n') break;                  //如果输入为换行,结束输入
		if (c >= 'a' && c <= 'z') c -= 32;
		else if (c >= 'A' && c <= 'Z') c += 32;
		putchar(c);                       //输出处理过的字符
	}
	return 0;
}


ps:这道题可以使用isupper()、islower()函数判断字母,但需要注意要加ctype.h头文件


C:字符统计


tips:这道题同样是一个基本的字符判断,列出两种方法,一种是用逻辑表达式判断,一种是使用库函数判断。


1.逻辑表达式

#include "cstdio"
#include "cstring"
using namespace std;
int main() {
	char str[100010];
	while (gets(str)) {
		int a = 0, b = 0, c = 0, d = 0, len = strlen(str);     //a,b,c,d代表四种情况,len储存字符串长度
		for (int i = 0; i < len; i++) {                            //四种情况分别判断
			if ((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z')) a++;
			else if (str[i] >= '0' && str[i] <= '9') b++;
			else if (str[i] == ' ') c++;
			else d++;
		}
		printf("%d %d %d %d\n", a, b, c, d);
	}
	return 0;
}


2.库函数

#include "cstdio"
#include "cstring"
#include "ctype.h"                    //注意头文件
using namespace std;
int main() {
	char str[100010];
	while (gets_s(str)) {
		int a = 0, b = 0, c = 0, d = 0, len = strlen(str);
		for (int i = 0; i < len; i++) {
			if (isalpha(str[i])) a++;            //isalpha函数判断一个字符是否为字母
			else if (isdigit(str[i])) b++;       //isdigit函数判断一个字符是否为数字
			else if (str[i] == ' ') c++;
			else d++;
		}
		printf("%d %d %d %d\n", a, b, c, d);
	}
	return 0;
}


D:C语言实验题――单词统计


tips:这道题是一个单词个数的判断,要注意的是空格可能有多个,同样两种方法,逻辑表达式和库函数


1.逻辑表达式

#include "cstdio"
#include "cstring"
using namespace std;
int main() {
	char str[100010];
	gets(str);
	int ans = 0, len = strlen(str);
	if ((str[0] >= 'a' && str[0] < 'z') || (str[0] >= 'A' && str[0] < 'Z')) ans++;
	for (int i = 1; i < len; i++) {
		if (((str[i] >= 'a' && str[i] < 'z') || (str[i] >= 'A' && str[i] < 'Z')) && str[i - 1] == ' ') ans++;
	}
	printf("%d\n", ans);
	return 0;
}


2.库函数

#include "cstdio"
#include "cstring"
#include "ctype.h"
using namespace std;
int main() {
	char str[100010];
	gets(str);
	int ans = 0, len = strlen(str);
	if (isalnum(str[0])) ans++;                //先判断首位是否为字母,是说明开头是一个单词
	for (int i = 1; i < len; i++) {
		if (isalnum(str[i]) && str[i - 1] == ' ') ans++;    //找到所有空格之后的字母,代表一个新的单词
	}
	printf("%d\n", ans);
	return 0;
}



E:统计同成绩学生人数


tips:这道题是一个数字统计,两种方法,先存后统计和边输入边统计


1.先将所有同学的成绩存到num数组中,再进行比较统计

#include "cstdio"
#include "iostream"
#include "cstring"
#include "ctype.h"
using namespace std;
int main() {
	int num[1010], n, m;
	while (~scanf("%d", &n) && n) {                                //&& n 等同于 && n != 0
		int ans = 0;
		for (int i = 0; i < n; i++) cin >> num[i];
		cin >> m;
		for (int i = 0; i < n; i++) if (num[i] == m) ans++;    //判断
		cout << ans << endl;
	}
	return 0;
}


2.由于这道题数据并不大,可以在输入的时候直接用一个数组统计各个成绩的人数,这种方法也是计数排序的一种

#include "cstdio"
#include "iostream"
#include "cstring"
#include "ctype.h"
using namespace std;
int main() {
	int num[105], n, m;
	while (~scanf("%d", &n) && n) {
		memset(num, 0, sizeof(num));            //由于我们不是输入而是进行++操作,所以需要初始化整个数组
		for (int i = 0; i < n; i++) {
			int x;
			cin >> x;
			num[x]++;                        //输入成绩x,成绩x的人数++
		}
		cin >> m;
		cout << num[m] << endl;                   //直接输出成绩m的人数
	}
	return 0;
}


ps:第二种方法用到memset函数初始化数组,对memset函数不了解的同学可以去了解一下,是一个比较常用的函数


F:元素的删除


tips:这道题是一个删除数组元素,说是删除,实际上只需要在输出的时候跳过那个元素就可以了,这里列出一种写法


1.以跳过输出的方式删除元素,由于要考虑删除的元素可能是第一个元素,所以控制输出格式时需要用一个flag变量来判断是否为第一次输出

#include "cstdio"
#include "iostream"
#include "cstring"
#include "ctype.h"
using namespace std;
int main() {
	int t;
	cin >> t;
	while (t--) {
		int n, m, num[10010], flag = 0;        //用一个flag来判断是否为第一次输出
		cin >> n;
		for (int i = 0; i < n; i++) cin >> num[i];
		cin >> m;
		for (int i = 0; i < n; i++) {
			if (flag == 0 && num[i] != m) {        //判断是否为第一次输出并且是不是需要删除的元素
				cout << num[i];
				flag = 1;                      //第一次输出结束,将flag变为1
			}
			else if (num[i] != m) cout << " " << num[i];
		}
		cout << endl;
	}
	return 0;
}


G:首字母变大写


tips:这道题同样是一个判断字母和判断单词的题目,但是台州平台的数据中会存在特殊字符,如果特殊字符作为单词的首字母,是不需要转换的,这里列出几个容易wa的数据:

输入
,aa ,aa aa,
输出
,aa ,aa Aa,
输入
a,,,,,a
输出
A,,,,,a


这里是AC代码:

#include "cstdio"
#include "iostream"
#include "cstring"
#include "ctype.h"
using namespace std;
int main() {
	char str[105];
	while (gets(str)) {
		int len = strlen(str);
		if (str[0] >= 'a' && str[0] <= 'z') str[0] -= 32;      //这里判断整个字符串的首位
		for (int i = 1; i < len; i++) {
			if (str[i] >= 'a' && str[i] <= 'z' && str[i - 1] == ' ') str[i] -= 32;
			//查找前面是空格的字母,就是一个单词的首字母
		}
		puts(str);
	}
	return 0;
}


ps:同样可以使用ctype库中的函数


H:支配值数目


tips:这道题是一个比较数组元素的题目,这里列出两种方法,一种是暴力写法,时间复杂度为O(n*m),另一种是优化代码,时间复杂度为O(n+m)


1.暴力做法,直接用双重循环比较

#include "cstdio"
#include "iostream"
#include "cstring"
#include "ctype.h"
using namespace std;
int main() {
	int n, m, f[1010], g[1010];
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> f[i];
	for (int i = 0; i < m; i++) cin >> g[i];
	int sum = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (f[i] > g[j]) sum++;            //简单粗暴,比较如果f[i]>g[j],sum++
	cout << sum;
	return 0;
}


2.优化算法,由于两个数组都是有序数组,我们可以让内循环的循环变量不重置,每次比较都从上一次比较的结束位置开始比较

#include "cstdio"
#include "iostream"
#include "cstring"
#include "ctype.h"
using namespace std;
int main() {
	int n, m, f[1010], g[1010];
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> f[i];
	for (int i = 0; i < m; i++) cin >> g[i];
	int j = 0, sum = 0;
	for (int i = 0; i < n; i++) {
		for (; j < m; j++) if (f[i] <= g[j]) break;
		//如果发现当前位置f[i]比g[j]小了,说明f[i]比前面j个数大
		sum += j;
	}
	cout << sum;
	return 0;
}


ps:给不知道时间复杂度的同学科普一下,时间复杂度是acm中比较重要的一个数值,主要用来计算代码的运行时间,一段代码是否超时一般就是通过计算时间复杂度来判断。时间复杂度一般用一个公式来表示,O(复杂度),计算的方法是计算代码中循环的次数。比如使用for循环循环了n变量,那么复杂度就是O(n)。如果使用双重循环并且两重循环都是从0开始到变量n或者其他变量结束,那么复杂度就是O(n2)或者O(n*m)。还有其他的复杂度比如O(1)、O(log(n))等,与时间复杂度对应的还有空间复杂度


I:数字对


tips:这道题和上面的字符串统计单词很类似,只不过把字符串改成了整数数组,可以通过同时判断这一项和前一项来判断是否满足条件


AC代码:

#include "cstdio"
#include "iostream"
#include "cstring"
#include "ctype.h"
using namespace std;
int main() {
	int n, m, num[100010];
	cin >> n;
	for (int i = 0; i < n; i++) cin >> num[i];
	cin >> m;
	while (m--) {
		int x, y, ans = 0;
		cin >> x >> y;
		for (int i = 0; i < n - 1; i++) if (num[i] == x && num[i + 1] == y) ans++;
		if (ans) cout << "(" << x << "," << y << ")=" << ans << endl;
		else cout << "Not Found!" << endl;                    \\如果统计个数为0那么说明没有找到
	}
	return 0;
}



J:C语言实验题――鞍点


tips:这道题的问题应该是最多的,同时相对于这次的练习这道题也是最难的一题,难点在于二维数组行和列的掌控,以及最大值和最小值之间调配的问题,这里列出两种解法


1.先找到每一行中最大的值,找到一行的最大值时,循环最大值所在的这一列,判断这个值是否同时时这一列的最小值

#include "cstdio"
#include "iostream"
#include "cstring"
#include "ctype.h"
using namespace std;
int main() {
	int n, m, mp[20][20];
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) cin >> mp[i][j];
	for (int i = 0; i < n; i++) {                                //循环每一行
		int maxn = mp[i][0], h = 0;                          //用maxn来储存这一行中最大的值
		for (int j = 1; j < m; j++) {                        //找到这一行中最大的值
			if (mp[i][j] > maxn) {                
				maxn = mp[i][j];
				h = j;                                //并且记录这个值所在的列
			}
		}
		int minn = mp[0][h], l = 0;                            //用minn来储存这一列中最小的值
		for (int j = 1; j < n; j++) {
			if (mp[j][h] <minn) {
				minn = mp[j][h];
				l = j;                                //记录这一列中最小的值的行数
			}
		}
		if (l == i) {                                        //如果这一列最小值的行数等于这一行的行数,说明这个值就是一个鞍点
			cout << "Array[" << i << "][" << h << "]=" << mp[i][h] << endl;
			return 0;                                    //直接return 0;结束掉程序
		}    
	}
	cout << "None" << endl;                                       //走到这一步说明没有找到过鞍点,那么输出None
	return 0;
}


1.找到每一行的最大值所在的列数存在h数组中,找到每一列的最小值所在的行数存在l数组中,最后将h数组中的列数作为l数组的下标查找匹配

比如第2行最大值的列数是3,在h数组中就是h[2]=3,那么我们拿3作为下标去查l[3],也就是第3列的最小值所在的行数,如果l[3]=2,那么说明这个第2行第3列的数是一个鞍点,那么就可以直接输出结束程序了

#include "cstdio"
#include "iostream"
#include "cstring"
#include "ctype.h"
using namespace std;
int main() {
	int n, m, mp[20][20],h[20],l[20];
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) cin >> mp[i][j];
	for (int i = 0; i < n; i++) {
		int maxn = mp[i][0];
		h[i] = 0;
		for (int j = 1; j < m; j++) {
			if (mp[i][j] > maxn) {
				maxn = mp[i][j];
				h[i] = j;                //h数组储存行最大值所在的列数
			}
		}
	}
	for (int i = 0; i < m; i++) {
		int minn = mp[0][i];
		l[i] = 0;
		for (int j = 1; j < n; j++) {
			if (mp[j][i] <minn) {
				minn = mp[j][i];
				l[i] = j;                //l数组储存列最小值所在的行数
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (l[h[i]] == i) {                    //将h数组中的列数作为l数组的下标查找匹配
			cout << "Array[" << i << "][" << h[i] << "]=" << mp[i][h[i]] << endl;
			return 0;                        //匹配成功,直接return 0;结束掉程序
		}
	}
	cout << "None" << endl;
	return 0;
}



为解题报告打分
暂时不评分

★★
★★★
★★★★
★★★★★
发表您的评论(若贴AC代码或发表禁止言论等违禁行为将被删除并扣除积分)

|返回 |   | 转到页头|
Copyright @ 2008-2024(浙ICP备2022001332号), TZOJ. All Rights Reserved.