007_整数翻转

风扫地

题目来源：力扣
算法好难，只好从简单的题刷起。

1. /*
   
2. 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
   
3. 示例 1:
   
4. 输入: 123
   
5. 输出: 321
   
6. 示例 2:
   
7. 输入: -123
   
8. 输出: -321
   
9. 示例 3:
   
10. 输入: 120
    
11. 输出: 21
    
12. 注意:
    
13. 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231,  231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
    
14. */

复制代码

实现方案：

1. class Solution {
   
2. public:
   
3.     int reverse(int x)
   
4.     {
   
5.         int p_or_n        = 0               ;
   
6.         int overflow_flag = 0               ;
   
7.         int maxvalueLimit = 2147483647/10   ;
   
8.         int ret_val       = 0               ;
   
9.         do{
   
10.             if(  (x == -2147483648  )
    
11.                ||(x == 0            )
    
12.             )
    
13.             {
    
14.                 ret_val = 0;
    
15.                 break;
    
16.             }
    
17.             p_or_n  = x > 0 ? 1:-1; /* 1为正,-1为负数 */
    
18.             x       = x*p_or_n;
    
19.             ret_val = 0;
    
20.             while(x!=0)
    
21.             {
    
22.                 if(ret_val>maxvalueLimit)
    
23.                 {
    
24.                     overflow_flag = 1;
    
25.                     break;
    
26.                 }
    
27.                 ret_val = ret_val*10 + x % 10;
    
28.                 x /= 10;
    
29.             }
    
30.             if(overflow_flag == 0)
    
31.             {
    
32.                 ret_val = ret_val * p_or_n;
    
33.                 break;
    
34.             }
    
35.             else
    
36.             {
    
37.                 return 0;
    
38.             }
    
39.             break;
    
40.         }while(0);
    
41.         return ret_val;
    
42.     }
    
43. };

复制代码

测试代码：

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int main(void)
   
5. {
   
6.    Solution solution;
   
7.    cout << solution.reverse(-2147483648) << endl;
   
8.    cout << solution.reverse(-2147483647) << endl;
   
9.    cout << solution.reverse(-110)        << endl;
   
10.    cout << solution.reverse(2147483641)  << endl;
    
11.    return 0;
    
12. }

复制代码

提交结果：

1. /*
   
2. 执行用时 : 12 ms, 在Reverse Integer的C++提交中击败了98.18% 的用户
   
3. 内存消耗 : 8.4 MB, 在Reverse Integer的C++提交中击败了74.72% 的用户
   
4. */

复制代码

Nice.


附录：
2^31-1=2147483647,-2^31=-2147483648

jackz007

    楼主看看这个实现如何？

1. #include <stdio.h>
   
2. 
   
3. int ReversInt(const int n)
   
4. {
   
5.         int d , i , k , m                            ;
   
6.         bool f                                       ;
   
7. 
   
8.         f = false                                    ;
   
9.         m = n                                        ;
   
10.         if (m < 0) {
    
11.                 m = - m                              ;
    
12.                 f = true                             ;
    
13.         }
    
14.         d = 1                                        ;
    
15.         for(d = 1 , i = m ; i > 0 ; i /= 10) d *= 10 ;
    
16.         for(i = m , k = 0 , d /= 10 ; i > 0 ; i /= 10) {
    
17.             k += (i % 10) * d                        ;
    
18.             d /= 10                                  ;
    
19.         }
    
20.         if (f) k = - k                               ;
    
21.         return k                                     ;
    
22. }
    
23. 
    
24. int main(void)
    
25. {
    
26.         int n                                        ;
    
27.         scanf("%d" , & n)                            ;
    
28.         printf("%d\n" , ReversInt(n))                ;
    
29. }
    

复制代码

风扫地

jackz007 发表于 2019-5-6 20:23
楼主看看这个实现如何？

输入 1534236469
溢出了,楼上没处理溢出的情况.

jackz007

风扫地 发表于 2019-5-6 20:29
输入 1534236469
溢出了,楼上没处理溢出的情况.

      虚心接受楼主的意见，现在再测呢：

1. #include <stdio.h>
   
2. 
   
3. int ReversInt(int m)
   
