lc marathon 7.23

81. Search rotation sort array II

This question is really great ！！！

First of all, you can find it by dichotomy , There will always be one side Orderly

We first judge which side is orderly （nums[mid]>nums[left]）

Then according to the orderly side Judge whether there is this number No, Then go to the other side

But because there is repetition , Therefore, we must strictly judge whether it is orderly （< >）

When nums[mid]==nums[left] or nums[mid] == nums[right]

Adopt a conservative strategy ,left+=1 right-=1

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        #  The key is   Find out which side is orderly 
        #  Then use the orderly side to judge 
        left=0
        right=len(nums)-1
        while(left<=right):
            mid=(right-left)//2 +left
            if left==right and nums[mid]!=target: #  Anti deadlock 
                return False
            if nums[mid]==target:
                return True
            if nums[mid]>nums[left]: #  Indicates that the left side is orderly , One side must be orderly 
                if target>=nums[left] and target<=nums[mid]: #  On the left 
                    right=mid-1
                else:
                    left=mid+1
            elif nums[mid]<nums[right]:
                if target >= nums[mid] and target <= nums[right]:  #  On the right 
                    left=mid+1
                else:
                    right=mid-1
            else:
                if nums[left]==nums[mid]:
                    left+=1
                else:
                    right-=1
        return False

452. Detonate the balloon with a minimum number of arrows

Same as above

First sort the first digit

Then according to the following situation , Update the following

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        def ls(x1,x2):
            if x1<x2:
                return -1
            else:
                return 1
        points=sorted(points,key=cmp_to_key(ls))
        ans=0
        for index in range(1,len(points)):
            if points[index][0]>points[index-1][1]:
                ans+=1
            else:
                points[index][1]=min(points[index][1],points[index-1][1])
        return ans+1

79. Word search Answer key - Power button （LeetCode）

This problem is really worth accumulating

There are two details

The first is recursive Enter the next round no need Judge

It is expression “ Try to enter the next round ” The meaning of

After entering , Then judge

Boundary judgment

Access judgment

Success judgment

Failure judgment

Access array for global access

After judging success , Then mark this position 1, Try again

After trying , Restore the position

Be careful not to copy , Just quote

from copy import deepcopy
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        visiteds=[[0 for i in range(len(board[0]))] for j in range(len(board))]
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j]==word[0]:
                    rs=dfs(i,j,word,board,visiteds)
                    if rs:
                        return True
        return False

def dfs(i,j,word,boards,visiteds):
    #  Illegally cross the border 
    if not (i>=0 and i<len(boards) and j>=0 and j<len(boards[0])):
        return False
    #  This one has visited 
    if visiteds[i][j]==1:
        return False
    #  Successfully matched all strings 
    if len(word)==1:
        if boards[i][j]==word[-1]:
            return True
        else:
            return False
    #  Can't match 
    if boards[i][j]!=word[0]:
        return False
    #  Description match , Setting this location has been accessed 
    visiteds[i][j]=1
    rs1=dfs(i-1,j,word[1:],boards,visiteds)#  Up 
    rs2=dfs(i+1,j,word[1:],boards,visiteds)#  Down 
    rs3=dfs(i, j-1, word[1:],boards,visiteds)#  towards the left 
    rs4=dfs(i,j+1,word[1:],boards,visiteds)#  towards the right 
    visiteds[i][j]=0
    return rs1 or rs2 or rs3 or rs4

101. Symmetric binary tree

I originally wanted to traverse with hierarchy , But recursion is more elegant ,

It actually detects The left node of a node and The right node of a node Whether it is equal or not （ Mirror image ）

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if root==None:
            return True
        return ismirror(root.left,root.right)
def ismirror(node1,node2):
    if node1==None and node2==None:
        return True
    if node1!=None and node2!=None and node1.val == node2.val:
        return ismirror(node1.left,node2.right) and ismirror(node1.right,node2.left)
    return False