LeetCodeのBFSおよびDFSトピック



Bfs Dfs Topics Leetcode



LeetCodeのBFSおよびDFSトピック

BFS幅優先 、レイヤーに応じて展開されます DFS深さ優先 、「黒に行く1つの方法」です。



2のn乗の問題である場合、BFSの時間計算量は2のn乗であり、DFSの時間計算量はnです。

通常、迷路の最短経路問題を解決するためにBFSを使用します これは、DFSが終点に到達すると、大きな円の後に終点に到達する可能性があるためです。



BFS

1.たくさんのスペースがあり、指数関数的に成長しています

2.スタック爆発のリスクはありません。適用されるスペースはヒープスペースです。



3.最短または最小のパスを検索できます

DFS

1.スペースは深さに比例します

2.樹木の深さが深すぎる場合など、スタックが爆発する危険性があります。

3.最短パスと最小パスを検索できません

111.二分木の最小深さ

画像

/** * Definition for a binary tree node. * struct TreeNode { * int val * TreeNode *left * TreeNode *right * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * } */ class Solution { public: int minDepth(TreeNode* root) { if(!root) return 0 int left = minDepth(root->left) int right = minDepth(root->right) if(!left&&right) return right+1 if(!right&&left) return left+1 return min(left,right)+1 } }

279.完璧な正方形

画像

class Solution { public: int numSquares(int n) { queue<int> q vector<int> dist(n+1,INT_MAX) q.push(0) dist[0] = 0 while(q.size()){ int t=q.front() q.pop() if(t==n) return dist[t] for(int i=1i*i+t<=ni++){ int j=t+i*i if(dist[j]>dist[t]+1){ dist[j]=dist[t]+1 q.push(j) } } } return 0 } }

733.画像のレンダリング

画像

class Solution { public: vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) { if(image.empty()||image[0].empty()) return image int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1} int oldColor = image[sr][sc] if(oldColor==newColor) return image image[sr][sc] = newColor for(int i=0i<4i++){ int x=sr+dx[i],y=sc+dy[i] if(x>=0&&x<image.size()&&y>=0&&y<image[0].size()&&image[x][y]==oldColor){ floodFill(image,x,y,newColor) } } return image } }

200.島の数

画像

class Solution { public: int m,n int numIslands(vector<vector<char>>& grid) { if(grid.empty()||grid[0].empty()) return 0 n = grid.size(),m=grid[0].size() int res=0 for(int i=0i<ni++){ for(int j=0j<mj++){ if(grid[i][j]=='1'){ res++ dfs(grid,i,j) } } } return res } void dfs(vector<vector<char>>& grid,int x,int y){ int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1} grid[x][y]='0' for(int i=0i<4i++){ int a=x+dx[i],b=y+dy[i] if(a>=0 && a<n && b>=0 && b<m && grid[a][b]=='1') dfs(grid,a,b) } } }