中国建设银行江西分行网站首页,番茄网络营销策划方案,易语言网站批量注册怎么做,深圳论坛前言
溢出问题是面试当中输出涉及到数字的一个需要特别注意的地方#xff0c;典型的题目有三个#xff1a;数字反转#xff0c;将字符串转成数字和回文数。
1.整数反转
力扣7题#xff0c;给你一个 32 位的有符号整数 x #xff0c;返回将 x 中的数字部分反转后的结果。…前言
溢出问题是面试当中输出涉及到数字的一个需要特别注意的地方典型的题目有三个数字反转将字符串转成数字和回文数。
1.整数反转
力扣7题给你一个 32 位的有符号整数 x 返回将 x 中的数字部分反转后的结果。如果反转后整数超过 32 位的有符号整数的范围 [ − 2 31 , 2 31 − 1 ] [−2^{31}, 2^{31} − 1] [−231,231−1]就返回 0。假设环境不允许存储 64 位整数有符号或无符号。
分析这个问题处理时需要考虑两点:1.如何反转数字2.反转后的数字是否会溢出。反转比较简单我们可以使用循环取模取余的方法也就是一边左移一边处理末尾数字。以33156为例循环取模然后为了得到末尾数字循环取余即可得到65133最后反转拼接。 按照循环取模只要最后输入的x ! 0即可终止。
对于溢出比如1245221927这个数反转过来就是7291225421已经比最大的32位整数都要大了如果一个整数num MAX_VALUE, 其中MAX_VALUE 214746483647 那么就有如下规律
nums / 10 MAX_VALUE / 10 214748364,也就是如果底数第二位大于4了那么最后一位是什么都已经溢出了 如上图所示
当num / 10 214748364那肯定会溢出当num / 10 214748364需要考虑上图第三四五排数字如果末尾数字 7说明溢出当num / 10 214748364说明没问题
完整实现代码如下
// 循环取模取余
function reverse(x) {let res 0;while (x ! 0) { // 获得末尾数字let tailNum x % 10;// 判断是否超出最大32位整数if (res 214748364 || (res 214748364 tailNum 7)) {return 0;}// 判断是否超出最小32位整数if (res -214748364 || (res -214748364 tailNum -8)) {return 0;}res res * 10 tailNum;// Math.floor() 函数总是返回小于等于一个给定数字的最大整数,对于负数精确度不够x ~~(x / 10); // ~~ 是相当于 parseInt,这里存在一个关于浮点数的精确度问题}return res;
}2.字符串转整数
这道题在我的另外一篇文章已经讲过这里不再重复。算法通关村第十二关——不简单的字符串转换问题
3.回文数
力扣9题给你一个整数 x 如果 x 是一个回文整数返回 true 否则返回 false 。回文数是指正序从左向右和倒序从右向左读都是一样的整数。 例如121 是回文而 123 不是。
分析第一个想法是将数字转换为字符串并检查字符串是否为回文。但是这需要额外空间来创建问题描述中所不允许的字符串。 第二个想法是将数字本身反转然后将反转后的数字与原始数字进行比较如果相同说明是回文。 但如果反转后的数字大于int.MAX就会遇到整数溢出问题。 其实只要改进一下第二个想法就可以避免数字反转可能导致的溢出问题我们可以只反转数字的一半因为如果数字是回文其后半部分反转后应该与原始数字的前半部分相同。 例如输入 142241我们可以将数字 “142241” 的后半部分从 “241” 反转为 “142”并将其与前半部分 “142” 进行比较因为二者相同得知数字 14241 是回文数。
代码如下
function isPalindrome(x) {// 特判 如果x 0或者x % 10 0 x ! 0if (x 0 || (x % 10 0 x ! 0)) {return false;}let reversedNum 0;// 循环取模取余来反转数字,反转一半数字来进行比较如果是回文整数// 则反转的一半应当等于未反转的的那一半while (x reversedNum) {reversedNum reversedNum * 10 x % 10;x parseInt(x / 10);}// 当数字长度为奇数时可以通过 parseInt(reversedNum / 10)去除处于中间的数字// 例如当输入 x 23232 时在循环的末尾可以得到 x 23, reversedNum 232,// 由于处于中间的数字不影响回文它总是与自己相等所以可以简单地将其去除。return x reversedNum || x parseInt(reversedNum / 10);
}
