1 前言

題目來源于Leetcode。

重點：理清邏輯，忽略細節，模仿高手，五毒神掌

2 題目分析

題目很容易理解，先分成兩個部分

• 正數
• 負數

先解決正數

最開始想到的是

唯一增加的就是，先判斷整數是多少位。

之后再判斷溢出

然后解決負數
先使用一個bool變量保存符號，如果是負數，則取絕對值，再按正數進行運算，之后再加上符號，再判斷溢出。

整體思維非常容易想到，分治思想，下面是代碼。

3 自己想

int reverse(int x) {// 不管正負數，全變正數bool isNegativeNumber = false;int  xAbsoluteValue = 0;if (x < 0) {isNegativeNumber = true;if (x != INT_MIN)xAbsoluteValue = -x;elsereturn 0;}else {isNegativeNumber = false;xAbsoluteValue = x;}// 判斷整數多少位【動態的】int xTemporary = xAbsoluteValue;int count = 0;for (int i = 0; i < sizeof(int)*8; i++) { // 【注意】字節數*8if (xTemporary == 0) {break;}else {count++;}xTemporary /= 10;}// 反轉long long xNew = 0; // 不要用long，它在32位下也是4字節xTemporary = xAbsoluteValue;for (int i = 0; i < count; i++) {xNew = xNew * 10 + xTemporary % 10;xTemporary /= 10;}// 符號回歸if (isNegativeNumber) {xNew = -xNew;}// 判斷溢出if (xNew < INT_MIN || xNew > INT_MAX) {return 0;}else{return xNew;}}

運行結果還可以，就是系統本身不穩定，有時候是4ms，這不重要，重要的是，這種做法太啰嗦了，我先嘗試按照這個思路優化一下。

去掉符號轉換，這部分沒有也一樣

注意使用long long，而不是long，32位下前者8字節，后者和int一樣4個字節

判斷溢出，使用一行代碼搞定，取締if else，使用三元運算符

// 判斷整數多少位【動態的】int xTemporary = x;int count = 0;for (int i = 0; i < sizeof(int) * 8; i++) { // 【注意】字節數*8if (xTemporary == 0) {break;}else {count++;}xTemporary /= 10;}// 反轉long long xNew = 0; xTemporary = x;for (int i = 0; i < count; i++) {xNew = xNew * 10 + xTemporary % 10;xTemporary /= 10;}return (xNew < INT_MIN || xNew > INT_MAX) ? 0 : xNew;

好了，這個程序已經優化了很多了，還有沒有空間繼續優化呢？

再優化，就只能在獲取整數位數下手，將其直接變成反轉的條件使用。

好吧……我做不下去了，看大神解法好了。

談一談收獲

1. 對待算法題，重點關注邏輯，對于防御性編程等細節可以不用深究
2. 先把邏輯在紙面上搞清楚，再寫代碼！
3. int、long等數據類型的大小，根據系統位數以及編譯器決定，需要實際測試一下，盡量使用sizeof等通用的東西
4. 計算位數部分，有一點動態規劃的意思，很有趣。

毫無移位，按照我這么寫算法題，可以涼涼了~~~~接下來，我來學習一下大神的解法吧。

4 看大神做法，直接模仿學會

4.1 大神一

long long res = 0;
while (x) {res = res * 10 + x % 10;x /= 10;
}
return (res < INT_MIN || res > INT_MAX) ? 0 : res;

這個大神與我的思路類似，只不過比我的又進一步優化，我們學習一下。

這里最重要的一點，不需要判斷多少位，也不需要暫存，不用管循環次數，循環結束的條件，就是x = 0。

這也不是本質，這題的本質是數學問題。

• 是1234變成4321的問題
• 是1234提取出每一個數字的問題

來看看我的算法中愚蠢的點。

// 判斷整數多少位【動態的】int xTemporary = x;int count = 0;for (int i = 0; i < sizeof(int) * 8; i++) { // 【注意】字節數*8if (xTemporary == 0) {break;}else {count++;}xTemporary /= 10;}// 反轉long long xNew = 0; xTemporary = x;for (int i = 0; i < count; i++) {xNew = xNew * 10 + xTemporary % 10;xTemporary /= 10;}

關注一下兩個循環的條件

• 循環32次，確定位數
• 根據位數再反轉

事實上，我想的是，先確定好位數，這樣就不用每次都循環32次了，但是，我在確定位數的時候，還是循環了32次……蠢到家……

雖然不是每次循環32次，但是，這種程序結構無疑是垃圾的，盡管是雙重保險，但是沒有必要阿，我們警惕一下！

值得警惕的結構

拋開題目本身，我們看一看這個結構

for (int i = 0; i < sizeof(int) * 8; i++) { // 【注意】字節數*8if (xTemporary == 0) {break;}else {count++;}xTemporary /= 10;
}

for循環中，嵌套一個通過if判斷的跳出循環的裝置，我們來改進一下

while(xTemporary){ xTemporary /= 10;count++;}

嗯，這倆功能完全一樣，但是顯然后者更加簡潔

現在，我們是通過中介count來完成程序，那么，可以去掉中間商嗎？

當然可以！

既然，xTemporary /= 10就可以作為終止條件，我們直接用就好了，沒必要再管中間商，忽略它！

看一下我們剛才優化的本質，將x /= 10;和while(x) 二者配合，作為循環終止條件，因此，我們進一步優化。

// 判斷整數多少位【動態的】int xTemporary = x;int count = 0;while(xTemporary){ xTemporary /= 10;count++;}// 反轉long long xNew = 0; while(xTemporary) {xNew = xNew * 10 + xTemporary % 10;xTemporary /= 10;}

這樣一來，你很容易發現，第一個循環完全沒有用，直接刪掉。

int reverse(int x) {long long xNew = 0; while(x) {xNew = xNew * 10 + x % 10;x /= 10;}return (xNew < INT_MIN || xNew > INT_MAX) ? 0 : xNew;
}

我們，成功將自己的爛程序一步步優化成了大神的程序。

為了程序的通用性，我們稍改一下

int reverse(int x) {long long xNew = 0; while(x != 0) {xNew = xNew * 10 + x % 10;x /= 10;}return (xNew < INT_MIN || xNew > INT_MAX) ? 0 : xNew;
}

因為只有C/C++使用0和false是一樣的，但是Java就不允許，只能使用布爾值。

4.2 大神二

int reverse(int x) {int d = 0;while (x){if (d > INT_MAX / 10 || d < INT_MIN / 10)return 0;d = d * 10 + x % 10;x = x / 10;}return d;
}

我們分析大神的思路，我先緩緩下跪了！

在后面五毒神掌第二掌會分析。

5 收獲

5.1 一個重要結構的優化

for循環內，通過if跳出的時候，可以優化。

for(int i = 0;i < sizeof(int)*8;i++){if(x){break;	}x /= 10
}

while(x){x /= 10
}

5.2 去掉“中間商”的方法

對于一些共性的東西，不再單獨列出中間結果，直接得到最終答案。

5.3 算法的本質是數學問題

這個數學表達式其實是這么來的

• 先分治，拆解為數字+權重的形式，本質是硬件思維
• 再調換數字的權重
  

至于最終的表達式，需要一點點優化過來。

我們需要知道，對于int x;

• 求最低位的數字：x % 10
• 降維，降低數量級：x / 10（利用int直接抹掉小數點）

第一次的算法(使用偽代碼)

while(遍歷每一位的數字){number[i] = x % 10;x /= 10;
}

這是很容易想到的，那么，我們保存了每一位數字，怎么保存它的權重？真的有必要保存權重嗎？
顯然沒有必要，我們試一下就知道，可以直接一邊處理舊數字，一邊計算新數字。

newX = 0;
while(遍歷每一位的數字){number[i] = x % 10;x /= 10;newX = newX*10 + number[i];
}

這已經是最小單元，沒法解釋，自己試一下吧。

然后你會發現number[i]是多余的，并且遍歷的條件就是x ！= 0。

long long newX = 0;
while(x != 0){newX = newX*10 + x % 10;x /= 10;
}

至于為什么用long long，這叫先假想結果，因為結果會溢出，所以只能用long long了。

5.4 一些衍生的題目

5.4.1 求整數位數

所有整數均可。

int reverse(int x) {int count = 0;while (x){x /= 10;count++;}return count;
}

5.4.2 求整數的每一位

void reverse(int x) {int count = 0;int xTemporary = x;while (xTemporary){xTemporary /= 10;count++;}int *everyNumber = new int[count];for (int i = 0; i < count; i++) {everyNumber[i] = x % 10;x /= 10;}for (int i = 0; i < count; i++) {cout << everyNumber[i] << endl;}
}

注意

char與int轉換，記得差一個'0'

int i = 4;
char a = i + '0';
cout << a << endl;

6 五毒神掌

五毒神掌是什么？

關注代碼邏輯和結構層面的細節

目標導向，一天一個，完全搞定300題

6.1 第一掌

1. 先正確理解題目
2. 自己想，5分鐘想出來就寫
3. 想不出來，就直接看世界大神答案，并且理解
4. 然后大致理解背下來（理解代替記憶，如果不理解，就先記憶，多用用就理解了）
5. 邊抄邊背的方式寫代碼

自己的思路不能只有一種，每種都要嘗試。

重點關注邏輯！畫圖+手算分析

6.1.1 自己思考的過程

題目很簡單，就是整數反轉，需要注意

• 正負數問題
• 反轉后溢出問題：用long long存儲

之后用幾個數字試一試，研究一下數學公式，先寫正確，再不斷優化。

int reverse(int x) {long long xNew = 0;while (x != 0) {xNew = xNew * 10 + x % 10;x /= 10;}return (xNew < INT_MIN || xNew > INT_MAX) ? 0 : xNew;
}

6.1.2 大神的代碼

public int reverse(int x)
{int result = 0;while (x != 0){int tail = x % 10;int newResult = result * 10 + tail;if ((newResult - tail) / 10 != result){ return 0; }result = newResult;x = x / 10;}return result;
}

基于我的思路，如果可能溢出，就直接使用更大的容器取存儲數據，然后看看有沒有超過小容器的值，那么，如果沒有更大的容器，又該怎么辦？

沒有大容器，那就用2個小容器，比較新值和舊值。

對于重點公式x1新 = x1舊 * 10 + x % 10，我們知道，在數學公式中，進行等價變形，等式應該相等，也就是等式(x1新 - x%10) / 10 = x1舊成立。

但是對于計算機不同，如果第一個公式計算過程有溢出，就會丟失數據，那么第二個公式就不成立。

這也就是我們判斷的重點：If overflow exists, the new result will not equal previous one.

如果溢出存在，那么，使用新值運算反過來得到的舊值，就不是原來的那個舊值。

代碼如下：

int reverse(int x) {int xNew1 = 0;  // 舊值int xNew2 = 0;	// 新值while (x) {xNew2 = xNew1 * 10 + x % 10;if ((xNew2 - x % 10) / 10 != xNew1)return 0;xNew1 = xNew2;x /= 10;}return xNew2;
}

事實上，在Leetcode編譯器，上面的寫法是錯誤的！

新的收獲：使用經典的測試用例

不得不說……任何的算法，在使用大量測試用例測試之前，都不一定完美，例如上面的算法，如果使用INT_MAX作為測試用例，對于能夠進行溢出檢測的嚴格編譯器來說，會出現報錯（不過C++編譯器一般不檢測……），那么，報錯的原因是什么？

我們看一下xNew2 = xNew1 * 10 + x % 10;，試想一下，我們剛才假定這個過程中，編譯器是允許溢出后直接截斷，但不會報錯，那么現在，我們假定，編譯器不允許溢出的發生，我們又該怎么辦？

【思維修煉】“治未病”思想：在問題發生之前處理掉

對于xNew2 = xNew1 * 10 + x % 10;，我們需要在溢出發生前，就檢測出來，因此有以下程序

int reverse(int x) {int xNew = 0;while(x != 0){if(xNew > INT_MAX/10 || xNew < INT_MIN/10)	return 0;xNew = xNew * 10 + x % 10;x /= 10;}return xNew;}

更嚴格來說，是不是需要把x % 10也“治未病”呢？顯然不需要，因為不存在一個數字，乘10后沒有溢出，但是再+1就溢出了。

思考：為什么不是>=？

因為，對于極限數字214748364（也就是INT_MAX / 10），乘10之后，再加上x % 10是不可能溢出的（可以想象，如果溢出，那x % 10的結果需要 >7，那么，在這個數反轉之前，就已經溢出了，所以不可能）。

經典測試案例 + 嚴格編譯器 = 優秀算法

對于經典測試案例，例如本題，可以有

123
-123
INT_MAX
INT_MIN
1230000

這些提交前的測試案例，足夠描述各種情況了。

6.1.3 小結

1. 1個大容器與2個小容器
2. 算法與數學公式

6.2 第二掌

把大神的代碼完全不看的情況下寫出來。

• 搞定

自己的代碼，多種寫法，不斷優化到極致。

6.3 第三掌

過了24 小時的時間以后，再次重復做題

不同解法的熟練程度 ——> 專項練習

• 新的收獲

6.3.1 整數反轉圖解——安檢排隊模型

如果你從動態的角度去看一下，是不是像一個U型排隊區人員流動的樣子？

想一想你過安檢排隊的情形。

怎么樣，是不是瞬間記住了這個整數反轉模型？

int reverse(int x) {int xNew = 0;while(x){if(xNew > INT_MAX/10 || xNew < INT_MIN/10)	return 0; // 預測xNew = xNew*10 + x%10;x /= 10;}return xNew;}

通過預測提高性能

這是偉大計算機思想之一，應用廣泛，例如指令操作的分支預測，在本題中，溢出的檢測就使用了預測思想。

6.4 第四掌

過了一周之后: 反復回來練習相同的題目

6.5 第五掌

面試前一周恢復性的訓練，所有題目全都刷一遍