leetcode刷题记录08——top100题里的5道中等题
leetcode刷题记录08——top100题里的5道中等题
上一篇博客：
leetcode刷题记录01——top100题里的7道简单题
leetcode刷题记录02——top100题里的7道简单题
leetcode刷题记录03——top100题里的6道简单+1道中等题
leetcode刷题记录04——top100题里的7道中等题
leetcode刷题记录05——top100题里的7道中等题
leetcode刷题记录06——top100题里的7道中等题
leetcode刷题记录07——top100题里的5道中等题
- 从前序与中序遍历序列构造二叉树
看了题解，从前序和中序，前序能得到根基的点，中序能根据根节点把树分为左子树和右子树，每一个节点都可以这么去划分左/右子树。
/*** 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 {int[] preorder;HashMap<Integer, Integer> dic = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {this.preorder = preorder;for(int i =0;i< inorder.length; i++){dic.put(inorder[i], i);}return recur(0,0,inorder.length-1);}TreeNode recur(int root,int left, int right){if(left > right){return null;}TreeNode node = new TreeNode(preorder[root]);int i = dic.get(preorder[root]);node.left = recur(root+1,left,i-1);node.right = recur(root+i-left+1,i+1,right);return node;}
}
-
路径总和 III
没有太多想法，知道需要根据递归遍历去写，但是没有太多的想法；
看了题解，相对好理解一些；
前序遍历，从根节点开始，往下遍历，看是否有值总和满足的。/*** 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;} } -
二叉树的最近公共祖先
直觉上得用递归，写了深度遍历，但是接下来不太会写了。看了题解觉得这道题不算难，mark下/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/ class Solution {private TreeNode ans;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {dfs(root,p,q);return this.ans;}public boolean dfs(TreeNode root,TreeNode p,TreeNode q){if(root==null){return false;}boolean lson = dfs(root.left,p,q);boolean rson = dfs(root.right,p,q);if((lson && rson) || (root.val == p.val || root.val==q.val) && (lson || rson)){ans = root;}return lson || rson || (root.val==p.val || root.val==q.val);} } -
岛屿数量
回溯的题，这是做的第一道，就是俩个思路，广度遍历和深度遍历。
看了答案豁然开朗，把所有的水田和陆地遍历一遍，把陆地四周的全部置为其他值，当遍历一遍结束，也知道了所有岛屿的数量。class Solution {public void dfs(char[][] grid, int r, int c){int nr = grid.length;int nc = grid[0].length;if(r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c]=='0'){return;}grid[r][c] = '0';dfs(grid,r-1,c);dfs(grid,r+1,c);dfs(grid,r,c-1);dfs(grid,r,c+1);}public int numIslands(char[][] grid) {if(grid==null || grid.length == 0){return 0;}int nr = grid.length;int nc = grid[0].length;int nums_islands = 0;for(int r = 0; r < grid.length;r++){for(int c = 0; c < nc; c++){if(grid[r][c]=='1'){++nums_islands;dfs(grid,r,c);}}}return nums_islands;} } -
腐烂的橘子
自己尝试写了下，部分用例无法通过。class Solution {public int orangesRotting(int[][] grid) {// 判断是否有新橘子if(nonNewOranges(grid)){return 0;}// 判断是否本身就没有坏橘子// 判断是否有本身是新，四维都是空的情况存在；if(nonBadOrganges(grid) || newNoneBadOranges(grid)){return -1;}// 进行橘子腐蚀return overrideOrange(grid);}public boolean nonNewOranges(int[][] grid){for(int i =0; i< grid.length; i++){for(int j= 0; j< grid[i].length;j++){if(grid[i][j]==1){return false;}}}return true;}public boolean nonBadOrganges(int[][] grid){for(int i =0; i< grid.length; i++){for(int j= 0; j< grid[i].length;j++){if(grid[i][j]==2){return false;}}}return true;}public boolean dfs(int[][] grid,int r,int c){if(r<0 || c<0 || r>=grid.length || c >= grid[r].length || grid[r][c] == 0){return true;}return false;}public boolean newNoneBadOranges(int[][] grid){for(int i =0; i< grid.length; i++){for(int j= 0; j< grid[i].length;j++){if(grid[i][j]==1&& dfs(grid,i-1,j) && dfs(grid,i,j-1)&& dfs(grid,i+1,j) && dfs(grid,i,j+1)){return true;}}}return false;}public int overrideOrange(int[][] grid){int n = grid.length,m= grid[0].length;int count = 0;Queue<int[]> queue = new LinkedList();for(int i = 0; i < n; i++){for(int j = 0; j< m; j++){int num = grid[i][j];if(num == 1){count++;}else if(num==2){queue.offer(new int[]{i,j});}}}int time = 0;int[][] direct = {{0,1},{0,-1},{-1,0},{-1,1}};while(count>0 && !queue.isEmpty()){time++;int N = queue.size();for(int i = 0; i < N; i++){int[] cur = queue.poll();int x = cur[0], y = cur[1];for(int[] dir: direct){int newX = x+dir[0], newY = y+dir[1];if(newX>=0 && newX < n && newY>=0 && newY<m){grid[newX][newY] = 2;count--;queue.offer(new int[]{newX,newY});}}}}if(count>0){return -1;}else{return time;}} }看了一个相对好理解的题解。
class Solution {public int orangesRotting(int[][] grid) {int n = grid.length, m = grid[0].length;int count = 0;Queue<int[]> queue = new LinkedList();for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {int num = grid[i][j];if (num == 1) {count++;} else if (num == 2) {queue.offer(new int[] { i, j });}}}int time = 0;int[][] direct = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };while (count > 0 && !queue.isEmpty()) {time++;int N = queue.size();for (int i = 0; i < N; i++) {int[] cur = queue.poll();int x = cur[0], y = cur[1];for (int[] dir : direct) {int newX = x + dir[0], newY = y + dir[1];if (newX >= 0 && newX < n && newY >= 0 && newY < m && grid[newX][newY] == 1) {grid[newX][newY] = 2;count--;queue.offer(new int[] { newX, newY });}}}}if (count > 0) {return -1;} else {return time;}} }