目录
基础知识
-
哈希表是根据关键码的值而直接进行访问的数据结构。
-
一般哈希表都是用来快速判断一个元素是否出现集合里。
哈希函数
总结
总结一下，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。
242. 有效的字母异位词——简单
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
class Solution {
public boolean isAnagram(String s, String t) {
//判断是否相等
if(s.length() != t.length()) return false;
//存入 减去
int[] a = new int[26];
for(int i=0; i<s.length(); ++i){
a[s.charAt(i)-'a']++;
a[t.charAt(i)-'a']--;
}
// 判断结果是否为0
for(int i=0; i<26; ++i){
if(a[i] != 0) return false;
}
return true;
}
}
383. 赎金信_简单
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b"
输出：false
示例 2：
输入：ransomNote = "aa", magazine = "ab"
输出：false
示例 3：
输入：ransomNote = "aa", magazine = "aab"
输出：true
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if(ransomNote.length() > magazine.length()) return false;
int[] a = new int[26];
for(char i : magazine.toCharArray()){
a[i -'a']++;
}
for(char i : ransomNote.toCharArray()){
a[i-'a']--;
if(a[i-'a'] < 0){
return false;
}
}
return true;
}
}
49. 字母异位词分组——中等
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
1、排序
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// 存放字符串
Map<String, List<String>> map = new HashMap<String, List<String>>();
for(String str : strs){
// 将字符串换为数组
char[] array = str.toCharArray();
// 数组排序
Arrays.sort(array);
// 返回字符串
String key = new String(array);
// 判断数组里有字符串吗
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
2、stream 的 grouping
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// // stream 的 groupingBy
// // groupingBy 算子计算完以后，返回的是一个 Map<String, List<String>>
// // Collector是专门用来作为Stream的collect方法的参数的。
// // collect 可以收集流中的数据到【集合】或者数组中去
// // groupingBy 根据字符串进行分组
return new ArrayList<>(Arrays.stream(strs)
.collect(Collectors.groupingBy(
str->{
//将str转换为数组
char[] array = str.toCharArray();
//排序
Arrays.sort(array);
//返回排序后的数组
return new String(array);
}
)).values()
);
}
}
438. 找到字符串中所有字母异位词——中等
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
方法一：滑动窗口
class Solution {
//方法一：滑动窗口
public List<Integer> findAnagrams(String s, String p) {
// 字符串长
int slen = s.length();
int plen = p.length();
// s<p 直接返回
if(slen < plen ){
return new ArrayList<Integer>();
}
// 定义数组存索引
List<Integer> num = new ArrayList<Integer>();
// 定义两个数组存字符串
int[] sCount = new int[26];
int[] pCount = new int[26];
// 先判断开始是否与p相同，返回0
for(int i=0; i<plen; ++i){
++sCount[s.charAt(i)-'a'];
++pCount[p.charAt(i)-'a'];
}
if(Arrays.equals(sCount,pCount)){
num.add(0);
}
// 继续判断下一位
for(int i=0; i<slen-plen; ++i){
--sCount[s.charAt(i)-'a'];
++sCount[s.charAt(i+plen)-'a'];
if(Arrays.equals(sCount,pCount)){
num.add(i+1);
}
}
return num;
}
}
349. 两个数组的交集
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
方法一：两个集合
class Solution {
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);
}
}
//将字符串转换成数组
int[] result = new int[resSet.size()];
int index = 0;
for(int i : resSet){
result[index++] = i;
}
return result;
}
}
350. 两个数组的交集 II——简单
力扣
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
方法一：哈希表
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
// 先循环 短的数组 将短数组存起来
if(nums1.length > nums2.length){
return intersect(nums2,nums1); // 交换位置
}
//创建 HashMap
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
// 将前一个数组存进去
// map.getOrDefault() 方法获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值
for(int i : nums1) {
int count = map.getOrDefault(i, 0) + 1;
map.put(i, count);
}
// 循环第二个数组 有相同的数，count值减1
// 再判断count的值是否为0，不为0，存入新的（key, value）,为0， 移除数
int index = 0;
int[] result = new int[nums1.length];
for(int i:nums2){
int count = map.getOrDefault(i, 0);
if(count>0){
result[index++] = i;
count--;
if(count>0){
map.put(i, count);
}else{
map.remove(i);
}
}
}
// 对一个已有的数组进行截取复制,copyOfRange(原数组，开始下标，结束下标)
return Arrays.copyOfRange(result, 0, index);
}
}
202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
输入：n = 2
输出：false
提示：
- 1 <= n <= 231 - 1
方法一：用哈希集合检测循环
class Solution {
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
while(n != 0 && !seen.contains(n)){
seen.add(n);
n = getNext(n);
}
return n==1;
}
private int getNext(int n){
int next = 0;
while(n>0){
int a = n % 10;
n = n / 10;
next += a * a;
}
return next;
}
}
