打卡Day6
- 1.哈希表理论基础
- 2.242.有效的字母异位词
- 2.349. 两个数组的交集
- 3.202. 快乐数
- 4.1. 两数之和
1.哈希表理论基础
文档讲解: 代码随想录
当遇到要快速判断一个元素是否出现在集合中时,要考虑哈希法。但是哈希法牺牲了空间换取了时间,因为要使用额外的数组、set、map来存放数据,才能实现快速的查找。
2.242.有效的字母异位词
题目链接:有效的字母异位词
文档讲解: 代码随想录
思路:新建两个数组存储s和t中字符出现的频率,依次进行比较。我用了之前209.长度最小的子数组的思路。
class Solution {public boolean isAnagram(String s, String t) {char[] sAr = s.toCharArray();char[] tAr = t.toCharArray();int sLen = s.length();int tLen = t.length();int[] ss = new int[128];int[] tt = new int[128];for(int i = 0; i < sLen; i++){ss[sAr[i]]++;}for(int i = 0; i < tLen; i++){tt[tAr[i]]++;}for(int i = 0; i < 128; i++){if(ss[i] != tt[i]){return false;}}return true;}
}
标答的思路改进:新建一个数组,记录s中字符出现的频率,数组的大小只需要26就行。数组是一个简单的哈希表,需要把字符映射到数组也就是哈希表的索引下标上。在遍历t的时候,对t中出现的字符映射到哈希表索引上的数值做-1操作。最后检查记录数组的元素是否全为0。
class Solution {public boolean isAnagram(String s, String t) {int[] record = new int[26];int sLen = s.length();int tLen = t.length();for(int i = 0; i < sLen; i++){record[s.charAt(i) - 97]++;}for(int i = 0; i < sLen; i++){record[t.charAt(i) - 97]--;}//for(variable : collection) statementfor(int i: record){if(i != 0){return false;}}return true;}
}
时间复杂度都为O(M+N)
2.349. 两个数组的交集
题目链接:两个数组的交集
文档讲解: 代码随想录
注意点:
(1)nums1 == null 和 nums.length == 0 的区别
nums1 = null 意味着数组变量并没有指向任何有效的数组对象,不占用内存空间,指针为空;
nums.length = 0 意味着nums 是一个有效的数组对象,但数组中并没有任何元素。
(2)使用数组来做哈希的题目是因为题目限制了数值的大小。这道题如果用数组做,思路为统计每个数出现的频率,若某个数字出现的频率在两个数组中都大于0,则该数字属于交集。
import java.util.HashSet;
import java.util.Set;class Solution {public int[] intersection(int[] nums1, int[] nums2) {if(nums1 == null || nums1.length == 0 || nums2.length == 0 || nums2 == null){return new int[0];}Set<Integer> set1 = new HashSet();Set<Integer> resSet = new HashSet();for(int i : nums1){set1.add(i);}for(int i : nums2){if(set1.contains(i)){resSet.add(i);}}//将结果集合转变为数组//方法1//return resSet.stream().mapToInt(x -> x).toArray();//方法2int[] arr = new int[resSet.size()];int j = 0;for(int i : resSet){arr[j++] = i;}return arr;}
}
3.202. 快乐数
题目链接:快乐数
文档讲解: 代码随想录
class Solution {public boolean isHappy(int n) {Set<Integer> record = new HashSet<>();while(n != 1 && !record.contains(n)){record.add(n);n = getSum(n);}return n == 1; }private int getSum(int n){int res = 0;while(n > 0){int temp = n % 10;res += temp * temp;n = n / 10; }return res;}
}
4.1. 两数之和
题目链接:两数之和
文档讲解: 代码随想录
//暴力求解
class Solution {public int[] twoSum(int[] nums, int target) {int[] arr = new int[2];for(int i = 0; i < nums.length - 1; i++){for(int j = i + 1; j < nums.length; j++){if(nums[i] + nums[j] == target){arr[0] = i;arr[1] = j;}}}return arr;}
}
(1)为什么会想到用哈希表
需要查询一个元素是否出现过,或者一个元素是否在集合中。在此题中,对于元素A,我们需要找是否存在另一个元素B,使得A + B =9。
(2)哈希表为什么用map
由于题目需要返回下标,则需要记录值与下标,需要使用key value结构来存放,key放值,value放下标。map用来存放我们遍历访问过的元素。
//哈希表
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> map = new HashMap<>();for(int i = 0; i < nums.length; i++){int temp = target - nums[i];if(map.containsKey(temp)){res[0] = i;res[1] = map.get(temp);break;}map.put(nums[i], i);}return res;}
}