【LeetCode-数学】回文数

题目描述

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例：

输入: 121
输出: true

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

题目链接： https://leetcode-cn.com/problems/palindrome-number/

思路1

将数字转为字符串，然后使用两个指针left和right，left从前往后遍历，right从后往前遍历。判断left和right两个位置的字符串是否相等，如果有不等的，返回false. 代码如下：

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

• 时间复杂度：O(n)
  n为字符串长度。
• 空间复杂度：O(n)

思路2

如果不能转为字符串，则可以数字拆分到数组里面，然后使用同样的两个指针来判断。代码如下：

class Solution {
public:
    bool isPalindrome(int x) {
        vector<char> v;

        bool isNegative = false;
        if(x<0) isNegative = true;
        while(x!=0){
            v.push_back(char(x%10));
            x /= 10;
        }
        if(isNegative) v.push_back('-');
        
        int left=0, right=v.size()-1;
        while(left<right){
            if(v[left]!=v[right]){
                return false;
            }
            left++;;
            right--;
        }
        return true;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)