9. Palindrome Number

The problem

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward. 

 Example 1: 


Input: 121
Output: true


 Example 2: 


Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.


 Example 3: 


Input: 10
Output: false
Explanation: 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? 
Copy the code

Translation:

Determines whether an integer is a palindrome. An integer is a palindrome when it reads the same thing backwards as it reads forward.

Example 1:

Input :121 Output: true

Example 2:

Input :-121 Output: False Description: From left to right, the value is -121. From right to left, it becomes 121 minus. So it’s not a palindrome.

Example 3:

Input :10 Output: False Description: Read 01 from right to left. So it’s not a palindrome.

Follow up:

Can you solve an integer without converting it to a string?

Their thinking

A number is a palindrome number.

Definition of a palindrome number: when a number is flipped, it is the same as itself.

According to the definition of palindrome numbers, negative numbers are not acceptable. After all, there is a sign constraint. The units digit must be a palindrome number.

In the definition, you want to flip the number, see if it’s consistent, so it’s easy to think of converting it to String, and then flipping it to see if it’s consistent.

There is another way, is to take a bit, reassemble the numbers, determine whether they are consistent, but this needs to avoid overflow problems.

The problem solving method

1. The first method of disintegration is to edit it as we would like, with the following code

   // A negative number is not acceptableif (x < 0) {
           return false;
       }
       StringBuilder stringBuilder = new StringBuilder(x + "");
       return stringBuilder.toString().equals(stringBuilder.reverse().toString());
   Copy the code

   Time complexity: this scheme does not use a loop. In fact, it should be used for a loop in the flipping process, but it does not calculate, so f(n)=1=1; So O(f(n))=O(1), so T(n)=O(1).

   Space complexity: This scheme uses StringBuilder, which is equivalent to replicating an array, so the space complexity is O(1);

2. The second way to solve the problem is as follows:

   // A negative number is not acceptableif (x < 0) {
           return false;
       }
       int temp = x;
       long result = 0;
       while(temp ! = 0) { long remainder = temp % 10; result = result * 10 + remainder; temp /= 10; }return result == x;
   Copy the code

   Time complexity: the scheme used the single cycle, so (n) = f (log10 (n) + 1) / 2 = log10 (n) / 2; So O (f (n)) = O (log10 (n)) = O (log10 (n)), T (n) = O (log10 (n))

   Space complexity: This scheme does not use extra space to store values, so it is O(1);

conclusion

The general solution of this problem is described above. Scheme 2 does not use string and starts from itself directly, which is faster in space and time than scheme 1. The only point is that it needs to use long to control and avoid crossing the boundary.