007_整数翻转

风扫地 · 发表于 2019-5-6 19:09:12

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由风扫地于 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% 的用户
*/

Nice.

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

jackz007 · 发表于 2019-5-6 20:23:17

楼主看看这个实现如何？

#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))                ;
}

风扫地 · 发表于 2019-5-6 20:29:48

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

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

jackz007 · 发表于 2019-5-6 21:35:56

本帖最后由 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:00:52

本帖最后由风扫地于 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:28:18

本帖最后由 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)) ;
}

风扫地 · 发表于 2019-5-7 10:38:06

jackz007 发表于 2019-5-7 10:28
现在再测

执行出错信息： runtime error: signed integer overflow: 964632435 * 10 cannot be represented in type 'int' (solution.cpp)
最后执行的输入： 1534236469

还是溢出的问题~

风扫地 · 发表于 2019-5-7 10:53:36

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 14:42:30

风扫地发表于 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))         ;
}

风扫地 · 发表于 2019-5-7 17:24:10

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

1563847412
-2147483648
还是溢出了。

jackz007 · 发表于 2019-5-7 18:31:14

风扫地发表于 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))         ;
}

风扫地 · 发表于 2019-5-7 19:29:36

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

账号		自动登录	找回密码
密码			立即注册

[技术交流] 007_整数翻转

马上注册，结交更多好友，享用更多功能^_^

评分