回文数的golang实现

2018/11/15 22:13
阅读数 50
判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数
输入: 121
输出: true
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

首先分析题意,只要正序读与反序读时一样的,那就是回文数,那么负数就可以排除掉。

首先我们能想到的就是把整数转成字符串,然后比较字符串的第一位与最后一位、第二位与倒数第二位。。。以此类推,只要有不一样的就返回false

func isPalindrome(x int) bool {
    if x < 0 {
        return false
    }

    s := strconv.Itoa(x)//把整数转成字符串

    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        if s[i] != s[j] {
            return false
        }
    }

    return true
}

当然我们也可以不转成字符串来比较,那就有点麻烦,我们要借助一些容器,比如slice,首先我们要把整数每一位都拿出来:

var is []int
    var i float64 = 1

    for x != 0 {
        temp := x % int(math.Pow(10, i)) / int(math.Pow(10, i-1))//这里取余数的时候要注意去到20、100类似的数据,所以要再进行一次取模
        x -= temp * int(math.Pow(10, i-1))
        i++
        is = append(is, temp)
    }

拿到保存着每一位数字的slice之后的比较就跟字符串的比较一样了:

for o, p := 0, len(is)-1; o < p; o, p = o+1, p-1 {
        if is[o] != is[p] {
            return false
        }
    }
    return true

整体不用转成字符串的代码:

func isPalindrome(x int) bool {
    if x < 0 {
        return false
    }
    var is []int
    var i float64 = 1

    for x != 0 {
        temp := x % int(math.Pow(10, i)) / int(math.Pow(10, i-1))
        x -= temp * int(math.Pow(10, i-1))
        i++
        is = append(is, temp)
    }
    for o, p := 0, len(is)-1; o < p; o, p = o+1, p-1 {
        if is[o] != is[p] {
            return false
        }
    }
    return true
}

我们再来比较一下两种方法:

  • 首先转字符串的代码量较少(手动狗头)
  • 其次时间复杂度:
    • 转字符串:O(N/2)
    • 不转字符串:O(N+N/2)
  • 空间复杂度:
    • 转字符串:O(N)
    • 不转字符串:O(2N)
比较下来,还是转字符串的好

还有一种方法从LeetCode上看到:

func isPalindrome3(x int) bool {
    // 特殊情况:
    // 当 x < 0 时,x 不是回文数。
    // 同样地,如果数字的最后一位是 0,为了使该数字为回文,
    // 则其第一位数字也应该是 0
    // 只有 0 满足这一属性
    if x < 0 || (x%10 == 0 && x != 0) {
        return false
    }
    revertedNumber := 0
    for x > revertedNumber {
        revertedNumber = revertedNumber*10 + x%10
        x /= 10
    }

    // 当数字长度为奇数时,我们可以通过 revertedNumber/10 去除处于中位的数字。
    // 例如,当输入为 12321 时,在 while 循环的末尾我们可以得到 x = 12,revertedNumber = 123,
    // 由于处于中位的数字不影响回文(它总是与自己相等),所以我们可以简单地将其去除。
    return x == revertedNumber || x == revertedNumber/10
}

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部