目錄
- LeetCode_007_整數反轉
- 題目描述
- 總體分析
- 解決方案
- 小結
LeetCode_007_整數反轉
題目描述
給出一個 32 位的有符號整數，你需要將這個整數中每位上的數字進行反轉，
示例 1:
輸入: 123
輸出: 321
示例 2:
輸入: -123
輸出: -321
示例 3:
輸入: 120
輸出: 21
注意:
假設我們的環境只能存盤得下 32 位的有符號整數，則其數值范圍為 [?2^31, 2^31 ? 1]，請根據這個假設，如果反轉后整數溢位那么就回傳 0，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/reverse-integer
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
總體分析
題目中要求將一個有符號整數進行反轉，通過題目給出的例子，需要注意以下幾點：
-
整數會有負數的情況，反轉后符號不變，
-
只能存盤 32 位有符號整數，取值范圍為：-2147483648 ~ 2147483647，超過此范圍即為溢位，如果反轉后發生了溢位情況，回傳 0，
-
要反轉的數字最后一位是 0 的情況反轉過來后要將 0 舍棄，
- 如題目中的這個例子：120 --> 21，
解決方案
思路分析:
首先，先分析溢位問題，對于題目中要求的 32 位有符號整數，其實也就是 int 型別，相對應的取值范圍為：-2147483648 ~ 2147483647，那么發生溢位的情況就是反轉過來的數不在這個范圍內，
舉個例子：將 2111222239 反轉過來后為 9322221112，此時這個數超過了上面的范圍，這個情況就是溢位，此時回傳 0 即可，
接著，分析轉換的數是負數時的情況：如果要轉換的數是負數，就先取其絕對值將其反轉后再將結果轉換為負數回傳即可，
綜上，可以設計解題流程如下，假設要轉換的數為 x：
-
首先判斷 x 是否為 -2147483648，如果是回傳 0，防止取 x 絕對值 -x 時報錯，
-
判斷 x 是否為負數，如果是負數則先取其絕對值然后遞回取反，最后將結果轉換為負數，
-
使用一個變數 result 保存結果，初始時為 0，
-
對 x 取反時將 x % 10 依次取出最后一位數（例如: 256 % 10 = 6）放置到 result 中（即 result * 10 + x % 10），最后將 x / 10，依次進行此程序即可將 x 反轉，
-
在取反程序中需要注意的是要進行該判斷：if (result > 214748364) 進行提前判斷溢位處理，
舉個例子說明:
1463847412 反轉后為 2147483641,此時當反轉到 214748364 時,還沒有大于,所以沒有溢位，如果 result > 214748364 說明反轉后就已經溢位了，
例如：1563847412 -> 2147483651,當反轉到 214748365 時,由于大于了 214748364,所以可以提前判斷溢位，
-
判斷 result 是否溢位，如果溢位回傳 0，否則回傳反轉后的結果,這里判斷溢位是因為前面的提前判斷溢位不能判斷到最后一位,如果最后一位加的數超過溢位值的話就會產生溢位,所以需要判斷，不好理解的話可以結合下面代碼進行理解，
根據以上思路，可設計題解代碼如下：
/**
* 整數反轉解題方案
*
* @author 踏雪彡尋梅
* @date 2020/2/6 - 12:14
*/
class Solution {
public int reverse(int x) {
if (x == -2147483648) {
// 做此判斷防止取 x 絕對值時 x = -x 報錯
return 0;
}
if (x < 0) {
// 如果為負數,取其絕對值呼叫自己然后將結果轉為負數
return -reverse(-x);
}
// 用于保存結果回傳
int result = 0;
// 取反操作
while (x != 0) {
if (result > 214748364) {
// 處理溢位
// 舉例：1463847412
// 反轉后：2147483641
// 此時當反轉到 214748364 時,還沒有大于,所以沒有溢位
// 如果 result > 214748364 反轉后就已經溢位了
// 例如：1563847412 -> 2147483651
// 當反轉到 214748365 時,由于大于了 214748364,所以可以提前判斷溢位
return 0;
}
// 接收取反結果
result = result * 10 + x % 10;
x /= 10;
}
// 如果溢位就回傳 0
// 防止提前判斷溢位不能判斷到最后一位的情況,如果最后一位加的數超過溢位值的話就會產生溢位
return result <= 2147483647 ? result : 0;
}
}
提交結果:
提交后時間上和空間上的結果還是效果蠻好的O(∩_∩)O，接下來進行一些簡單的時間復雜度和空間復雜度分析，
時間復雜度簡單分析:
對于時間復雜度則是分析 while 回圈中的代碼，因為這塊代碼占據了程式的時間是最多的，
while (x != 0) {
if (result > 214748364) {
return 0;
}
result = result * 10 + x % 10;
x /= 10;
}
從以上代碼可以看出，x 每回圈一次就除以 10，直到 x = 0 時或者 result 溢位時才結束回圈，這里假設 result 不溢位的情況來進行分析：
對于 x / 10 判斷 x 是否等于 0 其實可以看為：x 除了幾次 10 才等于 0，這里假設這個次數為 n，
用式子表達也就是：x / 10 / 10 / 10 / ... / 10 = x / 10n = 0，即可以表示為 x = 10n
也就是說明，程式的運行時間主要跟 n 相關，所以需要將 n 計算出來：
通過 x = 10n 求解 n 這個問題在高中時就已經學過了，即 n = log10x，
所以，時間復雜度為 O(log10x) = O(lgx)，
空間復雜度簡單分析:
空間上使用了一個 result 整型變數用來輔助接收結果，每次賦值分配的空間都是常數級別的，所以空間復雜度為 O(1)，
小結
解題時需要注意特殊情況：為負數的情況、尾部為 0 的情況以及整數溢位的情況，
如有寫的不足的，請見諒，請大家多多指教，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/3042.html
標籤：其他