Golang算法之整数反转

发表于 | 更新于 | 分类于 | 浏览数
| 字数统计 485

整数反转，简单难度，leetcode地址：https://leetcode-cn.com/problems/reverse-integer

1.描述

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围，就返回 0。

示例 1：

1
2
3
4
5
6
7
8
输入：x = 123
输出：321

输入：x = -123
输出：-321

输入：x = 120
输出：21

2.题解

方法一: 字符串反转

作为我这种算法菜鸟，第一眼就想出来了，把整数转成字符串，然后反转字符串，再转成整数。

虽然这方法没问题，但是总感觉有点low…而且有点不太符合题目要求。

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func reverse(x int) int {
    var isNg = false
    if x < 0 {
        x = -x
        isNg = true
    }
    n, _ := strconv.Atoi(reverseStr(strconv.Itoa(x)))
    if n > 2147483647  || n < -214748368  {
        return 0
    }
    if isNg {
        return -n
    }
    return n
}

func reverseStr(s string) string {
    r := []byte(s)
    for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
        r[i], r[j] = r[j], r[i]
    }
    return string(r)
}

方法二: 取模法

假设一个数字是12345，反转过来就是54321，分开看就是: 50000 + 4000 + 300 + 20 + 1

1
2
3
4
5
1、将12345 % 10 得到5，之后将12345 / 10
2、将1234 % 10 得到4，再将1234 / 10
3、将123 % 10 得到3，再将123 / 10
4、将12 % 10 得到2，再将12 / 10
5、将1 % 10 得到1，再将1 / 10

参考代码:

1
2
3
4
5
6
7
8
9
10
11
func reverse(x int) int {
    var res = 0
    for x != 0 {
        if res > 214748364 || res < -214748364 {
            return 0
        }
        res = res*10 + x%10
        x = x / 10
    }
    return res
}

上面这段代码很关键的地方是解决溢出问题，就是题目要求当整数超过int32范围的时候返回0。
有人可能会好奇，为什么是214748364，我记得是2的32次方是2147483648啊？很简单，因为我们每次都是*10进了一位，所以当然要在其超过之前判断。