王鹏飞

Blog

Tutorial

About

算法与数学

2021年9月16日

整数反转(Reverse Interger)

一.题目

这个题目是leetcode上的一道算法题,题目如下。

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0. Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

翻译:给一个有符号的32位整数,返回它的数字反转后的整数。如果反转后的数值溢出,即超出了32位整数范围[-2^31, 2^31 - 1],返回0。 限制:不允许存储64位整数。

例如:

Input: x = 123
Output: 321
Input: x = -123
Output: -321

二.分析

最近一年我都在从事JavaScript的工作,C++、C#接触少了,所以看到这种题目,突然有一种陌生感。这个算法题目原本就是为强类型语言程序员设计的,如果是没有接触过强类型语言(C++、C#、Java等)的JavaScript程序员看到这种题目,也许题目都看不大懂。

首先解释下一些概念。

  • signed: 符号,强类型语言中,数值类型都分为有符号和无符号两种,有符号数的二进制最后一位存储的是符号位,在这道题目中你不需要关心二进制的符号位,只需要知道题目表示的是正负整数。

  • 32-bit: int类型是4字节的,一个字节占8位,所以32-bit的整数范围为[-2^31, 2^31 - 1],即[-2147483648, 2147483647]。

假设有输入1111111119,反转整数为9111111111,结果超出了32-bit整数范围,所以应该返回0。

题目还限制不允许使用64位整数,所以不允许使用long类型(long类型是8个字节,64位)数值。

如果不考虑题目限制,可以很自然的写出如下解法:

// c++,使用了long类型,不符合题意
class Solution {
public:
    int reverse(int x) {
        long result = 0;
        while (x != 0) {
            result = 10 * result + x % 10;
            x /= 10;
        }
        return (result > INT_MAX || result < INT_MIN) ? 0 : res;
    }
};

令我惊讶的是,上面的题目竟然通过了,leetcode并没有检测是否使用了long类型。

三.最佳解法

上面的解法使用了long类型数据,显然不符合题意。在网上找到了另一种解法,如下:

class Solution {
public:
    int reverse(int x) {
        int res = 0;
        while (x != 0) {
            if (abs(res) > INT_MAX / 10) return 0;
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
};

与第一种解法很相似,但是没有用到long类型。它用了一种很巧妙的方法,避免了使用long类型。

通过abs(res) > INT_MAX / 10,检测结果是否溢出。为什么可以使用这种方式呢?

首先,输入的整数x也是一个32-bit整数,所以范围应该在[-2147483648, 2147483647]内。分以下两种情况讨论:

  • x位数等于10位:那么x的第一位只能为1或者2,反转后的值(不包含正负号)为xxxxxxxxx1xxxxxxxxx2
  • x位数小于10位:那么反转后的值肯定也在32-bit范围内,直接返回反转后的值。

x位数等于10位时,设反转后的值为rx,我们只需要判断abs(rx / 10) > INT_MAX / 10即可判断数值是否溢出,因为rx个位数值只可能为1或者2,不需要判断。

(完)

二叉树—已知二叉树的前序遍历和中序遍历,输出二叉树
正则表达式匹配

留言(0


发表评论

邮箱地址不会被公开。*表示必填项