算法：整数反转。

旧城等待， 2023-02-25 03:43 21阅读 0赞

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

# 示例 #

>     输入: 123
>     输出: 321

# 示例 #

>     输入: -123
>     输出: -321

# 示例 #

>     输入: 120
>     输出: 21

## 注意 ##

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

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

## 思路 ##

我们可以一次构建反转整数的一位数字。在这样做的时候，我们可以预先检查向原整数附加另一位数字是否会导致溢出。

## 算法 ##

反转整数的方法可以与反转字符串进行类比。

我们想重复“弹出” x 的最后一位数字，并将它“推入”到 rev 的后面。最后，rev 将与 x 相反。

要在没有辅助堆栈 / 数组的帮助下 “弹出” 和 “推入” 数字，我们可以使用数学方法。

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

但是，这种方法很危险，因为当 temp=rev⋅10+pop 时会导致溢出。

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

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

*  如果 temp=rev⋅10+pop 导致溢出，那么一定有 rev≥ INTMAX/10。

*  如果 rev> INTMAX/10，那么 temp=rev⋅10+pop 一定会溢出。

*  如果 rev== INTMAX/10，那么只要 pop>7，temp=rev⋅10+pop 就会溢出。  
    当 rev 为负时可以应用类似的逻辑。

class Solution {
        public int reverse(int x) {
            int rev = 0;
            while (x != 0) {
                int pop = x % 10;
                x /= 10;
                if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
                if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
                rev = rev * 10 + pop;
            }
            return rev;
        }
    }

## 复杂度分析 ##

*  时间复杂度：O(log(x))，x 中大约有 log10(x) 位数字。
 *  空间复杂度：O(1)。

发表评论取消回复

表情：

评论列表（有 0 条评论，21人围观）

还没有评论，来说两句吧...

相关阅读

相关算法面试题:整数反转

leetcode 题目：给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转 public static int reverse(int x)

港控/mmm°/ 2023年07月13日 15:25/ 0 赞/ 19 阅读

相关算法题解：整数反转（go）

题目给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。示例 1: 输入: 123 输出: 321 示例 2: 输入: -123

超、凢脫俗/ 2023年07月12日 14:54/ 0 赞/ 25 阅读

相关【整数反转】算法优化笔记

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。示例 1: 输入: 123 输出: 321

矫情吗；*/ 2023年06月29日 05:58/ 0 赞/ 27 阅读

相关算法题2||反转整数

题目给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。注意: 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 \[−2

叁歲伎倆/ 2023年02月27日 13:33/ 0 赞/ 6 阅读

相关算法：整数反转。

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。示例 > 输入: 123 > 输出: 321 示例 > 输入:

旧城等待，/ 2023年02月25日 03:43/ 0 赞/ 22 阅读

相关整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。注意：假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 \[−231, 231

分手后的思念是犯贱/ 2023年01月09日 01:26/ 0 赞/ 140 阅读

相关算法题：整数反转

整数反转题目描述：代码执行时间题目描述：给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。示例 1: 输

清疚/ 2022年12月28日 14:29/ 0 赞/ 158 阅读

相关整数反转

整数反转 1、参考资料 https://leetcode-cn.com/problems/reverse-integer/ 2、题目要求 > 题目描述给

亦凉/ 2022年12月03日 13:13/ 0 赞/ 166 阅读

相关【算法】【s】反转整数

给定一个 32 位有符号整数，将整数中的数字进行反转。示例 1: 输入: 123 输出: 321 示例 2: 输入: -123 输出: -321 示例

￡神魔★判官ぃ/ 2022年05月14日 22:07/ 0 赞/ 145 阅读

相关整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。示例 1: 输入: 123 输出: 321 示例 2: 输入: -123 输出:

ゝ一纸荒年。/ 2021年10月15日 03:39/ 0 赞/ 312 阅读