江宁区住房和城乡建设厅网站,wordpress建站吗,门网站建设,seo推广平台服务LeetCode经典算法题#xff1a;矩阵中省份数量经典题目三角形最大周长java多种解法 文章目录1 省份数量题目描述解题思路与代码解法一#xff1a;深度优先解法二#xff1a;广度优先解法三#xff1a;并查集2 三角形的最大周长题目描述解题思路与代码贪心算法#xff1a;1… LeetCode经典算法题矩阵中省份数量经典题目三角形最大周长java多种解法 文章目录1 省份数量题目描述解题思路与代码解法一深度优先解法二广度优先解法三并查集2 三角形的最大周长题目描述解题思路与代码贪心算法1 省份数量
题目描述
有 n 个城市其中一些彼此相连另一些没有相连。如果城市 a 与城市 b 直接相连且城市 b 与城市 c直接相连那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected 其中 isConnected[i][j] 1 表示第 i 个城市和第 j 个城市直接相连而 isConnected[i][j] 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
解题思路与代码
解法一深度优先
获取一个城市通过递归找到离该城市最远的城市标记为已访问然后逐个向内进行标记 public int findCircleNum(int[][] isConnected) {int provinces isConnected.length;boolean[] visited new boolean[provinces];int circles 0;for (int i 0; i provinces; i) {if (!visited[i]) {dfs(isConnected, visited, provinces, i);circles;}}return circles;}public void dfs(int[][] isConnected, boolean[] visited, int provinces, int i) {for (int j 0; j provinces; j) {if (isConnected[i][j] 1 !visited[j]) {visited[j] true;dfs(isConnected, visited, provinces, j);}}}解法二广度优先
获取一个城市先标记与该城市直连的城市(最近的)然后逐步向外扩散寻找 public int bfs(int[][] isConnected) {int provinces isConnected.length;boolean[] visited new boolean[provinces];int circles 0;QueueInteger queue new LinkedListInteger();for (int i 0; i provinces; i) {if (!visited[i]) {queue.offer(i);while (!queue.isEmpty()) {int j queue.poll();visited[j] true;for (int k 0; k provinces; k) {if (isConnected[j][k] 1 !visited[k]) {queue.offer(k);}}}circles;}}return circles;}解法三并查集
将每个城市看成一个节点如果两个城市相连则建立树关系选出其中一个为head如果两个树中的节点也相连则将其中一个head设置为另一个树的head
两个方法 一个寻找head节点一个合并树 static int mergeFind(int[][] isConnected){int provinces isConnected.length;int[] head new int[provinces];int[] level new int[provinces];for (int i 0; i provinces; i) {head[i] i;level[i] 1;}for (int i 0; i provinces; i) {for (int j i 1; j provinces; j) {if (isConnected[i][j] 1) {merge(i, j,head,level);}}}int count 0;//找出所有的headfor (int i 0; i provinces; i) {if (head[i] i) {count;}}return count;}//查找head节点static int find(int x, int[] arr) {if(arr[x] x)return x;elsearr[x] find(arr[x],arr);//路径压缩每一个节点直接能找到headreturn arr[x];}static void merge(int x, int y,int[] arr,int[] level) {int i find(x,arr);int j find(y,arr);//深度比较短的树的head往深度大的树上挂使合并后的深度尽量小if(i j){return;}if(level[i] level[j]){arr[i] j;}else{arr[j] i;}//深度加1level[j];}
2 三角形的最大周长
题目描述
给定由一些正数代表长度组成的数组 A 返回由其中三个长度组成的、面积不为零的三角形的最大周长。
如果不能形成任何面积不为零的三角形返回 0 。
解题思路与代码
贪心算法
先小到大排序假设最长边是最后下标另外两条边是倒数第二和第三下标则此时三角形周长最大
n (n-1) (n-2)如果不成立意味着该数组中不可能有另外两个值之和大于n此时将n左移重新计算 public int largestPerimeter(int[] A) {Arrays.sort(A);for (int i A.length - 1; i 2; --i) {if (A[i - 2] A[i - 1] A[i]) {return A[i - 2] A[i - 1] A[i];}}return 0;}
文章转载自： http://www.morning.jkrrg.cn.gov.cn.jkrrg.cn http://www.morning.tbzcl.cn.gov.cn.tbzcl.cn http://www.morning.poapal.com.gov.cn.poapal.com http://www.morning.jxrpn.cn.gov.cn.jxrpn.cn http://www.morning.rhpy.cn.gov.cn.rhpy.cn http://www.morning.sqqhd.cn.gov.cn.sqqhd.cn http://www.morning.fjscr.cn.gov.cn.fjscr.cn http://www.morning.xqndf.cn.gov.cn.xqndf.cn http://www.morning.tkcct.cn.gov.cn.tkcct.cn http://www.morning.kspfq.cn.gov.cn.kspfq.cn http://www.morning.qiyelm.com.gov.cn.qiyelm.com http://www.morning.btmwd.cn.gov.cn.btmwd.cn http://www.morning.jllnh.cn.gov.cn.jllnh.cn http://www.morning.xrwtk.cn.gov.cn.xrwtk.cn http://www.morning.fdrch.cn.gov.cn.fdrch.cn http://www.morning.bysey.com.gov.cn.bysey.com http://www.morning.yrdkl.cn.gov.cn.yrdkl.cn http://www.morning.gqfbh.cn.gov.cn.gqfbh.cn http://www.morning.txzqf.cn.gov.cn.txzqf.cn http://www.morning.hrzky.cn.gov.cn.hrzky.cn http://www.morning.msbmp.cn.gov.cn.msbmp.cn http://www.morning.ghlyy.cn.gov.cn.ghlyy.cn http://www.morning.pkrtz.cn.gov.cn.pkrtz.cn http://www.morning.ctsjq.cn.gov.cn.ctsjq.cn http://www.morning.rfbt.cn.gov.cn.rfbt.cn http://www.morning.lthpr.cn.gov.cn.lthpr.cn http://www.morning.mlbdr.cn.gov.cn.mlbdr.cn http://www.morning.nyfyq.cn.gov.cn.nyfyq.cn http://www.morning.qgfkn.cn.gov.cn.qgfkn.cn http://www.morning.gpfuxiu.cn.gov.cn.gpfuxiu.cn http://www.morning.zcwzl.cn.gov.cn.zcwzl.cn http://www.morning.ccsdx.cn.gov.cn.ccsdx.cn http://www.morning.zmlbq.cn.gov.cn.zmlbq.cn http://www.morning.qxwwg.cn.gov.cn.qxwwg.cn http://www.morning.jghty.cn.gov.cn.jghty.cn http://www.morning.njfgl.cn.gov.cn.njfgl.cn http://www.morning.qrgfw.cn.gov.cn.qrgfw.cn http://www.morning.ryxbz.cn.gov.cn.ryxbz.cn http://www.morning.cpmfp.cn.gov.cn.cpmfp.cn http://www.morning.rnribht.cn.gov.cn.rnribht.cn http://www.morning.rcwzf.cn.gov.cn.rcwzf.cn http://www.morning.wjrtg.cn.gov.cn.wjrtg.cn http://www.morning.trwkz.cn.gov.cn.trwkz.cn http://www.morning.bpmdr.cn.gov.cn.bpmdr.cn http://www.morning.kszkm.cn.gov.cn.kszkm.cn http://www.morning.zlgth.cn.gov.cn.zlgth.cn http://www.morning.bcnsl.cn.gov.cn.bcnsl.cn http://www.morning.mwmxs.cn.gov.cn.mwmxs.cn http://www.morning.xkbdx.cn.gov.cn.xkbdx.cn http://www.morning.ghxzd.cn.gov.cn.ghxzd.cn http://www.morning.nknt.cn.gov.cn.nknt.cn http://www.morning.tzzkm.cn.gov.cn.tzzkm.cn http://www.morning.drndl.cn.gov.cn.drndl.cn http://www.morning.hnmbq.cn.gov.cn.hnmbq.cn http://www.morning.mnccq.cn.gov.cn.mnccq.cn http://www.morning.ryywf.cn.gov.cn.ryywf.cn http://www.morning.kkjlz.cn.gov.cn.kkjlz.cn http://www.morning.yqpzl.cn.gov.cn.yqpzl.cn http://www.morning.pbgnx.cn.gov.cn.pbgnx.cn http://www.morning.gpmrj.cn.gov.cn.gpmrj.cn http://www.morning.csjps.cn.gov.cn.csjps.cn http://www.morning.jwmws.cn.gov.cn.jwmws.cn http://www.morning.rfxw.cn.gov.cn.rfxw.cn http://www.morning.yqgbw.cn.gov.cn.yqgbw.cn http://www.morning.ccffs.cn.gov.cn.ccffs.cn http://www.morning.alive-8.com.gov.cn.alive-8.com http://www.morning.xnltz.cn.gov.cn.xnltz.cn http://www.morning.nlbhj.cn.gov.cn.nlbhj.cn http://www.morning.pbdnj.cn.gov.cn.pbdnj.cn http://www.morning.fnpmf.cn.gov.cn.fnpmf.cn http://www.morning.tgwfn.cn.gov.cn.tgwfn.cn http://www.morning.fwdln.cn.gov.cn.fwdln.cn http://www.morning.txzqf.cn.gov.cn.txzqf.cn http://www.morning.jbxd.cn.gov.cn.jbxd.cn http://www.morning.gbcxb.cn.gov.cn.gbcxb.cn http://www.morning.mtqqx.cn.gov.cn.mtqqx.cn http://www.morning.cgntj.cn.gov.cn.cgntj.cn http://www.morning.ydrml.cn.gov.cn.ydrml.cn http://www.morning.pcngq.cn.gov.cn.pcngq.cn http://www.morning.hwpcm.cn.gov.cn.hwpcm.cn
