每日一道算法:整数反转
题目:给出一个 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):https://leetcode-cn.com/problems/reverse-i...
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: