題目描述:給定一個 32 位元有號整數 x,返回其數字反轉後的結果。若反轉後的數字超出 32 位元有號整數的範圍 [-2³¹, 2³¹ - 1],則返回 0。
解題思路:
核心操作是「逐位彈出再推入」:每次從 x 的末位取出一個數字(使用模運算 x % 10),再將其附加到反轉結果的末位(rev = rev * 10 + digit),直到 x 歸零為止。
關鍵難點:溢位偵測。在執行 rev * 10 + digit 之前,必須先確認此操作不會導致整數溢位。由於 C++ 的整數溢位是未定義行為,我們必須在乘法發生之前進行檢查:
rev > INT_MAX / 10,則 rev * 10 必然溢位 → 回傳 0rev < INT_MIN / 10,則 rev * 10 必然下溢 → 回傳 0負數的處理:在 C++ 中,% 運算符對負數的結果保留原始符號(例如 -123 % 10 = -3)。這讓我們可以用完全相同的邏輯處理正負數,無需特別分開處理。
時間複雜度:O(log n) — 迴圈執行次數等於 x 的十進位位數,即 log₁₀(n)。
空間複雜度:O(1) — 只使用了常數個額外變數(rev、digit),與輸入大小無關。
1. Initialize rev = 0 2. While x != 0: a. Extract last digit: digit = x % 10 b. Remove last digit from x: x = x / 10 c. Check overflow: if rev > INT_MAX/10 or rev < INT_MIN/10, return 0 d. Append digit to rev: rev = rev * 10 + digit 3. Return rev
字串轉換法 O(log n):將整數轉為字串,反轉字串後再轉回整數。優點是程式碼直觀易讀;缺點是需要額外的字串空間(O(log n) 空間),且需要手動處理負號與前導零,以及溢位檢查。整體來說不如數學法簡潔。
遞迴法 O(log n):使用遞迴來逐一提取數字,透過函式呼叫堆疊隱式地存儲中間狀態。思路與迭代法相同,但每次遞迴呼叫提取一位數字並傳遞累積的反轉值。缺點是遞迴深度與位數相同,有額外的函式呼叫開銷,且溢位檢查邏輯相同。實務上迭代法更為推薦。
long long)來暫存中間結果,解法會如何簡化?這樣做有什麼取捨?INT_MAX = 2147483647(末位為 7)與 INT_MIN = -2147483648(末位為 -8)。若在不同平台上整數大小不同,如何讓溢位偵測更具通用性?