提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

leetcode 7. 整数反转

2023-03-14 22:51:30 时间

取模运算实现整数反转

  • 首先我们可以先实现逆序打印当前给定整数的效果：
class Solution
{
public:
	void reverse(int x)//x输入123
	{
		while (x!=0)
		{
			if (x % 10 != 0)
				cout << x % 10 <<" ";
			x /= 10;
		}
	}
};
  • 接着我们来思考如何通过取模运算返回一个反转后的整数呢?：

1、将12345 % 10 得到5，之后将12345 / 10 2、将1234 % 10 得到4，再将1234 / 10 3、将123 % 10 得到3，再将123 / 10 4、将12 % 10 得到2，再将12 / 10 5、将1 % 10 得到1，再将1 / 10

  • 这么看起来，一个循环就搞定了，循环的判断条件是x>0
  • 但这样不对，因为忽略了 负数
  • 循环的判断条件应该是while(x!=0)，无论正数还是负数，按照上面不断的/10这样的操作，最后都会变成0，所以判断终止条件就是x!=0
  • 有了取模和除法操作，对于像12300这样的数字，也可以完美的解决掉了。
  • 看起来这道题就这么解决了，但请注意，题目上还有这么一句

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31, 2^31 − 1]。

不完美解法：

class Solution
{
public:
	int reverse(int x)
	{
		long res = 0;//保存反转后的整数
		while (x != 0)
		{
			//每次取末尾数字
			int temp = x % 10;
			res = res * 10 + temp;
			x /= 10;
		}
		return res;
	}
};

完美解法：

  • 在「不完美解法」中，我们使用了不符合文字限制的 long 数据结构。
  • 接下来我们看看，不使用 long 该如何求解。
  • 从上述解法来看，我们在循环的 ans = ans * 10 + x % 10 这一步会有溢出的风险，因此我们需要边遍历边判断是否溢出：
  • 对于正数而言：溢出意味着 ans * 10 + x % 10 > Integer.MAX_VALUE，对等式进行变化后可得 ans > (Integer.MAX_VALUE - x % 10) / 10。所以我们可以根据此变形公式进行预判断。
  • 对于负数而言：溢出意味着 ans * 10 + x % 10 < Integer.MIN_VALUE，对等式进行变化后可得 ans < (Integer.MIN_VALUE - x % 10) / 10。所以我们可以根据此变形公式进行预判断。
class Solution
{
public:
	int reverse(int x)
	{
		int res = 0;//保存反转后的整数
		while (x != 0)
		{
			//每次取末尾数字
			int temp = x % 10;
			if (x > 0 && res > (INT_MAX- temp) / 10)  return 0;
			if (x < 0 && res < (INT_MIN - temp) / 10) return 0;
			res = res * 10 + temp;
			x /= 10;
		}
		return res;
	}
};

2.利用string类字符串反转实现整数反转的效果 使用下面方法前，需要补充一些知识点：

1. 求整数位数的四种常用方法：

1、传统的用一个计数变量count，然后循环体中一直number/10,count计数，最后的count就是位数 

int max=5000;
int maxlen = 0;
while (max > 0)
{
	max /= 10;
	maxlen++;
}
cout << maxlen << endl;

2、直接用log函数，位数count=(int)log10(num)+1 

  int max=1000;
	int maxlen = (int)(log10(max)) + 1;
	cout << maxlen << endl;

3、用sprintf和strlen函数，sprintf(str,”%d”,num)，count=strlen(str)，这种直接求长度效率肯定要低很多，但是直接用了库函数不需要自己实现，如果需要对字符串处理的话，str还是很有价值的 

	int max=5000;
	char str[100];
	sprintf_s(str,"%d", max);
	int maxlen = strlen(str);

4.利用to_string将整数转化为string类字符串，再对string求长度 

string s=to_string(x);
s.size();

2. string类与整数互相转化的方法

1.整数转string 

int x=100;
string s=to_string(x);

2.string转整数—需要包含头文件 #include < sstream > 

   string s;
    cin >> s;
    int n;
    stringstream ss(s);
    ss >> n;
    cout << n << endl;

stringstream的作用和使用方法详情可以看这篇大佬的文章

完整代码：

#include<iostream>
using namespace std;
#include<string>
#include<numeric>
#include<sstream>
class Solution
{
public:
	int Reverse(int x)
	{
		int ret = 0;
		if (x == 0)
			return 0;
		string s;
		s = to_string(x);//s=="120000"
		reverse(s.begin(), s.end());//s=="000021"
		cout << s << endl;
		stringstream S(s);
		S >> ret;//ret=21,可见输入的时候会舍去前面的0，找到第一个有效的非0整数输入ret中
		return ret;
	}
};
int main()
{
	Solution s;
	cout << s.Reverse(120000) << endl;
	system("pause");
	return 0;
}
  • 当然以上代码无法在leetcode平台上直接通过，因为平台给出的c++函数名也是reverse，与我们要使用的反转算法reverse函数同名，因此我们可以换一种逆转string的方式：
class Solution
{
public:
	int reverse(int x)
	{
		int ret = 0;
		if (x == 0)
			return 0;
		string s;
		s = to_string(x);
		//反转字符串的另外一种方式
		int i = 0, j = s.size() - 1;
		for (; i <= j; i++, j--)
		{
			swap(s[i], s[j]);
		}
		stringstream S(s);
		S >> ret;
        //判断反转整数后，范围是否溢出
		if (ret <= -2147483648 || ret>= 2147483647)
			return 0;
		return x >= 0 ? ret : -ret;
	}
};
  • 本题中还涉及了一个知识点，就是int整数的范围: -2147483648~2147483647

相关文章