哈希表
哈希表(Hash table),也叫散列表，是根据关键码值(Key value)而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数(Hash Function),存放记录的数组叫做哈希表(或散列表)。
Map:key-value对，key不重复
new HashMap()/new TreeMap()
map.set(key,value)
map.get(key)
map.has(key)
map.size();
map.clear();
Set:不重复元素的集合
new HashSet()/new TreeSet()
set.add(value)
set.delete(value)
set.hash(value)
1.Python code
list_x = [1,2,3,4]
map_x = {'jack':100,'张三':80,'selina':90,...}
set_x = {'jack','selina','Andy'}
set_y = set(['jack','selina','jack'])
有效的字母异味词
https://leetcode-cn.com/problems/valid-anagram
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 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;
char[] ss = s.toCharArray();
char[] tt = t.toCharArray();
Arrays.sort(ss);
Arrays.sort(tt);
return Arrays.equals(ss,tt);
}
}
方法二:哈希表
- 1.统计次数是否等于0
public boolean isAnagram0(String s,String t){
if (s.length() != t.length()) return false;
char[] ss = s.toCharArray();
char[] tt = t.toCharArray();
int[] n = new int[26];
for (int i = 0;i<s.length();i++){
n[ss[i] - 'a']++;
n[tt[i] - 'a']--;
}
for (int a: n) {
if (a != 0)
return false;
}
return true;
}
- 2.统计一个字符串，后减一是否小于0
public boolean isAnagram1(String s,String t){
if (s.length() != t.length()) return false;
int[] n = new int[26];
for (int i=0;i<s.length();i++){
n[s.charAt(i) - 'a']++;
}
for (int j=0;j<s.length();j++){
n[t.charAt(j)-'a' ]--;
if(n[t.charAt(j) - 'a'] < 0)
return false;
}
return true;
}
字母异味词分组
https://leetcode-cn.com/problems/group-anagrams/
方法一:排序
public List<List<String>> groupAnagrams(String[] strs) {
if (strs.length == 0) return new ArrayList<>();
Map<String,List> ans = new HashMap<String, List>();
for (String s : strs) {
char[] ss = s.toCharArray();
Arrays.sort(ss);
String str = String.valueOf(ss);
if (!ans.containsKey(str))
ans.put(str,new ArrayList());
ans.get(str).add(s);
}
return new ArrayList(ans.values());
}
方法二:按计数分类
public List<List<String>> groupAnagrams0(String[] strs) {
if (strs.length == 0) return new ArrayList<>();
Map<String,List> ans = new HashMap<String, List>();
for (String str:strs){
char[] ss = str.toCharArray();
int[] tt = new int[26];
for (int i=0;i<ss.length;i++){
tt[ss[i] - 'a']++;
}
StringBuilder sb = new StringBuilder("");
for (int j=0;j<26;j++){
sb.append('#');
sb.append(tt[j]);
}
String sbStr = sb.toString();
if (!ans.containsKey(sbStr)) ans.put(sbStr,new ArrayList());
ans.get(sbStr).add(str);
}
return new ArrayList(ans.values());
}
两数之和
https://leetcode-cn.com/problems/two-sum/
方法一:暴力法
public int[] twoSum(int[] nums, int target) {
int[] sums = new int[2];
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
sums[0] = i;
sums[1] = j;
}
}
}
return sums;
}
方法二:两遍哈希法
为了对运行时间复杂度进行优化，我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在，我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。
通过以空间换取速度的方式，我们可以将查找时间从 O(n)O(n) 降低到 O(1)O(1)。哈希表正是为此目的而构建的，它支持以 近似 恒定的时间进行快速查找。我用“近似”来描述，是因为一旦出现冲突，查找用时可能会退化到 O(n)O(n)。但只要你仔细地挑选哈希函数，在哈希表中进行查找的用时应当被摊销为 O(1)O(1)。
一个简单的实现使用了两次迭代。在第一次迭代中，我们将每个元素的值和它的索引添加到表中。然后，在第二次迭代中，我们将检查每个元素所对应的目标元素（target - nums[i]target−nums[i]）是否存在于表中。注意，该目标元素不能是 nums[i]nums[i] 本身！
public int[] twoSum0(int[] nums, int target){
HashMap<Integer,Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
hashMap.put(nums[i],i);
}
for (int j = 0; j < nums.length; j++){
int complete = target - nums[j];
if (hashMap.containsKey(complete) && hashMap.get(complete) != j)
return new int[]{j,hashMap.get(complete)};
}
throw new IllegalArgumentException("No two sum solution");
}
方法三:一遍哈希法
事实证明，我们可以一次完成。在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。
public int[] twoSum1(int[] nums, int target){
HashMap<Integer,Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complete = target - nums[i];
if (hashMap.containsKey(complete))
return new int[]{hashMap.get(complete), i};
hashMap.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
