反向整数leetcode - 如何处理溢出

Question

问题是:整数的反转数字.

例1:x = 123,返回321

例2:x = -123,返回-321

您是否注意到反转的整数可能会溢出？假设输入是32位整数,则反向1000000003溢出.你应该如何处理这类案件？

抛出异常？很好,但如果抛出异常不是一种选择呢？然后,您必须重新设计该功能(即添加一个额外的参数).

我搜索的网站的解决方案是:

public class Solution {

     public static int reverse(int x) {
            int ret = 0;
            boolean zero = false;
            while (!zero) {
                ret = ret * 10 + (x % 10);
                x /= 10;      
                if(x == 0){
                    zero = true;
                }
            }
            return ret;   
        }

    public static void main(String[] args) {
        int s = 1000000003;
        System.out.println(reverse(s));
    }

}

但是,当s = 1000000003控制台打印-1294967295而不是3000000001.因此,如果我们不能使用异常,这个解决方案仍然无法解决溢出问题.这里有什么帮助？(虽然有一个提示:添加一个额外的参数,我仍然无法弄清楚我应该添加什么参数)

Answer 1

除了int之外,不需要任何数据类型.只需确保当有一个增加数字的操作时,反转操作应该给你以前的数字.否则,就会溢出.

public int reverse(int x) {
    int y = 0;

    while(x != 0) {
        int yy = y*10 + x%10;

        if ((yy - x%10)/10 != y) return 0;
        else y = yy;

        x = x/10;   
    }
    return y;
}

Answer 2

在大多数具有微不足道问题的答案之上,int变量可能会溢出.您可以尝试:x = -2147483648作为参数.有一种简单的方法可以解决这个问题.将x转换为long,并检查结果是否> = Integer.MAX_VALUE,否则返回0.解决方案通过https://leetcode.com/problems/reverse-integer/上的所有测试用例

这是一个java版本.

public int reverse(int x) {
        long k = x;
        boolean isNegtive = false;        
        if(k < 0){
            k = 0 - k;
            isNegtive = true;
        }

        long result = 0;
        while(k != 0){
            result *= 10;
            result += k % 10;
            k /= 10;
        }

        if(result > Integer.MAX_VALUE) return 0;
        return isNegtive  ? 0 - ((int)result) : (int)result;
    }

C#版本

    public int Reverse(int x)
    {
        long value = 0;
        bool negative = x < 0;
        long y = x;
        y = Math.Abs(y);

        while (y > 0)
        {
            value *= 10;
            value += y % 10;
            y /= 10;
        }

        if(value > int.MaxValue)
        {
            return int.MaxValue;
        }

        int ret = (int)value;

        if (negative)
        {
            return 0 - ret;
        }
        else
        {
            return ret;
        }
    }

Python版本

def reverse(self, x):                
    isNegative = x < 0
    ret = 0
    x = abs(x)
    while x > 0:
        ret *= 10
        ret += x % 10
        x /= 10
    if ret > 1<<31:
        return 0

    if isNegative:
        return 0 - ret
    else:
        return ret

Answer 3

这是一个老问题，但无论如何让我也尝试一下！我刚刚在leetcode上解决了这个问题。通过此检查，您永远不会遇到任一方向的上溢/下溢，并且我认为该代码比所有列出的代码更简洁。它通过了所有测试用例。

public int reverse(int x) {
    int y = 0;
    while(x != 0) {
        if(y > Integer.MAX_VALUE/10 || y < Integer.MIN_VALUE/10) return 0;
        y *= 10;
        y += x % 10;
        x /= 10;
    }
    return y;
}

Answer 4

public static int reverse(int x) {
  boolean pos = x >= +0;
  int y = (pos) ? x : -x;
  StringBuilder sb = new StringBuilder(
      String.valueOf(y));
  sb.reverse();
  int z = Integer.parseInt(sb.toString());
  return pos ? z : -z;
}

public static void main(String[] args) {
  for (int i = -10; i < 11; i++) {
    System.out.printf("%d r= '%d'\n", i, reverse(i));
  }
}

输出

-10 r= '-1'
-9 r= '-9'
-8 r= '-8'
-7 r= '-7'
-6 r= '-6'
-5 r= '-5'
-4 r= '-4'
-3 r= '-3'
-2 r= '-2'
-1 r= '-1'
0 r= '0'
1 r= '1'
2 r= '2'
3 r= '3'
4 r= '4'
5 r= '5'
6 r= '6'
7 r= '7'
8 r= '8'
9 r= '9'
10 r= '1'

你注意到 10 和 -10 的相反了吗？还是20？例如，您可以只返回一个字符串

public static String reverse(int x) {
  boolean pos = x >= +0;
  int y = (pos) ? x : -x;
  StringBuilder sb = new StringBuilder(
      String.valueOf(y));
  sb.reverse();
  if (!pos) {
    sb.insert(0, '-');
  }
  return sb.toString();
}

public static void main(String[] args) {
  for (int i = -10; i < 11; i++) {
    System.out.printf("%d r= '%s'\n", i, reverse(i));
  }
}

正如我所期望的那样工作。