1 省份数量
题目描述
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c直接相连，那么城市 a 与城市 c 间接相连。
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; Queue<Integer> queue = new LinkedList<Integer>(); 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; //找出所有的head for (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; else arr[x] = find(arr[x],arr);//路径压缩，每一个节点直接能找到head return 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; } //深度加1 level[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; }
3 打家劫舍
题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
输入：[1,2,3,1] 输出：4
输入：[2,7,9,3,1] 输出：12
解题思路与代码
static int maxMoney(int[] nums,int index){ if (nums == null || index < 0) { return 0; } if (index == 0) { return nums[0]; } return Math.max(maxMoney(nums,index - 2) + nums[index], maxMoney(nums,index - 1)); } static int maxMoney(int[] nums){ if (nums == null || nums.length == 0) { return 0; } int length = nums.length; if (length == 1) { return nums[0]; } /* int[] dp = new int[length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < length; i++) { dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); } return dp[length - 1]; */ int first = nums[0], second = Math.max(nums[0], nums[1]); for (int i = 2; i < length; i++) { int temp = second; second = Math.max(first + nums[i], second); first = temp; } return second; }
如果房子首尾相连：
public int rob(int[] nums) { int length = nums.length; if (length == 1) { return nums[0]; } else if (length == 2) { return Math.max(nums[0], nums[1]); } return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1)); } public int robRange(int[] nums, int start, int end) { int first = nums[start], second = Math.max(nums[start], nums[start + 1]); for (int i = start + 2; i <= end; i++) { int temp = second; second = Math.max(first + nums[i], second); first = temp; } return second; }
public int rob(TreeNode root) { int[] rootStatus = dfs(root); return Math.max(rootStatus[0], rootStatus[1]); } public int[] dfs(TreeNode node) { if (node == null) { return new int[]{0, 0}; } int[] l = dfs(node.left); int[] r = dfs(node.right); int selected = node.val + l[1] + r[1]; int notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1]); return new int[]{selected, notSelected}; }
