LeetCode | 2. Reverse Integer 整数反转

关注
发布于: 2020 年 06 月 03 日
Reverse Integer 是 LeetCode 算法题库中的第七道题，难度为 Easy，题目地址为：https://leetcode.com/problems/reverse-integer/
1. 问题描述给定一个32位的整数，反转其数字。
示例：
Input 123
Output 321
﻿
Input -123
Output -321
﻿
2. 解题思路该题有两种解决思路：转换为字符串 + 借用堆栈的 Pop/Push
转换为字符串：这个思路是我一开始看到该问题，就自然想到的一个方法。将整数转化为字符串，再通过字符串的反转来求解。
借用堆栈的 Pop/Push：该方法是看到官方提供的 Solution 才知道的，即类似于采用堆栈的先进先出的概念，对整数本身进行处理，对原始数值依次进行弹出（Pop）操作，在反转的数值中将之前弹出的数值进行推入（Push）操作。
﻿
我觉得 Pop/Push 的方法2应该是要第一时间就想到的，因为是个算法题嘛，可见我自己在算法这方面的「无知」。
﻿
在处理整型数值时，需要注意到溢出的问题。
3. 知识点我依然是采用了两种编程语言来实现该算法，下面分别来记录我的一些收获。
Python通过 Python 来实现该算法时，有三个新知识点：
Python 的列表及其切片
Python 的取模操作
Python 的 int 最大值
列表及其切片Python 中的列表就相当于数组，可以通过下标来取得列表中的单个值。虽然下标hi从0开始向上增长的，但也可以通过负整数作为下标。比如，-1是指列表中的最后一个下标，-2是指列表中倒数第二个下标。
list[1]
通过下标组合成「切片」，可以取得子列表。在切片中，冒号左边的整数（第一个）是切片的开始处下标，冒号右边的整数（第二个）是切片的结束处下标。冒号两边的整数是可以省略的，左边的整数省略则相当于使用下标0，左边的整数省略则相当于使用了列表的原始长度。
list[0:2]
list[:]
在切片语法中，也支持第三个可选的参数，来表示步幅 Step。当采用负值时，则可以按相反的顺序对同一列表进行复制。
L = range(10)
L[::2] //range(0, 10, 2)
L[::-1] //range(9, -1, -1)
﻿
Python 的取模操作一般求余操作都是通过 % 符号来完成，在 Python 中，如果被除数是负数时，需要小心，因为 Python 中的 % 是取模运算。
求余和取模运算的为：
求整数商：c = a / b
取模或求余：r = a - c * b
求余操作和取模操作的不同点在于第一步的处理上，
求余操作时，计算 c 的值是向 0 方向舍入
取模操作时，计算 c 的值是向负无穷方向舍入
﻿
示例：
﻿
以 -7 % 4 = 1 为例
首先，计算-7 / 4 = 1.75，在取模操作时，需向负无穷方向舍入，因此 c = -2；
由此得到最终的结果为：r = -7 - (-2 * 4) = 1。
﻿
以 7 % -4 = -1 为例
首先，计算 7 / -4 = -1.75，在取模操作时，依旧是向负无穷方向舍入，因此 c = -2；
由此得到最终的结果为：r = 7 - (-2 * -4) = -1。
由上也可以看出，取模运算得到的结果的符号是与除数相同的。
﻿
参考：python负数求余不正确？——取模 VS 取余
Python 的 int 最大值整型的最大值一般是指 Int32 的范围，[-2^31, 2^31-1]。在 Python 中，是去掉了整型最大值的概念，只是提供了一个表示大于任何我们实际工作中能够表示的最大的整型数值。在 Python 2 中是内置的 sys.maxint ，在Python 3 则改为 sys.maxsize。
﻿
也可以通过inf 来表示一个比其他数都要大的值：float('inf')
﻿
参考：https://stackoverflow.com/questions/7604966/maximum-and-minimum-values-for-ints
C#通过 C# 来实现该算法时，主要是了解了 C# 的一些内置函数，包括：
Math.Pow(Double, Double) 方法，是用来求乘幂数的，比如Math.Pow(2, 3)是求23
Int32.MaxValue 和Int32.MinValue 字段，分别是用来求 C# 中的 Int32 位的最大值和最小值的内置字段
Int32.ToString 方法，是将整型转换为字符串。
Int32.Parse(input)，是将输入的字符串转换为整型数值。
String.ToCharArray 方法，是将字符串转换为字符数组。
Array.Reverse 方法，是将数组内的元素进行反转。
由于以上方法都是在代码中的直接使用，便不做过多的解释，详情查看分别链接到的官方文档或者下面的代码片段。
4. 代码代码实现中，也是参考了 LeetCode 中的示例、讨论，以及各种文档。
﻿
Python 实现整型转字符串的实现：
class Solution:
    def reverse(self, x: int) -> int:
        maxint = 2**31 - 1
        minint = -2**31
        flag = 1
        if x < 0:
            flag = -1
        x = x * flag
        x_str = str(x)
        reverse = int(x_str[::-1]) * flag
        if (reverse > maxint or reverse < minint):
            return 0
        return reverse
