LeetCode Hot 100 解题笔记

LeetCode Hot 100 解题笔记1、两数之和关键词HashMapnums[j] target - nums[i]暴力算法用两个指针依次遍历所有两个数的组合若nums[i] nums[j] target输出[i, j]。算法复杂度O(n2)运行108次导致超时。空间复杂度O(1)优化思路算法慢的原因在于盲目地同时遍历两数nums[i]和nums[j] 。而 b nums[j] target - nums[i] target - a只需遍历 i 另外一个数b就确定了只需验证b是否在数组里并得到对应的索引由此想到构建一个HashMap集合其中键为数值值为索引判断b是否在map的键中。算法定义一个双列集合HashMap键为nums中的数值为数的索引遍历nums中的每个数nums[i]判断target - nums[i] 是否在HashMap中若在 找到两数索引直接return若不在将当前数的值与索引加入HashMap遍历完后没找到classSolution{publicint[]twoSum(int[]nums,inttarget){MapInteger,IntegerhmnewHashMap();intnnums.length;for(inti0;in;i){inttemptarget-nums[i];if(hm.containsKey(temp)){returnnewint[]{hm.get(temp),i};}hm.put(nums[i],i);}returnnewint[]{-1,-1};}}2、字母异位词分组(关键词HashMap、字符串排序)核心思路怎么用唯一的key共同具有的特征表示[eat,ate,tea]字母异位词分组思路一简单、快速 eatatetea 经排序后都为aet用aet作为key用[eat,ate,tea]作为值思路二eatatetea都可以表示为a1e1t1用a1e1t1作为key。(字符及其个数字符须按顺序保证key的唯一性字符除了标记还有分隔的作用参考以下例子)错误警示只统计不是0的也不行strs [“bdddddddddd”,“bbbbbbbbbbc”][0, 1, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]010100000000000000000000000[0, 10, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]010100000000000000000000000思路一classSolution{publicListListStringgroupAnagrams(String[]strs){MapString,ListStringhmnewHashMap();for(Stringstr:strs){char[]arraystr.toCharArray();Arrays.sort(array);StringkeynewString(array);if(hm.containsKey(key)){hm.get(key).add(str);}else{ListStringlnewArrayList();l.add(str);hm.put(key,l);}}returnnewArrayListListString(hm.values());}}思路二classSolution{publicListListStringgroupAnagrams(String[]strs){MapString,ListStringhmnewHashMap();ListListStringansnewArrayList();for(Stringstr:strs){int[]staticsnewint[26];StringBuilderrnewStringBuilder();for(inti0;istr.length();i){statics[str.charAt(i)-a]1;}for(inti0;istatics.length;i){if(statics[i]!0){r.append((char)(ai));r.append(statics[i]);}}Stringtempr.toString();ListStringlhm.getOrDefault(temp,newArrayList());l.add(str);hm.put(temp,l);}returnnewArrayListListString(hm.values());}}3 、最长连续序列核心思路枚举nums数组【nums数组实际为HashSet当相同的起点有多个时会超时】中每个数x判断x-1是否存在即该数是否为连续序列的起点若存在直接跳过因为x-1开始的连续序列的长度优于x开始的长度没必要计算当前x开始的长度若不存在即当前x为连续序列的起点。匹配x1,x2…xy记录当前匹配长度与最长的长度比较取最大值【匹配使用HashSet在O(1)内快速判断数组中是否存在某个数】classSolution{publicintlongestConsecutive(int[]nums){intlongest0;SetIntegerhsnewHashSet();for(intnum:nums){hs.add(num);}for(intnum:hs){if(hs.contains(num-1))continue;inttempnum1;intl1;while(hs.contains(temp)){l;temp;}longestMath.max(longest,l);}returnlongest;}}4、移动零核心思路使用双指针左指针指向当前已经处理好的序列的尾部右指针指向待处理序列的头部。右指针不断向右移动每次右指针指向非零数则将左右指针对应的数交换同时左指针右移。注意到以下性质左指针左边均为非零数右指针左边直到左指针处均为零。因此每次交换初始时都是将左指针的零与右指针的非零数交换且非零数的相对顺序并未改变。作者力扣官方题解链接https://leetcode.cn/problems/move-zeroes/solutions/489622/yi-dong-ling-by-leetcode-solution/【初始时未遇到0时左右指针重叠同时右移当遇到0时左指针停止指向0右指针继续右移直到遇见第一个非0】// 官方题解classSolution{publicvoidmoveZeroes(int[]nums){intnnums.length,left0,right0;while(rightn){if(nums[right]!0){swap(nums,left,right);left;}right;}}publicvoidswap(int[]nums,intleft,intright){inttempnums[left];nums[left]nums[right];nums[right]temp;}}我的代码显示初始化官方题解则融合了初始化以及后续交换的过程代码更简洁classSolution{publicvoidmoveZeroes(int[]nums){intleft0,right0;intnnums.length;//初始左指针指向第一个0while(leftnnums[left]!0){left;}if(leftn)return;//初始右指针指向左指针向右的第一个非0rightleft;while(rightnnums[right]0){right;}while(rightn){nums[left]nums[right];nums[right]0;left;//找到右指针指向的下一个非零while(rightnnums[right]0){right;}}}}5、盛最多水的容器双指针左右指针分别指向两侧边界计算容积维护最大容积变量比较高矮指向较矮边界的指针向另一侧移动直到两指针相遇或错过【若移动指向较高边界的指针容积只可能变得更少】classSolution{publicintmaxArea(int[]height){intnheight.length;intleft0,rightn-1;intmaxV0;while(leftright){intcurrentVMath.min(height[left],height[right])*(right-left);if(currentVmaxV){maxVcurrentV;}if(height[left]height[right]){left;}else{right--;}}returnmaxV;}}6、三数之和