[数据结构与算法]信息学奥赛一本通 1162：字符串逆序

【题目链接】

ybt 1162：字符串逆序

【题目考点】

1. 字符串

2. 递归

【解题思路】

先去掉字符串末尾的’!’
递归输出逆序字符串

• 递归问题：输出字符串s的逆序字符串
• 递归关系：设字符串s有l个字符，要想输出字符串s的逆序字符串，需要先输出s的最后一个字符，再输出s的前l-1个字符的逆序字符串
• 递归出口：如果s是空字符串，直接返回

【题解代码】

解法1：使用字符数组 递归输出逆序字符串

#include<bits/stdc++.h>
using namespace std;
void revShow(char s[], int len)//逆向输出字符数组s，s长度为len 
{
	if(len == 0)
		return;
	cout << s[len-1];
	revShow(s, len-1);
}
int main()
{
	char s[1005];
	cin.getline(s, 1005);
	int len = strlen(s);
	s[--len] = '\0';//去掉最后的'!' 
	revShow(s, len);
	return 0;
}

解法2：使用string类 递归构造逆序字符串

#include<bits/stdc++.h>
using na#include<bits/stdc++.h>
using namespace std;
string revStr(string s)//构造s的逆向字符串 
{
	int len = s.length();
	if(len == 0)
		return string("");
	return s[len-1] + revStr(s.substr(0, len-1));//最后一个字符 连接 前len-1个字符的逆序 
}
int main()
{
	string s;
	getline(cin, s);
	s.pop_back();//去掉最后的'!'
	cout << revStr(s);
	return 0;
}

解法3：使用getchar()，递归完成逆序输出

#include<bits/stdc++.h>
using namespace std;
void revChar()
{
	char c = getchar();
	if(c == '!')
		return;
	revChar();
	cout << c;
}
int main()
{
	revChar();
	return 0;
}

解法4：非递归 字符串逆序输出

#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	getline(cin, s);
	s.pop_back(); 
	for(int i = s.length() - 1; i >= 0; --i)
		cout << s[i];
	return 0;
}