9. Palindrome Number

problem description

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Coud you solve it without converting the integer to a string?

algorithm thought

最开始拿到这题，发现，这不是跟第7题很类似吗。直接int2string，使用string来判断就是个很简单的题了。不到一分钟写完之后，发现description里的follow up要求能不能不用string结题。于是又开始想如何不用string，其实在c++中string的结构和vector很像，动态数组vector也很适合存储数字中的所有位。

code

//convert to string
class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0)
            return false;
        string res=to_string(x);
        int left=0,right=res.size()-1;
        while(left<right){
            if(res[left++]!=res[right--])
                return false;
        }
        return true;
    }
};

//without converting to string
class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0)
            return false;
        vector<int> res;
        while(x){
            res.push_back(x%10);
            x/=10;
        }
        int left=0,right=res.size()-1;
        while(left<right){
            if(res[left++]!=res[right--])
                return false;
        }
        return true;
    }
};

//improve menmory performance
class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0)
            return false;
        if(x==0)
            return true;
        vector<int> res(10);
        int left=0,right=-1;
        while(x){
            right++;
            res[right]=x%10;
            x/=10;
        }
        while(left<right){
            if(res[left++]!=res[right--])
                return false;
        }
        return true;
    }
};

algorithm analysis

时间复杂度前两个算法其实都是一样的，都是O(n)。但是字符串的算法更快。我认为是由于每次vector调用push_back后扩容导致。于是想了一下能否提前知道vector的size。防止在运行时分配内存，想到input都是int类型，INT_MAX只有10位，所以定义一个大小为10的数组足够了。改进了一下，发现效果不是很明显，因为大小为10的话，其实内存分配所消耗的资源也不是很多。但是之后很多题目，如果能减少vector或者unordered_map的内存加倍操作，也就是提前resize好大小，很多题目会快很多。