6.哈希
一.宝石与石头
1.题目描述：
给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。
2.示例：
输入: J = "aA", S = "aAAbbbb"
输出: 3
S 和 J 最多含有50个字母。
J 中的字符不重复。
3.解:
（1）我的答案：
class Solution {
public int numJewelsInStones(String jewels, String stones) {
int nums=0;
Set<Character> jewelSet = new HashSet<Character>();
for (int i = 0;i<jewels.length();i++){
jewelSet.add(jewels.charAt(i));
}
for (int i=0;i<stones.length();i++){
if (jewelSet.contains(stones.charAt(i))){
nums++;
}
}
return nums;
}
}（2）网友答案：
class Solution {
public int numJewelsInStones(String J, String S) {
int len = J.length();
int[] type = new int[256];
for(int i = 0; i < len; i++){
type[J.charAt(i)] = 1;
}
int ans = 0;
len = S.length();
for(int i = 0; i < len; i++){
ans += type[S.charAt(i)];
}
return ans;
}
}4.总结：
常规的思路是哈希集合或者两个for循环遍历，总之这两种方案是不能及兼容时间复杂度又兼容空间复杂度的。但是网友的答案就很灵巧，利用了字符可以转换为int类型的原理，不仅时间复杂度小，空间复杂度也小。
二.存在重复元素
1.题目描述：
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。。
2.示例：
输入: [1,2,3,1]
输出: true
3.解:
（1）我的答案：
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> a = new HashSet<Integer>();
boolean b=false;
for (int i=0;i<nums.length;i++){
if(a.contains(nums[i])) b=true;
else a.add(nums[i]);
}
return b;
}
}（2）网友答案：
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> a = new HashSet<Integer>();
for (int i=0;i<nums.length;i++){
if(!a.add(nums[i])) return true;
}
return false;
}
} public boolean containsDuplicate(int[] nums) {
Set<Integer> data = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
data.add(nums[i]);
}
if (data.size() == nums.length) {
return false;
}
return true;
}class Solution {
public boolean containsDuplicate(int[] nums) {
//遇事不决先排序
Arrays.sort(nums);
int m = 0;
for(int i = 1; i < nums.length; ++i){
if(nums[i] == nums[m]){
//存在重复元素
return true;
} else {
++m;
}
}
//不存在
return false;
}
}4.总结：我的方法思路是对的，正常的哈希集合，但是需要优化一下下，比如网友答案的第一个答案中，.add()方法本身就具有去重复的功能，这一点，第二个答案也体现了。所以不需要再去调用.contains()方法去判断是否包含当前元素了。另外最后一个答案的排序做法也很巧妙，排序之后，如果存在重复元素，那么一定存在相邻的两个元素的值相等。
三.存在重复元素ii
1.题目描述：
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
2.示例：
输入: nums = [1,2,3,1], k = 3
输出: true
3.解:
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashMap<Integer,Integer> a = new HashMap<>();
for (int i=0;i<nums.length;i++){
if(a.containsKey(nums[i])&&(i-a.get(nums[i]))<=k) return true;
else a.put(nums[i],i);
}
return false;
}
}class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashSet<Integer> a = new HashSet<>();
for (int i=0;i<nums.length;i++){
if(!a.add(nums[i])) return true;
a.add(nums[i]);
if(i>=k)a.remove(nums[i-k]);
}
return false;
}
}4.总结:
在这种情况下有两种方法：
（1）使用哈希map/哈希table，根据key找出value，key设置为值，value设置为数组的下标。
（2）这种方法利用了哈希集合的最独特的特点，即它的大小是可变的，可随意添加和删除指定元素。因此诞生了滑窗法，滑窗法顾名思义，滑块内的元素个数永远是固定大小的，先在末尾添加一个元素，再删除头部的元素，这样可以模拟滑块的前进操作。
四.存在重复元素iii
1.题目描述：
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。如果存在则返回 true，不存在返回 false。
2.示例：
输入：nums = [1,2,3,1], k = 3, t = 0
输出：true
3.解:
后面再做
4.总结:
五.变位词组
1.题目描述：
编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。
2.示例：
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
3.解:
（1）我的答案：
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> hashMap = new HashMap<>();
for (int i = 0; i < strs.length; i++) {
char[] ele = strs[i].toCharArray();
Arrays.sort(ele);
if (!hashMap.containsKey(String.valueOf(ele))) hashMap.put(String.valueOf(ele), new ArrayList<>());
hashMap.get(String.valueOf(ele)).add(strs[i]);
}
List<List<String>> res = new ArrayList<>(hashMap.values());
return res;
}
}4.总结:
学到哈希的两个新用法，1.hash的value可以是集合，每次添加元素时，先判断有没有key，没有就创建一个键值对，然后用hash对象.get(key).add(element)即可。2.在创建ArrayList时候可以直接传值new ArrayList<>(value),value甚至可以是集合。
六.T9键盘
1.题目描述：
在老式手机上，用户通过数字键盘输入，手机将提供与这些数字相匹配的单词列表。每个数字映射到0至4个字母。给定一个数字序列，实现一个算法来返回匹配单词的列表。你会得到一张含有有效单词的列表。映射如下图所示：
2.示例：
输入: num = "8733", words = ["tree", "used"]
输出: ["tree", "used"]
输入: num = "2", words = ["a", "b", "c", "d"]
输出: ["a", "b", "c"]
num.length <= 1000
words.length <= 500
words[i].length == num.length
num中不会出现 0, 1 这两个数字
3.解:
class Solution {
public List<String> getValidT9Words(String num, String[] words) {
HashMap<Character, Character> tire = new HashMap<>(26);
tire.put('a', '2');
tire.put('b', '2');
tire.put('c', '2');
tire.put('d', '3');
tire.put('e', '3');
tire.put('f', '3');
tire.put('g', '4');
tire.put('h', '4');
tire.put('i', '4');
tire.put('j', '5');
tire.put('k', '5');
tire.put('l', '5');
tire.put('m', '6');
tire.put('n', '6');
tire.put('o', '6');
tire.put('p', '7');
tire.put('q', '7');
tire.put('r', '7');
tire.put('s', '7');
tire.put('t', '8');
tire.put('u', '8');
tire.put('v', '8');
tire.put('w', '9');
tire.put('x', '9');
tire.put('y', '9');
tire.put('z', '9');
List<String> res = new ArrayList<>();
for (String str : words) {
boolean tip = true;
for (int i = 0; i < str.length(); i++) {
if (num.charAt(i) != tire.get(str.charAt(i))) {
tip = false;
break;
}
}
if (tip) res.add(str);
}
return res;
}
}4.总结
属于暴力解法了
查看1道真题和解析