找回密码
 立即注册
首页 业界区 安全 代码随想录第五天 | 哈希表part01

代码随想录第五天 | 哈希表part01

穆望 2025-6-1 21:30:57
哈希表理论基础
建议:大家要了解哈希表的内部实现原理,哈希函数,哈希碰撞,以及常见哈希表的区别,数组,set 和map。
什么时候想到用哈希法,当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。  这句话很重要,大家在做哈希表题目都要思考这句话。
文章讲解:https://programmercarl.com/哈希表理论基础.html
242.有效的字母异位词
建议: 这道题目,大家可以感受到 数组 用来做哈希表 给我们带来的遍历之处。
题目链接/文章讲解/视频讲解: https://programmercarl.com/0242.有效的字母异位词.html
题目感想:
1.就是相同数量的字母来组成的不同的单词嘛,我们可以通过暴力循环来得出是否是异位词,也可以通过初始化一个数组,因为全是字母且小写,所以只用26位数组就行,然后先遍历第一个字符串,在数组其对应的位置上面+1,然后再遍历第二个字符串,在数组对应位置上-1,最后再检查整个数组,看是否有不为0的位,有则不是,没有则是异位字;
  1. /**
  2. * 242. 有效的字母异位词 字典解法
  3. * 时间复杂度O(m+n) 空间复杂度O(1)
  4. */
  5. class Solution {
  6.     public boolean isAnagram(String s, String t) {
  7.         int[] record = new int[26];
  8.         for (int i = 0; i < s.length(); i++) {
  9.             record[s.charAt(i) - 'a']++;
  10. // 并不需要记住字符a的ASCII,只要求出一个相对数值就可以了
  11.         }
  12.         for (int i = 0; i < t.length(); i++) {
  13.             record[t.charAt(i) - 'a']--;
  14.         }
  15.         for (int count: record) {
  16.             if (count != 0) {
  17. // record数组如果有的元素不为零0,说明字符串s和t 一定是谁多了字符或者谁少了字符。
  18.                 return false;
  19.             }
  20.         }
  21.         return true;
  22. // record数组所有元素都为零0,说明字符串s和t是字母异位词
  23.     }
  24. }
复制代码
<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或者出现重复的就结束;
  1. import java.util.HashSet;
  2. import java.util.Set;
  3. class Solution {
  4.     public int[] intersection(int[] nums1, int[] nums2) {
  5.         if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
  6.             return new int[0];
  7.         }
  8.         Set<Integer> set1 = new HashSet<>();
  9.         Set<Integer> resSet = new HashSet<>();
  10.         //遍历数组1
  11.         for (int i : nums1) {
  12.             set1.add(i);
  13.         }
  14.         //遍历数组2的过程中判断哈希表中是否存在该元素
  15.         for (int i : nums2) {
  16.             if (set1.contains(i)) {
  17.                 resSet.add(i);
  18.             }
  19.         }
  20.         //方法1:将结果集合转为数组
  21.         return resSet.stream().mapToInt(x -> x).toArray();
  22.         //方法2:另外申请一个数组存放setRes中的元素,最后返回数组
  23.         int[] arr = new int[resSet.size()];
  24.         int j = 0;
  25.         for(int i : resSet){
  26.             arr[j++] = i;
  27.         }
  28.         return arr;
  29.     }
  30. }
复制代码
2.还有一个方法就是用到了快慢指针,慢指针一次走一步,快指针一次走两步,之后比较他们的出的值是否有为1的或者他们的值是否相等,这样就不用存储了!!!是不是很熟悉,没错,我们在找链表中的环的时候也用到了这个,太有意思了。
  1. class Solution {
  2.     public int[] intersection(int[] nums1, int[] nums2) {
  3.         int[] hash1 = new int[1002];
  4.         int[] hash2 = new int[1002];
  5.         for(int i : nums1)
  6.             hash1[i]++;
  7.         for(int i : nums2)
  8.             hash2[i]++;
  9.         List<Integer> resList = new ArrayList<>();
  10.         for(int i = 0; i < 1002; i++)
  11.             if(hash1[i] > 0 && hash2[i] > 0)
  12.                 resList.add(i);
  13.         int index = 0;
  14.         int res[] = new int[resList.size()];
  15.         for(int i : resList)
  16.             res[index++] = i;
  17.         return res;
  18.     }
  19. }
复制代码
3.还有一种是数学解法,这个就是找到一个三位数字可能会进入的循环链然后存起来,只要后面的计算的数字在这个循环链中那么就是不能为1的
  1. class Solution {
  2.     public boolean isHappy(int n) {
  3.         Set<Integer> record = new HashSet<>();
  4.         while (n != 1 && !record.contains(n)) {
  5.             record.add(n);
  6.             n = getNextNumber(n);
  7.         }
  8.         return n == 1;
  9.     }
  10.     private int getNextNumber(int n) {
  11.         int res = 0;
  12.         while (n > 0) {
  13.             int temp = n % 10;
  14.             res += temp * temp;
  15.             n = n / 10;
  16.         }
  17.         return res;
  18.     }
  19. }
复制代码
感兴趣的可以去力扣看看详细的题解;

  • 两数之和
    建议:本题虽然是 力扣第一题,但是还是挺难的,也是 代码随想录中 数组,set之后,使用map解决哈希问题的第一题。
    建议大家先看视频讲解,然后尝试自己写代码,在看文章讲解,加深印象。
    题目链接/文章讲解/视频讲解:https://programmercarl.com/0001.两数之和.html
题目感想:
1.简单的方法有两种,一种是在set中匹配自己需要的,匹配不到把自己加进去,然后循环;另外一种是,给这个数组排序,然后两个指针分布数组两端,根据和目标的大小进行缩进;
  1. class Solution {
  2.      public int getNext(int n) {
  3.         int totalSum = 0;
  4.         while (n > 0) {
  5.             int d = n % 10;
  6.             n = n / 10;
  7.             totalSum += d * d;
  8.         }
  9.         return totalSum;
  10.     }
  11.     public boolean isHappy(int n) {
  12.         int slowRunner = n;
  13.         int fastRunner = getNext(n);
  14.         while (fastRunner != 1 && slowRunner != fastRunner) {
  15.             slowRunner = getNext(slowRunner);
  16.             fastRunner = getNext(getNext(fastRunner));
  17.         }
  18.         return fastRunner == 1;
  19.     }
  20. }
  21. 作者:力扣官方题解
  22. 链接:https://leetcode.cn/problems/happy-number/solutions/224894/kuai-le-shu-by-leetcode-solution/
  23. 来源:力扣(LeetCode)
  24. 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
复制代码
  1. class Solution {
  2.     private static Set<Integer> cycleMembers =
  3.         new HashSet<>(Arrays.asList(4, 16, 37, 58, 89, 145, 42, 20));
  4.     public int getNext(int n) {
  5.         int totalSum = 0;
  6.         while (n > 0) {
  7.             int d = n % 10;
  8.             n = n / 10;
  9.             totalSum += d * d;
  10.         }
  11.         return totalSum;
  12.     }
  13.     public boolean isHappy(int n) {
  14.         while (n != 1 && !cycleMembers.contains(n)) {
  15.             n = getNext(n);
  16.         }
  17.         return n == 1;
  18.     }
  19. }
  20. 作者:力扣官方题解
  21. 链接:https://leetcode.cn/problems/happy-number/solutions/224894/kuai-le-shu-by-leetcode-solution/
  22. 来源:力扣(LeetCode)
  23. 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
复制代码
[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
您需要登录后才可以回帖 登录 | 立即注册