【算法攻坚】整数翻转的小技巧

简介: 【算法攻坚】整数翻转的小技巧

题目


给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。


如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ,就返回 0。


假设环境不允许存储 64 位整数(有符号或无符号)。


示例 1:


输入:x = 123 输出:321


示例 2:


输入:x = -123 输出:-321


示例 3:


输入:x = 120 输出:21


示例 4:


输入:x = 0 输出:0


思路


看到这道题目的时候,首先想到的是转换成字符串,然后翻转,所以迅速写完第一版


public int reverse(int x) {
    StringBuffer s = new StringBuffer(String.valueOf(x));
    if(x> 0){
        return Integer.valueOf(s.reverse().toString());
    }else if(x <0){
        return - Integer.valueOf(s.reverse().toString().substring(0,s.length()-1));
    }else{
        return 0;
    }
}


执行出错信息:


java.lang.NumberFormatException: For input string: "9646324351"  at line 68, java.base/java.lang.NumberFormatException.forInputString  at line 658, java.base/java.lang.Integer.parseInt  at line 989, java.base/java.lang.Integer.valueOf  at line 6, Solution.reverse  at line 54, __DriverSolution__.__helper__  at line 84, __Driver__.main
最后执行的输入:
1534236469


这个报错是因为当输入是1534236469,翻转后是9646324351

但是这样再用Integer.valurOf()就会超过int类型的最大值2147483647

如果能够看出问题所在,这时按照题目要求,超出范围后直接返回0

我们就可以利用异常来控制返回,当有异常时直接返回0


public static int reverse(int x) {
    try {
        StringBuffer s = new StringBuffer(String.valueOf(x));
        if (x > 0) {
            return Integer.valueOf(s.reverse().toString());
        } else if (x < 0) {
            return -Integer.valueOf(s.reverse().toString().substring(0, s.length() - 1));
        } else {
            return 0;
        }
    } catch (Exception e) {
        return 0;
    }
}


执行用时:2 ms, 在所有 Java 提交中击败了22.09%的用户

内存消耗:35.7 MB, 在所有 Java 提交中击败了22.48%的用户


从结果看,效率不算太高,可以考虑下其他方法,字符串操作相对比较耗时


解法二


由于字符串操作比较耗时,所以选择数学公式方式实现

依次取出当前数字的最后一位数,累加。


关键在于如何判断整数溢出:


可以每次操作后的数字用临时变量存储,对该变量反向运算,

若与操作前的结果不等,则发生溢出,直接返回0


public int reverse(int x) {
    int result = 0;
    while(x != 0){
        //当前操作位数字
        int cuur = x%10;
        //result*10相当于低位每次右移以为就乘以10,比如123, 3*10, 3*10*10*10+2*10,3*10*10+2*10*10 +1*10
        int temp =  cuur + result*10;
        //上一行运算的逆运算,判断是否超出int范围
        if((temp - cuur)/10 != result){
            return 0;
        }
        x = x/10;
        result = temp;
    }
    return result;
}


执行用时:1 ms, 在所有 Java 提交中击败了97.47%的用户

内存消耗:35.6 MB, 在所有 Java 提交中击败了30.81%的用户


解法三


int类型的数字翻转也不会超过long的范围,所以可以利用long类型和int类型转换后

判断是否相等来验证是否超出int范围


public int reverse(int x) {
    long result = 0;
    while(x != 0){
        int cuur = x%10;
        result = result *10 + cuur;
        x = x/10;
    }
    //如果不超出范围,强转类型后数值不变化
    int res = (int)result;
    return res == result? res: 0;
}

执行用时:1 ms, 在所有 Java 提交中击败了97.47%的用户

内存消耗:35.2 MB, 在所有 Java 提交中击败了94.37%的用户


相关文章
|
1月前
|
自然语言处理 Rust 算法
【算法】13. 罗马数字转整数(多语言实现)
罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。 | 字符 | 数值 | |--|--| | I | 1 | | V | 5 | | X | 10 | | L | 50 | | C | 100 | | D | 500 | | M | 1000 | 例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。 通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1
【算法】13. 罗马数字转整数(多语言实现)
|
1月前
|
算法 Java
[Java·算法·简单] LeetCode 13. 罗马数字转整数 详细解读
[Java·算法·简单] LeetCode 13. 罗马数字转整数 详细解读
28 0
|
7天前
|
存储 机器学习/深度学习 算法
python 五种算法转置后翻转、层次旋转、递归分块、一次性旋转、环状替换 实现旋转图像【力扣题48】
python 五种算法转置后翻转、层次旋转、递归分块、一次性旋转、环状替换 实现旋转图像【力扣题48】
|
7天前
|
SQL 算法 数据挖掘
深入探索力扣第12题:整数转罗马数字的算法之旅
深入探索力扣第12题:整数转罗马数字的算法之旅
|
10天前
|
算法
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
8 0
|
11天前
|
算法 Java C语言
【经典算法】LeetCode25:K 个一组翻转链表(Java/C/Python3,Hard)
【经典算法】LeetCode25:K 个一组翻转链表(Java/C/Python3,Hard)
5 1
|
20天前
|
算法
简记二分算法模板与代码案例:整数二分和浮点数二分
本文介绍了两种算法模板,分别是整数二分和浮点数二分。
19 0
|
1月前
|
存储 算法 容器
算法刷题小技巧【持续补充~】
算法刷题小技巧【持续补充~】
12 2
|
1月前
|
算法 C语言
【C语言】求最小新整数(贪心算法)
【C语言】求最小新整数(贪心算法)
17 1
|
1月前
|
算法
算法题 — 整数转二进制,查找其中1的数量
算法题 — 整数转二进制,查找其中1的数量
16 0