算法训练营day05 | {242.有效的字母异位词, 349.两个数组的交集, 202.快乐数，1.两数之和}

第三章哈希表-part01，以O(1)时间快速判断一个元素是否出现在集合里。

242. 有效的字母异位词

• 题目链接：242. 有效的字母异位词
• 状态：数组也是简单的哈希表，且题目条件说仅包含小写字母，维护一个长度为26的数组即可，简单。

1.1 解题过程

▶

数组存储

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        int[] val= new int[26];
        int n = sArr.length;
        for (int i = 0; i < n; i++) {
            val[sArr[i] - 'a'] += 1;
            val[tArr[i] - 'a'] -= 1;
        }

        for (int i = 0; i < 26; i++) {
            if(val[i] != 0) return false;
        }
        return true;
    }
}

▶

Map存储

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        Map<Character, Integer> map = new HashMap<>();
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            map.put(sArr[i], map.getOrDefault(sArr[i], 0) + 1);
            map.put(tArr[i], map.getOrDefault(tArr[i], 0) - 1);
        }
        // 遍历map
        for(Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (entry.getValue() != 0) {
                return false;
            }
        }
        return true;
    }
}

• 为什么要用Map存储？因为key用来保存出现过的字母，value保存出现的次数。

349. 两个数组的交集

• 题目链接：349. 两个数组的交集
• 状态：用HashSet，简单。

2.1 解题过程

• 主要思想是用哈希表存储元素，可以在O(1)时间内判断一个元素是否在集合中，比暴力的枚举时间复杂度更低。
  ▶

  两个数组的交集

  class Solution {
      public int[] intersection(int[] nums1, int[] nums2) {
          Set<Integer> res = new HashSet<>();
          Set<Integer> set1 = new HashSet<>();
          for(int num: nums1) {
              set1.add(num);
          }
          for(int num : nums2) {
              if (set1.contains(num)) {
                  res.add(num);
              }
          }
          return res.stream().mapToInt(Integer::intValue).toArray();
      }
  }

202. 快乐数

• 题目链接：202. 快乐数
• 状态：没做出来。

3.1 解题过程

• 一开始就是想顺着题目模拟获取下一个平方和的过程，缺乏探索，应该继续考虑以下三钟可能：
  1. 最终会得到1。
  2. 最终会进入循环。
  3. 值会越来越大，最后接近无穷大。
• 第三种情况是否可能呢？可以仔细想一想，每一位数的最大数字的next数是多少。排除第三种可能
• 第二种可能，循环表示之前出现过的数字再次出现，此时无解，其实和昨天的《环形链表判断》一模一样吧，解法有两种：
  1. 用哈希表检测循环
  2. 用快慢指针检测循环（getNext(n)构成一个隐式的链表）

▶

解法一哈希表

class Solution {
    private int getNext(int k) {
        int sum = 0;
        while(k > 0) {
            sum += (k % 10) * (k % 10);
            k /= 10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while(n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);

        }
        return n == 1;
    }
}

▶

解法二快慢指针

class Solution {
    private int getNext(int k) {
        int sum = 0;
        while(k > 0) {
            sum += (k % 10) * (k % 10);
            k /= 10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        int slowRunner = n;
        int fastRunner = getNext(n);
        while(fastRunner != 1 && slowRunner != fastRunner) {
            slowRunner = getNext(slowRunner);
            fastRunner = getNext(getNext(fastRunner));
        }
        return fastRunner == 1;
    }
}

1. 两数之和

• 题目链接：1. 两数之和
• 文档讲解：代码随想录–1. 两数之和
• 状态：对哈希表的使用还是不够熟练。

4.1 解题过程

• 为什么会想到用哈希表？
  • target - x能O(1)快速找到，对比暴力的枚举。
• 为什么用Map？
  • 因为本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标。
• map用来存什么的？
  • 已经遍历过的元素存入其中。

▶

两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> prev = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int leave = target - nums[i];
            if (prev.containsKey(leave)) {
                 return new int[]{prev.get(leave), i};
            }
            prev.put(nums[i], i);
        }
        return null;
    }
}

5. Java API小结

• 对于String类型的字符串，不能直接通过下标索引取出字符，一般有两种方式：

  String str = "leetcode";
  
  char c = str.charAt(0);  // 返回下标为0的字符
  char[] chars = str.toCharArray();  // 返回一个字符数组

• 对于一个集合类型，如Set集合，要转为int[]数组，可以通过stream流式编程，但要注意两个map函数的区别：

  • map(): 返回的是Stream<Integer>，由此toArray()返回Object[];
  • mapToInt(): 返回的是基本输入流IntStream，由此toArray()返回int[]，不需要再拆箱。

  • Set<Integer> res = new HashSet<>();
    
    // 匿名内部类写法
    return res.stream().mapToInt(new ToIntFunction<Integer>() {
    
            @Override
            public int applyAsInt(Integer x) {
                return x.intValue();
            }
        }).toArray();
    
    // lambda表达式写法
    return res.stream().mapToInt(x -> x.intValue()).toArray();
    
    // 类名::实例方法
    return res.stream().mapToInt(Integer::intValue).toArray();