今天的題單：

• Missing Number

• Palindrome Number

268. Missing Number

思路: 先用公式算出預期所有數字總合，然後依序扣除 vector 裡所有數字，結果就是 missing number。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int len = nums.size() + 1;
        int sum = len * (0 + len-1) / 2;

        for (int num : nums) {
            sum -= num;
        }
        return sum;
    }
};

9. Palindrome Number

思路: 把數字轉成字串比較

class Solution {
public:
    bool isPalindrome(int x) {
        string s = "";
        
        if (x < 0) return false;

        while (x != 0){
            char new_bit = '0' + x % 10;
            s = new_bit + s;
            x = x / 10;
        }

        int front = 0;
        int end = s.length()-1;
        while (front <= end) {
            if (s[front] != s[end])
                return false;
            front++;
            end--;
        }
        return true;
    }
};

Follow up: Could you solve it without converting the integer to a string?

先找出數字的位數有多少，一樣依照回文的比較方式，從頭尾的位數一步一步往中間的位數比較，只是這次是一邊比較一邊計算。

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        
        // find the nearest power 10 to x
        int power = 1;
        while (x > power) {
            if ((x / power) < 10) break;
            power = power * 10;
        }
        
        int reverse = x;
        while (x != 0 && power > 0) {
            if ((reverse / power) != (x % 10)) {
                return false;
            }
            x = x / 10;
            reverse -= reverse / power * power;
            power = power / 10;
        }
        return true;
    }
};