网站怎样制作 优帮云,自己在线制作logo免费软件下载,普陀区网站开发,qq是哪家公司开发的软件463.岛屿的周长
分析#xff1a;
1.陆地的旁边是海面#xff0c;存在周长2.陆地在边界上#xff0c;存在周长
思路一#xff1a;深度优先遍历
1.通过记录访问情况来访问数据
class Solution {
public:int direct[4][2]{{0,1},{0,-1},{1,0},{-1,0}};int res0;void dfs(…463.岛屿的周长
分析
1.陆地的旁边是海面存在周长2.陆地在边界上存在周长
思路一深度优先遍历
1.通过记录访问情况来访问数据
class Solution {
public:int direct[4][2]{{0,1},{0,-1},{1,0},{-1,0}};int res0;void dfs(vectorvectorintgrid,vectorvectorboolvisted,int x,int y){for(int i0;i4;i){int nextxxdirect[i][0];int nextyydirect[i][1];if(nextx0 nextxgrid.size() nexty0 nextygrid[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(vectorvectorint grid) {int ngrid.size(),mgrid[0].size();vectorvectorboolvisted(n,vectorbool(m,false));for(int i0;in;i){for(int j0;jm;j){if(!visted[i][j] grid[i][j]1){visted[i][j]true;dfs(grid,visted,i,j);}}}return res;}
}; 1971.寻找图中是否存在路径
分析
寻找两个节点间是否存在路径就是寻找两个节点是否在同一集合中
思路一并查集
1.初始化集合2.把各个节点进行连接3.寻根判断
class Solution {
public:int n200005;vectorintfathervectorint(n,0);void init(){//并查集初始化for(int i0;in;i) father[i]i;}int find(int u){//并查集寻根return ufather[u]?u:father[u]find(father[u]);}bool isSame(int u,int v){ufind(u);vfind(v);return uv;}void join(int u,int v){//连接两个节点ufind(u);vfind(v);if(uv) return;//说明已经存在连接father[u]v;//进行连接}bool validPath(int n, vectorvectorint edges, int source, int destination) {init();for(int i0;iedges.size();i) join(edges[i][0],edges[i][1]);//连接节点return isSame(source,destination);//寻根判断}
}; 684.冗余连接
分析
1.出现两个节点在同一集合即有冗余
思路一并查集
1.初始化2.边添加边判断
class Solution {
public:vectorintfathervectorint(1001,0);void init(){for(int i0;i1001;i) father[i]i;}int find(int u){//寻根return ufather[u]?u:father[u]find(father[u]);}bool isSame(int u,int v){//判断是否同一集合ufind(u);vfind(v);if(u0 v0) return false;return uv;}void join(int u,int v){//连接节点ufind(u);vfind(v);if(uv) return;father[u]v;}vectorint findRedundantConnection(vectorvectorint edges) {init();//初始化int nedges.size();for(int i0;in;i){if(isSame(edges[i][0],edges[i][1])) return edges[i];//出现两个节点在同一集合else join(edges[i][0],edges[i][1]);}return vectorint();}
}; 685.冗余连接 ||
分析
只存在一条冗余边有三种情况 1.入度可以通过遍历获取2.环可以通过判断两节点是否在同一集合获取
思路一并查集
1.先获取所有节点的入度2.存在节点入度为2 倒序找出入度为 2 的节点边节点边不考虑时判断图是否为树3.不存在节点入度为2 判断删除那一条边存在环直接返回
class Solution {
public:static const int N1010;int father[N];int n;void init(){//初始化for(int i1;in;i) father[i]i;}int find(int u){//寻根return ufather[u]?u:father[u]find(father[u]);}bool same(int u,int v){//判断是否在同一集合ufind(u);vfind(v);return uv;}void join(int u,int v){//连接两个节点ufind(u);vfind(v);if(uv) return;father[u]v;}vectorint getMoveEdge(const vectorvectorintedges){//获取要删除的冗余边init();for(int i0;in;i){if(same(edges[i][0],edges[i][1])) return edges[i];//已经存在同一集合所以此线冗余join(edges[i][0],edges[i][1]);}return {};//不存在冗余}bool judge(const vectorvectorintedges,int deleteEdge){//判断删除该边是否是树init();for(int i0;in;i){if(ideleteEdge) continue;//删除就不考虑if(same(edges[i][0],edges[i][1])) return false;//仍然存在同一集合绝对不是树join(edges[i][0],edges[i][1]);}return true;}vectorint findRedundantDirectedConnection(vectorvectorint edges) {nedges.size();int inDegree[N]{0};vectorintmid;for(int i0;in;i) inDegree[edges[i][1]];//记录入度for(int in-1;i0;i--){//从右侧开始记录if(inDegree[edges[i][1]]2) mid.push_back(i);//记录入度为2的节点的下标}if(mid.size()0){//存在入度为2的节点if(judge(edges,mid[0])) return edges[mid[0]];//最右边的边不考虑图为树else return edges[mid[1]];}return getMoveEdge(edges);}
};
