专栏首页五分钟学算法法解种三的数文回:画动

法解种三的数文回:画动

题目描述

判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

示例 1:

输入: 121
输出: true

示例 2:

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

示例 3:

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

进阶:

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

题目解析

解法一:普通解法

最好理解的一种解法就是先将 整数转为字符串 ,然后将字符串分割为数组,只需要循环数组的一半长度进行判断对应元素是否相等即可。

动画描述

代码实现

///简单粗暴,看看就行
class Solution {
    public boolean isPalindrome(int x) {
        String reversedStr = (new StringBuilder(x + "")).reverse().toString();
        return (x + "").equals(reversedStr);
    }
}

解法二:进阶解法---数学解法

通过取整和取余操作获取整数中对应的数字进行比较。

举个例子:1221 这个数字。

  • 通过计算 1221 / 1000, 得首位1
  • 通过计算 1221 % 10, 可得末位 1
  • 进行比较
  • 再将 22 取出来继续比较

动画描述

代码实现

class Solution {
    public boolean isPalindrome(int x) {
        //边界判断
        if (x < 0) return false;
        int div = 1;
        //
        while (x / div >= 10) div *= 10;
        while (x > 0) {
            int left = x / div;
            int right = x % 10;
            if (left != right) return false;
            x = (x % div) / 10;
            div /= 100;
        }
        return true;
    }
}

解法三:进阶解法---巧妙解法

直观上来看待回文数的话,就感觉像是将数字进行对折后看能否一一对应。

所以这个解法的操作就是 取出后半段数字进行翻转

这里需要注意的一个点就是由于回文数的位数可奇可偶,所以当它的长度是偶数时,它对折过来应该是相等的;当它的长度是奇数时,那么它对折过来后,有一个的长度需要去掉一位数(除以 10 并取整)。

具体做法如下:

  • 每次进行取余操作 ( %10),取出最低的数字:y = x % 10
  • 将最低的数字加到取出数的末尾:revertNum = revertNum * 10 + y
  • 每取一个最低位数字,x 都要自除以 10
  • 判断 x 是不是小于 revertNum ,当它小于的时候,说明数字已经对半或者过半了
  • 最后,判断奇偶数情况:如果是偶数的话,revertNum 和 x 相等;如果是奇数的话,最中间的数字就在revertNum 的最低位上,将它除以 10 以后应该和 x 相等。

动画描述

代码实现

class Solution {
    public boolean isPalindrome(int x) {
        //思考:这里大家可以思考一下,为什么末尾为 0 就可以直接返回 false
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
        return x == revertedNumber || x == revertedNumber / 10;
    }
}

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:程序员小吴

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 10% + 10% = 0.11 ?是 bug 还是 feature ?微软开源的计算器项目告诉你答案!

    近日,关于手机计算器10%+10%=0.11的事情火热,多个品牌的手机未能幸免,基本“阵亡”,同时还包括了windows10的自带标准计算器。你的手机阵亡了吗?

    五分钟学算法
  • 好吧,又是两分钟看完一道投机取巧的算法题

    事实上,你在使用暴力破解法的过程中就能发现规律: 这 9 个数字中只有 2(它的倍数) 与 5 (它的倍数)相乘才有 0 出现。

    五分钟学算法
  • 每天一算:Evaluate Reverse Polish Notation

    我们会在每天早上8点30分准时推送一条LeetCode上的算法题目,并给出该题目的动画解析以及参考答案,每篇文章阅读时长为五分钟左右。

    五分钟学算法
  • 数据分表小结

    本次拆分主要包括订单和优惠券两大块,这两块都是覆盖全集团所有分子公司所有业务线。随着公司的业务飞速发展,不管是存储的要求,还是写入、读取的性都基本上到了警戒水位...

    王清培
  • 每日一刷:回文数

    判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

    乐心湖
  • leetcode-806-Number of Lines To Write String

    chenjx85
  • Python内置函数sorted()从入门到精通

    Python内置函数sorted()可以对列表、元组、字典、集合、字符串、range对象以及其他可迭代对象进行排序,返回排序后的列表,支持使用key参数指定排序...

    Python小屋屋主
  • LeetCode 806. 写字符串需要的行数

    我们要把给定的字符串 S 从左到右写到每一行上,每一行的最大宽度为100个单位,如果我们在写某个字母的时候会使这行超过了100 个单位,那么我们应该把这个字母写...

    Michael阿明
  • 不同时间复杂度的规模上限

    饶文津
  • 卡特兰数扩展

    对于排队买票问题的一些说法.....   假若有M+ N人去买票,n人手持5元,m人手持10元,而售货阿姨没有零钱,问有多少种方法能使大家都买到票。 其中m<=...

    Gxjun

扫码关注云+社区

领取腾讯云代金券