007. 整数反转 | Leetcode题解

苏南

发布于 2020-12-16 14:49:56

41900

代码可运行

文章被收录于专栏：漫画前端漫画前端

运行总次数：0

代码可运行

点击上方“蓝色字体”，选择“设为星标”

每天复习一道面试题，轻松拿大厂Offer~

题目描述:

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

示例1:

输入: 123
输出: 321

示例 2:

输入: -123
输出: -321

示例 3:

输入: 120
输出: 21

注意:

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

难度：

难度：简单
支持语言：JavaScript、Java、Python

思路 1:

使用字符串在反转并不是最好的选择，因为还需要处理负号和0的情况，用数字运算方式反转比较适合。
每次找到当前数的最后一位，然后作为反转数字的第一位，例如123：

123 --> 0*10  + 3
12  --> 3*10  + 2
1   --> 32*10 + 1

再注意保存开始的正负状态和结果的限制[−2^31, 2^31 − 1]。

思路 2:

本题如果不考虑溢出问题，是非常简单的。解决溢出问题有两个思路，第一个思路是通过字符串转换加try catch的方式来解决，第二个思路就是通过数学计算来解决。
由于字符串转换的效率较低且使用较多库函数，所以解题方案不考虑该方法，而是通过数学计算来解决。
通过循环将数字x的每一位拆开，在计算新值时每一步都判断是否溢出。
溢出条件有两个，一个是大于整数最大值MAX_VALUE，另一个是小于整数最小值MIN_VALUE，设当前计算结果为ans，下一位为pop。
从ans * 10 + pop > MAX_VALUE这个溢出条件来看
- 当出现 ans > MAX_VALUE / 10 且 还有pop需要添加 时，则一定溢出
- 当出现 ans == MAX_VALUE / 10 且 pop > 7 时，则一定溢出，7是2^31 - 1的个位数
从ans * 10 + pop < MIN_VALUE这个溢出条件来看
- 当出现 ans < MIN_VALUE / 10 且 还有pop需要添加 时，则一定溢出
- 当出现 ans == MIN_VALUE / 10 且 pop < -8 时，则一定溢出，8是-2^31的个位数
作者：guanpengchn

思路 3:

result * 10 + x % 10 取出末位 x % 10（负数结果还是负数，无需关心正负），拼接到 result 中。
x / 10 去除末位，| 0 强制转换为32位有符号整数。
通过 | 0 取整，无论正负，只移除小数点部分（正数向下取整，负数向上取整）。
result | 0 超过32位的整数转换结果不等于自身，可用作溢出判断。
运算过程:

x	result
123	0
12	3
1	32
0	321

代码

JavaScript 实现

/**
 * @来源：Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
  let symbol=x<0 ? -1 : 1
  x=Math.abs(x)
  let res=0
  while(x>0){
    let t=x%10
    res=res*10+t
    x=Math.floor(x/10)
  }
  res*=symbol
  if(res<-Math.pow(2,31) || res>Math.pow(2,31)-1)return 0
  return res
};

/**
 * @作者：zoffer
 * @链接：https://leetcode-cn.com/problems/reverse-integer/solution/wei-yun-suan-ji-jian-jie-fa-by-ijzqardmbd/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {number} x
 * @return {number}
 */

var reverse = function(x) {
    let result = 0;
    while(x !== 0) {
        result = result * 10 + x % 10;
        x = (x / 10) | 0;
    }
    return (result | 0) === result ? result : 0;
};

Java 实现

/**
 * @作者：jianrry
 * @链接：https://leetcode-cn.com/problems/reverse-integer/solution/zheng-shu-fan-zhuan-by-jianrry/
 */
class Solution {
    public int reverse(int x) {

        int res = 0;
        while (x != 0) {
            int t = x % 10;
            int newRes = res * 10 + t;
            //如果数字溢出，直接返回0
            if ((newRes - t) / 10 != res)
                return 0;
            res = newRes;
            x = x / 10;
        }
        return res;

    }
}

/**
 * @作者：javaniuniu
 * @链接：链接：https://leetcode-cn.com/problems/reverse-integer/solution/suan-shu-javapython-by-javaniuniu/
 */

public int reverse(int x) {
      String a = Integer.toString(x);
      int b = 1;
      if(a.charAt(0) == '-') {
          a = a.substring(1);
          b = -1;
      }
      char[] chars = a.toCharArray();
      char[] chars1 = new char[chars.length];
      for (int i = chars.length - 1; i >= 0; i--) {
          chars1[chars.length - 1 - i] = chars[i];
      }
      Long aLong = Long.valueOf(new String(chars1));
      if(aLong > Integer.MAX_VALUE || aLong < Integer.MIN_VALUE) {
          return 0;
      }
      return (int) (aLong * b);

  }

Python 实现

# @作者：stray_camel
# @链接：https://leetcode-cn.com/problems/reverse-integer/solution/pythondan-chu-he-tui-ru-shu-zi-yi-chu-qian-jin-xin/

 def reverse_force(self, x: int) -> int:
        if -10 < x < 10:
            return x
        str_x = str(x)
        if str_x[0] != "-":
            str_x = str_x[::-1]
            x = int(str_x)
        else:
            str_x = str_x[:0:-1]
            x = int(str_x)
            x = -x
        return x if -2147483648 < x < 2147483647 else 0

# @作者：xi-ri-dan-zeng
# @链接：https://leetcode-cn.com/problems/reverse-integer/solution/zheng-shu-fan-zhuan-by-xi-ri-dan-zeng/

class Solution:
    def reverse(self, x: int) -> int:
        #将整数的绝对值转换成字符串
        s=str(abs(x))
        #翻转字符串
        s=s[::-1]
        #如果输入整数是负数，增加负号
        if x <0:
            s ='-' + s
        #转换为整数
        result = int(s)
        #判断是否溢出
        if result>=-2**31 and result<=2**31-1:
            return result
        else:
            return 0

其他

原题leetcode链接：https://leetcode-cn.com/problems/reverse-integer/
合作方：JavaScript中文网 – 全球极客挚爱的技术成长平台
说明：leetcode 题解 | 每日一题? 所有题目并非全部为本人解答，部分为在复习学习中整理提取其他解题作者的优秀笔记，便于大家学习共同进步，如有侵权，请联系删除。

- 完 -

关注公众号「IT平头哥联盟」，一起进步，一起成长！

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-11-17，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法