Java Reverse Integer leetcode——如何处理溢出
声明:本页面是StackOverFlow热门问题的中英对照翻译,遵循CC BY-SA 4.0协议,如果您需要使用它,必须同样遵循CC BY-SA许可,注明原文地址和作者信息,同时你必须将它归于原作者(不是我):StackOverFlow
原文地址: http://stackoverflow.com/questions/21070506/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Reverse Integer leetcode -- how to handle overflow
提问by CSnerd
The problem is: Reverse digits of an integer.
问题是:反转整数的数字。
Example1: x = 123, return 321
示例 1:x = 123,返回 321
Example2: x = -123, return -321
示例 2:x = -123,返回 -321
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
您是否注意到反转整数可能会溢出?假设输入是一个 32 位整数,那么 1000000003 的反向溢出。遇到这种情况应该怎么处理?
Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).
抛出异常?很好,但是如果抛出异常不是一种选择呢?然后您将不得不重新设计该函数(即,添加一个额外的参数)。
The solution from the website I search is:
我搜索的网站的解决方案是:
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));
}
}
However when s = 1000000003
, the console prints -1294967295
instead of 3000000001
. So this solution still does not solve the overflow problem if we cannot use exception. Any help here?(Although there is a hint: add an extra parameter, I still cannot figure out what parameter I should add)
但是,当 时s = 1000000003
,控制台打印-1294967295
而不是3000000001
. 所以如果我们不能使用异常,这个解决方案仍然不能解决溢出问题。这里有什么帮助吗?(虽然有提示:添加一个额外的参数,但我仍然不知道我应该添加什么参数)
回答by Elliott Frisch
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));
}
}
Outputs
输出
-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'
Did you notice the reverse of 10 and -10? Or 20? You could just return a String, for example
你注意到 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));
}
}
Works as I would expect.
正如我所期望的那样工作。
回答by suh
If you are required to return a 32 bit int, and still need to know if there was an overflow perhaps you could use a flag as an extra parameter. If you were using c or c++ you could use pointers to set the flag, or in Java you can use an array (since Java objects pass by value).
如果您需要返回 32 位 int,并且仍然需要知道是否存在溢出,那么您可以使用标志作为额外参数。如果您使用的是 c 或 c++,您可以使用指针来设置标志,或者在 Java 中您可以使用数组(因为 Java 对象按值传递)。
Java example:
Java示例:
public class Solution {
public static int reverse(int x, Boolean[] overflowed) {
int ret = 0;
boolean zero = false;
boolean inputIsNegative = x < 0;
while (!zero) {
ret = ret * 10 + (x % 10);
x /= 10;
if(x == 0){
zero = true;
}
}
//Set the flag
if ( (inputIsNegative && (ret > 0)) || ((!inputIsNegative) && (ret < 0)))
overflowed[0] = new Boolean(true);
else
overflowed[0] = new Boolean(false);
return ret;
}
public static void main(String[] args) {
int s = 1000000004;
Boolean[] flag = {null};
System.out.println(s);
int n = reverse(s,flag); //reverse() will set the flag.
System.out.println(flag[0].booleanValue() ? "Error: Overflow": n );
}
}
Notice if the reversed number is too large for a 32 bit integer the flag will be set. Hope this helps.
请注意,如果反转数对于 32 位整数来说太大,则标志将被设置。希望这可以帮助。
回答by Vikram Bhat
Use string to store the reverse and then print or use long or BigInt
使用字符串存储反向然后打印或使用 long 或 BigInt
回答by Charles Wang
My soluton for this problem is to convert integer inputed to c-string, then everthing will be easy.
我对这个问题的解决方案是将输入的整数转换为 c 字符串,然后一切都会很容易。
class Solution {
public:
int reverse(int x) {
char str[11];
bool isNegative = false;
int i;
int ret = 0;
if ( x < 0 ) {
isNegative = true;
x = -x;
}
i = 0;
while ( x != 0 ) {
str[i++] = x % 10 + '0';
x = x / 10;
}
str[i] = 'public class Solution {
/**
* OVERFLOW
* @param x
* @return
*/
public int reverse(int x) {
int sign = x>0? 1: -1;
x *= sign;
int ret = 0;
while(x>0) {
ret *= 10;
if(ret<0 || x>10&&ret*10/10!=ret) // overflow
return 0;
ret += x%10;
x /= 10;
}
return ret*sign;
}
public static void main(String[] args) {
assert new Solution().reverse(-2147483412)==-2147483412;
}
}
';
if ( (isNegative && strlen(str) == 10 && strcmp(str, "2147483648") > 0) || (!isNegative && strlen(str) == 10 && strcmp(str, "2147483647") > 0) ) {
cout << "Out of range!" << endl;
throw new exception();
}
i = 0;
int strLen = (int)strlen(str);
while ( str[i] != '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;
}
' ) {
ret += ((str[i] - '0') * pow(10.0, strLen - 1 - i));
i++;
}
return (isNegative ? -ret : ret);
}
};
};
回答by Daniel
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;
}
回答by user3366372
There's no need for any data type other than int. Just make sure when there's an operation that increases a number, reversing the operation should give you the previous number. Otherwise, there's overflow.
除了 int 之外,不需要任何数据类型。只要确保当有一个增加数字的操作时,反转操作应该给你以前的数字。否则就会溢出。
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;
}
}
回答by Jiaji Li
Above most of the answers having a trivial problem is that the int variable possibly might overflow. You can try this : x = -2147483648 as parameter. There has an easy way to solve the problem. Convert x to long, and check if the result >= Integer.MAX_VALUE, otherwise return 0. The solution passed all test cases on https://leetcode.com/problems/reverse-integer/
大多数有一个小问题的答案是 int 变量可能会溢出。你可以试试这个: x = -2147483648 作为参数。有一个简单的方法可以解决这个问题。将x转换为long,并检查结果是否>=Integer.MAX_VALUE,否则返回0。解决方案通过https://leetcode.com/problems/reverse-integer/上的所有测试用例
This is a java version.
这是一个java版本。
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
C# version
C#版本
public int reverse(int x) {
long reverse = 0;
while( x != 0 ) {
reverse = reverse * 10 + x % 10;
x = x/10;
}
if(reverse > Integer.MAX_VALUE || reverse < Integer.MIN_VALUE) {
return 0;
} else {
return (int) reverse;
}
}
Python version
蟒蛇版
public class Solution {
public int Reverse(int x) {
var sign = x < 0 ? -1 : 1;
var reverse = 0;
if (x == int.MinValue)
{
return 0;
}
x = Math.Abs(x);
while(x > 0)
{
var remainder = x % 10;
if (reverse > ((int.MaxValue - remainder)/10))
{
return 0;
}
reverse = (reverse*10) + remainder;
x = x/10;
}
return sign * Convert.ToInt32(reverse);
}
}
回答by Apurva Kumar Sinha
This java code handles the overflow condition:
此 java 代码处理溢出条件:
public class Solution {
public int reverse(int x) {
long tmp = Math.abs((long)x);
long res = 0;
while(tmp >= 10){
res += tmp%10;
res*=10;
tmp=tmp/10;
}
res+=tmp;
if(x<0){
res = -res;
}
return (res>Integer.MAX_VALUE||res<Integer.MIN_VALUE)? 0: (int)res;
}
}
回答by nimmi chhabra
public class Solution {
public int reverse(int x) {
long tmp = x;
long res = 0;
if(x>0){
while(tmp >= 10){
res += tmp%10;
res*=10;
tmp=tmp/10;
}
}
else{
while(tmp <= -10){
res += tmp%10;
res*=10;
tmp=tmp/10;
}
}
res+=tmp;
return (res>Integer.MAX_VALUE||res<Integer.MIN_VALUE)? 0: (int)res;
}
}
回答by Zar Shardan
This works:
这有效:
##代码##I tried to improve the performance a bit but all I could come up with was this:
我试图稍微提高性能,但我能想到的是:
##代码##Its C# equivalent runs 5% faster than the 1st version on my machine, but their server says it is slower, which can't be - I got rid of extra function call here, otherwise it is essentially the same. It places me between 60-30% depending on the language (C# or Java). Maybe their benchmarking code is not very good - if you submit several times - resulting times vary a lot.
它的 C# 等价物在我的机器上比第一个版本快 5%,但他们的服务器说它更慢,这不可能 - 我在这里去掉了额外的函数调用,否则它本质上是一样的。取决于语言(C# 或 Java),它让我处于 60-30% 之间。也许他们的基准测试代码不是很好——如果你多次提交——结果时间差异很大。