字符串例题——求逆序数

问题：输入一个正整数$n$（$1 \le n \le 10^{16}$），计算并输出$n$的逆序数。正整数$n$的逆序数就是$n$倒着念的整数（高位不能有多余的0），例如123的逆序数是321,5700的逆序数是75。

分析：使用循环拆分出存储在long long类型变量$n$每位上的数字，一边拆分一边组装逆序数。（可参阅【循环结构例题一】中例题【五、逆序数】的详细讲解）

#include<iostream>
using namespace std;
int main()
{
	long long n,m = 0;
	cin>>n;
	while(n){
		m = m*10 +n%10; 
		n /= 10;
	}
	cout<<m<<endl;
	return 0;
} 

问题变形：输入的正整数$n$的位数不超过100位，计算并输出$n$的逆序数。

分析：正整数$n$的位数不超过100位，不能再使用int、long long这样的基本数据类型存储正整数$n$，可以使用字符串来存储。那么此时逆序数就是字符串逆序输出，但是要避免输出高位多余的0。

#include<iostream>
#include<cstring>
using namespace std;
char num[110];   //额外多开一些 
int main()
{
	cin>>num;
	//逆序找到第一个不是'0'的字符
	int i = strlen(num)-1; 
	while(num[i]=='0') i--;
	
	//从下标i开始逆序输出 
	while(i>=0){
		cout<<num[i--];
	}
	return 0;
} 

此外还可以使用string来存储整数，并且使用string的find_last_not_of方法逆向找到第一个不是'0'的字符的位置：

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string num;
	cin>>num;
	//用string的find_last_not_of方法返回逆向第一个不是'0'的字符的位置 
	int i = num.find_last_not_of('0');
	while(i>=0) cout<<num[i--];
	return 0;
} 

当然，也可以使用find_last_of方法返回字符串逆序查找"123456789"中任意字符的第一处位置，其实就是逆向第一个不是'0'的字符的位置：

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string num;
	cin>>num;
	//用string的find_last_of方法返回num逆序查找"123456789"中任意字符的第一处位置 
	int i = num.find_last_of("123456789");
	while(i>=0) cout<<num[i--];
	return 0;
}