# 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

```cpp
//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好大小，很多题目会快很多。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kongchengzhuge.gitbook.io/leetcode/9.-palindrome-number.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.