一个网站怎么做2个服务器,创意网站 模板,企业管理系统免费网站,公司做网站建设图算法刷到这块#xff0c;感觉像是走了一段黑路快回到家一样#xff0c;看到这三个一直分不太清总是记混的名字#xff0c;我满脑子想起的是大学数据结构课我坐在第一排#xff0c;看着我班导一脸无奈#xff0c;心想该怎么把这个知识点灌进木头脑袋里边呢。有很多算法我… 图算法刷到这块感觉像是走了一段黑路快回到家一样看到这三个一直分不太清总是记混的名字我满脑子想起的是大学数据结构课我坐在第一排看着我班导一脸无奈心想该怎么把这个知识点灌进木头脑袋里边呢。有很多算法我当时想不明白感觉这样不对劲这咋变一变就能找到么。但是现在想来当时确实没必要想得太明白如果我早知道这些知识在过了短短一两年之后我又会以陌生人的身份重新认识他们当时就该转过头去和我舍友大聊特聊离谱的八卦让谢导早点放弃教会我们这个想法。 生成树就是在图中找到一棵包含图中所有节点的树生成树是含有图中所有顶点的无环连通子图所有可能的生成树中权重和最小的那棵生成树就叫「最小生成树」
1584. 连接所有点的最小费用Kruskal
class Solution {public int minCostConnectPoints(int[][] points) {int n points.length;ListEdge edges new ArrayListEdge();DisjoinSetUnion dsu new DisjoinSetUnion(n);for(int i0;in;i){for(int ji1;jn;j){edges.add(new Edge(i,j,dist(points,i,j)));} }// 升序Collections.sort(edges, new ComparatorEdge() {public int compare(Edge edge1, Edge edge2) {return edge1.weight - edge2.weight;}});int ret 0; int num 0;for(Edge edge:edges){int x edge.start;int y edge.end;int weight edge.weight;if(dsu.unionSet(x,y)){ret weight;num;if(numn-1){break;}}}return ret;}public int dist(int[][] points,int i,int j){int weight Math.abs(points[i][0]-points[j][0]) Math.abs(points[i][1]-points[j][1]);return weight;}
}class DisjoinSetUnion{int[] parent;int[] rank;int n;public DisjoinSetUnion(int n){this.n n;this.rank new int[n];Arrays.fill(this.rank,1);this.parent new int[n];for(int i0;in;i){this.parent[i] i;}}public int find(int x){if(parent[x]!x){parent[x] find(parent[x]);}return parent[x];}public boolean unionSet(int x, int y){int px find(x);int py find(y);// 是连通的当节点联通后就会有共同的parent说明这两个点已经被加入到树中了没加入的话parent是自身if(px py){return false;}else{if(rank[px]rank[py]){int temp px;px py;py temp;}rank[px] rank[py];parent[py] px;return true; }}
}class Edge{int start;int end;int weight;public Edge(int start,int end,int weight){this.start start;this.end end;this.weight weight;}
}
1584. 连接所有点的最小费用Prim
class Solution {public int minCostConnectPoints(int[][] points) {int n points.length;Listint[][] graph buildGraph(n,points);Prim prim new Prim(graph);int ret prim.weightSum();return ret;}Listint[][] buildGraph(int n,int[][] points){Listint[][] graph new LinkedList[n];for(int i0;in;i){graph[i] new LinkedListint[]();}for(int i0;in;i){for(int ji1;jn;j){int xi points[i][0]; int yi points[i][1];int xj points[j][0]; int yj points[j][1];int weight Math.abs(xi-xj) Math.abs(yi-yj);graph[i].add(new int[]{i,j,weight});graph[j].add(new int[]{j,i,weight});}}return graph;}
}class Prim{private PriorityQueueint[] pq;private boolean[] inMST;private int weightSum 0;private Listint[][] graph;public Prim(Listint[][] graph){this.graph graph;this.pq new PriorityQueue((a,b)-{return a[2]-b[2];});int n graph.length;this.inMST new boolean[n];// 将0节点的所有的边加入到pq中cut(0);inMST[0] true;while(!pq.isEmpty()){int[] edge pq.poll();int to edge[1];int weight edge[2];if(inMST[to]){continue;}cut(to);inMST[to] true;weightSum weight;}}private void cut(int n){Listint[] edges graph[n];for(int[] edge:edges){if(inMST[edge[1]]){continue;}pq.offer(edge);}}public int weightSum(){return weightSum;}public boolean allConnected(){for(int i0;iinMST.length;i){if(!inMST[i]) return false;}return true;}
}
743. 网络延迟时间 dijkstra
class Solution {public int networkDelayTime(int[][] times, int n, int k) {Listint[][] graph new LinkedList[n1];for(int i1;in1;i){graph[i] new LinkedList();}for(int[] time:times){int from time[0];int to time[1];int len time[2];graph[from].add(new int[]{to,len});}int[] distTo dijkstra(k,graph);int maxtime 0;for(int i1;in1;i){if(distTo[i] Integer.MAX_VALUE){return -1;}maxtime Math.max(distTo[i],maxtime);}return maxtime;}int[] dijkstra(int start, Listint[][] graph){int n graph.length;int[] distTo new int[n];Arrays.fill(distTo,Integer.MAX_VALUE);//给定初始化距离distTo[start] 0;QueueState pq new PriorityQueue((a,b)-{return a.distFromStart- b.distFromStart;});pq.offer(new State(start,0));while(!pq.isEmpty()){State curnode pq.poll();int nodeId curnode.id;int distFromStart curnode.distFromStart;// 如果这条路径没有改变那就不需要对该路径的邻接节点进行更新if(distFromStartdistTo[nodeId]){continue;}for(int[] adjnode:graph[nodeId]){int to adjnode[0];int len adjnode[1];// 经过曲折之后的路径小于原始的最初设定if(distFromStartlen distTo[to]){distTo[to] distFromStartlen;pq.offer(new State(to,distFromStartlen));}}}return distTo;}
}class State{int id;int distFromStart;State(int id, int distFromStart) {this.id id;this.distFromStart distFromStart;}
}1631. 最小体力消耗路径
class Solution {public int minimumEffortPath(int[][] heights) {int n heights.length*heights[0].length;Listint[][] graph new LinkedList[n];for(int i0;in;i){graph[i] new LinkedList();}for(int i0;iheights.length;i){for(int j0;jheights[0].length;j){int loc i*heights[0].lengthj;if(i-1-1){graph[loc].add(new int[]{i-1,j,Math.abs(heights[i][j]-heights[i-1][j])});}if(j-1-1){graph[loc].add(new int[]{i,j-1,Math.abs(heights[i][j]-heights[i][j-1])});}if(i1heights.length){graph[loc].add(new int[]{i1,j,Math.abs(heights[i][j]-heights[i1][j])});}if(j1heights[0].length){graph[loc].add(new int[]{i,j1,Math.abs(heights[i][j]-heights[i][j1])});}}}int[] maxheight new int[n];Arrays.fill(maxheight,Integer.MAX_VALUE);maxheight[0] 0;QueueState pq new PriorityQueue((a,b)-{return a.maxh-b.maxh;});pq.offer(new State(0,0,0));while(!pq.isEmpty()){State s pq.poll();int row s.row;int col s.col;int maxh s.maxh;if (row heights.length - 1 col heights[0].length - 1) {return maxh;}// 到达某点找到一条更近的距离if(maxh maxheight[row*heights[0].lengthcol]){continue;}for(int[] adjnode:graph[row*heights[0].lengthcol]){int r adjnode[0];int c adjnode[1];int h adjnode[2];int temp Math.max(maxheight[row*heights[0].lengthcol],h);if(tempmaxheight[r*heights[0].lengthc]){maxheight[r*heights[0].lengthc] temp;pq.offer(new State(r,c,temp));}}}return -1;}
}class State{int row;int col;int maxh;State(int row,int col,int maxh){this.row row;this.col col;this.maxh maxh;}
}
