LeetCode热题100（一）

LeetCode热题100一1. 两数之和题目详情https://leetcode.cn/problems/two-sum/给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值target的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案并且你不能使用两次相同的元素。你可以按任意顺序返回答案。示例 1输入nums [2,7,11,15], target 9 输出[0,1] 解释因为 nums[0] nums[1] 9 返回 [0, 1] 。示例 2输入nums [3,2,4], target 6 输出[1,2]示例 3输入nums [3,3], target 6 输出[0,1]解答过程第一时间想到的就是暴力枚举去解决publicint[]twoSum(int[]nums,inttarget){for(inti0;inums.length;i){for(intji1;jnums.length;j){if(nums[i]nums[j]target){returnnewint[]{i,j};}}}returnnull;}看了官方的解题思路十分巧妙的利用map特性第一次遍历的时候就记录元素及其下标避免重复遍历publicint[]twoSum(int[]nums,inttarget){HashMapInteger,IntegerhashMapnewHashMapInteger,Integer();for(inti0;inums.length;i){if(hashMap.containsKey(target-nums[i])){returnnewint[]{hashMap.get(target-nums[i]),i};}hashMap.put(nums[i],i);}returnnewint[]{};}49. 字母异位词分组题目详情https://leetcode.cn/problems/group-anagrams/给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。示例 1:输入:strs [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]输出:[[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]解释在 strs 中没有字符串可以通过重新排列来形成bat。字符串nat和tan是字母异位词因为它们可以重新排列以形成彼此。字符串ateeat和tea是字母异位词因为它们可以重新排列以形成彼此。示例 2:输入:strs [“”]输出:[[“”]]示例 3:输入:strs [“a”]输出:[[“a”]]解答过程延续上一题的思路将字符串拆解为字符数组排序后重新组装为字符串作为key并记录原始字符publicListListStringgroupAnagrams(String[]strs){HashMapString,ArrayListStringhashMapnewHashMap();for(Stringstr:strs){StringsArrays.stream(str.split()).sorted().collect(Collectors.joining());ArrayListStringarrayListhashMap.getOrDefault(s,newArrayList());arrayList.add(str);hashMap.put(s,arrayList);}returnnewArrayList(hashMap.values());}看了一下官方解题思路基本一致只是我这里用了切割字符串然后使用stream处理确实过于繁琐了publicListListStringgroupAnagrams(String[]strs){HashMapString,ArrayListStringhashMapnewHashMap();for(Stringstr:strs){char[]charArraystr.toCharArray();Arrays.sort(charArray);StringsnewString(charArray);ArrayListStringarrayListhashMap.getOrDefault(s,newArrayList());arrayList.add(str);hashMap.put(s,arrayList);}returnnewArrayList(hashMap.values());}另外一种解法利用了“互为字母异位词的两个字符串包含的字母相同”这里不再阐述128. 最长连续序列题目详情https://leetcode.cn/problems/longest-consecutive-sequence/给定一个未排序的整数数组nums找出数字连续的最长序列不要求序列元素在原数组中连续的长度。请你设计并实现时间复杂度为O(n)的算法解决此问题。示例 1输入nums [100,4,200,1,3,2] 输出4 解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。示例 2输入nums [0,3,7,2,5,8,4,6,0,1] 输出9示例 3输入nums [1,0,1,2] 输出3解答过程延续上一题的思路第一次的思路是将数组排序后将连续最大的数字作为key连续数字开始作为value记录序列长度最后通过遍历map去获取长度publicintlongestConsecutive(int[]nums){Arrays.sort(nums);HashMapInteger,IntegerhashMapnewHashMap();for(intnum:nums){hashMap.put(num,hashMap.getOrDefault(num-1,num));}intmax0;for(Map.EntryInteger,Integerentry:hashMap.entrySet()){intkeyentry.getKey();intvalueentry.getValue();if(key-value1max){maxkey-value1;}}returnmax;}后来发现其实可以优化一下value直接记录长度但是仍然不是较好的解题思路publicintlongestConsecutive(int[]nums){Arrays.sort(nums);intmax0;HashMapInteger,IntegerhashMapnewHashMap();for(intnum:nums){intlenhashMap.getOrDefault(num-1,0)1;hashMap.put(num,len);if(lenmax){maxlen;}}returnmax;}官方是使用的hashset处理看了下评论区其实可以排序后去获取最长序列publicintlongestConsecutive(int[]nums){Integer[]arrayArrays.stream(nums).boxed().distinct().sorted().toArray(Integer[]::new);intmax0;intlen0;for(inti0;iarray.length;i){if(i0){len1;}else{if(array[i]array[i-1]1){len;}else{len1;}}if(lenmax){maxlen;}}returnmax;}283. 移动零题目详情https://leetcode.cn/problems/move-zeroes/给定一个未排序的整数数组nums找出数字连续的最长序列不要求序列元素在原数组中连续的长度。请你设计并实现时间复杂度为O(n)的算法解决此问题。示例 1输入nums [100,4,200,1,3,2] 输出4 解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。示例 2输入nums [0,3,7,2,5,8,4,6,0,1] 输出9示例 3输入nums [1,0,1,2] 输出3解答过程这道题是个简单题但是第一次做的时候还是话费了很长时间并且不是一次性做对的第一次忽略了没有0的情况firstZeroIndex初始设置为0导致结果错误第二次忽略了0在元素后的情况错误交换了顺序publicvoidmoveZeroes(int[]nums){intfirstZeroIndex-1;for(inti0;inums.length;i){for(intj0;jnums.length;j){if(nums[j]0){firstZeroIndexj;break;}}if(nums[i]!0firstZeroIndex!-1ifirstZeroIndex){nums[firstZeroIndex]nums[i];nums[i]0;}}// System.out.println(Arrays.toString(nums));}11.盛最多水的容器题目详情https://leetcode.cn/problems/container-with-most-water/给定一个数组nums编写一个函数将所有0移动到数组的末尾同时保持非零元素的相对顺序。请注意必须在不复制数组的情况下原地对数组进行操作。示例 1:输入: nums [0,1,0,3,12] 输出: [1,3,12,0,0]示例 2:输入: nums [0] 输出: [0]解答过程直接尝试的暴力解法但是在数组很长的时候会超时publicintmaxArea(int[]height){intmax-1;for(inti0;iheight.length;i){for(intjheight.length-1;ji1;j--){intareaMath.min(height[i],height[j])*(j-i);if(areamax){maxarea;}}}returnmax;}看了解题思路才写出正确答案应该使用双指针由于宽度减少高度不增加的情况下一定会导致面积减小所以每次移动高度较低的指针publicintmaxArea(int[]height){intmax-1;intleft0;intrightheight.length-1;System.out.println(leftright);while(leftright){intareaMath.min(height[left],height[right])*(right-left);maxMath.max(max,area);if(height[left]height[right]){right--;}else{left;}System.out.println(max);}returnmax;}