Palindrome Number

https://leetcode.com/problems/palindrome-number/
https://leetcode.com/problems/palindrome-number/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import sys

class Solution1:
    def isPalindrome(self, x: int) -> bool:
        return False if x < 0 or str(x) != str(x)[::-1] else True

class Solution2:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        x = str(x)
        left, right = 0, len(x) - 1
        while left < right:
            if x[left] != x[right]:
                return False
            left += 1
            right -= 1
        return True

s1 = Solution1()
s2 = Solution2()
while True:
    try:
        x = int(input("An integer please: "))
    except ValueError:
        print("Input is not an integer!")
        sys.exit()
    print(s1.isPalindrome(x), s2.isPalindrome(x))

Find Palindrome With Fixed Length

https://leetcode.com/problems/find-palindrome-with-fixed-length/
https://leetcode.com/problems/find-palindrome-with-fixed-length/

根据索引值遍历前一半的字符串，拼接反转的后一半部分，保证不要加到进位即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def kthPalindrome(self,queries:List[int],intLength:int)->List[int]:
        res=[]
        half_of_intLength=ceil(intLength/2)
        # intLength=3: start_from_base=10 
        start_from_base=10**(half_of_intLength-1)

        # intLength=3: 1->101
        def getPalindrome(index_of_queries:int)->int:
            str_half=str(start_from_base+index_of_queries-1)
            if len(str_half)>half_of_intLength:
                return -1
            # don't forget to transfer the number to integer
            return int(str_half+str_half[-2::-1] if intLength%2==1 else str_half+str_half[-1::-1])
        
        for index_of_queries in queries:
            res.append(getPalindrome(index_of_queries))
        
        return res

Count Symmetric Integers

https://leetcode.com/problems/count-symmetric-integers/
https://leetcode.com/problems/count-symmetric-integers/

一定要小心int和string的转换，其次还要注意取值范围，边界情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def countSymmetricIntegers(self, low: int, high: int) -> int:
        cnt = 0
        for number in range(low, high + 1):
            str_number = str(number)
            length = len(str_number)
            if length % 2 == 1:
                continue
            middle = length // 2
            first_half = str_number[:middle]
            second_half = str_number[-middle:]
            if sum(map(int, first_half)) == sum(map(int, second_half)):
                cnt += 1
                print(first_half + second_half)
        return cnt

Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/
https://leetcode.com/problems/palindrome-linked-list/

使用快慢指针，当fast来到链表的尾部，slow也来到了链表的中部，现在我想要反转右半段，达到另起一个从右往左的头节点的效果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # reverse second half
        pre = None
        while slow:
            tmp = slow.next
            slow.next = pre
            pre = slow
            slow = tmp
        left, right = head, pre
        while right:
            if left.val == right.val:
                left = left.next
                right = right.next
                continue
            else:
                return False
        return True

Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/
https://leetcode.com/problems/longest-palindromic-substring/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution1:
    def longestPalindrome(self, s: str) -> str:
        res = ""

        def expand(left: int, right: int):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left + 1:right]

        for index in range(len(s)):
            tmp_res = expand(index, index)
            if len(tmp_res) > len(res):
                res = tmp_res
            tmp_res = expand(index, index + 1)
            if len(tmp_res) > len(res):
                res = tmp_res
        return res

class Solution2:
    def longestPalindrome(self, s: str) -> str:
        length_s = len(s)

        def palindrome_check(left, right):
            right = right - 1
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True

        for length in range(length_s, 0, -1):
            for start in range(0, length_s - length + 1):
                if palindrome_check(start, start + length):
                    return s[start:start + length]

s1 = Solution1()
s2 = Solution2()
while True:
    input_string = input("A string please: ")
    print(s1.longestPalindrome(input_string), s2.longestPalindrome(input_string))

快来参与讨论吧~