算法学习day06哈希表part01-242、349、202、1

package SecondBrush.Hash;
/**
 * 242.有效字母异位词
 * 现在看到这个题目能想到怎么做，但是具体不知道怎么写
 * 大致思路自己先描述一下：
 * 就是建立一个hash表，然后遍历s，写进表中，遍历t，减去对应的数
 * hash表就可以理解为数组
 */

public class ValidAnagram_242 {
    public boolean is_anagram(String s, String t) {
        int[] recode = new int[26];

        for (int i = 0; i < s.length(); i++) {
            recode[s.charAt(i) - 'a']++;
        }

        for (int i = 0; i < t.length(); i++) {
            recode[t.charAt(i) - 'a']--;
        }
        for (int count : recode) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }

}

package SecondBrush.Hash;

import java.util.HashSet;
import java.util.Set;

/**
 * 349. 两个数组的交集
 * 刚开始是没思路，只能看一下题解，
 * 梳理一下思路：
 * 定义两个set，
 * 遍历第一个数组，存入set中，然后遍历第二个数组，判断哈希表中是否有该元素，
 * 如果有将该元素加入至新set中，将set转成数组，返回数组
 */

public class IntersectionOfTwoArrays_349 {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        //遍历数组1
        for (int i : nums1) {
            set1.add(i);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for (int i : nums2) {
            if (set1.contains(i)) {
                resSet.add(i);
            }
        }

        //方法2：另外申请一个数组存放setRes中的元素,最后返回数组
        int[] arr = new int[resSet.size()];
        int j = 0;
        for (int i : resSet) {
            arr[j++] = i;
        }

        return arr;
    }
}

package SecondBrush.Hash;

import java.util.HashSet;
import java.util.Set;

/**
 * 202. 快乐数
 * 快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，
 * 也可能是 无限循环 但始终变不到 1。
 * 如果 可以变为  1，那么这个数就是快乐数。
 *
 * 刚看到还是没思路，操。
 * 首先需要设计怎么计算每次每个位置上的平方和,想不起来，之前明明看过一遍
 *
 * */
public class HappyNumber_202 {

    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        while (n != 1 && !record.contains(n)) {
            record.add(n);
            n = getNextNum(n);
        }
        return n == 1;
    }
    public int getNextNum(int n){
        int sum = 0;
        while (n > 0) {
            int temp = n % 10;
            sum += temp * temp;
            n = n / 10;
        }
        return sum;
    }

}

package SecondBrush.Hash;

import java.util.HashMap;
import java.util.Map;

/**
 * 1.两数之和
 * 给定一个整数数组 nums和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。
 * 再次看到的时候，还是写不出来，知道具体的思想。
 * */
public class TwoSum_1 {
    public int[] twoSum(int[] nums, int target){
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i< nums.length; i++) {
            if(map.containsKey(target - nums[i])) {
                return new int[] {map.get(target-nums[i]),i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }

}