反转数字（7）

题目

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

示例

输入: 123 输出: 321

输入: -123 输出: -321

输入: 120 输出: 21 s

注意

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

算法

暴力法

原数字 => 字符串 => 判断是否需要取出符号 => 数组 => 反转数组 => 是否需要在头部添加负号 => 拼接字符串 => 转换数字 => 判断是否溢出 => 返回结果

export const reverse = (x) => {
	const s = x.toString();
	const arr = s.split("");
	let minusSign = "";
	if (arr[0] === "-") {
		minusSign = arr.shift();
	}
	arr.reverse();
	if (minusSign === "-") {
		arr.unshift(minusSign);
	}
	const n = Number.parseInt(arr.join(""));
	if (n >= -(2 ** 31) && n <= 2 ** 31 - 1) {
		return n;
	}
	return 0;
};

模拟push和pop

类似反转字符串的方法，将原数字最后一位取出，放入新数字的最后一位

因为数字没有类似数组的pop和push方法，所以我们利用数学运算模拟出这两个方法的效果

• 类似pop取出原数字的最后一位：x%10; ~~(x/10)
• 类似push将取出数字加入新数字最后一位：res*10+pop

在放入新数字之前，判断结果是否溢出，溢出则直接返回0

export const reverse_2 = (x) => {
	const INT_MAX = 2 ** 31 - 1;
	const INT_MIN = -(2 ** 31);
	let res = 0;
	while (x !== 0) {
		const temp = x % 10;
		x = ~~(x / 10);
		if (res > (INT_MAX - temp) / 10) return 0;
		if (res < (INT_MIN - temp) / 10) return 0;
		res = res * 10 + temp;
	}
	return res;
};

JS 位运算

类似第二种方法：

x|0进行位运算可以返回一个带符号的32位整数

如果res|0!==res则说明res溢出了

export const reverse = (x) => {
	let res = 0;
	while (x !== 0) {
		res = res * 10 + (x % 10);
		x = (x / 10) | 0;
	}
	if ((res | 0) === res) {
		return res;
	}
	return 0;
};

优化算法二

其实是不是回文数，无需全部反转后判断，而是只反转数字的一半就可以判断

如何判断已经反转了一般数字并跳出循环是关键：当被反转的原数字小于等于反转后数字时，说明已经反转了一半了，所以循环条件是被反转数>翻转数

最后是回文数的条件是：翻转数和被反转数相等（数字长度是偶数）、或者翻转数相等和被反转数去掉一位后相等（数字长度是奇数）

排除临界条件：

• 负数
• 除0以外末尾为0的数字

export const isPalindrome = (x) => {
	if (x < 0 || (x !== 0 && x % 10 === 0)) return false;
	let palindrome = 0;
	while (palindrome < x) {
		palindrome = palindrome * 10 + (x % 10);
		x = ~~(x / 10);
	}
	return x === palindrome || x === ~~(palindrome / 10);
};