代码随想录算法训练营第六天|哈希表理论基础、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 = 828^2 + 2^2 = 686^2 + 8^2 = 1001^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;    }}