Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Recommended reading

  • CSDN home page
  • GitHub open source address
  • Unity3D plugin sharing
  • Jane’s address book
  • My personal blog
  • QQ group: 1040082875

Hello, everyone, I am a little Magic dragon, Unity3D software engineer, VR, AR, virtual simulation direction, update software development skills from time to time, life perception, remember to use one button three links.

A, the title

1. Algorithm topic

“Determine whether a given integer is a palindrome.”

Title link: Source: LeetCode

Link: leetcode-cn.com/problems/st…

2

Given an integer x, if x is an integer, return true; Otherwise, return false.

Palindromes are integers in both positive (left to right) and backward (right to left) order. For example, 121 is palindrome and 123 is not.

Such as:

Input: x = 121 Output: true

S = “-121” input: s = “-121” output: false

Second, the problem solving

1. Analysis of ideas

The first idea of this problem is to convert a number to a string and then check if the string is palindrome, but this requires extra space to create the string.

The second idea is to simply reverse the number itself, and then compare the inverted number to the original number, and if they are the same, the whole number is a palindrome.

However, it is possible to have a reversed number greater than int.max, which is an integer overflow.

So following the second idea, to avoid integer overflow problems, consider reversing only half of the number, for example, 1221, to reverse the number 12 to 21, compared to the second half of the number 21, because they are the same, so 1221 is a palindrome.

2. Code implementation

First, we need to deal with some cases that are definitely not palindromes:

  • 1. A palindrome must not start with a sign, such as -123 or -1221, in which case return false
  • If the number is greater than 0 and the mantissa is 0, such as 10 or 100, return false

Next reverse half of the number:

  • 1. For example, the number 1221, perform the modulo 1221%10 operation to obtain the last digit 1.
  • 2. Divide 1221 by 10 to remove the last digit. 1221/10 = 122.
  • 3. Repeat the above operation until the original number is less than or equal to the inverted number, indicating that half of the original number has been reached.
public class Solution 
{
    public bool IsPalindrome(int x) 
    {
        // when x < 0, x is not a palindrome.
        / / when x! = 0, mantissa = 0, x is not a palindrome
        if (x < 0 || (x % 10= =0&& x ! =0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }

        // When the number length is odd, we can use revertedNumber/10 to remove the median number.
        // For example, at the end of the while loop we get x = 12, revertedNumber = 123,
        // Since the number in the middle does not affect the palindrome (it is always equal to itself), we can simply remove it.
        return x == revertedNumber || x == revertedNumber / 10; }}Copy the code

Execution Result:

3. Time complexity

Time complexity: O(log N)

For each iteration, we divide the input by 1010, so the time is order log n.

Space complexity: O(1)

There are constant variables, so space complexity is O(1).

Third, summary

One point to note is that since the palindrome number has even and odd bits, it should be equal when folded in half when its length is even.

When its length is odd, then when folded in half, one of its lengths needs to be removed by one digit (divide by 10 and round).