「LeetCode Hot 100 题」详解

前言

前言：LeetCode Hot 100 题详解

1. 两数之和

• 原题链接：两数之和

• 知识点：哈希表

• 题解

  class Solution {
      public int[] twoSum(int[] nums, int target) {
          Map<Integer, Integer> heap = new HashMap<>();  // 哈希表用于记录枚举数的前面所有数
          for (int i = 0; i < nums.length; i ++ ) {  // 枚举第二个数
              int another = target - nums[i];
              if (heap.containsKey(another))  // 查找哈希表中是否存在和为 target 的目标值
                  return new int[] {heap.get(another), i};  // 返回答案对象
              heap.put(nums[i], i);
          }
          return null;
      }
  }
  

2. 字母异位词分组

• 原题链接：字母异位词分组
  
• 知识点：哈希表

•   class Solution {
        public List<List<String>> groupAnagrams(String[] strs) {
            // 字母相同，但排列不同
            // 分组标准：将所有字符串排序，判断排序后的是否相等
            // 哈希表，将 string 映射到 vector 中
    
            List<List<String>> res = new ArrayList<>();  // 结果数组
            Map<String, List<String>> hashMap = new HashMap<>();
    
            for (int i = 0; i < strs.length; i ++) {
                char[] c = strs[i].toCharArray();
                Arrays.sort(c);
                String s = new String(c);
                if (!hashMap.containsKey(s)) hashMap.put(s, new ArrayList<String>());
                hashMap.get(s).add(strs[i]);
            }
    
            // hashMap.values()：返回哈希表中所有值
            for (List<String> tmp : hashMap.values()) res.add(tmp);
            return res;
    
        }
    }
  

3. 最长连续序列

• 原题链接：最长连续序列
• 知识点：哈希表
• 题解

  	class Solution {
      public int longestConsecutive(int[] nums) {
          // 先将所有数插入到哈希表中，再去枚举所有数
          // 枚举只枚举每一段的开始，每次枚举完将其删除
          Set<Integer> hashSet = new HashSet<>();
          for (int x : nums) 
              hashSet.add(x);
          
          int res = 0;
          for (int x : nums) {
              if (hashSet.contains(x) && !hashSet.contains(x - 1)) {
                  int y = x;
                  hashSet.remove(x);
                  while (hashSet.contains(y + 1)) {
                      hashSet.remove(++ y);
                  }
                  if (y - x + 1 > res)
                      res = y - x + 1;
              }
          }
          return res;
      }
  }
  

4. 移动零

• 原题链接：移动零
• 知识点：双指针
• 题解

  	class Solution {
      public void moveZeroes(int[] nums) {
          int k = 0;
          for (int num : nums) {
              if (num != 0)
                  nums[k ++] = num;
          }
          while (k < nums.length) nums[k ++] = 0;
      }
  }
  

5. 盛最多水的容器

class Solution {
    public int maxArea(int[] height) {
        int res = 0;
        for (int i = 0, j = height.length - 1; i < j; ) {
            res = max(res, min(height[i], height[j]) * (j - i));
            if (height[i] > height[j]) j --;
            else i ++;
        }

        return res;
    }

    public int min (int a, int b) {
        if (a <= b) return a;
        else return b;
    }

    public int max (int a, int b) {
        if (a >= b) return a;
        else return b;
    }
}