回文数

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

前因

一是做笔记，记忆是会忘的，以便以后回来复习，加深印象。二是记录自己思想的变化过程吧，可能回头看的时候，会发现自己多么的低级。三是更文激励自己刷下去，提升自己。不进步就是退步。

题目

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

分析

初步思考

从后往前遍历一半元素的字符串和前一半的字符串对比。如果一样则是回文数，如果不一样则不是回文数。

 public static boolean isPalindrome(int x) {
        String xToString = String.valueOf(x);
        StringBuffer stringBuffer = new StringBuffer();
        if (xToString.length() % 2 == 0) {
            for (int i = 0; i < xToString.length() / 2; i++) {
                stringBuffer.append(xToString.substring(xToString.length() - 1 - i, xToString.length() - i));
            }
            xToString = xToString.substring(0,xToString.length()/2);
        } else {
            for (int i = 0; i < (xToString.length() - 1) / 2; i++) {
                stringBuffer.append(xToString.substring(xToString.length() - 1 - i, xToString.length() - i));
            }
            xToString = xToString.substring(0,(xToString.length()-1)/2);
        }
​
        if (xToString.equals(stringBuffer.toString())) {
            return true;
        }
        return false;
    }

继续思考

看似没什么问题，但是 题目有一句话，让我一愣。进阶：你能不将整数转为字符串来解决这个问题吗？ 果然我想到的就是最低级的做法，人家早就料到了。

那么怎么用数字来解决这个问题呢？用数字的话，那么怎么能得到两段数字呢？

无论是拆分数字还是提取数字，少不了遍历，这样的话最方便的还是上边的转换成数字，肯定是行不通的。

既然是数字，那么肯定是可以运算的，那么怎么运算能得到两段数字呢？

我们知道整数对十取余正好可以得到最后一个数字。整数除十就是前边的数字。

比如我们计算12321是不是回文数，只需要

• 12321%10=1；12321/10=1232
• 1232%10=2；1232/10=123；
• 123/10=12

只需要拿着剩下的12和1*10+2进行比较即可。

答案

public static boolean isPalindrome(int x) {
        if (x < 0 || x % 10 == 0) {
            return false;
        }
        int length = 0;
        while (x > length) {
            length = length * 10 + x % 10;
            x /= 10;
        }
        if (length == x || x / 10 == length) {
            return true;
        }
        return false;
    }

复杂度

• 时间复杂度：O(logn)。每次迭代除以10。
• 空间复杂度：O(1)。我们只需要常数length存放尾数部分的值。

总结

每次最开始想到的好像都是最低级的解法，然后再这个基础上继续思考，才能想出点好的解法。这还都是刷的简单的算法，天天进步吧。兄弟们，加入算法大军，一块进步吧。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！