0009._Palindrome_Number.md

9. Palindrome Number

难度:Medium

刷题内容

原题连接

• https://leetcode.com/problems/palindrome-number

内容描述

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?

解题方案

思路1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

这题的难度不大，由于是数字，判断回文只需要求出倒过来的数字，判断两者是否相等，不过要注意负数一定不是回文

class Solution {
public:
    bool isPalindrome(int x) {
        long long ret = 0;
        int num = x;
        if(x < 0)
            return false;
        while(num)
        {
            ret = 10 * ret + num % 10;
            num /= 10;
        }
        if(ret == x)
            return true;
        return false; 
        }
};

思路2 - 时间复杂度: O(N)- 空间复杂度: O(1)******

计算出数字的长度，用双指针法，一个指针指向头，另一个指向尾，相等就前一个指针加一，后一个指针减一，若不相等则返回 false

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0)
            return false;
        
        int cnt = 0;
        long fac = 1;
        int div = INT_MAX;
        while (div != 0) {
            cnt++;
            fac *= 10;
            div = x/fac;
        }
        
        fac /= 10;
        for (int i=0; i<cnt/2; i++) {
            int last = x%10;
            int first = x/fac;
            if (first != last)
                return false;
            x = x % fac;
            x = (x-last)/10;
            fac /= 100;
        }
        
        return true;
    }
};

这两种方法的时间复杂度都取决于输入的数字的长度