本文共 2786 字,大约阅读时间需要 9 分钟。
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
Example 1:
Input: 121Output: true
Example 2:
Input: -121Output: falseExplanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3:
Input: 10Output: falseExplanation: Reads 01 from right to left. Therefore it is not a palindrome.
Follow up:
Coud you solve it without converting the integer to a string?
判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
示例 1:
输入: 121输出: true
示例 2:
输入: -121输出: false解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10输出: false解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶:
你能不将整数转为字符串来解决这个问题吗?
=========================================================
如果用字符串就很好解决了,字符串s和s.reverse()比较是否相等就出结果了。
=========================================================
第一种方法:网友的思路,翻转一半能够避免21亿零9这样的数字溢出问题,很巧妙,但是9000000012这个数字溢出后也和原来的数字不等,int型的溢出在这里并不会造成影响
class Solution { public boolean isPalindrome(int x) { // 负号肯定导致不对称,或者除了0外能被10整除的也不对称 // 因为最后一定为0,翻转后最高位为0,那么就少了一位 if (x < 0 || (x != 0 && x % 10 == 0)) return false; int sum = 0; // 翻转一半,避免溢出,虽然这里溢出也不会对结果造成影响 while (x > sum) { sum = sum * 10 + x % 10; x /= 10; } // 如果是偶数位,翻转一半直接判断是否相等 // 如果是奇数位,除去中间位翻转判断相等 return x == sum || sum / 10 == x; }}
第二种,翻转全部,几次测试均比上面的方法快。因为虽然是多做了几次循环和计算,可是第一种方法和非零的数字相比也是需要时间的,比如1234544321会判断12345和12344,长度相等,寄存器就会一位一位的判断数字是否相等,当比较的数据量很多组的时候就不一定很优了。
这里和零比较,一次就能得出谁大,在while的循环判断条件会节省时间。
class Solution { public boolean isPalindrome(int x) { if (x < 0 || (x != 0 && x % 10 == 0)) return false; int sum = 0, temp = x; while (temp > 0) { sum = sum * 10 + temp % 10; temp /= 10; } return x == sum; }}
Debug code in playground:
class Solution { public boolean isPalindrome(int x) { if (x < 0 || (x != 0 && x % 10 == 0)) return false; int sum = 0, temp = x; while (temp > 0) { sum = sum * 10 + temp % 10; temp /= 10; } return x == sum; }}public class MainClass { public static String booleanToString(boolean input) { return input ? "True" : "False"; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String line; while ((line = in.readLine()) != null) { int x = Integer.parseInt(line); boolean ret = new Solution().isPalindrome(x); String out = booleanToString(ret); System.out.print(out); } }}
=========================Talk is cheap, show me the code=======================
转载地址:https://liuchenyang0515.blog.csdn.net/article/details/82918374 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!