49. 字母异位词分组

用hashmap存储，其中每个key，用这组异位词的排序后的字符串；value是这组异位词。比如“tea”和“ate”是一组异位词，他们的排序结果都是“aet”。

public List<List<String>> groupAnagrams(String[] strs) {Map<String,List<String>> res=new HashMap<>();for(String str:strs){//记得先声明一下str类型char[] array=str.toCharArray();Arrays.sort(array);String key=new String(array);List<String> list=new LinkedList<>();list=res.getOrDefault(key,new LinkedList<>());list.add(str);res.put(key,list);//如果已经存在key，会直接覆盖}List<List<String>> result=new LinkedList<>(res.values());//values()方法//的作用是得到HashMap中的value的集合return result;}

在原来的Java课上，关于HashMap的插入元素的原理是：

其实，在res.put(key,list);语句中，就是equals比较结果为true的情况——直接覆盖

53. 最大子数组和

思路：
这个问题可以分成如下的子问题，经过数组第一个元素的子数组的和是多少；经过数组第二个元素的子数组的和是多少；经过数组第三个元素的子数组的和是多少……经过数组第n个元素的子数组的和是多少；
但是这样描述不能体现元素所在的子数组的位置，所以改成，以数组第一个元素 结尾 的子数组的和是多少；以数组第二个元素 结尾 的子数组的和是多少；以数组第三个元素 结尾 的子数组的和是多少……以数组第n个元素 结尾 的子数组的和是多少；

可以发现，如果使用dp[i] 来存储以第i个元素为结尾的子数组的和的最大值，又可以分成下面两种情况：①dp[i] 小于等于0，这样的话dp[i+1] =nums[i] ，因为第i+1个元素之前的所有子树组的和的最大值小于等于0，那么第i+1个元素对应的最大值肯定比只有i+1一个元素的最大值大。②dp[i] >0，dp[i+1]=dp[i] +nums[i+1]

class Solution {public int maxSubArray(int[] nums) {int len=nums.length;int[] dp=new int[len];//注意这里的写法dp[0]=nums[0];for(int i=1;i<len;i++){if(dp[i-1]<=0){dp[i]=nums[i];}else{dp[i]=dp[i-1]+nums[i];}}int res=-(int)Math.pow(10,4);//强制类型转换，不然报错for(int i=0;i<len;i++){res=Math.max(res,dp[i]);}return res;}
}

改善空间复杂度，因为第i个dp[i]之和dp[i-1]有关：

		int len=nums.length;int max=nums[0];int pre,now,temp=nums[0];for(int i=1;i<len;i++){pre=temp;//pre存储dp[i-1]if(pre<=0){now=nums[i];//now存储dp[i]}else{now=pre+nums[i];}temp=now;//temp暂存now，作为下一次的dp[i-1]max=Math.max(max,now);}return max;

注意：要想清楚，dp[i]是和dp[i-1]有关，而不是和max有关！max只存储和的最大值，而dp[i]是对前面的i-1个元素的和的最大值进行分类讨论，而”前i-1个元素组成的子数组的和的最大值“与最大值max不一定相等。

55. 跳跃游戏

注意：题目的意思是，并不一定要固定跳nums[i]对应的步数，而是最多跳这么多步
思路：不用管每次到底是在规定的范围内跳几步，只要每次都在新的范围内，更新最大的范围，最后范围能够覆盖到最后一个元素就行

class Solution {public boolean canJump(int[] nums) {int cover=nums[0];for(int i=0;i<=cover;i++){cover=Math.max(cover,i+nums[i]);if(cover>=nums.length-1){return true;}}return false;}
}