007_整数翻转
本帖最后由 风扫地 于 2019-5-7 19:31 编辑题目来源：力扣
算法好难，只好从简单的题刷起。
/*
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231,231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
*/
实现方案：
class Solution {
public:
int reverse(int x)
{
int p_or_n = 0 ;
int overflow_flag = 0 ;
int maxvalueLimit = 2147483647/10 ;
int ret_val = 0 ;
do{
if((x == -2147483648)
||(x == 0 )
)
{
ret_val = 0;
break;
}
p_or_n= x > 0 ? 1:-1; /* 1为正,-1为负数 */
x = x*p_or_n;
ret_val = 0;
while(x!=0)
{
if(ret_val>maxvalueLimit)
{
overflow_flag = 1;
break;
}
ret_val = ret_val*10 + x % 10;
x /= 10;
}
if(overflow_flag == 0)
{
ret_val = ret_val * p_or_n;
break;
}
else
{
return 0;
}
break;
}while(0);
return ret_val;
}
};
测试代码：
#include <iostream>
using namespace std;
int main(void)
{
Solution solution;
cout << solution.reverse(-2147483648) << endl;
cout << solution.reverse(-2147483647) << endl;
cout << solution.reverse(-110) << endl;
cout << solution.reverse(2147483641)<< endl;
return 0;
}
提交结果：
/*
执行用时 : 12 ms, 在Reverse Integer的C++提交中击败了98.18% 的用户
内存消耗 : 8.4 MB, 在Reverse Integer的C++提交中击败了74.72% 的用户
*/
{:10_277:} Nice.
附录：
2^31-1=2147483647,-2^31=-2147483648
楼主看看这个实现如何？
#include <stdio.h>
int ReversInt(const int n)
{
int d , i , k , m ;
bool f ;
f = false ;
m = n ;
if (m < 0) {
m = - m ;
f = true ;
}
d = 1 ;
for(d = 1 , i = m ; i > 0 ; i /= 10) d *= 10 ;
for(i = m , k = 0 , d /= 10 ; i > 0 ; i /= 10) {
k += (i % 10) * d ;
d /= 10 ;
}
if (f) k = - k ;
return k ;
}
int main(void)
{
int n ;
scanf("%d" , & n) ;
printf("%d\n" , ReversInt(n)) ;
}
jackz007 发表于 2019-5-6 20:23
楼主看看这个实现如何？
输入 1534236469
溢出了,楼上没处理溢出的情况. 本帖最后由 jackz007 于 2019-5-6 21:39 编辑
风扫地 发表于 2019-5-6 20:29
输入 1534236469
溢出了,楼上没处理溢出的情况.
虚心接受楼主的意见，现在再测呢：
#include <stdio.h>
int ReversInt(int m)
{
int i , k ;
bool f ;
f = false ;
if(m < 0) {
m = - m ;
f = true ;
}
for(k = 0 , i = m ; i > 0 ; i /= 10) {
if(k < 0x7fffffff / 10) {
k = k * 10 + (i % 10) ;
} else {
k = 0 ;
break ;
}
}
if (f && k) k = - k ;
return k ;
}
int main(void)
{
int n ;
scanf("%d" , & n) ;
printf("%d\n" , ReversInt(n)) ;
}
本帖最后由 风扫地 于 2019-5-7 09:03 编辑
jackz007 发表于 2019-5-6 21:35
虚心接受楼主的意见，现在再测呢：
1.
-2147483648（ -2^31）这个测试用例挂了， -2^31~ 2^31 -1
最小不能取反，取反就溢出。
2.
测试用例 1463847412 挂了，实际上没溢出，但判断成溢出了。 本帖最后由 jackz007 于 2019-5-7 10:41 编辑
风扫地 发表于 2019-5-7 09:00
1.
-2147483648（ -2^31）这个测试用例挂了， -2^31~ 2^31 -1
最小不能取反，取反就溢出。
现在再测
#include <stdio.h>
#include <stdlib.h>
int ReversInt(int m)
{
int i , k ;
for(k = 0 , i = m ; abs(i) > 0 ; i /= 10) {
k = k * 10 + (i % 10) ;
if((m > 0 && k <= 0) || (m < 0 && k >= 0)) {
k = 0 ;
break ;
}
}
return k ;
}
int main(void)
{
int n ;
scanf("%d" , & n) ;
printf("%d\n" , ReversInt(n)) ;
}
jackz007 发表于 2019-5-7 10:28
现在再测
执行出错信息：runtime error: signed integer overflow: 964632435 * 10 cannot be represented in type 'int' (solution.cpp)
最后执行的输入： 1534236469
还是溢出的问题~ jackz007 发表于 2019-5-7 10:28
现在再测
最后执行的输入： 1534236469
执行出错信息：runtime error: signed integer overflow: 964632435 * 10 cannot be represented in type 'int' (solution.cpp)
溢出的问题还是木有处理啊~ 风扫地 发表于 2019-5-7 10:53
最后执行的输入： 1534236469
执行出错信息：runtime error: signed integer overflow: 964632435 * 10...
锲而不舍，彻底解决溢出问题：
#include <stdio.h>
#include <stdlib.h>
int ReversInt(int m)
{
int i , k ;
for(k = 0 , i = m ; abs(i) > 0 ; i /= 10) {
if((m > 0 && k + (i % 10) > 214748371) || (m < 0 && k + (i % 10) < -214748372)) {
k = 0 ;
break ;
} else {
k = k * 10 + (i % 10) ;
}
}
return k ;
}
int main(void)
{
int n ;
scanf("%d" , & n) ;
printf("%d\n" , ReversInt(n)) ;
}
jackz007 发表于 2019-5-7 14:42
锲而不舍，彻底解决溢出问题：
1563847412
-2147483648
还是溢出了。 风扫地 发表于 2019-5-7 17:24
1563847412
-2147483648
还是溢出了。
楼主厉害，再把这个攻破！#include <stdio.h>
#include <stdlib.h>
int ReversInt(int m)
{
int i , k ;
for(k = 0 , i = m ; abs(i) > 0 ; i /= 10) {
if((m > 0 && (k > 214748364 || (k == 214748364 && i % 10 > 7))) || (m < 0 && (k < -214748364 || (k == -214748364 && i % 10 < -8)))) {
k = 0 ;
break ;
} else {
k = k * 10 + (i % 10) ;
}
}
return k ;
}
int main(void)
{
int n ;
scanf("%d" , & n) ;
printf("%d\n" , ReversInt(n)) ;
}
jackz007 发表于 2019-5-7 18:31
楼主厉害，再把这个攻破！
增加一句：
if(-2147483648 == m)
{
return 0;
}
就跑完所有的测试用例了：
1032 / 1032 个通过测试用例
状态：通过
执行用时：12 ms
提交时间：0 分钟之前
执行用时 : 12 ms, 在Reverse Integer的C++提交中击败了98.19% 的用户
内存消耗 : 8.2 MB, 在Reverse Integer的C++提交中击败了78.71% 的用户
页:
[1]