LeetCode 回文数（巧解）

LeetCode 回文数

@author:Jingdai
@date:2020.09.23

题目描述（9题）

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。如121、123321。

思路

判断回文数非常简单，就和字符串判断回文一样，一个双指针就可以解决。但是需要额外多创建一个字符串，这里不用这种方法，用一种比较巧妙的方法解决这个问题。

首先想到可以将整个整数翻转，如果翻转得到的数字和原来的数字一样，则代表是回文数，否则不是。有些细心的童靴可能会想到有整数溢出问题，但是其实不用考虑，如果翻转得到数会溢出，那他肯定不是回文数，因为如果一个可以溢出的数是回文数，那么他自己一定是溢出的数，但它又是一个int，这样就矛盾了，所以翻转溢出的数肯定不是回文数。代码见片段1。

其实还有更加巧妙的方法，我们可以取出整数的前一半和后一半，将后一半翻转，如果后一半翻转后和前一半相同，则代表是回文数，否则不是。那我们怎么知道取到了一半了呢，其实只要翻转的数比原始的数大或者相等就代表到了一半了，看下图就懂了。

如果长度为偶数，则翻转后的数和前一半相等，代表是回文数，如果长度是奇数，则翻转后的数/10和前一半相等，代表是回文数。代码见片段2。

代码

• 片段1

  public static boolean isPalindrome(int x) {
      if (x == 0) {
      	return true;
      }
      if (x < 0 || x % 10 == 0) {
      	return false;
      }
      int preX = x;
      int reverse = 0;
      while (x != 0) {
      	reverse = reverse * 10 + x % 10;
      	x /= 10;
      }
      return reverse == preX;
  }
  

• 片段2

  public static boolean isPalindrome(int x) {
  
  	if (x == 0) {
  		return true;
  	}
  	if (x < 0 || x % 10 == 0) {
  		return false;
  	}
  
  	// reverse the seceond half of x(post)
  	int reverse = 0;
  	while (x > reverse) {
  		reverse = reverse * 10 + x % 10;
  		x /= 10;
  	}
  
  	//       12344321   || 12321
  	return reverse == x || reverse/10 == x;
  }