LeetCode刷题笔记(九）回文数

古城微笑少年丶 2022-05-25 09:59 155阅读 0赞

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

示例 1:

输入: 121
    输出: true

示例 2:

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

示例 3:

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

进阶:

你能不将整数转为字符串来解决这个问题吗？

解法1：

class Solution {
        public boolean isPalindrome(int x) {
            if(x<0){
                return false;     //如果是负数就直接返回
            }else if(x<10){
                return true;      //0-9直接返回true
            }
            int temp = x;         
            int left = 1;     //最大的位数  
            while((x=x/10) != 0){     
                left *= 10;       //计算出x的最大位，如x=23456,left=10000
            }
            while(temp>0){
                int hi = temp/left;       //左边的数
                int low = temp%10;        //右边的数
                if(hi != low){            //左右不等就不是回文
                    return false;
                }
                temp -= hi*left;       //去除最高位
                temp /= 10;            //去除最低位
                left /= 100;           //这里是把left去除两位，以为左右各去除了一位
            }
            
            return true;
        }
    }

这是解法是先计算出x的位数，如果是n为，则left = 10^n;然后用x/left得出最左边的数字，x%10得出最右边的数字。判断两个数是否相等，得出不相等就返回false,如果当判断到最中间还是相等，就返回true;

时间复杂度：O（n）;

空间复杂度：O（n）;

**解法2：**

class Solution {
        public boolean isPalindrome(int x) {
            if(x<0){
                return false;    //如果负数直接返回false;
            }
            int temp = x;        
            int base = 0;       //反转后的数字
            int cur = 0;       //当前的数字
            while(x != 0){
                cur = x % 10;
                base = base * 10 + cur;
                x /= 10;
            }
            
            return base == temp;
        }
    }

这种解法和第一种的不同，这里是直接把数字翻转，然后判断和传入的值是否相等；

时间复杂度：O（n）;

空间复杂度：O  (1);