Leetcode programming practice -- Tencent selected 50 questions (I)

LeetCode Programming practice —— Selected by Tencent 50 topic ( One ）

$\star$ Question no -2 $\star$ difficulty - secondary

Topic link : https://leetcode-cn.com/problems/add-two-numbers/

subject ： Two are given. Non empty The list of is used to represent two non negative integers . among , Their respective digits are based on The reverse Stored in , And each of their nodes can only store a Numbers . If , Let's add the two numbers together , A new list will be returned to represent their sum . You can assume that in addition to the numbers 0 outside , Neither of these numbers 0 start .

Prepare for questions ：

• Introduction to linked list ： Linked list $(linkedlist)$ It's a physical discontinuity 、 Non sequential data structures , By a number of nodes $(node)$ The composition of .
• Each node of the unidirectional linked list contains two parts , Part of it is the variables that hold the data $data$ , The other part is a pointer to the next node $next$ .

class Node:
		def  __init__(self,data);
				self.data=data
				self.next=None

• The first node in a linked list is called the header node , The last node is called the tail node , The tail node $next$ The pointer points to null .
• Unlike arrays that randomly look for elements by subscript , For one of the nodes in the linked list $A$ , We can only base on nodes A Of $next$ Pointer to find the next node of this node $B$ , And then according to the nodes $B$ Of $next$ The pointer finds the next node $C$ … …
• If you want to trace back to its predecessor through a node of the linked list , We use Double linked list . A two-way linked list is slightly more complex than a one-way linked list , Every node of it has $data$ and $next$ The pointer , It also has... Pointing to the front node $prev$ The pointer .
• summary ： The elements in the linked list can be stored anywhere in memory . Each element of the linked list stores the address of the next element , Thus, a series of random memory addresses are strung together . It's easy to add elements to a linked list ： Just put it in memory , And store its address in the previous element .

Topic realization (pycharm Realization )：

#!/usr/bin/python3
# -*- coding:utf-8 -*-

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        #  Something like this needs to generate new listnode Using dummy nodes will make it easier to deal with the problems of ,
        #  Is to add an arbitrary node in front , Finally back to .next Can 
        #  Actually ans and head It can be understood as a pointer to the same linked list , So for head The changes can also be reflected in ans On 
        # ans Used to output the last listnode,head Used to process traversal and generate new listnode
        ans = head = ListNode(0)
        digit = 0  #  Mark carry 

        #  When l1 And l2 When you haven't finished traversing , Traverse and add in turn , And add and to the result 
        while l1 and l2:
            num = l1.val + l2.val + digit  #  Calculation l1 and l2 Sum on this digit 
            head.next = ListNode(num % 10)  #  Add the sum of both in single digits to the result head and ans in 
            digit = num // 10  #  Mark carry , If there is carry 1, No carry is 0
            head, l1, l2 = head.next, l1.next, l2.next  #  All linked lists are moved backward to achieve the traversal effect 

        #  When l1 Execute the loop when it is long 
        while l1:
            num = l1.val + digit
            head.next = ListNode(num % 10)
            digit = num // 10
            head, l1 = head.next, l1.next

        #  When l2 Execute the loop when it is long 
        while l2:
            num = l2.val + digit
            head.next = ListNode(num % 10)
            digit = num // 10
            head, l2 = head.next, l2.next
        # l1 and l2 Are traversed , Check whether there is carry in the highest bit , If so, join 
        if digit:
            head.next = ListNode(digit)

        #  Returns the of the dummy node next
        return ans.next


def listToListnode(l):
    head = temp = ListNode(0)
    for num in l:
        temp.next = ListNode(num)
        temp = temp.next
    temp.next = None
    return head.next


def listnodeToList(head):
    ans = []
    while head:
        ans.append(head.val)
        head = head.next
    return ans


if __name__ == '__main__':
    l1 = [2, 4, 3]
    l2 = [5, 6, 4]

    l1 = listToListnode(l1)
    l2 = listToListnode(l2)

    so = Solution()
    ans = so.addTwoNumbers(l1, l2)  

    ans = listnodeToList(ans)
    print(ans)

⋆ Question no -4 ⋆ difficulty - difficult

Topic link ：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

subject ： Given two sizes m and n Ordered array of nums1 and nums2. Please find the median of these two ordered arrays , And the time complexity of the algorithm is required to be O(log(m + n)). You can assume nums1 and nums2 Will not be empty at the same time .

Topic realization ：

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        m = len(nums1)
        n = len(nums2)
        nums1.extend(nums2)#  Merge 
        nums1.sort()#  Sort  
        if (m + n) & 1:#  If it's odd   Return to the median 
            return nums1[(m + n - 1) >> 1]
        else:#  Returns the average of the two median values 
            return (nums1[(m + n - 1) >> 1] + nums1[(m + n) >> 1]) / 2

⋆ Question no -5 ⋆ difficulty - secondary

Topic link ：https://leetcode-cn.com/problems/longest-palindromic-substring/

subject ： Given a string s, find s The longest palindrome substring in . You can assume s The maximum length of is 1000.

Topic realization ：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        count = len(s)
        if count == 0 or count == 1:
            return s
        longestPalindromelen = 1
        longestPalindromeStr = s[0:1]
        dp = [[False] * count for i in range(count)]
        for r in range(1, count):
            for l in range(0, r):
                if s[r] == s[l] and (r - l <= 2 or dp[l + 1][r - 1] == True):
                    dp[l][r] = True
                    if longestPalindromelen < r - l + 1:
                        longestPalindromelen = r - l + 1
                        longestPalindromeStr = s[l:l + longestPalindromelen]
        return longestPalindromeStr