day05 | 有效的字母异位词、两个数组的交集、快乐数、两数之和

有效的字母异位词

题目链接：242. 有效的字母异位词

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

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

思路：由于s和t都是由26个小写字母构成，数量很少，直接定义一个26空间的数组即可

数组下标：表示每个字母，0-'a',1-'b'...等

每个下标对应的数字：表示s字符串和t字符串中某字母出现的次数之差

若数组中的数字都是0，则为true；否则，返回false；

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] arrs = new int[26];
        for(char ch : s.toCharArray())
            arrs[ch - 'a']++;
        for(char ch : t.toCharArray())
            arrs[ch - 'a']--;
        for(int num : arrs)
            if(num != 0)return false;
        return true;
    }
}

两个数组的交集

题目链接：349. 两个数组的交集

---给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

思路：本题要求输出结果每个元素是唯一的，明显需要有去重操作，所以可以定义两个set来解决。

set1：用于保存nums1数组中的唯一元素

set2：用于保存nums1和nums2两数组交集的唯一元素

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        for (int num : nums1) 
            set1.add(num);

        for (int num : nums2) 
            if (set1.contains(num)) 
                set2.add(num);
        
        int [] result = new int[set2.size()];
        int index = 0;
        for (int num : set2) {
            result[index++] = num;
        }
        return result;
    }
}

其实本题也可以用一个数组和一个set来完成，用时更短！！

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        int[] arr = new int[1001];
        //将nums1出现的数字赋值为1，相当于另类的去重了
        for(int num : nums1)
            arr[num] = 1;

        for(int num : nums2)
            if(arr[num] != 0)//表示num是两数组的交集元素
                set.add(num);//set会自动去重
        
        // return set.stream().mapToInt(x -> x).toArray();//耗时3s,空间42.42

        int[] res = new int[set.size()];
        int index = 0;
        for(int num : set)
            res[index++] = num;
        return res;//耗时1ms，空间42.07
    }
}

快乐数

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

「快乐数」 定义为：

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

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

思路：题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现！！所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        while(!set.contains(n)){
            if(n == 1)return true;
            set.add(n);
            n = getSum(n);
        }
        return false;
    }
    public int getSum(int n){
        int num;
        int sum = 0;
        while(n != 0){
            num = n % 10;
            sum += num * num;
            n /= 10;
        }
        return sum;
    }
}

两数之和

题目链接：1. 两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

 思路：本题我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，所以我们需要定义一个map来解决

key：用来存放遍历的元素

value：用来存放遍历元素的下标

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            //如果map中存在遍历元素所需要的“搭档”，就直接返回对应下标即可
            if(map.containsKey(target - nums[i]))return new int[]{map.get(target - nums[i]),i};
            map.put(nums[i],i);
        }
        return null;
    }
}