Li Kou brush question diary [January 19, 2022]

1. Sum of two numbers

Given an integer array nums and an integer target value target, please find the two integers with and as the target value target in the array and return their array subscripts.
You can assume that each input will correspond to only one answer. However, the same element in the array cannot be repeated in the answer.
You can return answers in any order.

Example 1:

Input: num = [2,7,11,15], target = 9
Output: [0,1]
Explanation: because num [0] + num [1] = = 9, return [0, 1].
Example 2:

Input: num = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: num = [3,3], target = 6
Output: [0,1]

1. Method 1
   Ordinary two times traversal search. i traverses from the first to the penultimate, and j traverses from the i+1 to the last, so the complexity is obviously less than O ( n 2 ) O(n^2) Of O(n2)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n=len(nums)
        for i in range(n-1):
            for j in range(i+1,n):
                if nums[i]+nums[j]==target:
                    return [i,j]

1. Method 2
   This is learned by the problem solving boss. Hash lookup.
   For a+b=target, then a=target-b. obviously, when we loop, we just need to find the value of target-b. This is obviously less than O ( n ) O(n) O(n)
   For each traversal value B, we look up target-b in the hash table. If found, we return the found value and current location. If it is not found, it will be stored in the hash table [where the key is target-b and the value is target-b]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        map = {}
        for i, num in enumerate(nums):
            if target - num in map:
                return [map[target - num], i]
            map[num] = i

20. Valid brackets

Given a string s that only includes' (',') ',' {','} ',' [','] ', judge whether the string is valid.

Valid strings must meet:
The left parenthesis must be closed with the same type of right parenthesis.
The left parentheses must be closed in the correct order.

Example 1:

Input: s = "()"
Output: true
Example 2:

Input: s = "() [] {}"
Output: true
Example 3:

Input: s = "(]"
Output: false
Example 4:

Input: s = "([)]"
Output: false
Example 5:

Input: s = "{[]}"
Output: true

This problem is a simple idea of going out of the stack and into the stack

class Solution:
    def isValid(self, s: str) -> bool:
        stack=[]
        for i in s:
            if i=='(' or i=='[' or i=='{':
                stack.append(i)
            else:
                if len(stack)==0:
                    return False
                if i==')' and stack[-1]=='(':
                    stack.pop(-1)
                elif i=='}' and stack[-1]=='{':
                    stack.pop(-1)
                elif i==']' and stack[-1]=='[':
                    stack.pop(-1)
                else:
                    return False
        if len(stack)==0:
            return True
        else:
            return False

python snake skin operation, you can directly delete the matching bracket pairs, so delete them several times.. If the string is' ', the match is successful

class Solution:
    def isValid(self, s: str) -> bool:
        for i in ('()','[]','{}')*(len(s)//2):
          s=s.replace(i,'')
        return not bool(s)

21. Merge two ordered linked lists

Merge the two ascending linked lists into a new ascending linked list and return. The new linked list is composed of all nodes of a given two linked lists.

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:

Input: l1 = [], l2 = []
Output: []
Example 3:

Input: l1 = [], l2 = [0]
Output: [0]

This is to create a new linked list, and then judge the value size of the two linked lists, small insertion. Then keep cycling. When one of the linked list elements has been inserted, all the remaining nodes of the second linked list are added to the new linked list.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        res=ListNode()
        temp=res
        while list1!=None and list2!=None:
            if list1.val<=list2.val:
                temp.next=list1
                list1=list1.next
            else:
                temp.next=list2
                list2=list2.next
            temp=temp.next

        if list1:temp.next=list1
        if list2:temp.next=list2
        return res.next

See the big guy's problem solution, there is also a recursive method. The idea is the same as above

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 is None:
            return list2
        elif list2 is None:
            return list1
        elif list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2