力扣热题100，力扣49.字母异位词分组力扣128.最长连续序列力扣.盛水最多的容器力扣42.接雨水(单调栈)

目录

力扣49.字母异位词分组

力扣128.最长连续序列

力扣.盛水最多的容器

力扣42.接雨水(单调栈)

---

 

1.包的命名规范:

java的命名规范

全部采用小写

结尾不能加负数

声明包:

位置必须在首行

类:

字母数字下划线，美元符号

不能数字开头

不能有中文

不能以关键字命名

区分英文大小写

导包:说明当前所使用的类所在的包

*通配符，倒入包下所有内容

类名:大驼峰命名

属性,方法名:小驼峰命名

方法中的参数叫形参，起作用的是数据类型，调用方法时候实际传递的参数叫实参。

引用类型

类，接口，枚举，注解，数组

力扣49.字母异位词分组

相当于，我们把每个字母排序之后，然后获取当前字符串是否有对应列表，假如有，给他添加进去，没有则生成一个

return new ArrayList<List<String>>(ret.values()) 这里是吧ret这个哈希表的值都给放到这个ArrayList里面，然后去返回。

class Solution {public List<List<String>> groupAnagrams(String[] strs) {//使用排好序的作为KeyMap<String,List<String>>ret=new HashMap<>();int n=strs.length;for(int i=0;i<n;i++){char[] a=strs[i].toCharArray();Arrays.sort(a);String str=new String(a);if(ret.get(str)==null){ret.put(str,new ArrayList<>());}ret.get(str).add(strs[i]);}return new ArrayList <List<String>>(ret.values());}
}

力扣128.最长连续序列

这个吗，第一想法就是排序，第二个想法看到ON，无脑哈希表，其余的再思考细节，用Set去个重复，然后这个题解写的一句话，我觉得特别牛逼，他说

假如一个数，他是最优的开头，换句话说，从他开始就是最长的，那么他不应该有前一个数，比如 200 100 1  2  3  4，那你说1作为最优的开头，是不是不应该有比1小1的数字，0，要不0就是最优秀的开头了。

class Solution {public int longestConsecutive(int[] nums) {//排序最少是nlogn，我可以哈希表，使用数组代替下班//我的话肯定首先先给他去重if(nums.length==0)return 0;Set<Integer>a=new HashSet<>();for(int num:nums){a.add(num);}//看到题解说的有道理，假如这个数应该是最长的话，那他肯定不存在前一个树//比如[100,4,200,1,3,2]，从1开始是最优秀的选择，那么假如存在0的话，那么1肯定不是最优秀的选择；//所以跳过就是需要看看是否存在前一个数，存在则跳过，再去检查后一个数字呗，更新长度int max=0;for(int number:a){int ret=0;if(a.contains(number-1)==true){continue;}else{while(a.contains(number)==true){ret++;number++;max=Math.max(ret,max);}}}return max;
}
}

力扣.盛水最多的容器

开始先全部找能盛多少，然后他的公式吗，长✖️宽，然后不断便利，看看左右哪个小，假如左边小就去移动左边，右边小移动右边，肯定不能移动大的边，不然只会更小

class Solution {public int maxArea(int[] height) {int n=height.length;int max=0;int cur=0;int end=n-1; //dp[n]:表示n位置上的可容纳的最多的水while(cur<end){max=Math.max(max,Math.min(height[cur],height[end])*(end-cur));if(height[end]>height[cur]){cur++;}else {end--;}}return max;}
}

力扣42.接雨水(单调栈)

这个题，之前写过，再次写又有不同感受，发现有一行代码是冗余的，所以我删了之后，发现好理解了很多

单调栈的作用是啥呢？

其实你不用在乎什么单调栈，你只需要存的下标，每个下标都比当前位置大，这样方便求他的长度，就好。其余倒是很简单没啥操作

相当于还是，我是找两个最近的水槽，然后出一个中间位置。相当于找到左右边界和水槽位置，就可以开始搞

class Solution {public int trap(int[] height) {Stack<Integer>stack=new Stack<>();int n=height.length;int sum=0;for(int i=0;i<n;i++){//什么样子会有雨水呢，两个水槽，并且中间有一个比两个水槽的一个要小while(!stack.isEmpty()&&height[stack.peek()]<height[i]){int mid=stack.pop();
//这里我们计算那个中间值if(!stack.isEmpty()){//两个边界值sum+=(Math.min(height[stack.peek()],height[i])-height[mid])*(i-stack.peek()-1);}}stack.add(i);}return sum;}
}

力扣31.下一个排列

相当于脑筋急转弯，我也是看题解的那个大哥写的，非常好

class Solution {public static void nextPermutation(int[] nums) {// 123456int n=nums.length;int i=n-2;//1  2  3while(i>=0&&nums[i]>=nums[i+1]){i--;}int ret=n-1;if(i>=0){while(ret>=0&&nums[ret]<=nums[i]){ret--;}}if(i>=0){swap(nums,ret,i);reverse(nums, i + 1, n - 1);}else if(i<0) {reverse(nums,0,n-1);}
}public static void swap(int[]nums,int a,int b){int t=nums[a];nums[a]=nums[b];nums[b]=t;}public static void reverse(int []nums,int x,int y){int left=x;int right=y;while(left<right){int t=nums[left];nums[left]=nums[right];nums[right]=t;left++;right--;}}
}

力扣287.寻找重复数

首先要保证不会越界，然后我们可以把它想象成一个链表，然后经典快慢指针确定是否有环，假如没环会一直不相遇，有环则会相遇，

然后让快或者慢回去，注意哈回去也是一个一个走，不能再是那个快走了

class Solution {public static int findDuplicate(int[] nums) {int n=nums.length;//不去越界的情况下,n+1个整数的数组，数字范围在[1,n]之内，这个是关键，否则可能会越界//那么我首先找他们相遇的地方int fast=nums[nums[0]];int slow=nums[0];//1  3  4  2 2   5 6while(slow!=fast){//走一步，vs走两步fast=nums[nums[fast]];slow=nums[slow];}fast=0;while(slow!=fast){//走一步，vs走两步fast=nums[fast];slow=nums[slow];}return slow;}
}

力扣239.滑动窗口最大值

这道题也是很有意思的反正，难度倒是不难，但是蛮考验代码，主要是针对情况，你是否能够井井有条的梳理出来，还要想一下，我平时用的Queue本质是LinkedList（这个本质可以支持头插，尾插，头删啥的)

我们需要面对一个情况，就是他如何更新最大值，当最大值迭代的时候，我们怎么处理，你假如开始不一条一条分析，而是直接想这两个问题，是不是很好去解决的，要是想要去解决这个题，我们需要一条一条的分析，首先就是用什么存储，肯定是一个队列，我们要维持什么呢，就是里面可以理解为一个

然后就是，维持一个递减的顺序，假如当前队列里面，所有人都是尾插，假如由于你的进入，导致顺序出现问题，不是递减的，那么就需要进行一个清空操作，然后就是因为开始没到3个，所以前三个是一个处理，后面那些就可以统一处理了，然后如何处理我们移动的时候

然后弹出的条件也很有意思，我们需要细思考一下，当前位置两种可能，要吗我移动是当前队列里面的队列首部，要吗是后面的某个值，假如是队首，那么你弹出，那么假如队列里面 3，2，1 然后你过去啦这个1(但是他并不是队列的队首，那么你又想一下，这种情况不存在的其实，只有第一种情况，因为，队首肯定是当前最大的元素，你弹出的元素，不可能是队列中的中间值甚至末尾值，因为队首登录的时候，假如1，2，3，4 这个4会把前面的1，2，3给清空，这样就好理解啦，所以只会出现一种情况

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if(nums == null || nums.length < 2) return nums;// 双端队列 保存当前窗口最大值的数组位置 保证队列中数组位置的数值按从大到小排序LinkedList<Integer> queue = new LinkedList();// 结果数组int[] result = new int[nums.length-k+1];for(int i = 0;i < nums.length;i++){// 保证从大到小 如果前面数小则需要依次弹出，直至满足要求，我看尾巴和当前值while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){//弹出末端元素queue.pollLast();}// 添加当前值对应的数组下标,尾插，细想一下，他肯定要吗是当前最大，要吗是当前最小queue.addLast(i);//插入的是下标//当最大的位置(队列头)，滑动窗口到了，我们的处理，i-k表示的就是，窗口的最左边。我们下标是到了[i,j]j+1   就是到达这个j+1时候的变化if(queue.peek() == i-k){     queue.poll();   } // 当窗口长度为k时（是窗口长度，不是队列长度，换句话队列只要有一个就行 保存当前窗口中最大值)if(i+1 >= k){//当i>2之后，后面就可以长度都是k了,所以对应定期的给他添加到结果里面result[i+1-k] = nums[queue.peek()];}}return result;}
}

力扣54.螺旋矩阵

没思路，看的题解，恍然大悟，这个题，复杂的地方是模拟想的很乱，导致不好去解题，

注意，边界值，可以相等，因为边界值相等的时候，他就是最后一行了。 

class Solution {public List<Integer> spiralOrder(int[][] matrix) {if (matrix.length == 0)return new ArrayList<Integer>();//找到上下左右四个边界int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1, x = 0;//就是矩阵的乘法来去做一个总数Integer[] res = new Integer[(r + 1) * (b + 1)];while (true) {//向右行走for (int i = l; i <= r; i++) res[x++] = matrix[t][i]; // left to right//这个++就相当于缩圈了，并且他这个t++之后，直接到的是下一个区域，就是6这个位置if (++t > b) break;//想下走for (int i = t; i <= b; i++) res[x++] = matrix[i][r]; // top to bottom//缩圈if (l > --r) break;//向左走for (int i = r; i >= l; i--) res[x++] = matrix[b][i]; // right to leftif (t > --b) break;//向上走for (int i = b; i >= t; i--) res[x++] = matrix[i][l]; // bottom to topif (++l > r) break;}return Arrays.asList(res);}
}