本文内容来自刘江的博客教程、LeetCode官网、

一、二分查找

供暖器

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]):
        n=len(heaters)
        heaters.sort()
        a=b=0
        for house in houses:
            j=bisect.bisect_right(heaters,house)
            i=j-1
            right_min=heaters[j]-house if j<n else float('inf')
            left_min=house-heaters[i] if i>=0 else float('inf')
            a=min(right_min,left_min) #一个房屋所需供暖器的最小加热半径
            b=max(a,b) 
            #所有房屋需要的供暖器的最小加热半径中的最大值,也就是可以覆盖所有房屋的最小加热半径
        return(b)
            

代码涉及的 bisect 模块

 二、动态规划

接雨水

 首先明确:对于数组中的每个元素,我们找出下雨后水能达到的最高位置,等于两边最大高度的较小值减去当前高度的值。

解法一:动态规划

class Solution:
    def trap(self, height: List[int]):
        n=len(height)
        ans=0
        if not height:
            return(0)
        left_max=[height[0]]+[0]*(n-1)
        right_max=[0]*(n-1)+[height[n-1]]
        #两次扫描寻找第i个柱子的左边最大值和右边最大值
        for i in range(1,n):   
            left_max[i]=max(height[i],left_max[i-1])
        for i in range(n-2,-1,-1):
            right_max[i]=max(height[i],right_max[i+1])
        #很显然最左边和最右边是必定接不到雨水的
        ans=sum((min(left_max[j],right_max[j])-height[j]) for j in range(n))
        return(ans)

解法二:双指针

class Solution:
    def trap(self, height: List[int]):
        left,right=0,len(height)-1
        ans=0
        left_max=right_max=0
        while left<=right:
            if left_max<right_max:
                ans+=max(0,left_max-height[left])
                left_max=max(left_max,height[left])
                left+=1
            else:
                ans+=max(0,right_max-height[right])
                right_max=max(right_max,height[right])
                right-=1
        return(ans)

 三、深搜+广搜

岛屿数量

深搜

class Solution:
    '''
    我们可以将二维网格看成一个无向图,竖直或水平相邻的 1 之间有边相连。
    为了求出岛屿的数量,我们可以扫描整个二维网格。
    如果一个位置为 1,则以其为起始节点开始进行深度优先搜索。
    在深度优先搜索的过程中,每个搜索到的 1 都会被重新标记为 0。
    最终岛屿的数量就是我们进行深度优先搜索的次数。
    '''
    def dfs(self,grid,r,c):
        grid[r][c]='0'
        nr,nc=len(grid),len(grid[0])
        for x,y in [(r-1,c),(r+1,c),(r,c-1),(r,c+1)]:
            if 0<=x<nr and 0<=y<nc and grid[x][y]=='1':
                self.dfs(grid,x,y)

    def numIslands(self, grid: List[List[str]]):
        nr=len(grid)
        if nr==0:
            return(0)
        nc=len(grid[0])

        numislands=0
        for r in range(nr):
            for c in range(nc):
                if grid[r][c]=='1':
                    numislands+=1  
#当前的grid[r][c]=='1',得知至少有一个岛屿,将与其相邻的'1'通过深搜变为0,直到该岛屿的相邻岛屿均为0,再找下一个连通分量岛屿
                    self.dfs(grid,r,c)
        return(numislands)

广搜

class Solution:
    '''
    同样地,我们也可以使用广度优先搜索代替深度优先搜索。
    为了求出岛屿的数量,我们可以扫描整个二维网格。
    如果一个位置为 1,则将其加入队列,开始进行广度优先搜索。
    在广度优先搜索的过程中,每个搜索到的 1 都会被重新标记为 0。
    直到队列为空,搜索结束。
    最终岛屿的数量就是我们进行广度优先搜索的次数。
    '''
    def numIslands(self, grid: List[List[str]]):
        nr=len(grid)
        if nr==0:
            return(0)
        nc=len(grid[0])

        numislands=0
        for r in range(nr):
            for c in range(nc):
                if grid[r][c]=='1':
                    numislands+=1  
                    grid[r][c]='0'
                    neighbors=collections.deque([(r,c)])
                    while(neighbors):
#将(r,c)的邻居为'1'的加入队列,并同时值置为'0',队列为空时表示已找到其所有‘真正’的邻居
                        row,col=neighbors.popleft()
                        for x,y in [(row-1,col),(row+1,col),(row,col-1),(row,col+1)]:
                            if 0<=x<nr and 0<=y<nc and grid[x][y]=='1':
                                neighbors.append((x,y))
                                grid[x][y]='0'
        return(numislands)

更多推荐