原题地址:整数反转
给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123 输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231, 231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。
直观解法
拿到题后我想到的第一个直观的解法就是将数字转换为字符串,调用字符串的反转函数后再转换回数字。注意处理好溢出的情况就可以:
/**
* @param {number} x
* @return {number}
*/
const reverse1 = function(x) {
// 区分正数和负数
if (x < 0) {
x = -parseInt(`${-x}`.split('').reverse().join(''))
} else {
x = parseInt(`${x}`.split('').reverse().join(''))
}
// 判断是否溢出
if (x > Math.pow(2, 31) - 1 || x < -Math.pow(2, 31)) {
return 0;
}
return x;
};
测试
let start = new Date();
const test = reverse1;
console.log(test(123)); // 321
console.log(test(-123)); // -321
console.log(test(120)); // 21
console.log(test(1534236469)); // 0
console.log(test(1563847412)); // 0
console.log(new Date().getTime() - start.getTime()); // 8
时间复杂度: 时间复杂度为O(n) 空间复杂度: 需要一个中间字符串,空间复杂度为O(n)
只用数字
上面的解法利用了多个系统函数,并经过了多次转换,效率不高,也不是题目所需要的。
要想完成这种反转,我们只要从后往前依次取出每一位并放到新数字的最后就可以了。注意要处理好溢出的判断:
/**
* @param {number} x
* @return {number}
*/
const reverse2 = function(x) {
let reversed = 0;
while (x !== 0) {
reversed = reversed * 10 + x % 10;
// 注意是向0取整,所以x大于0时是向下取整,小于0则是向上取整
x = x > 0 ? Math.floor( x / 10) : Math.ceil(x / 10);
}
// 因为js中整数的范围远大于题目给定的范围,所以x在js中是不可能溢出的,只需要判断是否在题目给定的范围内即可
if (reversed > Math.pow(2, 31) - 1 || reversed < -Math.pow(2, 31)) {
return 0;
}
return reversed;
};
测试:
let start = new Date();
const test = reverse1;
console.log(test(123)); // 321
console.log(test(-123)); // -321
console.log(test(120)); // 21
console.log(test(1534236469)); // 0
console.log(test(1563847412)); // 0
console.log(new Date().getTime() - start.getTime()); // 5
时间复杂度: 时间复杂度为O(n)
空间复杂度: 需要一个整数来存结果,空间复杂度为O(n)
本文由 李海平 创作,采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Jul 27,2019