【原】LeetCode題集-7 - 整數(shù)反轉(zhuǎn)

IT規(guī)劃師 2024-12-14

展開全文

題目：給你一個(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)）。**假設(shè)環(huán)境不允許存儲(chǔ) 64 位整數(shù)（有符號(hào)或無符號(hào)）。**

01、long類型字符串轉(zhuǎn)換法

雖然題目要求不允許使用64位整數(shù)，但是我們還是先使用最簡單最直觀的最符合思維邏輯的方式實(shí)現(xiàn)，然后以此打開思維尋找出更好的方法。

看到此題我第一反應(yīng)就是直接把整數(shù)x轉(zhuǎn)為字符串，然后直接調(diào)用字符串方法反轉(zhuǎn)字符串，最后把反轉(zhuǎn)后的字符串轉(zhuǎn)換為long類型，同時(shí)比較是否再有效范圍內(nèi)即可。

當(dāng)然這是大致解題思路，其中還有許多細(xì)節(jié)需要處理。

首先需要處理負(fù)號(hào)問題，如果是負(fù)數(shù)我們需要取其絕對(duì)值，然后再反轉(zhuǎn)絕對(duì)值，而在取絕對(duì)值時(shí)需要注意int的最小值int.MinValue為-2147483648，而int.MaxValue最大值為2147483647，因此我們不能直接對(duì)int整數(shù)x直接取絕對(duì)值，而需要先把x轉(zhuǎn)為long類型整數(shù)，不然會(huì)報(bào)錯(cuò)。

然后把絕對(duì)值反轉(zhuǎn)成字符數(shù)組，同時(shí)判斷正負(fù)號(hào)，如果是負(fù)數(shù)則需要在字符數(shù)組前加上負(fù)號(hào)’-’。

最后直接使用long.TryParse方法對(duì)字符數(shù)組進(jìn)行轉(zhuǎn)換，同時(shí)判斷其有效范圍，并輸出結(jié)果，具體代碼如下：

//字符串long
public static int ReverseLongString(int x)
{
    //是否為負(fù)數(shù)
    var isNegative = x < 0;
    //取絕對(duì)值,必須要先轉(zhuǎn)為long類型
    //否則int.MinValue -2147483648會(huì)報(bào)錯(cuò)
    var abs = Math.Abs((long)x);
    //把值轉(zhuǎn)為字符串并反轉(zhuǎn)，得到字符集合
    var reversedChars = abs.ToString().Reverse();
    if (isNegative)
    {
        //如果是負(fù)數(shù)則在字節(jié)數(shù)組前加入負(fù)號(hào)'-'
        reversedChars = reversedChars.Prepend('-');
    }
 
    //轉(zhuǎn)換為long類型，并且是有效的int值，則返回結(jié)果
    if (long.TryParse(reversedChars.ToArray(), out long result) && result >= int.MinValue && result <= int.MaxValue)
    {
        return (int)result;
    }
 
    return 0;
}

02、int類型字符串轉(zhuǎn)換法

既然題目中要求我們不能使用64位整數(shù)long類型，那么我們是否可以直接int類型進(jìn)行轉(zhuǎn)換呢？

根據(jù)上一個(gè)解法，同樣的思路，我們先把int整數(shù)x轉(zhuǎn)為字符串，然后直接使用int.TryParse進(jìn)行轉(zhuǎn)換即可。這樣可以利用轉(zhuǎn)換失敗過濾掉所有溢出的值。

具體實(shí)現(xiàn)代碼如下：

//字符串int
public static int ReverseIntString(int x)
{
    //把值轉(zhuǎn)為字符串，并去掉負(fù)號(hào)'-'，最后反轉(zhuǎn)，得到字符集合
    var reversed = x.ToString().TrimStart('-').Reverse();
 
    //轉(zhuǎn)換為int，成功則返回
    if (int.TryParse(reversed.ToArray(), out int result))
    {
        //根據(jù)原始符號(hào)，返回結(jié)果
        return x < 0 ? -result : result;
    }
 
    return 0;
}

03、數(shù)學(xué)方法

上面兩個(gè)方法本質(zhì)還是通過字符串轉(zhuǎn)換，就效率來說是比較低的，因此我們可以通過數(shù)學(xué)計(jì)算的方式來實(shí)現(xiàn)其轉(zhuǎn)換。

如上圖，我們以把12345反轉(zhuǎn)為例，詳解講解反轉(zhuǎn)過程。

（1）通過12345%10，獲取到尾數(shù)字5，而尾數(shù)字又將作為新數(shù)值的首數(shù)字，新數(shù)值5；

（2）通過1234%10，獲取到尾數(shù)字4，新數(shù)值為5*10+4=54；

（3）通過123%10，獲取到尾數(shù)字3，新數(shù)值為54*10+3=543；

（4）通過12%10，獲取到尾數(shù)字2，新數(shù)值為543*10+2=5432；

（5）通過1%10，獲取到尾數(shù)字1，新數(shù)值為5432*10+1=54321；

其中還有一個(gè)重點(diǎn)是關(guān)于溢出的判斷，前兩個(gè)方法本質(zhì)都是通過轉(zhuǎn)換方法觸發(fā)異常來攔截溢出，而在此方法中我們可以在實(shí)時(shí)計(jì)算的過程中直接判斷出是否溢出。

因?yàn)?2位有符號(hào)整數(shù)x的取值范圍是-2147483648<=x<=2147483647，如果要保證反轉(zhuǎn)過來不溢出，則在處理到第九位的時(shí)候整個(gè)值應(yīng)該在（-214748364，214748364）之間，不然結(jié)果肯定會(huì)溢出，而有效的int值首位數(shù)字最大為2，即使反轉(zhuǎn)過來也不可能大于7或小于-8，因此只需要判斷第九位數(shù)字是否合法即可完成溢出判斷。

具體實(shí)現(xiàn)代碼如下：

//數(shù)學(xué)方法
public static int ReverseMath(int x)
{
    var result = 0;
    while (x != 0)
    {
        //判斷溢出,因?yàn)檩斎氲氖?2位的有符號(hào)整數(shù) x
        //即輸入的 -2147483648<=x<=2147483647
        //所以翻轉(zhuǎn)后的最后一位是1或2并不會(huì)導(dǎo)致溢出
        //因此只需判斷九位數(shù) > int.MaxValue / 10 或者 < int.MinValue / 10
        if (result < int.MinValue / 10 || result > int.MaxValue / 10)
        {
            return 0;
        }
 
        //獲取當(dāng)前末尾的數(shù)字
        var digit = x % 10;
        //去掉末尾數(shù)字
        x /= 10;
        //反轉(zhuǎn)并累積結(jié)果
        result = result * 10 + digit;
    }
 
    return result;
}