代码随想录第6天

新的一周开始啦！
哈希表的关键：快速查找用哈希

242.有效的字母异位词

题目描述：
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

题解：Hashmap

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] record = new int[26];
        for (char c: s.toCharArray()){
            record[c-'a'] = record[c-'a']+1;
        }
        for (char c: t.toCharArray()){
            record[c-'a'] = record[c-'a']-1;
        }
        // for (int i = 0; i<record.length ; i++){
        //     if (record[i] !=0) return false;
        //迭代器，i为record中存的值，不是index
                for(int i: record) {
            if (i!=0)  return false;  
            }
        return true;    
    }    
}

思考：

为什么使用s.toCharArray()来遍历字符串数组，而不是用length()来循环？

因为前者只需要遍历数组一次即可，而如果使用for (int i = 0; i<record.length ; i++)，则每次循环都需要遍历数组一次，如果字符串很长，则时间复杂度较大。
toCharArray和CharAt的区别
前者是将原来的数组进行复制，再将复制的数组返回给函数；后者则直接返回数组中的某个字符；

349. 两个数组的交集

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

解题思路：

1.遍历数组1。
2.再去遍历数组2，判断数组2中的每一个元素是否在数组1中出现；
·如果出现，则存入结果
·如果没出现，就跳过
3.返回结果list

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> res = new HashSet<>();

        for (int i : nums1) {
            set1.add(i);
        }
        
        for (int i : nums2) {
            if (set1.contains(i)) {
                res.add(i);
            }
        }
        //将结果几何转成数组
        //数组定义时要设定数组的长度
        int[] resArr = new int[res.size()];
        int index = 0;
        for (int i : res) {
            resArr[index++] = i;
        }
        return resArr;
    }
}

202.快乐数

编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：

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

解题思路：

通过哈希表来检测循环。
1.用哈希表来检测sum是否重复出现
2.通过取余操作来获取int整数的各个单位数，来计算每个单位数的平方和

class Solution {
    //设置函数来获取下一个值每一单位数的平方和
    private int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            //取余操作：1223 % 10 = 3；1223/10=122 122%10=2...
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }       

    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        //如果之前计算的sum没有出现过，则写入哈希表；如果出现过，则表明会进入循环，得不到1；
        while (n != 1 && !record.contains(n)) {
            record.add(n);
            n = getNext(n);
        }
        return n==1;
        }
    }

解法二：龟兔赛跑/快慢指针

解题思路：
判断是否有循环，可以看着这个链表是否存在cycle，也就是环形链表这一题
1.设置快慢指针，初始值不能相同
2.快指针走两步，这边看成嵌套调用2次getNext函数；
慢指针走一步，调用一次getNext；
3.如果存在循环，快慢指针一定会在环内相遇，则这个数不是快乐数
4.如果不存在循环，快指针一定先一步成为1，返回fast即可

class Solution {
    //设置函数来获取下一个值每一单位数的平方和
    private int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            //取余操作：1223 % 10 = 3；1223/10=122 122%10=2...
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }       

    //龟兔赛跑算法，与题142思想相同
    public boolean isHappy(int n) {
        //fast和slow初始值不能相同，原因见题141
        int slow = n;
        int fast = getNext(n);
        while (fast != 1 && fast != slow) {
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }
        return fast == 1;
        }
    }

1. 两数之和

题目描述：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

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

        Map<Integer, Integer> hashTable = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int temp = target-nums[i];
            //查看target-x的值是否在哈希表中，在的话写入res表内
            if (hashTable.containsKey(temp)) {
                res[1] = i;
                res[0] = hashTable.get(temp);
            }
            hashTable.put(nums[i],i);
        }
        return res;
    }
}

代码随想录第6天