代码随想录刷题总结--哈希篇

发布时间:2023年12月28日

总结

  1. 题中为某个元素出现的次数等意思,考虑使用哈希法

  2. 哈希表实际操作一般由三类,数组,元素有限且数量较小的情况使用,set,可以去重,数量大不确定适用,map适用于key:vaule的结构

242.有效的字母异位词

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。示例 1: 输入: s = "anagram", t = "nagaram" 输出: true

思路
  1. 根据题意可以解释为两个单词组成的字母相同,但顺序可能不同的则为true

  2. 可以使用暴力循环,同时解析为一个单词中的字母在另一个单词中的出现,考虑使用哈希法

  3. 新建一个数组作为哈希表,下标为出现过的单词,值为出现的频率

  public boolean isAnagram(String s, String t) {
         //1.新建数组,作为hash表,
         int[] ints = new int[26];
         //2.遍历第一个字符串,记录出现过的字母和频率
         for (int i = 0; i < s.length(); i++) {
             ints[s.charAt(i)] += 1;
         }
         //3.遍历第二个字符,当数组对应下标的字符出现,则频率减一
         for (int i = 0; i < t.length(); i++) {
             ints[t.charAt(i)] -= 1;
         }
         //4.遍历数组,如果数组有哪个下标的值没有为0,说明两个字符串中的字符没有抵消掉,则它们组成的字符不一样
         for (int i = 0; i < ints.length; i++) {
             if (ints[i] != 0){
                 return false;
             }
             
         }
         return true;
     }

349. 两个数组的交集

349. 两个数组的交集

思路
  1. 可以理解为某一个元素同时出现在两个数组中,

  2. 数组长度不确定,使用set作为哈希表处理

  public int[] intersection(int[] nums1, int[] nums2) {
         //1.新建2个set,分别映射两个数组
         HashSet<Integer> set = new HashSet<>();
         HashSet<Integer> set1 = new HashSet<>();
         //2.开始遍历一个数组,将元素映射到set1
         for (int i : nums1) {
             set.add(i);
         }
         //3.遍历第二个数组,并且当第一个set中的元素出现过则加入第二个set中
         for (int i : nums2) {
             if (set.contains(i)){
                 set1.add(i);
             }
         }
         //第二个set即为交集
         return set1.stream().mapToInt(x -> x).toArray();   
     }

第202题. 快乐数

「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为 1,那么这个数就是快乐数。

如果 n 是快乐数就返回 True ;不是,则返回 False 。

示例:

输入:19 输出:true 解释: 1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1

思路:
  1. 根据题意中,有一个重要的点,当非快乐数,可能存在每次处理后得到相同的结果,并形成无限循环状态,因此需要考虑处理循环场景‘

  2. 形成循环,说明处理结果已经出现过,因此可以理解为处理结果出现的次数问题

  3. 使用set作为哈希表,处理每次的结果,当出现过一样的值,则为非快乐数

  public boolean isHappy(int n) {
         //1.新建一个set,映射每次处理的结果
         HashSet<Integer> set = new HashSet<>();
         //2.开始循环处理 快乐数的规则,当处理结果不为1且没有重复出现的时候循环处理
         while (!set.contains(n) && n != 1){
             set.add(n);
             //按照题意处理
             n = doSome(n);
         }
         //循环结束则判断是否为快乐数
         return n == 1;
     }
 ?
     private int doSome(int n) {
         //和
         int sum = 0;
         while (sum > 0){
             //取模获取末尾数字
             int num1 = n % 10;
             sum += num1 * num1;
             //取第一个商获取前面的数组
             n = n / 10;
         }
         return n;
         
     }

1. 两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

思路
  1. 寻找给定数组中的是否能相加得到给定和,理解为数组中的元素,对于的给定和减去该元素得到的数字,是否在数组中出现,考虑使用hash表

  2. 题意需要返回下标,因此在hash‘映射中不仅要存储下标,还要存储值,考虑使用map,使用key为值,value为下标

  public int[] twoSum(int[] nums, int target) {
         //定义一个数组作为返回 0下标第一个符合下标值 1下标为数组的第二个下标
         int[] ints = new int[2];
         if(nums == null || nums.length == 0){
             return ints;
         }
         Map<Integer,Integer> map = new HashMap<>();
         //变量数组
         for (int i = 0; i < nums.length; i++) {
             //定义一个临时值为 目标和减去当前数字的值 ,用于查询映射的map中是否存在该值,存在则符合条件
             int temp = target - nums[i];
             if (map.containsKey(temp)) {
                 //存在符合条件的值
                 //组装数组 ,第0个元素下标w为当前下标 ,第二个根据map中的映射获取
                 ints[0] = i;
                 ints[1] = map.get(temp);
                 break;
             }
             //没有匹配到 则组装map数据
             map.put(nums[i],i);
 ?
         }
         return ints;
     }

