Leetcode Reverse Integer

Leetcode Reverse Integer

每天刷题!

参考:https://leetcode-cn.com/articles/reverse-integer/

一、题目

给定一个 32 位有符号整数,将整数中的数字进行反转。

示例1:

示例2:

示例3:

注意:

假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231,  231 − 1]。根据这个假设,如果反转后的整数溢出,则返回 0。

二、解决方案

(1)我的解决方案

我的做法是把这串数字当成字符串解析。

一看到倒转数字,马上就想到先入后出,马上就想到使用栈。

再看到存在三个特殊情况:

  1. 如果给出的x为负数,那么倒转的结果依然是负数。
  2. 如果以一个/多个0结尾,那么倒转后不为0开头,应该全部清除至不为0为止。
  3. 一个数在反转时非常容易溢出。

进一步思考:

  1. 如果为负数,那么“-”一定在开头出现,需要特殊处理。
  2. 如果使用循环来拼接数字,需要通过某种条件把开头的0跳过。
  3. 整个程序只会有一种预期内的异常,就是溢出。溢出的情况需要返回0,那么完全可以捕获溢出异常,返回0,从而简化溢出判断逻辑(其实就是投机取巧,笑出声)。

大致模型:

  1. 解析int类型为string类型,循环解析字符。如果为负数,那么开头必然为“-”,因为“-”不需要入栈,所以游标可以跳过,默认拼接至结果头位。
  2. 记录一个标识为Flag。如果开头持续为0 && Flag == false,那么0全部不入栈。直到某位数字不为0,那么入栈并且把Flag置为true,跳过过滤0的逻辑。
  3. 使用try-catch捕获关键部位/方法体,捕获错误时返回0。

于是有以下代码:

ReverseInteger.java

运行结果为:

我的解法看起来很有点投机取巧,但是确实能得到正确结果,并且在性能测试中击败了98.63%的同学。

(2)官方解决方案

通过数学方法解析,需要有层层递进的分析能力。

1.方法

弹出和推入数字 && 溢出前进行检查。

2.思路

  1. 我们可以一次构建反转整数的一位数字。
  2. 在这样做的时候,我们可以预先检查向原整数附加另一位数字,查看是否会导致溢出。如果不会溢出,继续下一步。如果溢出,返回0值。

3.算法

  1. 反转整数的方法可以与反转字符串进行类比。
  2. 我们想重复“弹出” xx 的最后一位数字,并将它“推入”到 rev 的后面。最后,rev 将与 xx 相反。
  3. 要在没有辅助堆栈 / 数组的帮助下“弹出”和“推入”数字,我们可以使用数学方法。

但是,这种方法很危险,因为当计算:

时,很容易导致溢出。

幸运的是,事先检查这个语句是否会导致溢出很容易。

为了便于解释,我们假设 rev 是正数。

  1. 如果 temp = rev * 10 + pop 一定会导致溢出,那么做个简单转换,溢出时必有 rev >= INT_MAX / 10。
  2. 反推过来,如果有 rev > INT_MAX / 10 ,那么temp = rev * 10 + pop 一定会导致溢出。
  3. 如果有 rev == INT_MAX / 10 ,那么只要 pop > 7,temp = rev * 10 + pop 就会溢出。
  4. 根据第三点,考虑到负数的情况,如果rev是负数,只要 pop < -8,temp = rev * 10 + pop 就会溢出。

首先这确实是数学分析的方法,刚接触的同学肯定有压力,可以在纸上算算。

得出代码:

ReverseInteger2.java

运行结果为:

三、总结

虽然是简单题,但是方式一考察基本数据结构栈的知识,方式二考虑数学分析推理能力,所以通过率真的不高…

发布者

xie4ever

发表评论

电子邮件地址不会被公开。