CodeTop100 Day24

73、最小路径和64

class Solution {public int minPathSum(int[][] grid) {int m=grid.length;int n=grid[0].length;int[][]dp=new int[m][n];for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(i==0&&j==0){dp[i][j]=grid[i][j];}else if(i==0){dp[i][j]=grid[i][j]+dp[i][j-1];}else if(j==0){dp[i][j]=grid[i][j]+dp[i-1][j];}else{dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];}}}return dp[m-1][n-1];}
}

动态规划问题：设置dp[i][j]数组是从左上角走到i,j位置的最小距离，然后分析转移方程

起点位置路径为grid[0][0],最上方和最左方，只能从上个位置递推，否则就是求上方和左方的最小距离+该位置的值，最后输出dp[m-1][n-1];

74、路径总和II

class Solution {public List<List<Integer>> pathSum(TreeNode root, int targetSum) {List<List<Integer>> ans = new ArrayList<>();List<Integer> path = new ArrayList<>();dfs(root, targetSum, path, ans);return ans;}private void dfs(TreeNode node, int left, List<Integer> path, List<List<Integer>> ans) {if (node == null) {return;}path.add(node.val);left -= node.val;// node.left == node.right 相当于判断左右节点是否均为 nullif (node.left ==null&& node.right==null && left == 0) {ans.add(new ArrayList<>(path));} else {dfs(node.left, left, path, ans);dfs(node.right, left, path, ans);}path.remove(path.size() - 1);}
}

回溯路径题，注意它找的从根节点到叶子节点

75、最长公共前缀

class Solution {public String longestCommonPrefix(String[] strs) {String s0 = strs[0];for (int j = 0; j < s0.length(); j++) {char c = s0.charAt(j);for (String s : strs) {if (j == s.length() || s.charAt(j) != c) {return s0.substring(0, j);}}}return s0;}
}

简单题，根据题意模拟

76、最长连续序列

class Solution {public int longestConsecutive(int[] nums) {//返回hash表最大长度Set<Integer> numset=new HashSet<Integer>();for(int num:nums){numset.add(num);}//去重int longest=0;for(int num:numset){if(!numset.contains(num-1)){int curnum=num;int currst=1;while(numset.contains(curnum+1)){curnum+=1;currst+=1;}longest=Math.max(longest,currst);}}return longest;}
}

本题采用巧妙的hashset快速判断连续序列，时间复杂度为O（n）

首先将所有的数存入hashset，然后遍历每个值，先判断该值是否为连续序列的起点，比如上述例子[100 4 200 1 3 2] 遍历到100，发现hashset中不存在99,就开始找从100起始的序列，while循环一直找100++，用longest更新最大值，发现最大为1，遍历到1的时候，发现是起点，则找2，3，4

最大长度为4.

77、路径总和

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if(root==null){return false;}return dfs(root,targetSum);}public boolean dfs(TreeNode root,int targetSum){if(root==null){return false;}if(root.left==null&&root.right==null){return targetSum==root.val;}boolean left=dfs(root.left,targetSum-root.val);boolean right=dfs(root.right,targetSum-root.val);return left||right;}
}

会II，I就更简单了，直接判断该路径通不通即可。

78、二叉树最大宽度

class Solution {int result = 0;Map<Integer, Integer> minValue = new HashMap();public int widthOfBinaryTree(TreeNode root) {depth(root, 1, 0);return result;}public void depth(TreeNode node , int nodeIndex, int level) {if (node == null) return;minValue.putIfAbsent(level, nodeIndex);result = Math.max(result, nodeIndex - minValue.get(level) + 1);depth(node.left, 2 * nodeIndex, level + 1);depth(node.right, 2 * nodeIndex + 1, level + 1);}
}

该题要分清树的索引还有活用hashmap，比如上的例子

1

2 3

4 5    6

就是上述节点的索引，左节点为根节点*2，右节点为根节点*2+1,每次遍历的时候判断是否该层存入最左索引，然后每次遍历更新最大宽度结果result