C/C++编程三级 题库
扩号匹配问题(2022.12)
在某个字符串(长度不超过100)中有左括号、右括号和大小写字母;规定(与常见的算数式子一样)任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序,找到无法匹配的左括号和右括号,输出原来字符串,并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.
时间限制:3000
内存限制:65536
输入
输入包括多组数据,每组数据一行,包含一个字符串,只包含左右括号和大小写字母,字符串长度不超过100
输出
对每组输出数据,输出两行,第一行包含原始输入字符,第二行由"$","?"和空格组成,"$"和"?"表示与之对应的左括号和右括号不能匹配。
样例输入
((ABCD(x) )(rttyy())sss)(
样例输出
((ABCD(x) $$ )(rttyy())sss)( ? ?$
//解法1:递归
#include <bits/stdc++.h>
using namespace std;
#define N 105
char s[N], sign[N];
int si, len;
void find()//找下一个右括号 如果找到,si指向右括号 如果没找到,做标记
{
int lp = si;//当前左括号的下标
si++;
while(si < len)
{
if(s[si] == ')')
return;
else if(s[si] == '(')
find();
si++;
}
sign[lp] = '$';//没有找到右括号,左括号的位置标记为$
}
int main()
{
while(cin >> s)
{
len = strlen(s);
for(int i = 0; i < len; ++i)//初始化sign字符串为空格
sign[i] = ' ';
sign[len] = '\0';
si = 0;
while(si < len)
{
if(s[si] == ')')//右括号的位置标记为?
sign[si] = '?';
else if(s[si] == '(')
find();
si++;
}
cout << s << endl << sign << endl;
}
return 0;
}//解法2
// 就近原则匹配:栈
// 遍历字符串
// 遇到左括号,将其下标入栈
// 右括号则先判断栈内元素情况
// 1.空,则将其下表记录到数组中
// 2.非空,则栈顶元素弹出(匹配到了)
// 将字符串便遍历后,将栈内元素记录入另一个数组
// 用两数组内的对应下标分别改成对应字符
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
string s;
char ans[N]; // 第二排的输出数组
stack<int> st;
int a[N], cnt = 1; // 未匹配的右括号的下标存储
int b[N], cnn = 1; // 未匹配的左括号的下标存储
int main() {
while (getline(cin, s)) { // 输入不结束
memset(ans, 0, sizeof(ans));
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
cnt = 1;
cnn = 1; // 数据初始化
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') {
st.push(i); // 左括号统一入栈
}
if (s[i] == ')') {
if (!st.empty()) {
st.pop(); // 若栈非空,则可以匹配
} else {
a[cnt++] = i; // 否则无法匹配,记录
}
}
}
if (!st.empty())
while (!st.empty()) {
b[cnn++] = st.top();
st.pop();
} // 栈内数据(下标)的出栈
for (int i = 1; i < cnn; i++) {
ans[b[i]] = '$'; // 在ans内标记
}
for (int i = 1; i < cnt; i++) {
ans[a[i]] = '?'; // 在ans内标记
}
cout << s << endl;
for (int i = 0; i < s.size(); i++) {
if (ans[i] == 0)
cout << " ";
if (ans[i] == '$')
cout << "$";
if (ans[i] == '?')
cout << "?"; // 格式转化
}
cout << endl;
}
return 0;
}生成括号(2023.3)
Paul是一名数学专业的同学,在课余选修了C++编程课,现在他能够自己写程序判断判断一个给定的由'('和')'组成的字符串是否是正确匹配的。可是他不满足于此,想反其道而行之,设计一个程序,能够生成所有合法的括号组合,请你帮助他解决这个问题。
时间限制:1000
内存限制:65536
输入
输入只有一行N,代表生成括号的对数(1 ≤ N ≤ 10)。
输出
输出所有可能的并且有效的括号组合,按照字典序进行排列,每个组合占一行。
样例输入
3
样例输出
((())) (()()) (())() ()(()) ()()()
#include <bitset>
#include <ctime>
#include <iostream>
using namespace std;
int N;
bool judge(bitset<20> temp) {
int numL = 0, numR = 0;
for (int i = 2 * N - 1; i >= 0; i--) {
if (temp[i])
numR++;
else
numL++;
if (numL - numR < 0)
return false;
}
if (numL != numR)
return false;
return true;
}
int main() {
cin >> N;
int max = 1 << (2 * N - 1);
for (int i = 1; i <= max; i++) {
bitset<20> temp;
for (int j = 0; j < 2 * N; j++) {
temp[j] = (i >> j) & 1;
}
if (judge(temp)) {
for (int j = 2 * N - 1; j >= 0; j--) {
if (temp[j])
cout << ")";
else
cout << "(";
}
cout << endl;
}
}
return 0;
}子串与子列
子串是一个字符串中连续的一部分,而子列是字符串中保持字符顺序的一个子集,可以连续也可以不连续。例如给定字符串 atpaaabpabtt,pabt 是一个子串,而 pat 就是一个子列。
现给定一个字符串 S 和一个子列 P,本题就请你找到 S 中包含 P 的最短子串。若解不唯一,则输出起点最靠左边的解。
时间限制:1000
内存限制:65536
输入
输入在第一行中给出字符串 S,第二行给出 P。S 非空,由不超过 104 个小写英文字母组成;P 保证是 S 的一个非空子列。
输出
在一行中输出 S 中包含 P 的最短子串。若解不唯一,则输出起点最靠左边的解。
样例输入
atpaaabpabttpcat pat
样例输出
pabt
#include <stdio.h>
#include <string.h>
int main(){
char s[10001], p[10001];
int i, j, t = 0, len, min = 10001, m, n, k = 0, flag = 0;
scanf("%s\n%s", s, p);
while(1){
for(i = 0;i < strlen(p);i++){
if(!i){
for(j = t + k;j < strlen(s);j++){
if(s[j] == p[i]){
k = 1;
break;
}
}
t = j;
}else{
for(j++;j < strlen(s);j++){
if(s[j] == p[i]) break;
}
}
if(j == strlen(s)){
flag = 1;
break;
}
}
if(flag == 1) break;
len = j - t + 1;
if(len < min){
min = len;
m = t;
n = j;
}
}
for(i = m;i <= n;i++) printf("%c", s[i]);
return 0;
}中位字符
给定一个字符串 S,输出该字符串的中位字符。中位字符指的是字符串正中间的字符。当字符串长度为奇数时,中位字符是唯一的;当长度为偶数时,中位字符是中间的两个字符。
输入格式
一个字符串 S。
输出格式
一个字符,表示 S的中间字符。
输入样例#1
c++
输出样例#1
+
输入样例#2
a
输出样例#2
a
输入样例#3
abc
输出样例#3
b
输入样例#4
abcd
输出样例#4
bc
数据范围:
1≤∣S∣≤106;∣S∣ 表示字符串的长度,且 S 不含任何不可见字符。
#include <stdio.h>
#include <string.h>
char s[1000001];
int main() {
scanf("%s", s); // 读取输入字符串
int len = strlen(s); // 获取字符串长度
int mid = len / 2; // 计算中间位置(整数除法)
if (len % 2 == 1) {
printf("%c\n", s[mid]);
} else {
printf("%c%c\n", s[mid - 1], s[mid]);
}
return 0;
}数山峰
某地质勘探队正在研究一条山脉的 N 个连续山峰,山峰编号为 1 到 N。每个山峰的高度状态用字符串 S 表示:# 表示高峰,. 表示低谷。
地质学家需要统计存在多少山峰编号 i(1≤i≤N - 2)满足以下特殊地形特征:山峰 i 是高峰;山峰 i+1 是低谷;山峰 i+2 是高峰。即寻找所有满足“高峰-低谷-高峰”模式的连续三个山峰组的起始位置数量。
时间限制:1000ms,内存限制:256MB
输入格式
第一行:整数 N(山峰数量);
第二行:长度为 N 的字符串 S(山峰高度状态)。
输出格式
满足条件的山峰编号 i 的个数。
输入样例#1
6 #.##.#
输出样例#1
2
输入样例#2
1 #
输出样例#2
0
输入样例#3
9 ##.#.#.##
输出样例#3
3
数据范围:
1≤N≤2×105;S 仅包含字符 # 和 . 。
#include <stdio.h>
#include <string.h>
char s[200001];
int main() {
int n;
scanf("%d", &n);
scanf("%s", s);
int count = 0;
// 遍历所有可能的起始位置i(字符串索引从0开始)
for (int i = 0; i <= n - 3; i++) {
// 检查是否符合"高峰-低谷-高峰"模式
if (s[i] == '#' && s[i+1] == '.' && s[i+2] == '#') {
count++;
}
}
printf("%d\n", count);
return 0;
}扑克牌
给定一个字符串表示扑克牌的牌面顺序,两名玩家轮流抽取卡牌。每次抽取后,立即比较双方当次抽取的牌面大小,并输出比较结果。比较规则:
牌面大小顺序:3 < 4 < 5 < 6 < 7 < 8 < 9 < T < J < Q < K < A < 2,若牌面相同,则判定为平局。
时间限制:1000ms,内存限制:256MB
输入格式
一个字符串,表示扑克牌的顺序。
输出格式
一个字符串,依次表示每次比较的结果:>表示玩家1的牌更大;<表示玩家2的牌更大;= 表示平局。
输入样例#1
8632T5669A
输出样例#1
><>=<
输入样例#2
J2TT34K5
输出样例#2
<=<>
数据范围:
单张牌面字符属于集合 {3, 4, 5, 6, 7, 8, 9, T, J, Q, K, A, 2},输入字符串长度一定是偶数,且不超过 2×106。
#include <stdio.h>
#include <string.h>
char cards[2000001]; // 存储输入的牌面字符串
char table[14] = "3456789TJQKA2";
int main() {
scanf("%s", cards);
int len = strlen(cards);
int res_len = 0; // 结果字符串的当前长度
for (int i = 0; i < len; i += 2) {
char c1[2], c2[2];
c1[0] = cards[i]; // 玩家1的牌
c2[0] = cards[i + 1]; // 玩家2的牌
c1[1] = c2[1] = '\0';
char *p1 = strstr(table, c1);
char *p2 = strstr(table, c2);
if(p1 - p2 > 0)
printf(">");
else if(p1 - p2 < 0)
printf("<");
else
printf("=");
}
return 0;
}倒排文字
题目描述
给定若干单词,请你将输入的所有单词的顺序倒排并输出,单词之间用单个空格分隔。
输入格式
输入共一行,一个字符串。
输出格式
输出为按要求排序后的字符串。
输入样例
I am a student
输出样例
student a am I
说明提示
字符串长度不超过100
保证单词都由可见字符组成,且单词之前有且仅有一个空格。
//C++参考代码1
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
string input;
getline(cin, input); // 读取整行输入
vector<string> words; // 用来存储单词
string word;
// 分割字符串为单词
for (char c : input) {
if (c == ' ') {
if (!word.empty()) {
words.push_back(word);
word = "";
}
} else {
word += c;
}
}
if (!word.empty()) {
words.push_back(word);
}
// 倒序输出单词
for (int i = words.size() - 1; i >= 0; i--) {
cout << words[i];
if (i > 0) {
cout << " ";
}
}
return 0;
}//C++参考代码2
#include<bits/stdc++.h>
using namespace std;
string a,x[101];
int main(){
int t=1;
getline(cin,a);
for(int i=0;i<a.size();i++){
if(a[i]!=' '){
x[t]+=a[i];
}
else{
t++;
}
}
for(int i=t;i>0;i--){
if(x[i]!="")
cout<<x[i]<<' ';
}
return 0;
}//C语言代码
#include<stdio.h>
#include<string.h>
int main()
{
char a[101]={0};
int i,j,len,t;
gets(a);
len=strlen(a);
t=len;
for(i=len-1;i>=0;i--) //从字符串的最后进行遍历
{
if(a[i]==' ') //当遇到的字符为空格时,说明此时已找到了一个完整的单词,位置是i~t-1
{
for(j=i+1;j<=t-1;j++) //从空格的后面一个字符打印到第t-1个字符
{
printf("%c",a[j]);
}
printf(" "); //打印空格
t=i; //a[i]字符为空格,把第i个位置赋值给t,以后的打印到t-1为止
}
}
for(j=0;j<t;j++)
{
printf("%c",a[j]);
}
return 0;
}改写字符串
题目描述
给定一个字符串 s,请将 s 中的所有元音字母改成大写,所有辅音字母改成小写。元音字母包括 a、e、i、o、u,其它字母都算辅音。
输入格式
第一行:单个字符串表示 s。
输出格式
第一行:改写后的字符串。
输入样例
HowAreYou
输出样例
hOwArEyOU
说明提示
记 ∣s∣ 表示字符串 s 的长度,则1≤∣s∣≤1,000
保证 s 中只包含大写或小写英文字母
#include <iostream>
#include <cctype>
using namespace std;
int main() {
string s;
cin >> s; // 读取输入的字符串
for (char &c : s) {
char lower_char = tolower(c); // 转换为小写方便判断
if (lower_char == 'a' || lower_char == 'e' || lower_char == 'i'
|| lower_char == 'o' || lower_char == 'u') {
c = toupper(c); // 元音转大写
} else {
c = tolower(c); // 辅音转小写
}
}
cout << s << endl; // 输出结果
return 0;
}