当前位置：首页 > article >正文

代码随想录算法训练营第三十天 | hot30/100| 49.字母异位词分组、128.最长连续序列、283.移动零、11.盛最多水的容器、42.接雨水

article 2025/1/8 18:58:47

49.字母异位词分组

互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

所以键是排序之后的字符串，值是原来的字符串。键相同的值，都是异位词

思路是：
1. 新建哈希表map，里面是<String, List<String>>，因为键是一个字符串，值是一系列字符串
2. 遍历strs里的每个字符串，将字符串转成字符数组后排序，排完序再转回字符串，作为key
3. 获取key对应的值，赋值给list。获取的方法是map.getOrDefault(key, new ArrayList<String>());意思是获取key对应的值，如果存在，就是这个值，如果不存在，就获取一个空字符串。
4. 这样的话，就把当前所有key一样的值聚到list里一起，接下来再把刚遍历到的这个str加入到list里
5. 再把键-值加入map
6. 最后返回map里的所有值部分

总结思路就是：
新建map
往map里添加键值（遍历每个字符串，排好序后作为key，原本的字符串作为值，键值添加到map里）
结果返回所有值

这道题各种新建，全部要背下来

128.最长连续序列

* 首先，将数组中的所有整数存入哈希集合中，同时去除重复的整数。
* 然后，遍历哈希集合中的每个整数。如果当前整数的前一个整数不在集合中，说明当前整数可能是一个连续序列的起点。存在那这个数肯定不是开头，直接跳过。
* 从可能的起点开始，不断检查下一个连续的整数是否在集合中，如果在，则继续延伸连续序列，同时记录连续序列的长度。
* 最后，在遍历过程中不断更新最长连续序列的长度。

class Solution {
    public int longestConsecutive(int[] nums) {
        // 创建一个 HashSet 集合用于存储数组中的整数
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            // 将数组中的每个整数添加到集合中，去除重复元素
            num_set.add(num);
        }
        int longestStreak = 0;
        for (int num : num_set) {
            // 如果集合中不包含当前整数减一的值，说明当前整数可能是一个连续序列的起点
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                // 当集合中包含当前数字加一的值时，说明连续序列可以继续延伸
                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }
                // 更新最长连续序列的长度
                longestStreak = Math.max(longestStreak, currentStreak);
            }
            //存在那这个数肯定不是开头，直接跳过。
        }
        return longestStreak;
    }
}

283.移动零

这道题写出来了

但是注意思路是：关注于处理不是0的数字，不要想着挑出0

11.盛最多水的容器

这道题用暴力法做出来了，但是超时了

class Solution {
   public int maxArea(int[] height) {
       int left;
       int right;
       int size = 0;
       int result = 0;
       for(left = 0; left < height.length -1; left++){
          for(right = left+1; right < height.length; right++){
              size = (right - left)\*Math.min(height\[left], height\[right]);
              result = Math.max(result, size);
              }
           }
       return result;
   }

这是暴力解法

但是既然想到双指针了，就应该想到用while(left < right)控制，然后找条件让left++ right—来替代for循环

这道题是if左边比右边高，右边就递减，else左边比右边低，左边就递增