如何優(yōu)雅地反轉(zhuǎn)有符號(hào)整數(shù)

題目描述

整數(shù)反轉(zhuǎn)

給你一個(gè) 32 位的有符號(hào)整數(shù) x ，返回將 x 中的數(shù)字部分反轉(zhuǎn)后的結(jié)果。

如果反轉(zhuǎn)后整數(shù)超過 32 位的有符號(hào)整數(shù)的范圍 [?231,  231 ? 1] ，就返回 0。

假設(shè)環(huán)境不允許存儲(chǔ) 64 位整數(shù)（有符號(hào)或無符號(hào)）。

示例:

輸入：x = 123
輸出：321
示例 2：

輸入：x = -123
輸出：-321
示例 3：

輸入：x = 120
輸出：21
示例 4：

輸入：x = 0
輸出：0

題目分析

這題之所以是簡(jiǎn)單題，是因?yàn)榇_實(shí)有簡(jiǎn)單解法，大部分都知道。

常規(guī)解法

此題看起來非常簡(jiǎn)單，就是一個(gè)字符串反轉(zhuǎn)問題。一串?dāng)?shù)字在js中可以轉(zhuǎn)化為字符串，然后調(diào)用反轉(zhuǎn)api就可以了，就像這樣：

var s = 123;
s= s.toString() // '123'
s= s.split('').reverse().join('') // '321'
s= parseInt(s) // 321

這種寫法問題不大，不過此題還要包括有符號(hào)整數(shù)，即負(fù)數(shù)的情況，這種情況下，得先求絕對(duì)值，完了后再變成負(fù)的。因?yàn)橐粋€(gè)負(fù)整數(shù)經(jīng)過.toString()后，負(fù)號(hào)也變字符串了，所以負(fù)整數(shù)就得這樣處理：

var s= -123;
s = Math.abs(s);
s= s.toString() // '123'
s= s.split('').reverse().join('') // '321'
s= parseInt(s) // 321
s= -s

最后總結(jié)下來就是這樣寫：

var reverse = function(x) {
    var res = 0;f=false;
    if(x<0){
        x=Math.abs(x);
        f = true
    }
    res= x.toString()
    res= res.split('').reverse().join('')
    res= parseInt(res)
    if(f)res = -res;
    if (res < Math.pow(-2, 31) || res > Math.pow(2, 31) - 1) {
        return 0;
    }
    return res;
};

需要注意是題目中提到此有符號(hào)整數(shù)是有范圍的，所以在后面要加上相關(guān)判斷。

高級(jí)解法

下面來介紹一種高級(jí)解法，所謂的高級(jí)解法也不過是用到了一點(diǎn)數(shù)學(xué)知識(shí)而已。這個(gè)解法的關(guān)鍵思路就是每次循環(huán)時(shí)把原始數(shù)字的末位數(shù)取出來并保存，然后在下一次遍歷時(shí)將保存的值乘以10，再加上當(dāng)前取出的末位數(shù)。這樣循環(huán)下去，直到原始數(shù)字被拆解完。

用代碼表達(dá)起來就是這樣：

let rev = 0;
    while (x !== 0) {
        const rmder = x % 10; //取最末位數(shù)字(帶符號(hào))
        x = ~~(x / 10); //兩次按位取反，可以去除小數(shù)部分
        rev = rev * 10 + rmder;
        if (rev < Math.pow(-2, 31) || rev > Math.pow(2, 31) - 1) {
            return 0;
        }
    }
    return rev;

關(guān)鍵的就是這兩行代碼 "const rmder = x % 10;  x = ~ ~(x / 10);"第一句就是為了取出末位數(shù)字，第二句就是為了得到原始數(shù)字在失去了末位數(shù)字之后的值。

最終的結(jié)果rev = rev * 10 + rmder；也比較好理解,每取出一個(gè)余數(shù)，反轉(zhuǎn)過來就要在下次循環(huán)時(shí)逐次乘以10倒推晉升到高分位。比如，原來是123，第一次遍歷后得到3，再遍歷就是32，最后就是321了，3逐漸從個(gè)位增長到十分位最后再百分位；

整個(gè)過程對(duì)有符號(hào)整數(shù)即負(fù)數(shù)也是適用的。

最后的最后就是要注意下數(shù)值范圍就可以了。

復(fù)雜度分析

就說下高級(jí)解法的

時(shí)間復(fù)雜度就是O(log|x|),即原始十進(jìn)制數(shù)字的位數(shù)
空間復(fù)雜度是O(1)，常量階的變量

題目來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/reverse-integer

參考：

1. https://leetcode-cn.com/problems/reverse-integer/solution/zheng-shu-fan-zhuan-by-leetcode-solution-bccn/