https://mp.weixin.qq.com/s/96NdHInxMUnd_et5WQQMBw    

递归方法与非递归方法  # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def swapPairs(self, head: ListNode) -> ListNode: #递归 # if head ==None or head.next == None: # return head # node1=head # node2=head.next #...

dfs求最短需要遍历所有路径，设置全局变量比较leetcode global 关键字失效，使用self.方法超时  globalnonlocalhttps://blog.csdn.net/qq_42780289/article/details/89244761 讲条件从 for循环里拆出来 class Solution: def shortestPathBinaryMatrix(self, grid) -> int: self.minvalue= float('inf') def dfs(x, y, sum_val): direct = [(0, 1), (1, 0), (0, -1),...

使用朴素匹配方法。  class Solution: def strStr(self, haystack: str, needle: str) -> int: if haystack=="" and needle!="": return -1 if needle=="": return 0 haystack=list(haystack) flag=True i=0 while i+len(needle)<=len(haystack): if haystack[i]==needle[0]: flag=True for j i...

如果使用递归时间会超时。使用记忆化递归也会超时。   # memo={} # def dfs(index,nums,sumval,i,j): # if (i,j) in memo: # return memo[(i,j)] # if index==k: # return sumval # if i>j: # return sumval # left=dfs(index+1,nums[1:],sumval+nums[0],i+1,j) # right=dfs(index+1,nums[:-1],sumval+nums[-1],i,j-1) # maxvalue=max(left,right...

dfs 超时通过遍历时设置不同的标志，来遍历，也可以通过栈。时间复杂度：O(N^4)O(N4 )，其中 NN 是 grid 的长和宽。空间复杂度：O(N^2)O(N2 )，深度优先搜索需要的 stack 和 seen 的空间。  作者：LeetCode链接：https://leetcode-cn.com/problems/making-a-large-island/solution/zui-da-ren-gong-dao-by-leetcode/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 class Solution: def large...

使用dfs,遍历grid当为1的时候，就通过dfs看这个岛屿的面积有多大，最后比较选出最大的一个。  class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: def dfs(x,y,visit,count): if grid[x][y]==1: visit[x][y]=1 count+=1 else: return count for item in [(0,1),(1,0),(-1,0),(0,-1)]: if 0<=x+item[0]<len(grid) and 0<=y+it...

通过dfs,判断交界处进行加1  class Solution: def islandPerimeter(self, grid: List[List[int]]) -> int: visit=[[0]*len(grid[0]) for _ in range(len(grid))] def dfs(x,y,count,visit): if grid[x][y]==0: count+=1 return count else: visit[x][y]=1 for item in [(0,1),(1,0),(-1,0),(0,-1)]: if x+item[0]>=len(grid) or...

贪心加二分。  当遇到下雨天时答案对应位置返回-1即可。然后这道题的重点就在于当晴天的时候要放干哪些池的水，选择正确的话就会避免洪水。如果不能放好水的话就会发生洪水返回[]。 但是怎么做正确选择呢？也就是说要知道后面哪个池又一次下雨了，才能根据贪心法则做选择在这个池第二次下雨之前放干水，根据贪心法则选择最接近第一次下雨的晴天，也就是尽早放干水越好。 请注意这里选择放干水的晴天必须在第一次下雨和第二次下雨之间，所以选择在此之间且在第一次下雨之后最接近的就可以。 这样的话，就遍历数组，如果大于0说明下雨，答案数组直接赋值为-1，然后将池塘的下雨日期用hashmap记录下来，即记录池塘上一次下雨的时...

通过动态规划方式去解决, 一位一位进行比较，dp数组中的状态记录的是s的i到p的j是否是匹配的。其中dp[0][j]的状态通过偶数位置是不是"*"来判断，其他的判断当前字符是不是"*"如果是的话，要么把当成前面的字母出现了0次，要么当成前面的字母出现了1次或多次，所以要么看dp[i][j-2]的状态，要么当s[i-1]==p[i-1]的时候，去看dp[i-1][j]的状态，因为如果是看成出现多次的话，总会转移到最后一位的状态这个时候看dp[i][j-2]的状态就可以了。当当前字母不是""的时候，看s[i-1]==p[j-1] 或者p[j-1]=="."，这个时候就看dp[i-1][j-1]的状...

通过遍历岛屿中为1的点,然后进行bfs,将"1"变成"0",岛屿填成海洋.进行计数.空间复杂度：\O(min(M,N))，在最坏情况下，整个网格均为陆地，队列的大小可以达到 min(M,N)。斜对角线注意在面试中需要问面试官可以直接在二维数组上进行更改吗?如果不可以自己另开一个数组.  from collections import deque class Solution: def numIslands(self, grid: List[List[str]]) -> int: queue=collections.deque() count=0 for i in range(len(gr...

引用https://leetcode-cn.com/problems/flood-fill/solution/python3-dfs-yu-bfs-liang-chong-fang-fa-san-chong-s/ 图像渲染题目:BFS:首先找到初始节点，给它染色，这个初始节点当作第一层。找到初始节点周围四个节点，给它们染色（符合条件的才能染），这四个节点当作第二层。再找到这四个节点周围八个节点，给它们染色，这八个节点当作第三层。重复以往，层层递进，直到找不到符合要求的节点。就是一个从中间向外扩散的过程。 队列实现:我们可以这样利用 *队列 *实现 广度优先搜索。 我们设置一个队列，先把初始点添...

dfs方法,每一个点为起点的路径个数等于他下方和右方点为起点的路径个数相加.就是一个从中间向一个方向深入的过程。由于递归超时,需要记忆化.  class Solution: def uniquePaths(self, m: int, n: int) -> int: direction=[(0,1),(1,0)] di=[[-1]*n for _ in range(m)] def dfs(i,j): if i==m-1 or j==n-1: return 1 if di[i][j]!=-1: return di[i][j] di[i][j]= dfs(i+1,j)+dfs(i,j+1) r...

对图像进行染色,一圈一圈的为周围点上***fs其中需要注意给上同样颜色时,判断一下,直接输出.否则一直在循环中.  from collections import deque class Solution: def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]: queue=collections.deque() directions=[(0,1),(1,0),(-1,0),(0,-1)] queue.append((sr,sc)) target=im...