代码随想录算法训练营第六天|哈希表理论基础、242.有效的字母异位词两个数组的交集、202. 快乐数、1. 两数之和

242.有效的字母异位词

力扣题目链接(opens new window)

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = "anagram", t = "nagaram" 输出: true

示例 2: 输入: s = "rat", t = "car" 输出: false

说明: 你可以假设字符串只包含小写字母。

思路：

哈希表的方式，用key-value的方式来保存字符串中字母出现的个数。这里的一个难点就是如何选择字母key的表现形式。Java中存在一个方法就是charAt()方法，返回指定索引处的字符。而s.charAt(index) - ‘a’ 会返回一个数字，用数字代表字母key会方便很多。

为了判断是否为字母异位词，只需要将s字符串的字母出现次数保存在recode数组中，再将t字符串的字母出现次数减去即可。

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] record = new int[26];     //字符串一定是26个字母的
        for(int i = 0; i < s.length(); i++){
            record[s.charAt(i) - 'a']++;      //将s中出现的字母次数保存到record表中
        }
        for(int j = 0; j < t.length(); j++){
            record[t.charAt(j) - 'a']--;
        }

        for(int count : record){
            if(count != 0){
                return false;
            }
        }
        return true;
    }
}

349. 两个数组的交集

力扣题目链接(opens new window)

题意：给定两个数组，编写一个函数来计算它们的交集。

说明： 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。

思路：

一想到不重复元素且无序，首先想到的是Set集合，关于Java中Set集合的种种操作，要熟记于心。

题目要求最终返回数组，需要将求到的集合再转成数组。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1 == null || nums2 == null) return new int[0];
        //交集即为不重复无序元素，考虑用Set集合
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();   
        for(int i : nums1){
            set1.add(i);
        }
        for(int j : nums2){
            if(set1.contains(j)){
                set2.add(j);     //set2中保存着交集元素
            }
        }

        int[] arr = new int[set2.size()];    //将集合里的元素放到数组里去
        int j = 0;
        for(int i : set2){
            arr[j++] = i;
        }
        return arr;
    }
}

第202题. 快乐数

力扣题目链接(opens new window)

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为  1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

思路:

第一个难点，题目说是无限循环，意味着这个n会重复出现，判断一个元素有没有重复，需要用到Set集合

第二个难点，取数值各个位上的单数操作，要牢记。

class Solution {
    public boolean isHappy(int n) {
        //需要观察这个数是否一直在循环重复，需要用到Set集合
        Set<Integer> set = new HashSet<>();
        while(n != 1 && !set.contains(n)){
            set.add(n);
            n = getNext(n);
        }

        return n == 1;
    }

    private int getNext(int n){
        int res = 0;
        while(n > 0){     
            int tmp = n % 10;     //最后面一位
            res += tmp * tmp;
            n /= 10;
        }
        return res;
    }
}

1. 两数之和

力扣题目链接(opens new window)

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

思路：

1、为什么用哈希表

当想到要一个元素是否出现过，或者是否在一个集合中，就要想到用哈希表。

2、为什么用map

需要想到这个元素是否出现过，还得知道元素下标。用map中的key-value结构来保存，key保存元素，value保存元素下标。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        if(nums == null) return res;

        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int tmp = target - nums[i];
            if(map.containsKey(tmp)){
                res[0] = i;
                res[1] = map.get(tmp);
                break;
            }
            map.put(nums[i],i);
        }
        return res;
    }
}