463.岛屿的周长
分析:
- 1.陆地的旁边是海面,存在周长
- 2.陆地在边界上,存在周长
思路一:深度优先遍历
class Solution {
public:int direct[4][2]={{0,1},{0,-1},{1,0},{-1,0}};int res=0;void dfs(vector<vector<int>>&grid,vector<vector<bool>>&visted,int x,int y){for(int i=0;i<4;i++){int nextx=x+direct[i][0];int nexty=y+direct[i][1];if(nextx>=0 && nextx<grid.size() && nexty>=0 && nexty<grid[0].size()){if(!visted[nextx][nexty]){if(grid[nextx][nexty]==0) res++;//那一边是海面else{visted[nextx][nexty]=true;dfs(grid,visted,nextx,nexty);}}}else res++;//那一边是边界}}int islandPerimeter(vector<vector<int>>& grid) {int n=grid.size(),m=grid[0].size();vector<vector<bool>>visted(n,vector<bool>(m,false));for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(!visted[i][j] && grid[i][j]==1){visted[i][j]=true;dfs(grid,visted,i,j);}}}return res;}
};
1971.寻找图中是否存在路径
分析:
- 寻找两个节点间是否存在路径,就是寻找两个节点是否在同一集合中
思路一:并查集
class Solution {
public:int n=200005;vector<int>father=vector<int>(n,0);void init(){//并查集初始化for(int i=0;i<n;i++) father[i]=i;}int find(int u){//并查集寻根return u==father[u]?u:father[u]=find(father[u]);}bool isSame(int u,int v){u=find(u);v=find(v);return u==v;}void join(int u,int v){//连接两个节点u=find(u);v=find(v);if(u==v) return;//说明已经存在连接father[u]=v;//进行连接}bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {init();for(int i=0;i<edges.size();i++) join(edges[i][0],edges[i][1]);//连接节点return isSame(source,destination);//寻根判断}
};
684.冗余连接
分析:
思路一:并查集
class Solution {
public:vector<int>father=vector<int>(1001,0);void init(){for(int i=0;i<1001;i++) father[i]=i;}int find(int u){//寻根return u==father[u]?u:father[u]=find(father[u]);}bool isSame(int u,int v){//判断是否同一集合u=find(u);v=find(v);if(u==0 && v==0) return false;return u==v;}void join(int u,int v){//连接节点u=find(u);v=find(v);if(u==v) return;father[u]=v;}vector<int> findRedundantConnection(vector<vector<int>>& edges) {init();//初始化!!!int n=edges.size();for(int i=0;i<n;i++){if(isSame(edges[i][0],edges[i][1])) return edges[i];//出现两个节点在同一集合else join(edges[i][0],edges[i][1]);}return vector<int>();}
};