LeetCode || Palindrome Number
LeetCode number Palindrome
2023-09-11 14:20:56 时间
Determine whether an integer is a palindrome. Do this without extra space.
推断一个int值是否为回文数。
本题有几点须要注意:
(1)不能用额外存储空间,也就是说仅仅能用常数空间解决;诸如将int转换为string再去比較字符是不可行的;
(2)推断回文数的方法有两个:从中间開始向两头推断、从两头向中间推断。后者更简单一些。每次取出低位和高位数字进行比較。取低位直接模10即可,那怎样取高位呢?取高位也用模的方法,仅仅只是我们要首先知道X有多少位。如1001有四位,那么我们取高位的1时就模1000。我们设这个高位模为div。首先得计算出div才干開始推断回文,计算div的方法就是用x去除以10、100、1000.。
。。直到得0,即:
div =10;
while(x / div != 0) div *= 10;
然后最后div /= 10;即可了。
我一開始就是这么做的,可是不知道大家有没有发现,假设x是几十亿的数,while循环结束时得到的会是大一个数量级的上百亿的数(所以最后还要除以10),这样div就溢出了,所以这么求div是不正确的;应该这么求:
div =1;
while( x / div >10) div *= 10;
这样就不会溢出了。除非 x 溢出(这是不可能的);
(3)推断回文过程中能够取出收尾的数字,再比較,也能够直接比較,我用的直接比較;
代码例如以下:
class Solution { public: bool isPalindrome(int x) { if(x<0) return false; int div=1; while(x/div >= 10) div*=10; while(x>0 && (x%10 == x/div)){ x %= div; div /= 100; x /= 10; } if(x > 0) return false; return true; } };
注意假设 x = 100001。那么经过一轮循环,x就变为1了。小于div 了。由于中间的0被取模消去了,此时也不影响推断过程,由于 x /div 依旧等于0.
參考链接:http://leetcode.com/2012/01/palindrome-number.html
相关文章
- Leetcode: Additive Number
- Leetcode: Single Number III
- Leetcode: Delete Node in a Linked List
- Leetcode: Number of Islands
- Leetcode: Letter Combinations of a Phone Number
- leetcode 题解 || Letter Combinations of a Phone Number 问题
- 【leetcode】14. longest common prefix
- LeetCode高频题956:数组arr,能否把数组取出若干个数,使得取出数之和,与剩下数的和相同
- LeetCode高频题10:正则表达式匹配
- [LeetCode] Largest Number
- 【LeetCode】174. Dungeon Game
- 【LeetCode】9. Palindrome Number (2 solutions)
- 【LeetCode】26. Remove Duplicates from Sorted Array
- LeetCode——Palindrome Partitioning
- [LeetCode] 1297. Maximum Number of Occurrences of a Substring 子串的最大出现次数
- [LeetCode] 863. All Nodes Distance K in Binary Tree 二叉树距离为K的所有结点
- [LeetCode] Quad Tree Intersection 四叉树相交
- [LeetCode] 814. Binary Tree Pruning 二叉树修剪
- [LeetCode] Path Sum IV 二叉树的路径和之四
- [LeetCode] 347. Top K Frequent Elements 前K个高频元素
- [LeetCode] 246. Strobogrammatic Number 对称数
- [LeetCode] Missing Number 丢失的数字
- [LeetCode] 263. Ugly Number 丑陋数
- LeetCode合并二叉树
- LeetCode //C++ Palindrome Number
- Leetcode——16. 3Sum Closest