河北中保建设集团网站首页,江门网络推广公司,自己在线制作logo免费标智客,新产品宣传推广策划方案深度优先搜索|79. 单词搜索, 695. 岛屿的最大面积, 212. 单词搜索 II 单词搜索岛屿的最大面积单词搜索II 单词搜索
用的是深度优先搜索#xff0c;这种判断类型的回溯我就一直不知道要怎么回退#xff0c;然后勉强写了一个。 这里还有一个注意事项就是#xff0c;走到最后一… 深度优先搜索|79. 单词搜索, 695. 岛屿的最大面积, 212. 单词搜索 II 单词搜索岛屿的最大面积单词搜索II 单词搜索
用的是深度优先搜索这种判断类型的回溯我就一直不知道要怎么回退然后勉强写了一个。 这里还有一个注意事项就是走到最后一个元素的时候我设置的direction list里头就只有用过的几个元素再加上我写的if used这个时候他就走不下去了也不会到下一层的index1了这个时候又可以观察到如果走到最后有一个元素了和word也对得上其实并不需要再去看有没有direction了直接去index1不用管ij是谁就能直接True所以这个地方可以加一个判断就是如果走到这里已经在word最后一个字母后面了直接True。 然后写到这里就会发现如果直接出去了那么
if index len(word):return True 这句好像根本不需要后来发现确实不需要。
class Solution:def exist(self, board: List[List[str]], word: str) - bool:def direction(i,j,m,n):l [[i-1,j],[i1,j],[i,j-1],[i,j1]]if i 0:l.remove([i-1,j])if j 0:l.remove([i,j-1])if i m-1:l.remove([i1,j])if j n-1:l.remove([i,j1])return l def backtracking(index,i,j):#if index len(word):#return True l direction(i,j,m,n)if board[i][j] ! word[index]: return Falseused[i][j] Truefor k1,k2 in l:if index len(word) - 1:return True if used[k1][k2]: continueif backtracking(index1,k1,k2):return Trueif l [] and index len(word)-1:return Trueused[i][j] Falsereturn Falsem len(board)n len(board[0])used [[False]*n for _ in range(m)]for i in range(m):for j in range(n):if backtracking(0,i,j):return True return False岛屿的最大面积
这个题没上面的难因为他知道是1都是连着的所以不用回退。
class Solution:def maxAreaOfIsland(self, grid: List[List[int]]) - int:def direction(i,j,m,n):l [[i-1,j],[i1,j],[i,j-1],[i,j1]]if i 0:l.remove([i-1,j])if j 0:l.remove([i,j-1])if i m-1:l.remove([i1,j])if j n-1:l.remove([i,j1])return l m len(grid)n len(grid[0])used [[False]*n for _ in range(m)]def backtracking(i,j):nonlocal resif grid[i][j] 0: return 0l direction(i,j,m,n)res 1used[i][j] Truefor k1,k2 in l:if used[k1][k2]:continuebacktracking(k1,k2)return island 0for i in range(m):for j in range(n):res 0backtracking(i,j)island max(island,res)return island单词搜索II
在上一题的基础上加了一层循环然后剪枝了一下大多数还是能运行就是太长了就超时了 42 / 65这里有个要点是每次单词的used list都要重新设不然路都堵死了。
class Solution:def findWords(self, board: List[List[str]], words: List[str]) - List[str]:def direction(i,j,m,n):l [[i-1,j],[i1,j],[i,j-1],[i,j1]]if i 0:l.remove([i-1,j])if j 0:l.remove([i,j-1])if i m-1:l.remove([i1,j])if j n-1:l.remove([i,j1])return l def backtracking(index,word,i,j):l direction(i,j,m,n)if board[i][j] ! word[index]: return Falseused[i][j] Truefor k1,k2 in l:if index len(word) - 1:return True if used[k1][k2]: continueif backtracking(index1,word,k1,k2):return Trueif l [] and index len(word)-1:return Trueused[i][j] Falsereturn Falsem len(board)n len(board[0])res []for k in words:used [[False]*n for _ in range(m)]for i in range(m):if k in res:breakfor j in range(n):#print(i,j,k,res)if k in res:breakif backtracking(0,k,i,j):res.append(k)
