7. Reverse Integer

1.問題

2.想法

• 提問

• function header, parameter

• test input: integer overflow

• 說明想法

  • 直覺想法: 將每個位數放進vector後, 再加回答案

  • 改進做法: 每次疊代就將原還得值處以10, 但要記得處理overflow

• 測試

• 計算複雜度: O(n)?

3.程式碼

• 直覺想法

class Solution {
public:
    int reverse(int x) {
        int index = 1, sum = 0;
        vector<int> res;
        while (int(abs(x) / pow(10, index - 1)) > 0) {
            res.push_back(int(abs(x) % int(pow(10, index)) / pow(10, index - 1)));
            index++;
        }
        for (int i = 0; i < res.size(); i++) {
            sum += res[i] * pow(10, index - 2);
            index--;
        }
        if (0 > sum) {
                return 0;
            }
        return x < 0 ? -sum : sum;
    }
};

• 改進做法

class Solution {
public:
    int reverse(int x) {
        int index = 1, sum = 0;
        int t = abs(x);
        while (t > 0) {
            if(sum > INT_MAX/10 || sum<INT_MIN/10){
                return 0;
            }
            int res = t % 10;
            sum = sum * 10 + res;
            t = t /10;
        }
        
        return x < 0 ? -sum : sum;
    }
};

4.Performance