【Leetcode】【Easy】Palindrome Number
Determine whether an integer is a palindrome. Do this without extra space.
判断一个整数是不是回文整数（例12321）。不能使用多余的空间。
Some hints:
Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.
You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
There is a more generic way of solving this problem.
一些提示：
复数不是回文；如果你希望将整数转为字符串，注意不要使用多余的空间；
如果你希望反转整数，请注意“反转”可能导致溢出。你如何解决这个问题？
思路1：
可将此数按位从低到高依次取出，再从高到低反向排列，得到的新数字和原数字比较，一致则是回文数，否则不是。
至于提示中提到反转整数可能会出现int越界的问题，在此题中不会出现。因为如果一个int是回文整数，那么它和自身的反转相等，因此反转后不会越界。如果一个int不是回文数，反转后出现越界的情况，也不会影响结果的判定。
class Solution {
public:
bool isPalindrome(int x) {
int res = ;
int tmp_x = x;
if (x<)
return false;
while (tmp_x != ) {
res = res * + tmp_x % ;
tmp_x = tmp_x / ;
}
if (res == x) {
return true;
} else {
return false;
}
}
};
思路2：
可以将整数中，需要进行比较的首尾数字，不断取出并比较。
class Solution {
public:
bool isPalindrome(int x) {
if (x < )
return false;
int sig = ;
while (x / sig >= ) {
sig *= ;
}
while (x!=) {
if (x / sig == x % ) {
x = x % sig / ;
sig /= ;
} else {
return false;
}
}
return true;
}
};
上面代码在函数中对x进行了修改，为了避免x被修改：
class Solution {
public:
bool isPalindrome(int x) {
if (x < )
return false;
int high = , low = ;
while (x / high >= ) {
high *= ;
}
while (high > low) {
if (x / high % == x / low % ) {
high /= ;
low *= ;
} else {
return false;
}
}
return true;
}
};
附录：
算法中“不使用多余空间”的含义
最新文章
- ouath原理
- C#读取Excel文件：通过OleDb连接，把excel文件作为数据源来读取
- Word Excel 操作总结
- 【mysql】利用Navicat for MySQL的使用
- 解决Win10服务主机本地系统网络受限
- [转]Windows8下设置VS默认启动方式为管理员启动
- mysql的ERROR:1042
- 如何解决Oracle 11g EM网站报“此网站的安全证书存在问题”
- 【Hibernate 9】悲观锁和乐观锁
- 8.2.1.3 Range Optimization
- iperf网络测试工具
- [转]Net Framework引路蜂地图开发示例
- git版本控制系统更新
- 解决Navicat 出错:1130-host . is not allowed to connect to this MySql server,MySQL
- python的配置
- UIKit-UIBezierPath
- 1657 Distance on Chessboard（简单计算题）
- 为PartialView传递一个参数
- MongoDB高级操作(2)
- SPOJ 8222 NSUBSTR - Substrings