4. {
   
5.         int i , k                                                          ;
   
6.         bool f                                                             ;
   
7. 
   
8.         f = false                                                          ;
   
9.         if(m < 0) {
   
10.                 m = - m                                                    ;
    
11.                 f = true                                                   ;
    
12.         }
    
13.         for(k = 0 , i = m ; i > 0 ; i /= 10) {
    
14.                 if(k < 0x7fffffff / 10) {
    
15.                         k = k * 10 + (i % 10)                              ;
    
16.                 } else {
    
17.                         k = 0                                              ;
    
18.                         break                                              ;
    
19.                 }
    
20.         }
    
21.         if (f && k) k = - k                                                ;
    
22.         return k                                                           ;
    
23. }
    
24. 
    
25. int main(void)
    
26. {
    
27.         int n                                                              ;
    
28.         scanf("%d" , & n)                                                  ;
    
29.         printf("%d\n" , ReversInt(n))                                      ;
    
30. }
    

复制代码

风扫地

jackz007 发表于 2019-5-6 21:35
虚心接受楼主的意见，现在再测呢：

1.
-2147483648（ -2^31  ）这个测试用例挂了， -2^31  ~ 2^31 -1
最小不能取反，取反就溢出。
2.
测试用例 1463847412 挂了，实际上没溢出，但判断成溢出了。

jackz007

风扫地 发表于 2019-5-7 09:00
1.
-2147483648（ -2^31  ）这个测试用例挂了， -2^31  ~ 2^31 -1
最小不能取反，取反就溢出。

    现在再测

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int ReversInt(int m)
   
5. {
   
6.         int i , k                     ;
   
7.         for(k = 0 , i = m ; abs(i) > 0 ; i /= 10) {
   
8.                 k = k * 10 + (i % 10) ;
   
9.                 if((m > 0 && k <= 0) || (m < 0 && k >= 0)) {
   
10.                         k = 0         ;
    
11.                         break         ;
    
12.                 }
    
13.         }
    
14.         return k                      ;
    
15. }
    
16. 
    
17. int main(void)
    
18. {
    
19.         int n                         ;
    
20.         scanf("%d" , & n)             ;
    
21.         printf("%d\n" , ReversInt(n)) ;
    
22. }
    

复制代码

风扫地

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)


溢出的问题还是木有处理啊~

jackz007

风扫地 发表于 2019-5-7 10:53
最后执行的输入： 1534236469
执行出错信息：runtime error: signed integer overflow: 964632435 * 10  ...

    锲而不舍，彻底解决溢出问题：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int ReversInt(int m)
   
5. {
   
6.         int i , k                             ;
   
7.         for(k = 0 , i = m ; abs(i) > 0 ; i /= 10) {
   
8.                 if((m > 0 && k + (i % 10) > 214748371) || (m < 0 && k + (i % 10) < -214748372)) {
   
9.                         k = 0                 ;
   
10.                         break                 ;
    
11.                 } else {
    
12.                         k = k * 10 + (i % 10) ;
    
13.                 }
    
14.         }
    
15.         return k                              ;
    
16. }
    
17. 
    
18. int main(void)
    
19. {
    
20.         int n                                 ;
    
21.         scanf("%d" , & n)                     ;
    
22.         printf("%d\n" , ReversInt(n))         ;
    
23. }
    

复制代码

风扫地

jackz007 发表于 2019-5-7 14:42
锲而不舍，彻底解决溢出问题：

1563847412
-2147483648
还是溢出了。

jackz007

风扫地 发表于 2019-5-7 17:24
1563847412
-2147483648
还是溢出了。

    楼主厉害，再把这个攻破！

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int ReversInt(int m)
   
5. {
   
6.         int i , k                             ;
   
7.         for(k = 0 , i = m ; abs(i) > 0 ; i /= 10) {
   
8.                 if((m > 0 && (k > 214748364 || (k == 214748364 && i % 10 > 7))) || (m < 0 && (k < -214748364 || (k == -214748364 && i % 10 < -8)))) {
   
9.                         k = 0                 ;
   
10.                         break                 ;
    
11.                 } else {
    
12.                         k = k * 10 + (i % 10) ;
    
13.                 }
    
14.         }
    
15.         return k                              ;
    
16. }
    
17. 
    
18. int main(void)
    
19. {
    
20.         int n                                 ;
    
21.         scanf("%d" , & n)                     ;
    
22.         printf("%d\n" , ReversInt(n))         ;
    
23. }
    

复制代码

风扫地

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% 的用户