哈希表之哈希数组、HashSet

题目简述：判断两个字符串是否都是由类型且数目相同的字符组成的（这里字符全是小写英文字母）。
思路：键和数组索引联系起来，x-'a'的形式，自动换成数组索引，分别统计两个单词的字母频次（数组记录），然后各单词依次比较即可。

class Solution {
    public boolean isAnagram(String s, String t) {
       int[] num1 = new int[26]; 
       int[] num2 = new int[26]; 
       //统计s中字母的频次
       for(char i:s.toCharArray()){
        num1[i-'a']++;
       } 
       //统计t中字母的频次      
       for(char i:t.toCharArray()){
        num2[i-'a']++;
       }
       //比较两个频次数组
       for(int i =0;i<26;i++){
            if(num1[i]!=num2[i]){
                return false;
            }
       }
       return true;
    }
}

注：本题可以只用一个数组进行字母统计，前一个++，后一个在统计后的数组各字母位--即可，最后判断数组是否有非零的字母。

温习内容：

• toCharArray()可将字符串转变为char数组；
• 遍历字符串中的某一位置可以用charAt(index);
• 字符串长度得用size()函数获取。

题目简述：判断字符串A 能不能由字符串B 里面的字符构成（这里字符全是小写英文字母）。
思路：和上一题一样，只需验证字符串A中是否有B不含有的字母即可。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] num = new int[26]; 
        for(char i:ransomNote.toCharArray()){
            num[i-'a']++;
        }       
        for(char i:magazine.toCharArray()){
            num[i-'a']--;
        }
        for(int i =0;i<26;i++){
            if(num[i]>0){
                return false;
            }
       }
       return true;
    }
}

题目描述：求两个数组的相同元素并将每种输出一次。

• 数组法

  • 思路：分别统计两个字符串中的字母频次，只要某个字母在两个字符串中都出现过（>0）,即是交集元素。不过存储交集的数据结构不能为数组，因为交集大小未知，初始化大了返回的有多余的0，所以考虑动态数组。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] hash1 = new int[1001];
        int[] hash2 = new int[1001];
        for(int i : nums1)
            hash1[i]++;
        for(int i : nums2)
            hash2[i]++;
        List<Integer> resList = new ArrayList<>();
        for(int i = 0; i < 1001; i++)
            if(hash1[i] > 0 && hash2[i] > 0)
                resList.add(i);
        return  resList.stream().mapToInt(x -> x).toArray();
    }
}

• HashSet法

  • hashSet中一种元素只出现一次，所以可以先提取A中的各类型元素形成特征集，然后根据特征集查询B中的元素。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Set<Integer> result  = new HashSet<>();
        //遍历数组1放入set
        for (int i : nums1) {
            set.add(i);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素放入result(比较查找且去重)
        for (int i : nums2) {
            if (set.contains(i)) {
                result.add(i);
            }
        }
        return result.stream().mapToInt(x -> x).toArray();
    }
}

上述两种方法中最后都有这么一句stream().mapToInt(x -> x).toArray()，这里再开个小章节总结一下。

题目描述：给定一个数n,要求将每一位平方后相加得到一个新数，看能否变成1
思路：可以看成一个不断生成数据的动态数组，这个无非两种情况，一是最后变成1，二是中间某个数在前面出现过形成死循环了.

• 判断一个数是否出现过，所以采用HashSet的contains函数（可以直接对空表检查）
• 还需要一个循环不断去判断，首先判断新出的数是否直接是1了，是则返回；如果不是1再判断是否在死循环里，在循环里即返回此时的值，false；都不是则记录新的值。

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        //只记录非1且从未出现的新值
        while(n!=1&&!record.contains(n)){
            record.add(n);
            n = getSum(n);
        }
        return n==1;
    }
    //按位求和
    public int getSum(int n){
        int sum = 0;
        while(n>0){
            sum +=(n%10)*(n%10);
            n /=10;
        }
        return sum;
    }
}