LeeCode打卡第二十九天
LeeCode打卡第二十九天
第一题：岛屿数量（LeeCode第200题）:
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。
主要思想：对图进行表里，找到第一个陆地，即值为1的点，从该点开始进行深度遍历，每遍历到一个点，将该点置为0，直到遍历完所有的点、
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public int pathSum(TreeNode root, long targetSum) {if(root == null) return 0;int ret = rootSum(root, targetSum);ret += pathSum(root.left,targetSum);ret += pathSum(root.right,targetSum);return ret;}public int rootSum(TreeNode root, long targetSum){int ret = 0;if(root == null) return 0;int val = root.val;if(val == targetSum) ret++;ret += rootSum(root.left, targetSum - val);ret += rootSum(root.right, targetSum - val);return ret;}
}
第二题：腐烂的橘子（LeeCode第994题）:
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值 0 代表空单元格；
- 值 1 代表新鲜橘子；
- 值 2 代表腐烂的橘子。
主要思想：首先遍历一遍矩阵，用count记录其中的新鲜橘子的数量。这一步只要是为了之后如果有新鲜橘子旁边没有腐烂的橘子的话，新鲜橘子就不会烂，这个会影响到后续的广度优先遍历的终止条件。对二维数组进行广度优先遍历，用队列存放腐烂的橘子，每次将腐烂的橘子存入数组就将他周围的新鲜橘子变为腐烂橘子即可，最后返回循环的轮次即可
class Solution {public int orangesRotting(int[][] grid) {int M = grid.length;int N = grid[0].length;Queue<int[]> queue = new LinkedList<>();int count = 0;for(int i = 0; i < grid.length; i++){for(int j = 0; j < grid[0].length; j++){if(grid[i][j] == 1) count++;else if(grid[i][j] == 2) queue.add(new int[]{i, j});}}int round = 0;while(count > 0 && !queue.isEmpty()){round++;int n = queue.size();for(int i = 0; i < n; i++){int[] orange = queue.poll();int r = orange[0];int c = orange[1];if(r - 1 >= 0 && grid[r-1][c] == 1){grid[r-1][c] = 2;count--;queue.add(new int[]{r-1, c});}if(r + 1 < M && grid[r+1][c] == 1){grid[r+1][c] = 2;count--;queue.add(new int[]{r+1, c});}if(c - 1 >= 0 && grid[r][c - 1] == 1){grid[r][c - 1] = 2;count--;queue.add(new int[]{r, c - 1});}if(c + 1 < grid[0].length && grid[r][c + 1] == 1){grid[r][c + 1] = 2;count--;queue.add(new int[]{r, c + 1});}}}if(count > 0){return -1;}else{return round;}}
}