﻿
Pop/Push 方法实现：
class Solution:
    def reverse(self, x: int) -> int:
        reverse = 0
        maxint = 2**31 - 1
        minint = -2**31
        if x > 0:
            while (x != 0):
                pop = x % 10
                x = int(x/10)
                if (reverse > maxint/10 or (reverse == maxint/10 and pop > 7)):
                    return 0
                reverse = reverse * 10 + pop
        elif x < 0:
            while(x != 0):
                pop = -(-x % 10)
                x = int(x/10)
                if (reverse < minint/10 or (reverse == minint/10 and pop < -8)):
                    return 0
                reverse = reverse * 10 + pop
        return reverse
﻿
不同实现方法的效率对比：
﻿
C# 实现﻿
Pop/Push 的实现：
public class Solution {
    public int Reverse(int x) {
        int reverse = 0;
        int maxint = Int32.MaxValue;
        int minint = Int32.MinValue;
        while (x != 0)
        {
            int pop = x % 10;
            x = x/10;
            if (reverse > maxint/10 || (reverse == maxint/10 && pop > 7))
            {
                return 0;
            }
            if (reverse < minint/10 || (reverse == minint/10 && pop < -8))
            {
                return 0;
            }
            reverse = reverse * 10 + pop;
        }
        return reverse;
    }
}
﻿
字符串的方法，该实现没能处理好 reverse 的溢出问题，需要后续再花时间来处理：
public class Solution {
    public int Reverse(int x) {
        int reverse = 0;
        int maxint = Int32.MaxValue;
        int minint = Int32.MinValue;
        int flag = 1;
        if (x < 0)
        {
            flag = -1;
        }
        x = x * flag;
        string x_str = x.ToString();
        char[] x_str_Array = x_str.ToCharArray();
        Array.Reverse(x_str_Array);
        string reverse_string = new string(x_str_Array);
        double value = Double.Parse(reverse_string);
        if (value > maxint || value < minint)
        {
            return 0;
        }
        else 
        {
            reverse = Int32.Parse(reverse_string) * flag;
            return reverse;
        }
    }
}
﻿
方法的效率：
﻿
发布于: 2020 年 06 月 03 日阅读数: 57
原文链接:【http://xie.infoq.cn/article/5a389ac614f1452f00a877f04】。文章转载请联系作者。
Puran

关注
GIS从业者，正在往开发的路上小跑。 2018.03.29 加入
从业4年的GIS开发小白，work@esri。
发布
暂无评论
创作场景

LeetCode | 2. Reverse Integer 整数反转

1. 问题描述

2. 解题思路

3. 知识点

Python

列表及其切片

Python 的取模操作

Python 的 int 最大值

C#

4. 代码

Python 实现

C# 实现

Puran

评论
