哈希表理论基础
建议:大家要了解哈希表的内部实现原理,哈希函数,哈希碰撞,以及常见哈希表的区别,数组,set 和map。
什么时候想到用哈希法,当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。 这句话很重要,大家在做哈希表题目都要思考这句话。
文章讲解:https://programmercarl.com/哈希表理论基础.html
242.有效的字母异位词
建议: 这道题目,大家可以感受到 数组 用来做哈希表 给我们带来的遍历之处。
题目链接/文章讲解/视频讲解: https://programmercarl.com/0242.有效的字母异位词.html
题目感想:
1.就是相同数量的字母来组成的不同的单词嘛,我们可以通过暴力循环来得出是否是异位词,也可以通过初始化一个数组,因为全是字母且小写,所以只用26位数组就行,然后先遍历第一个字符串,在数组其对应的位置上面+1,然后再遍历第二个字符串,在数组对应位置上-1,最后再检查整个数组,看是否有不为0的位,有则不是,没有则是异位字;- /**
- * 242. 有效的字母异位词 字典解法
- * 时间复杂度O(m+n) 空间复杂度O(1)
- */
- class Solution {
- public boolean isAnagram(String s, String t) {
- int[] record = new int[26];
- for (int i = 0; i < s.length(); i++) {
- record[s.charAt(i) - 'a']++;
- // 并不需要记住字符a的ASCII,只要求出一个相对数值就可以了
- }
- for (int i = 0; i < t.length(); i++) {
- record[t.charAt(i) - 'a']--;
- }
- for (int count: record) {
- if (count != 0) {
- // record数组如果有的元素不为零0,说明字符串s和t 一定是谁多了字符或者谁少了字符。
- return false;
- }
- }
- return true;
- // record数组所有元素都为零0,说明字符串s和t是字母异位词
- }
- }
复制代码 <ol start="349">两个数组的交集
建议:本题就开始考虑 什么时候用set 什么时候用数组,本题其实是使用set的好题,但是后来力扣改了题目描述和 测试用例,添加了 0 0 && hash2 > 0) resList.add(i); int index = 0; int res[] = new int[resList.size()]; for(int i : resList) res[index++] = i; return res; }}[/code]
- 快乐数
建议:这道题目也是set的应用,其实和上一题差不多,就是 套在快乐数一个壳子
题目链接/文章讲解:https://programmercarl.com/0202.快乐数.html
题目感想:
1.最简单的方法就是计算然后去set里面找是否出现过,没出现就存起来,直到结果为1或者出现重复的就结束;- import java.util.HashSet;
- import java.util.Set;
- 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);
- }
- }
- //方法1:将结果集合转为数组
- return resSet.stream().mapToInt(x -> x).toArray();
- //方法2:另外申请一个数组存放setRes中的元素,最后返回数组
- int[] arr = new int[resSet.size()];
- int j = 0;
- for(int i : resSet){
- arr[j++] = i;
- }
- return arr;
- }
- }
复制代码 2.还有一个方法就是用到了快慢指针,慢指针一次走一步,快指针一次走两步,之后比较他们的出的值是否有为1的或者他们的值是否相等,这样就不用存储了!!!是不是很熟悉,没错,我们在找链表中的环的时候也用到了这个,太有意思了。- class Solution {
- public int[] intersection(int[] nums1, int[] nums2) {
- int[] hash1 = new int[1002];
- int[] hash2 = new int[1002];
- for(int i : nums1)
- hash1[i]++;
- for(int i : nums2)
- hash2[i]++;
- List<Integer> resList = new ArrayList<>();
- for(int i = 0; i < 1002; i++)
- if(hash1[i] > 0 && hash2[i] > 0)
- resList.add(i);
- int index = 0;
- int res[] = new int[resList.size()];
- for(int i : resList)
- res[index++] = i;
- return res;
- }
- }
复制代码 3.还有一种是数学解法,这个就是找到一个三位数字可能会进入的循环链然后存起来,只要后面的计算的数字在这个循环链中那么就是不能为1的- class Solution {
- public boolean isHappy(int n) {
- Set<Integer> record = new HashSet<>();
- while (n != 1 && !record.contains(n)) {
- record.add(n);
- n = getNextNumber(n);
- }
- return n == 1;
- }
- private int getNextNumber(int n) {
- int res = 0;
- while (n > 0) {
- int temp = n % 10;
- res += temp * temp;
- n = n / 10;
- }
- return res;
- }
- }
复制代码 感兴趣的可以去力扣看看详细的题解;
- 两数之和
建议:本题虽然是 力扣第一题,但是还是挺难的,也是 代码随想录中 数组,set之后,使用map解决哈希问题的第一题。
建议大家先看视频讲解,然后尝试自己写代码,在看文章讲解,加深印象。
题目链接/文章讲解/视频讲解:https://programmercarl.com/0001.两数之和.html
题目感想:
1.简单的方法有两种,一种是在set中匹配自己需要的,匹配不到把自己加进去,然后循环;另外一种是,给这个数组排序,然后两个指针分布数组两端,根据和目标的大小进行缩进;- class Solution {
- public int getNext(int n) {
- int totalSum = 0;
- while (n > 0) {
- int d = n % 10;
- n = n / 10;
- totalSum += d * d;
- }
- return totalSum;
- }
- public boolean isHappy(int n) {
- int slowRunner = n;
- int fastRunner = getNext(n);
- while (fastRunner != 1 && slowRunner != fastRunner) {
- slowRunner = getNext(slowRunner);
- fastRunner = getNext(getNext(fastRunner));
- }
- return fastRunner == 1;
- }
- }
- 作者:力扣官方题解
- 链接:https://leetcode.cn/problems/happy-number/solutions/224894/kuai-le-shu-by-leetcode-solution/
- 来源:力扣(LeetCode)
- 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
复制代码- class Solution {
- private static Set<Integer> cycleMembers =
- new HashSet<>(Arrays.asList(4, 16, 37, 58, 89, 145, 42, 20));
- public int getNext(int n) {
- int totalSum = 0;
- while (n > 0) {
- int d = n % 10;
- n = n / 10;
- totalSum += d * d;
- }
- return totalSum;
- }
- public boolean isHappy(int n) {
- while (n != 1 && !cycleMembers.contains(n)) {
- n = getNext(n);
- }
- return n == 1;
- }
- }
- 作者:力扣官方题解
- 链接:https://leetcode.cn/problems/happy-number/solutions/224894/kuai-le-shu-by-leetcode-solution/
- 来源:力扣(LeetCode)
- 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
复制代码 [code]//使用双指针public int[] twoSum(int[] nums, int target) { int m=0,n=0,k,board=0; int[] res=new int[2]; int[] tmp1=new int[nums.length]; //备份原本下标的nums数组 System.arraycopy(nums,0,tmp1,0,nums.length); //将nums排序 Arrays.sort(nums); //双指针 for(int i=0,j=nums.length-1;i |