第454题.四数相加II

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。

思路:
  1. 首先定义 一个map,key放a和b两数之和,value 放a和b两数之和出现的次数。

  2. 遍历大A和大B数组,统计两个数组元素之和,和出现的次数,放到map中。

  3. 定义int变量count,用来统计 a+b+c+d = 0 出现的次数。

  4. 在遍历大C和大D数组,找到如果 0-(c+d) 在map中出现过的话,就用count把map中key对应的value也就是出现次数统计出来。

  5. 最后返回统计值 count 就可以了

 ?
     public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
         Map<Integer,Integer> map = new HashMap<>();
         int count = 0;
         for (int i : nums1) {
             for (int i1 : nums2) {
                 int sum = i + i1;
                 //getOrDefault方法可以获取map,两个数之和出现的次数,没有出现过则为0,每一次次数加一
                 map.put(sum,map.getOrDefault(sum,0) + 1);
             }
         }
         for (int i : nums3) {
             for (int i1 : nums4) {
                 //统计加和的是否有为0 的元组,有则增加 次数
                 count += map.getOrDefault(-i - i1,0);
             }
         }
         return count;
     }

383. 赎金信

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成,返回 true ;否则返回 false。

思路
  1. 可以理解为一个字符串的字符是否全部在另一个字符串中出现过,考虑用哈希表

  2. 只用返回boolea,字符串中的字符固定,就是26个,可以新建一个数组作为哈希表

  3. 数组下标为对应字符,值为出现的频率

  4. 当第一个字符串的字符出现过,字符对应的下标频率,加一

  5. 第二个字符串出现的字符出现的,字符对应的下标减一

  6. 最终查询数组中是否有负值即可比较

     public boolean canConstruct(String ransomNote, String magazine) {
         // shortcut
         if (ransomNote.length() > magazine.length()) {
             return false;
         }
         // 定义一个哈希映射数组
         int[] record = new int[26];
 ?
         // 遍历
         for(char c : magazine.toCharArray()){
             record[c - 'a'] += 1;
         }
 ?
         for(char c : ransomNote.toCharArray()){
             record[c - 'a'] -= 1;
         }
         
         // 如果数组中存在负数,说明ransomNote字符串总存在magazine中没有的字符
         for(int i : record){
             if(i < 0){
                 return false;
             }
         }
         return true;
     }

第15题. 三数之和

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。

注意: 答案中不可以包含重复的三元组。

示例:

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]

思路
  1. 使用双指针方法,指定首尾两个指针,遍历数组,首先进行排序,

  2. 当前值和首尾指针的和大于目标值,则移动尾指针向前,整体变小

  3. 小于目标值移动前指针,整体变大

  4. 找到目标组合,则放入返回中

  5. 去重需要和当前元素的前一个元素去重

  public List<List<Integer>> threeSum(int[] nums) {
         List<List<Integer>> result = new ArrayList<>();
         Arrays.sort(nums);
     // 找出a + b + c = 0
         // a = nums[i], b = nums[left], c = nums[right]
         for (int i = 0; i < nums.length; i++) {
         // 排序之后如果第一个元素已经大于零,那么无论如何组合都不可能凑成三元组,直接返回结果就可以了
             if (nums[i] > 0) { 
                 return result;
             }
 ?
             if (i > 0 && nums[i] == nums[i - 1]) {  // 去重a
                 continue;
             }
 ?
             int left = i + 1;
             int right = nums.length - 1;
             while (right > left) {
                 int sum = nums[i] + nums[left] + nums[right];
                 if (sum > 0) {
                     right--;
                 } else if (sum < 0) {
                     left++;
                 } else {
                     result.add(Arrays.asList(nums[i], nums[left], nums[right]));
             // 去重逻辑应该放在找到一个三元组之后,对b 和 c去重
                     while (right > left && nums[right] == nums[right - 1]) right--;
                     while (right > left && nums[left] == nums[left + 1]) left++;
                     
                     right--; 
                     left++;
                 }
             }
         }
         return result;
     }
 }

文章来源:https://blog.csdn.net/weixin_48254383/article/details/135254900
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。