• Uncategorized
  • 0

[leetcode] 9. Palindrome + 7. Integer Reversal + 8. String to Integer

Hits: 0

Article directory

Integer inversion / palindrome: integer modulo operation, (after converting to a string) double pointer goes to the middle

lc 7

Integer to [String]

Determine the positive or negative condition of a given integer x, extract the sign, then turn abs(x) into a string, reverse the string, and finally restore it to an integer

class Solution(object):
    def reverse(self, x):
        string = str(abs(x))
        ans = int(string[::-1])
        if x > 0:
            return ans if ans <= (1<<31)-1 else 0
        if x < 0:
            return -ans if -ans >= -(1<<31) else 0
        return 0

Integer modulo operation

Python’s pit : Since Python’s // operation is rounded down, resulting in inconsistent results when taking the remainder of positive and negative numbers, it is necessary to convert the original number into a positive number operation.

  1. Pop the last digit of the input integer x in a loop and accumulate it to a new integer y
  2. Restore the sign of the integer y according to the sign of x
  3. The range of the output integer y should be [−2^31, 2^31 − 1] ( Available bit operation), if it overflows, it returns 0, if it does not overflow, it returns
    an integer y

class Solution:
    def reverse(self, x: int) -> int:
        y, res = abs(x), 0
        of = (1 << 31) - 1 if x > 0 else 1 << 31
        while y != 0:
            res = res * 10 + y % 10
            if res > of: return 0
            y //= 10

lc 8

regular expression

[Reference: LeetCode Panda Problem Solution]

common practice

To summarize the entire execution process:

  1. Filter out the preceding spaces (if any)
  2. Determine the positive and negative bits, and if it is a negative, record the status, indicating that the input is a negative number.
  3. The loop judges whether the following string is 0 to 9, and if so, accumulates the value

while i < n and str[i] >= '0' and str[i] <= '9':
    tmp = ord (str[i]) - ord ( '0' )   # convert characters to numbers

  1. Compare the current value with the largest and smallest 32-bit integer to see if it overflows, and calculate 2^31 available bit operations
  2. After the loop is over, return the corresponding positive or negative number according to the flag of the negative sign

[Reference: LeetCode wang_ni_ma]

class Solution(object):
    def myAtoi(self, str):

        if not str: return 0
        i, n = 0, len(str)

        # skip all whitespace at the beginning 
        while i < n and str[i] == ' ' :
            i += 1

        # If the string is all spaces, return 0 
        if i == n:
             return  0

        # If the first non-empty position is a symbol, log the symbol and advance i one bit 
        neg = True  if str[i] == '-'  else  False 
        if str[i] in ( '+' , '-' ) : i += 1 
        # the in operator is used here

        # Loop to judge whether the character is between 0~9     
        res = 0 
        while i < n and str[i] >= '0'  and str[i] <= '9' :
             # ASCII code of '0' is 48,' 1' is 49, so the real integer value can be obtained by subtracting it from 
            tmp = ord(str[i]) - ord( '0' )  
            res = res * 10 + tmp
            if not neg and res >= (1<<31)-1:
                return (1<<31)-1
            elif neg and -res <= -(1<<31):
                return -(1<<31)
            i += 1

        # If there is a negative sign, return a negative number  
        return -res if neg else res

lc 9

In special cases, return False directly:
1. Negative numbers
2.100 / 2000 / … whole ten hundred thousand numbers that are not 0

Integer to String

Integers must be converted to strings to use len() and pointers

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """ 
        ## Integers can only be converted to strings before len() and pointers
        x = str(x)
        n = len(x)
        j = n-1
        for i in range(n/2):
            if x[i] == x[j]:
                j -= 1 
            else :
                 return  False 
        return  True

Or use python built-in functions

class Solution(object):
    def isPalindrome(self, x):
        return str(x)==str(x)[::-1]

Integer Inversion: Modulo Operation

class Solution(object):
    def isPalindrome(self, x):
        if x<0:
            return False
        ans, old = 0, x
        while x>0:
            tmp = x%10
            ans = ans*10 + tmp
            x //= 10
        return ans==old

Integer reverse half

Use the symmetry of the palindrome: instead of reversing all the digits of an integer, you only need to reverse half of the digits.

The loop termination condition for reversing half of the numbers: It can be judged according to the length of the number (half), but you don’t want to traverse to find the length. It can be found that for the odd-length [palindrome], but you don’t want to traverse to find the length. It can be found that for the odd-length [palindrome] number 12321, we can split it into two numbers 12 and 12 123, for the even-length palindrome number 123321, we can split it into two numbers 123 and 123.

That is, if the length of the palindrome number is odd, the new number is exactly 10 times the original number x after loop processing, and if the length is even, the new number is exactly equal to the original number.

Or, directly use greater than to judge, if the original number is less than the new number​, exit the loop.

class Solution(object):
    def isPalindrome(self, x):
        if x<0 or (x%10==0 and x!=0):
            return False
        ans = 0
        while x>ans:
            ans = ans*10 + x%10
            x //= 10
        return x==ans or x==(ans//10)

You may also like...

Leave a Reply

Your email address will not be published.