无锡有人代做淘宝网站吗,石家庄网络推广的优势,ueeshop建站费用,刷评论网站推广题目与题解 参考资料#xff1a;哈希表理论基础 Tips#xff1a; 一般哈希表都是用来快速判断一个元素是否出现集合里哈希表生成原理#xff1a;先通过哈希函数将变量映射为hashcode#xff0c;如果二者hashcode相同#xff0c;再通过哈希碰撞方法#xff08;拉链法…题目与题解 参考资料哈希表理论基础 Tips 一般哈希表都是用来快速判断一个元素是否出现集合里哈希表生成原理先通过哈希函数将变量映射为hashcode如果二者hashcode相同再通过哈希碰撞方法拉链法线性探测法将新变量的hashcode放入链表或哈希表的其他空位中常见哈希结构数组集合set映射map 242.有效的字母异位词 题目链接242.有效的字母异位词 代码随想录题解242.有效的字母异位词 解题思路 翻译过来就是要判断两个字符串中各个字符的数量是否相同首先排除两个字符串长度不相同的情况。当两个字符串长度相同时统计它们字符的数量最简单的做法就是同时遍历两个字符串先用哈希表记录其中一个字符串中每个字符的数量然后根据另一个字符串的当前的字符减去哈希表中相应字符对应的数量。最后判断哈希表中每个字符的数量是否正好都为0即可。
class Solution {public boolean isAnagram(String s, String t) {if(s.length() ! t.length()) return false;int[] count new int[26];for (int i 0; i s.length(); i) {count[s.charAt(i) - a];count[t.charAt(i) - a]--;}for (int i 0; i count.length; i) {if (count[i] ! 0) return false;}return true;}
}
注意点 因为这里只需要统计字符的数量所以哈希表用数组足矣效率更高。
349. 两个数组的交集 题目链接349. 两个数组的交集 代码随想录题解349. 两个数组的交集 解题思路 交集是个很典型的集合概念所以这套题的哈希表用集合非常合适。 一开始想直接求出两个数组对应的集合然后再用集合自带的函数求出交集。但是凭空写的时候不知道怎么把数组直接转换为集合也不知道求交集的函数于是偷偷看了一眼答案。答案没有用现成函数所以老老实实手写吧。 首先遍历nums1用集合set逐一加入nums1中的元素得到nums1对应的集合。 然后设置集合crossSet遍历nums2如果nums2的元素也在set中说明该元素存在交集中将其加入crossSet。最后遍历crossSet将其存到数组中返回数组即可。
class Solution {public int[] intersection(int[] nums1, int[] nums2) {SetInteger set new HashSet();for (int i 0; i nums1.length; i) {set.add(nums1[i]);}SetInteger crossSet new HashSet();for (int i 0; i nums2.length; i) {if (set.contains(nums2[i])) {crossSet.add(nums2[i]);}}int[] res new int[crossSet.size()];int i 0;for (int item:crossSet) {res[i] item;}return res;}
}
注意点 在Java中求HashSet的交集可以使用removeAll()方法。这个方法会从当前集合中删除所有包含在指定集合的元素。交集操作完成后当前集合只保留与指定集合共有的元素。 import java.util.HashSet;public class Main {public static void main(String[] args) {HashSetInteger set1 new HashSet();HashSetInteger set2 new HashSet();HashSetInteger intersection new HashSet();// 填充集合set1.add(1);set1.add(2);set1.add(3);set2.add(2);set2.add(3);set2.add(4);// 交集操作intersection.addAll(set1);intersection.removeAll(set2);set1.removeAll(set2);// 输出结果System.out.println(set1: set1); // 会输出 []因为set1已经被修改System.out.println(set2: set2); // 输出 [2, 3, 4]System.out.println(交集: intersection); // 输出 [2, 3]}
} 另外注意一下hashset的用法加入元素要用add遍历可以用java for each循环得到所有元素。 题目有加数字的范围在0-1000之间这种情况可以用数组替代Set类型提高效率。
202. 快乐数 题目链接202. 快乐数 代码随想录题解202. 快乐数 解题思路 这题主要分成两步来写一步用于计算数字的每一位上的平方和sum一步用于判断sum是进入了无限循环还是满足了和为1的要求。判断sum进入循环与否的方式可以用哈希表来完成。 初始化本轮用于计算的数字numn用set记录每一次计算得到的平方和当num不为1时计算其每一位上的平方和得到sum如果sum不在set中就把它加入set否则说明已经出现了循环该数不是快乐数。
class Solution {public boolean isHappy(int n) {SetInteger set new HashSet();int num n;set.add(num);while (num ! 1) {int sum 0;while (num ! 0) {sum (num%10)*(num%10);num / 10;}if (set.contains(sum)) return false;else {set.add(sum);num sum;}}return true;}
}
注意点 计算平方和的时候要注意用sum这个临时变量存储结果当num不为0时不断对其取余用来计算平方数加到sum上取完余后不要忘记除以10最后将sum赋值给num用于下一轮的计算。 set中判断元素是否存在用set.contains(element)即可。
1. 两数之和 题目链接1. 两数之和 代码随想录题解1. 两数之和 解题思路 同一个元素不能使用两次还需要查找元素那最好遍历一次数组完成计算既提高效率又防止重复计算。 用哈希表记录元素值及其对应的下标但是这里有个小技巧遍历时在哈希表中记录的不是当前元素值和其下标而是target减去当前元素后的值和当前元素的下标这样往后遍历时就可以直接通过containsKey判断当前元素是否在哈希表中如果在就直接得到前一个元素的下标和当前的下标返回即可。
class Solution {public int[] twoSum(int[] nums, int target) {MapInteger, Integer map new HashMap();for (int i 0; i nums.length; i) {if (map.containsKey(nums[i])) {return new int[]{map.get(nums[i]), i};} else {map.put(target - nums[i], i);}}return new int[2];}
}
注意点 这题非常巧妙用target-nums[i]一举两得减少了搜索的时间保留了需要的下标。 同样注意一下hashmap的用法加入元素用map.put(key, value)判断元素是否存在用map.containsKey(key)。
454.四数相加II 题目链接454.四数相加II 代码随想录题解454.四数相加II 解题思路 这题跟前一题思路有点类似但更复杂一些因为这里要求出所有符合条件的元组数量不重复不遗漏。 将四个数组分为两组先用hashmap记录第一组数据分别有多少种不同的和(key)每个和的数量是多少(value)再遍历第二组数据每次遍历计算-nums3[i]-nums4[j]并判断它是否在前面的hashmap中如果在就把对应的value加入到结果的数量中。最后返回结果即可。
class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {MapInteger, Integer sum1 new HashMap();for (int i 0; i nums1.length; i) {for (int j 0; j nums2.length; j) {sum1.put(nums1[i]nums2[j], sum1.getOrDefault(nums1[i]nums2[j], 0) 1);}}int count 0;for (int i 0; i nums3.length; i) {for (int j 0; j nums4.length; j) {int target -nums3[i]-nums4[j];if (sum1.containsKey(target)) {count sum1.get(target);}}}return count;}
}
注意点 用hashmap统计数量的时候可以用map.getOrDefault(key, 0)的方式方便在map中找不到元素时就直接加入新元素并数量加一。
383. 赎金信 题目链接383. 赎金信 代码随想录题解383. 赎金信 解题思路 这题跟有效字母异位词有点类似不同之处在于magazine需要的字符数量需要包含ransomNote而非字符数量相同。 先用哈希表统计magazine中每个字符的数量然后遍历ransomNote在哈希表的基础上每遍历到一个字符就在相应字符的数量上减去1最后统计哈希表中每个字符的数量是不是大于等于0即可。
class Solution {public boolean canConstruct(String ransomNote, String magazine) {if (ransomNote.length() magazine.length()) return false;MapCharacter, Integer map new HashMap();for (int i 0; i magazine.length(); i) {map.put(magazine.charAt(i), map.getOrDefault(magazine.charAt(i), 0) 1);}for (int i 0; i ransomNote.length(); i) {char c ransomNote.charAt(i);if (map.containsKey(c)) {int count map.get(c) - 1;if (count 0) return false;else map.put(c, count);} else {return false;}}return true;}
}
注意点 这题其实也是统计字符数量所以可以不用hashmap直接用数组效率会更高。
今日收获 复习了一下哈希表的不同用法数组、集合、映射类型的哈希表都写到了。哈希表常用于变量的数量统计去重和用空间换时间的快速查找这里要注意set和map一些对应的用法不常写容易忘。
