算法研究-正数反转

这个系列是笔者练习LeetCode上的算法题的记录&分享

题目

正数反转（Reverse Integer）
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例 1:
输入: 123
输出: 321

示例 2:
输入: -123
输出: -321

示例 3:
输入: 120
输出: 21

注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为
[−2^31,2^31−1]
请根据这个假设，如果反转后整数溢出那么就返回 0

题解

需要注意的地方

1. 符号需要保存，负数反转之后也应该为负数
2. 首数字为0的时候
3. 数值溢出的问题处理

思路一

将int转为string，然后在string中进行循环操作
代码如下：

public int Reverse(int x) {
    if (x == 0) { return x; }
    int sign = 1, reverse = 0;
    if (x < 0) {
        sign = -1;
        x *= -1;
    }
    string num = x.ToString();
    for (int i = 0, d = 1; i < num.Length; i++ ,d*=10)
    {
        reverse += d * int.Parse(num[i].ToString());
    }
    reverse *= sign;
    return reverse;
}

其中尚未进行溢出问题处理。遇到 [-2147483648, 2147483647] 以外的数值会使得int整型溢出。

思路二

此题主要的问题就是对溢出问题的处理方法。
基于思路一的方法，每一次增值计算的时候加入判断
如果 即将溢出
返回 0
此处即将溢出需要做出数学判断
溢出结果 = 当前值 * 10 + 最后一个数
INT_MAX = reverse * 10 + pop
可以得到当 reverse >= INT_MAX/10 的时候，数值即将溢出
细化可以得到
reverse > INT_MAX/10 的时候，必定溢出
reverse == INT_MAX/10 时需要判断 pop 大于 INT_MAX 最高位数
代码如下：

public int Reverse(int x) {
    if (x == 0) { return x; }
    int sign = 1, reverse = 0;
    if (x < 0) {
        sign = -1;
        x *= -1;
    }
    string num = x.ToString();
    for (int i = 0, d = 1; i < num.Length; i++ ,d*=10)
    {
        if (reverse > int.MaxValue / 10 || (reverse == int.MaxValue / 10 && int.Parse(num[i].ToString()) > 2)) return 0;
        reverse += d * int.Parse(num[i].ToString());
    }
    reverse *= sign;
    return reverse;
}

此时，对于范围[-2147483648, 2147483647]左右两边的绝对值不一致，不便于计算。此处需要修改循环逻辑

思路三

通过while循环，引入push/pop的概念

//pop operation:
pop = x % 10;
x /= 10;

//push operation:
temp = rev * 10 + pop;
rev = temp;

代码如下：

public int Reverse(int x) {
    int reverse = 0;        
    while (x!= 0)
    {
        int pop = x % 10;
        if (reverse > int.MaxValue / 10 || (reverse == int.MaxValue / 10 && pop > 7))
            return 0;
        if (reverse < int.MinValue / 10 || (reverse == int.MinValue / 10 && pop < -8))
            return 0;
        reverse = reverse * 10 + pop;
        x /= 10;            
    }
    return reverse;
}