让我们一起啃算法----回文数

三斤和他的朋友们 · · 817 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

回文数(Palindrome-Number)

这是一个比较简单的题目,题干如下:

判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
示例 1:
  输入: 121
  输出: true
示例 2:
  输入: -121
  输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
  输入: 10
  输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
来源:力扣

解题思路

按照题目的定义: 负数一定不是回文数,并且 [0,9] 的数一定是回文数

其次,我们稍微延伸一下题目,如果判断一个字符串是否是回文字符串,我们会怎么做?常规思路就是设置两个指针 ij 分别指向字符串的第一个字符和最后一个字符,然后 指针 i 向后挪指针 j 向前挪,每挪动一次就比较 指针 i 指向的字符是否和指针 j 指向的字符相等。具体流程如下:

如上,那我们是不是可以沿用判断字符串是否是回文字符串的思路来判断数字呢?当然是可以的啦。

所以现在的问题变成了怎么拿到数字的第一位和最后一位?上一篇文章 让我们一起啃算法----整数反转 我们知道了 一个数与10取模可以得到最后一位的值。那第一位的值如何得到呢?可以用如下方式:

假设目标数字是 3245,它是一个四位数,最小的四位数是1000,3245 / 1000 就可以拿到第一位的值即 3 。

拿到了第一位的值和最后的一位的值之后,我们只需要判断是否相等即可。

具体的代码实现

GO语言实现:

func isPalindrome(x int) bool {
    if x < 0 {
        return false
    }
    div := 1
    // 得到相应位数的最小值
    // 例如:3245,那么div的值就是1000
    for x / (div) >=  10 {
        div *= 10
    }
    for x != 0 {
        // 得到第一位的值
        left := x / div
        // 得到最后一位的值
        right := x % 10
        if left != right {
            return false
        }
        // 去掉第一位和最后一位
        // 例如:( 3245 - 3 * 1000 )/ 10 = 24
        x = (x - left * div) / 10

        // 因为去掉了两位,因此div也相应的调整
        div /= 100
    }
    return true
}

总结

每天进步一点点,加油!
算法教程项目,每天更新一题,点个 star 支持一下呀
https://github.com/wx-satellite/learning-algorithm


有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:三斤和他的朋友们

查看原文:让我们一起啃算法----回文数

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

817 次点击  ∙  1 赞  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传