每日一道算法:整数反转

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

示例1:
输入: 123
输出: 321

示例2:
输入: -123
输出: -321

示例3:
输入: 120
输出: 21

说明:

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

解法一:把整数当字符串反转,再转整数

思路分析:

遍历+辅助函数

PHP代码实现:

/**
 * @param Integer $x
 * @return Integer
 */
function reverse($x) {
    if (!is_int($x)) return 0;
    $new_result = '';
    $max = pow(2,31)-1;
    $min = pow(-2,31);
    $zheng = true;
    if($x<0){
        $x = -$x;
        $zheng = false;
    }
    $lens = strlen($x);
    for($i=$lens-1;$i>=0;$i--){
        $new_result .= substr($x,$i,1);
    }
    $new_result = (int)$new_result;
    if(!$zheng){
        $new_result = -$new_result;
    }
    if($new_result > $max || $new_result < $min){
        return 0;
    }
    return $new_result;
}
使用:
$x = 199899;
var_dump(reverse($x));

复杂度分析:

时间复杂度:O(n)
空间复杂度:O(1)

解法二:把整数当字符串反转,再转整数

思路分析:

辅助函数

PHP代码实现:

/**
 * @param Integer $x
 * @return Integer
 */
function reverse($x) {
    if (!is_int($x)) return 0;
    $max = pow(2,31)-1;
    $min = pow(-2,31);
    $zheng = true;
    if($x<0){
        $x = -$x;
        $zheng = false;
    }
    $new_result = (int)strrev($x);
    if(!$zheng){
        $new_result = -$new_result;
    }
    if($new_result > $max || $new_result < $min){
        return 0;
    }
    return $new_result;
}

复杂度分析:

时间复杂度:O(n)
空间复杂度:O(1)

解法三:数学法

思路分析:

 * 通过循环将数字x的每一位拆开,在计算新值时每一步都判断是否溢出。
 * 溢出条件有两个,一个是大于整数最大值MAX_VALUE,另一个是小于整数最小值MIN_VALUE,设当前计算结果为ans,下一位为pop。
 * 1、从ans * 10 + pop > MAX_VALUE这个溢出条件来看
 当出现 ans > MAX_VALUE / 10 且 还有pop需要添加 时,则一定溢出
 当出现 ans == MAX_VALUE / 10 且 pop > 7 时,则一定溢出,7是2^31 - 1的个位数
 * 2、从ans * 10 + pop < MIN_VALUE这个溢出条件来看
 当出现 ans < MIN_VALUE / 10 且 还有pop需要添加 时,则一定溢出
 当出现 ans == MIN_VALUE / 10 且 pop < -8 时,则一定溢出,8是-2^31的个位数

PHP代码实现:

/**
 * @param Integer $x
 * @return Integer
 */
function reverse($x) {
    if (!is_int($x)) return 0;
    $new_result = 0;
    $max = pow(2, 31) - 1;
    $min = pow(-2, 31);
    while ($x != 0) {
        $pop = $x % 10;
        if ($new_result > $max/10 || ($new_result == $max/10 && $pop > 7)) return 0;
        if ($new_result < $min/10 || ($new_result == $min/10 && $pop < -8)) return 0;
        $new_result = $new_result * 10 + $pop;
        $x = ($x - $pop) / 10;
    }
    return $new_result;
}

复杂度分析:

时间复杂度:O(log(n))
n 中大约有 log10(n) 位数字
空间复杂度:O(1)

github

以后每次题解都会上传到这个项目

LeetCode_PHP:https://github.com/zhangdejian/LeetCode_PHP

题目来源

力扣(LeetCode):https://leetcode-cn.com/problems/reverse-i...

本作品采用《CC 协议》,转载必须注明作者和本文链接
阿德
zhangdeTalk
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!