1. numbers of islands
1 class Solution(object): 2 def dfs(self,grid,i,j): 3 m,n=len(grid),len(grid[0]) 4 5 for k in range(4): 6 nx,ny=i+self.dirs[k],j+self.dirs[k+1] 7 if(0<=nx<m and 0<=ny<n and self.visited[nx][ny]==False and grid[nx][ny]=='1'): 8 self.visited[nx][ny]=True 9 self.dfs(grid,nx,ny) 10 11 12 def numIslands(self, grid): 13 """ 14 :type grid: List[List[str]] 15 :rtype: int 16 """ 17 if(len(grid)==0): 18 return 0 19 20 self.res=0 21 m,n=len(grid),len(grid[0]) 22 23 self.visited=[[False for j in range(n)] for i in range(m)] 24 self.dirs=[-1,0,1,0,-1] 25 26 for i in range(m): 27 for j in range(n): 28 if(self.visited[i][j]==False and grid[i][j]=='1'): 29 self.res+=1 30 self.visited[i][j]=True 31 self.dfs(grid,i,j) 32 33 return self.res 34 35
uf：初始时，每个为“1”的点就是一个岛屿
1 class Solution(object): 2 def init_uf(self,grid): 3 m,n=len(grid),len(grid[0]) 4 5 self.fathers=[None]*(m*n) 6 self.size=[None]*(m*n) 7 self.cnt=0 8 9 for i in range(m): 10 for j in range(n): 11 if(grid[i][j]=='1'): 12 self.fathers[i*n+j]=i*n+j 13 self.size[i*n+j]=1 14 self.cnt+=1 15 16 def find(self,x): 17 if(x==self.fathers[x]): 18 return x 19 20 self.fathers[x]=self.find(self.fathers[x]) 21 return self.fathers[x] 22 23 def connect(self,x,y): 24 fx,fy=self.find(x),self.find(y) 25 if(fx!=fy): 26 self.fathers[fx]=fy 27 self.size[fy]+=self.size[fx] 28 self.cnt-=1 29 30 def numIslands(self, grid): 31 """ 32 :type grid: List[List[str]] 33 :rtype: int 34 """ 35 if(len(grid)==0): 36 return 0 37 38 self.res=0 39 m,n=len(grid),len(grid[0]) 40 self.init_uf(grid) 41 42 self.dirs=[-1,0,1,0,-1] 43 44 for i in range(m): 45 for j in range(n): 46 if(grid[i][j]=='1'): 47 48 for k in range(4): 49 nx,ny=i+self.dirs[k],j+self.dirs[k+1] 50 if(0<=nx<m and 0<=ny<n and grid[nx][ny]=='1'): 51 self.connect(i*n+j,nx*n+ny) 52 53 return self.cnt 54 55
2. word ladder
1 class Solution(object): 2 def bfs(self,beginWord,endWord,graph): 3 hash={} # 单词：起点到单词的距离 4 min_step=0 5 self.queue.append((beginWord,-1,1)) 6 front=0 7 8 while(front!=len(self.queue)): # fornt指向queue尾部时，队列为空 9 node=self.queue[front][0] 10 step=self.queue[front][2] 11 12 if(min_step!=0 and step>min_step): 13 break 14 15 if(node==endWord): 16 min_step=step 17 self.end_word_pos.append(front) 18 19 nbs=graph[node] 20 for nb in nbs: 21 if(nb not in hash or hash[nb]==step+1): 22 self.queue.append((nb,front,step+1)) 23 hash[nb]=step+1 24 25 front+=1 26 27 def findLadders(self, beginWord, endWord, wordList): 28 self.res=[] 29 30 wordSet=set(wordList) 31 wordSet.add(beginWord) 32 if(endWord not in wordSet): 33 return self.res 34 35 graph={} # construct graph 36 tmp_que=[beginWord] 37 for word in wordSet: 38 graph[word]=set() 39 40 while(len(tmp_que)!=0): 41 cur=tmp_que.pop(0) 42 43 for i in range(len(cur)): 44 for k in "abcdefghijklmnopqrstuvwxyz": 45 tmp_word=cur[:i]+k+cur[i+1:] 46 47 if(tmp_word!=cur and tmp_word in wordSet): 48 if(len(graph[tmp_word])==0): 49 tmp_que.append(tmp_word) 50 51 graph[cur].add(tmp_word) 52 graph[tmp_word].add(cur) 53 # print(graph) 54 55 56 self.queue=[] 57 self.end_word_pos=[] 58 self.bfs(beginWord,endWord,graph) 59 60 for i in range(len(self.end_word_pos)): 61 pos=self.end_word_pos[i] 62 path=[] 63 while(pos!=-1): 64 path.append(self.queue[pos][0]) 65 pos=self.queue[pos][1] 66 67 self.res.append(path[::-1]) 68 69 return self.res
beginWord="hit"
endWord="cog"
WordList=['hot','dot','dog','lot','log','cog']
s=Solution()
res=s.wordlabber(beginWord,endWord,WordList)
print(res)
3. trapping water ii
1 from Queue import PriorityQueue 2 3 class Solution(object): 4 def trapRainWater(self, heightMap): 5 """ 6 :type heightMap: List[List[int]] 7 :rtype: int 8 """ 9 self.res=0 10 if(len(heightMap)==0): 11 return self.res 12 m,n=len(heightMap),len(heightMap[0]) 13 14 visited=[[False for j in range(n)] for i in range(m)] 15 16 pq=PriorityQueue() 17 for i in range(m): 18 for j in range(n): 19 if(i==0 or i==m-1 or j==0 or j==n-1): 20 pq.put((heightMap[i][j],i,j)) 21 visited[i][j]=True 22 23 self.dirs=[-1,0,1,0,-1] 24 25 while(pq.qsize()!=0): 26 cur_h,i,j=pq.get() 27 28 for k in range(4): 29 nx,ny=i+self.dirs[k],j+self.dirs[k+1] 30 if(0<=nx<m and 0<=ny<n and visited[nx][ny]==False): 31 visited[nx][ny]=True 32 tmp_h=max(cur_h,heightMap[nx][ny]) 33 self.res+=tmp_h-heightMap[nx][ny] 34 35 pq.put((tmp_h,nx,ny)) 36 37 return self.res
4.
79. Word Search
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
1 class Solution(object): 2 def dfs(self,board,word,i,j,idx): 3 m,n=len(board),len(board[0]) 4 if(idx==len(word)): 5 return True 6 7 if(i<0 or i>=m or j<0 or j>=n or word[idx]!=board[i][j] or self.visited[i][j]==True): 8 return False 9 10 self.visited[i][j]=True 11 12 13 # for k in range(4): 14 # nx,ny=i+self.dirs[k],j+self.dirs[k+1] 15 # if(self.dfs(board,word,nx,ny,idx+1)): 16 # return True 17 res=self.dfs(board,word,i,j-1,idx+1) or self.dfs(board,word,i,j+1,idx+1) or self.dfs(board,word,i-1,j,idx+1) or self.dfs(board,word,i+1,j,idx+1) 18 19 20 self.visited[i][j]=False 21 22 return res 23 # return False # 搭配for循环 24 25 def exist(self, board, word): 26 """ 27 :type board: List[List[str]] 28 :type word: str 29 :rtype: bool 30 """ 31 if(len(board))==0: 32 return False 33 34 self.dirs=[-1,0,1,0,-1] 35 m,n=len(board),len(board[0]) 36 self.visited=[[False for j in range(n)] for i in range(m)] 37 38 for i in range(m): 39 for j in range(n): 40 if self.dfs(board,word,i,j,0): 41 return True 42 43 return False