二分查找、动态规划、深搜+广搜
·
本文内容来自刘江的博客教程、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)
更多推荐










所有评论(0)