lc marathon 7.23

81. 搜索旋转排序数组 II

这道题真的很棒！！！

首先可以通过二分去查找，总会有一边有序的

我们首先判断哪边是有序的（nums[mid]>nums[left]）

然后根据有序的那边 判断是否有这个数 没有 则到另一边

但因为有重复的，所以必须严格判断是否有序（< >）

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

采用保守策略，left+=1 right-=1

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        # 关键是 找到哪边有序
        # 然后用有序的那边进行判断
        left=0
        right=len(nums)-1
        while(left<=right):
            mid=(right-left)//2 +left
            if left==right and nums[mid]!=target: # 防死锁
                return False
            if nums[mid]==target:
                return True
            if nums[mid]>nums[left]: # 表明左边有序,一定会有一边是有序的
                if target>=nums[left] and target<=nums[mid]: # 在左边
                    right=mid-1
                else:
                    left=mid+1
            elif nums[mid]<nums[right]:
                if target >= nums[mid] and target <= nums[right]:  # 在右边
                    left=mid+1
                else:
                    right=mid-1
            else:
                if nums[left]==nums[mid]:
                    left+=1
                else:
                    right-=1
        return False

452. 用最少数量的箭引爆气球

与上面的一样

先对第一位数进行排序

然后根据下面的情况，对后面的进行更新

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. 单词搜索 题解 - 力扣（LeetCode）

这道题也真的值得积累

有两个细节

第一个是 递归 进入下一轮时候 不用 判断

而是 表达 “尝试进入下一轮”的意义

在进入后，再进行判断

边界判断

访问判断

成功判断

失败判断

全局访问的访问数组

判断成功后 ，再把该位标1，再进行各种尝试

尝试完后，再把该位置恢复

注意不用传复制，传引用即可

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):
    # 非法越界
    if not (i>=0 and i<len(boards) and j>=0 and j<len(boards[0])):
        return False
    # 这位访问过了
    if visiteds[i][j]==1:
        return False
    # 成功匹配全部字符串
    if len(word)==1:
        if boards[i][j]==word[-1]:
            return True
        else:
            return False
    # 无法匹配
    if boards[i][j]!=word[0]:
        return False
    # 说明匹配，设置该位置访问过了
    visiteds[i][j]=1
    rs1=dfs(i-1,j,word[1:],boards,visiteds)# 向上
    rs2=dfs(i+1,j,word[1:],boards,visiteds)# 向下
    rs3=dfs(i, j-1, word[1:],boards,visiteds)# 向左
    rs4=dfs(i,j+1,word[1:],boards,visiteds)# 向右
    visiteds[i][j]=0
    return rs1 or rs2 or rs3 or rs4

101. 对称二叉树

本来想用层次遍历，但递归更加优美，

它实际检测 一个节点的左节点 和 一个节点的右节点 是否相等（镜像）

# 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