題目地址:
整數(shù)反轉(zhuǎn)
1.題目描述
給出一個 32 位的有符號整數(shù)，你需要將這個整數(shù)中每位上的數(shù)字進行反轉(zhuǎn)。
示例 1:
輸入: 123
輸出: 321
示例 2:
輸入: -123
輸出: -321
示例 3:
輸入: 120
輸出: 21
注意:
假設(shè)我們的環(huán)境只能存儲得下 32 位的有符號整數(shù)，則其數(shù)值范圍為 [?231, 231 ? 1]。請根據(jù)這個假設(shè)，如果反轉(zhuǎn)后整數(shù)溢出那么就返回 0。
2.題解
2.1解題思路
首先整數(shù)反轉(zhuǎn)，比如123反轉(zhuǎn)成321，可以從個位數(shù)往前推，可以寫成這樣的格式
321=3*100+2*10+1
現(xiàn)在看一下123取余和取商的過程
//先對123取余
int x=123
//pop=3
int pop=x%10;
//對123取商
//bob=12
int bob =x/10;
//對bob取余
//yy=2
int yy= bob%10;
//對bob取商
//dd=1
int dd =bob/10;
//對dd取余
//a=1
int a=dd%10
//對dd取商
//b=0
int b = dd/10
當最后取商值為0的時候循環(huán)就結(jié)束了，每一次的余數(shù)乘以10的N次方，就可以得到反轉(zhuǎn)后的整數(shù)。
2.2第一版代碼
官方給了java提交的方法定義
class Solution {
public int reverse(int x) {
}
}
規(guī)定了方法返回值必須為int
2.2.1 保存每次的余數(shù)
先考慮全是正整數(shù)的情況，對x取絕對值，即可得到全是正整數(shù)的情況
Math.abs(x)
然后使用一個list來保存每次除以10的余數(shù)，使用一個for循環(huán)來做取余和取商的運算，結(jié)果保存在lsit中
List<Integer> list = new ArrayList<>();
//其實根據(jù)int的限制，i的最大值不會超過10
for (int i = 0; i < Integer.MAX_VALUE; i++) {
list.add(x%10);
x = x / 10;
//當x==0的時候，表明計算到了x的首位數(shù)字，循環(huán)結(jié)束
if (x == 0) {
break;
}
}
根據(jù)上述的步驟我們現(xiàn)在得到了x每次除以10的余數(shù)，然后遍歷list，乘以相應(yīng)的次冪，這樣就可以得到反轉(zhuǎn)的結(jié)果。
2.2.2 計算反轉(zhuǎn)的數(shù)
根據(jù)list.size(),可以得到該乘以多少個10,
//result定義成long型，是為了防止整型溢出
//最后可以將long轉(zhuǎn)成int
long result = 0;
for (int i = 0; i < list.size(); i++) {
result+=list.get(i)*power(10,list.size()-1-i);
}
下面是求冪次方的方法
public long power(long base, int expoment) {
long result = 1;
for (int i = 0; i < expoment; i++) {
result *= base;
}
return result;
}
2.2.3 最終的返回值
為了判斷入?yún)是正數(shù)還是負數(shù),引入了一個boolean參數(shù),初始值為false,如果x為負數(shù),就設(shè)為true
boolean isNegativeNu = false;
x為負的情況:
if (isNegativeNum) {
return new Long(((0-result)>-2147483648?(0-result):0)).intValue();
}
上面的result定義成了long型,所以最后返回的時候需要轉(zhuǎn)化為int，負數(shù)通過0-result得到。
x為正的情況
return new Long(result<2147483647?result:0).intValue();
這里考慮整形的范圍是[-2147483648,2147483647],即：
[-2^31,2^31-1]
超過整形的范圍需要返回0,不然會溢出,得到一些奇怪的結(jié)果,所以循環(huán)的時候result定義成long，先得出結(jié)果，等最終返回的時候在轉(zhuǎn)換成int，這樣會簡單一點。
2.2.3.完整的代碼
package com.fc.algorithm.array;
import java.util.ArrayList;
import java.util.List;
public class ReverseTest {
public static int reverse(int x) {
boolean isNegativeNum =false;
if (x==Integer.MIN_VALUE) {
return 0;
}
if (x<0) {
isNegativeNum =true;
}
x= Math.abs(x);
List<Integer> list = new ArrayList<>();
for (int i = 0; i < Integer.MAX_VALUE; i++) {
list.add(x%10);
x = x / 10;
if (x == 0) {
break;
}
}
long result = 0;
for (int i = 0; i < list.size(); i++) {
result+=list.get(i)*power(10,list.size()-1-i);
}
if (isNegativeNum) {
return new Long(((0-result)>-2147483648?(0-result):0)).intValue();
}
return new Long(result<2147483647?result:0).intValue();
}
public static long power(long base, int expoment) {
long result = 1;
for (int i = 0; i < expoment; i++) {
result *= base;
}
return result;
}
public static void main(String[] args) {
int reverse = reverse(-2147483648);
System.out.println(reverse);
System.out.println(Integer.MAX_VALUE);
System.out.println(Integer.MIN_VALUE);
int abs = Math.abs(-2147483648);
System.out.println(abs);
}
}
2.2.4.leetcode運行結(jié)果
性能差了一點，引入了list，導(dǎo)致內(nèi)存占用高了一點，運行時間也有點長,有的答案用C++運行耗時0ms;
2.2.5.需要注意的點
1.int范圍
剛開始的時候沒考慮到int的范圍問題，運行的時候頻繁溢出,得到一些奇怪的返回值
2.Integer.MIN_VALUE
Integer.MIN_VALUE取絕對值會比Integer.MAX_VALUE大一，也會導(dǎo)致溢出
2.3.第二版代碼
2.3.1.改進方向
現(xiàn)在去掉一些判斷，去掉list，看看結(jié)果會不會好一點
首先去掉正負數(shù)的判斷,然后去掉list
然后去掉定義的求冪次方的方法
改完之后代碼精簡了很多
public int reverse(int x) {
//-10<x<10直接返回
if (x/10==0) {
return x;
}
long result = 0;
for (int i = 0; i < 10; i++) {
//每循環(huán)一次，余數(shù)就會乘以10，可以達到上面用list統(tǒng)計需要乘以10的多少次冪的效果
result=result*10+x%10;
//超過整型范圍直接返回
if (result < Integer.MIN_VALUE || result > Integer.MAX_VALUE) {
return 0;
}
x = x / 10;
if (x==0) {
break;
}
}
return new Long(result).intValue();
}
2.3.2.改完之后的性能
根據(jù)leetcode執(zhí)行結(jié)果可以看到，運行時間和內(nèi)存消耗都有提升，不過提升的不太明顯，還附帶了一次C++代碼的執(zhí)行效果，C++的代碼運行效率和內(nèi)存消耗確實低了很多。
3.總結(jié)
這是一道數(shù)學(xué)題，反轉(zhuǎn)需要用到數(shù)學(xué)知識，從后往前乘以10的N次冪即可。主要是限定在整型范圍內(nèi)，需要考慮越界的問題。
