LeetCode

LeetCode

文章目录

• 【品悟基础DFS】
• • [695. 岛屿的最大面积](/)
  • [547. 省份数量](/)
  • [417. 太平洋大西洋水流问题](/)
• 【回溯系列题】
• • [46. 全排列](/)
  • 47. 全排列（如何去重？）
• 【需要剪枝】

【品悟基础DFS】

695. 岛屿的最大面积

1. 此题等价于找出连通子块中最大的那个子块大小
2. 需要标记该格子有无被访问过
3. 利用方向数组进行四次循环和直接写以下代码的本质是一样的，看个人喜好

// 基本的 DFS 框架：每次搜索四个相邻方格
void dfs(int[][] grid, int r, int c) {dfs(grid, r - 1, c); // 上边相邻dfs(grid, r + 1, c); // 下边相邻dfs(grid, r, c - 1); // 左边相邻dfs(grid, r, c + 1); // 右边相邻
}/*作者：nettee
链接：/ */

class Solution {
public:int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int maxAreaOfIsland(vector<vector<int>>& grid) {int m=grid.size(),n=grid[0].size();if(m==0||n==0) return 0;int maxArea=0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1)maxArea=max(maxArea,dfs(grid,i,j));}}return maxArea;}int dfs(vector<vector<int>>& grid,int x,int y){if(grid[x][y]==0) return 0;grid[x][y]=0;//相当于已经访问int area=1;for(int i=0;i<4;i++){int tx=x+dx[i];int ty=y+dy[i];if(tx>=0&&tx<grid.size()&&ty>=0&&ty<grid[0].size()){area+=dfs(grid,tx,ty);}}return area;}
};

547. 省份数量

1. 这题与格子类DFS的连通表示方法有所区别，相比与格子型DFS的直观，此题的表示显然更加含蓄
2. 也可以使用并查集，此处使用DFS
3. 等价于统计一个图中连通子块的数量，因此对于同一个连通块中的访问过的点，要作标记

class Solution {
public:bool vis[205]={false};//表示还未被访问int findCircleNum(vector<vector<int>>& isConnected) {int n=isConnected.size();int cnt=0;for(int i=0;i<n;i++){if(vis[i]==false){cnt++;dfs(isConnected,i);}}return cnt;}void dfs(vector<vector<int>>& isConnected,int k){vis[k]=true;for(int i=0;i<isConnected.size();i++){if(isConnected[k][i]==1&&vis[i]==false) dfs(isConnected,i);}}
};

417. 太平洋大西洋水流问题

1. 这题要是遍历整个图的话开销非常大，因此要用逆向思维，只遍历边上的点
2. 等价于找出图中与两边连通的所有点，并且标记vis数组
3. 从“水”中向更高的陆地处搜索，即能得到答案
4. c++函数指针忘了，所以把烂代码放在下面
5. 如果该点在vis1中为True且在vis2中为True，那么符合题意

class Solution {
public:bool vis1[160][160]={false};//记录能流到太平洋的点bool vis2[160][160]={false};//记录能流到大西洋的点int dx[4]={0,0,-1,1};int dy[4]={1,-1,0,0};vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {int n=heights.size();int m=heights[0].size();vector<vector<int>> res;for(int i=0;i<n;i++){dfs1(heights,i,0);dfs2(heights,i,m-1);}for(int j=0;j<m;j++){dfs1(heights,0,j);dfs2(heights,n-1,j);}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(vis1[i][j]&&vis2[i][j]){res.push_back({i,j});}}}return res;}void dfs1(vector<vector<int>>& heights,int x,int y){vis1[x][y]=true;for(int i=0;i<4;i++){int tx=x+dx[i];int ty=y+dy[i];if(tx>=0&&tx<heights.size()&&ty>=0&&ty<heights[0].size()&&heights[tx][ty]>=heights[x][y]&&vis1[tx][ty]==false) dfs1(heights,tx,ty);}}void dfs2(vector<vector<int>>& heights,int x,int y){vis2[x][y]=true;for(int i=0;i<4;i++){int tx=x+dx[i];int ty=y+dy[i];if(tx>=0&&tx<heights.size()&&ty>=0&&ty<heights[0].size()&&heights[tx][ty]>=heights[x][y]&&vis2[tx][ty]==false) dfs2(heights,tx,ty);}}
};

【回溯系列题】

NOTE:回溯经常用于排列、组合、选择类问题

46. 全排列

我用最为经典的方法做了…但效率不高。

1. 回溯都要设置访问数组，在dfs前将其设置为已经访问，而搜索完毕这种情况后要重新返回到原来的情况，也就是未访问的状态
2. 设置一个path/track/temp数组，将选过的满足条件点放入；达到边界条件的时候，则将整个容器输出or加入结果容器。回溯后则将最后放入的点pop

class Solution {
public:vector<vector<int>> res;bool vis[15]={false};vector<vector<int>> permute(vector<int>& nums) {vector<int> temp;dfs(nums,0,temp);return res;}void dfs(vector<int>& nums,int index,vector<int> temp){if(temp.size()==nums.size()){res.push_back(temp);return;}for(int i=0;i<nums.size();i++){if(vis[i]==false){temp.push_back(nums[i]);vis[i]=true;dfs(nums,i+1,temp);temp.pop_back();vis[i]=false;}}}
};

47. 全排列（如何去重？）

【需要剪枝】