7. Reverse Integer
2024-10-19 11:52:25
1. 问题描述
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
click to show spoilers.
Have you thought about this?
Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
Solution.
class Solution {
public:
int reverse(int x){
}
};
2. 解答思路
2.1. 为什么会有溢出？
整数的存储方式：最高位为符号位
- 16位整数范围：-2^15~2^15-1，即-32768到32767
- 32位整数范围：-2^31~2^31-1，即-2147483648到2147483647
2.2. 如何判断溢出？
- 传入的整数x的范围是：-2147483648 到 2147483648，反转后（暂不考虑溢出问题）：-2147483648 --> -8463847412； 2147483647 -->7463847412。
- 由32位整数的范围知，当且仅当整数x是10位数时，才可能溢出。
- 当x是10位数时，考虑个位，若x%10 > 2，则溢出；若x%10 < 2，则未溢出；若x%10 == 2，则需考虑x的十位。若十位为1，则需考虑百位，以此类推..
3. 代码
class Solution {
public:
int reverse(int x){
bool bIsPositive = x > ;
x = bIsPositive ? x : -x;//也可调用求绝对值的函数abs(x)
if (IsOverFlow(x))//处理溢出
{
return ;
}
int result = ;
while ( != x)
{
result = result * + x%;
x = x/;
}
if (!bIsPositive)
{
result = -result;
}
return result;
}
private:
/*! \fn bool IsOverFlow(int x)
* \brief 判断输入的整数x是否溢出.
* \param[in] x 用户输入的32位整数.
* \return 结果.
* - \b true 溢出.
* - \b false 未溢出.
*/
bool IsOverFlow(int x)
{
if (- == x)//注意，-2147483648的绝对值溢出，-x仍未-2147483648，故需单独判断。
{
return true;
}
int nBitCount = ;//记录当前输入整数的位数
int tx = x;
while ( != tx)
{
nBitCount++;
tx = tx/;
}
if ( == nBitCount)//2147483647 1463847412
{
if (recIsOverFlow(x))
{
return true;
}
}
return false;
}
/*! \fn bool recIsOverFlow(int x, int idx = 1463847412)
* \brief 递归判断输入的整数x是否溢出.
* \param[in] x 用户输入的32位整数.
* \param[in] idx 用于判断溢出的整数.
* \return 结果.
* - \b true 溢出.
* - \b false 未溢出.
*/
bool recIsOverFlow(int x, int idx = )
{
int x_remainder = x % ;
int idx_remainder = idx % ;
if (x_remainder > idx_remainder)
{
return true;
}
else if (x_remainder == idx_remainder && x!= && idx!=)
{
return recIsOverFlow(x/, idx/);
}
return false;
}
};
4. 反思
对于-2147483648，由于其绝对值溢出，-x仍未-2147483648，故需单独判断。
最新文章
- 谈事件冒泡(Bubble)和事件捕捉(capture)
- Groovy 转换JSON和生产JSON
- C++的函数名重载
- leetcode problem (5) Longest Palindromic Substring
- php生成二维码，使用qrcode类库创建
- HTML5入门总结 HTML5API
- Oracle to_char格式化函数 显示毫秒
- java HashSet改用
- Java基础之抽象类
- 编写高质量代码:改善Java程序的151个建议 --[78~92]
- 646. Maximum Length of Pair Chain 最长的链条长度
- K3CLOUD替代方案
- luogu P2680 运输计划
- super-smack压测工具
- Spring-IOC 扩展点 BeanFactoryPostProcessor及其子接口解析
- hdu4333 Revolving Digits(扩展kmp)
- gcd模板（欧几里得与扩展欧几里得、拓展欧几里得求逆元）
- 装饰模式和Java IO
- 【Linux】WinSCP普通用户登录sftp后切换到root权限
- 用python 实现生成双色球小程序