• 【图解算法】- 异位词问题：双指针+哈希表

      一 - 前言

    介绍：大家好啊，我是hitzaki辰。

    社区：（完全免费、欢迎加入）日常打卡、学习交流、资源共享的知识星球。

    自媒体：我会在b站/抖音更新视频讲解 或 一些纯技术外的分享，账号同名：hitzaki辰。

    正文开始，抓紧上车！

    ​

    二 - 异位词问题概述

    1 - 异位词是什么

    1）比如 abc 和 bca就是一个异构词

    2）异构词的简单判断：

    （1）长度相等

    （2）每个字母的数量都相等

    2 - 判断异位词

    对于需要比较的字符串s和t，使用哈希表可以很方便的判断异位词，维护1个count和一个哈希表。

    1）关键代码1解读 - 迭代s串：

    对字符串s的所有字符都进行哈希，此时map对应每个字符的数量，count代表字符的种类。

    1. Map map = new HashMap<>();
    2. int count = 0;
    3. for(int i=0; i
    4.     Integer temp = map.get(p.charAt(i));
    5.     map.put(p.charAt(i), temp==null? 1: temp+1);
    6.     if(temp==null) count++;
    7. }

    比如aabc对应的map和count迭代过程为：

    2）关键代码2解读 - 迭代t串：（不同的题，我们迭代的方式不同。）

    获取当前t.charAt(i)，

    （1）若map中没有对应key，说明不是异位词

    （2）若有key，将对应value-1，若减为0，则将count-1。

    （3）若有key，且对应value已经等于0，说明不是异位词。

    最后判断count是否为0，若为0说明是异位词。

    以aaba为例：

    3 - 根据题干优化

    如果题干说只有小写或大写字母这种情况，即固定了出现可能的集合，则我们可以使用一个数组代替哈希表

    s串每次迭代只需要这样：++count[s.charAt(i) - 'a'];

    三 - 例题1：找到字符串所有字母异位词

    题目索引：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

    给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

    1 - 使用哈希表题解：详细注解

    1. class Solution {
    2.  
    3.   public List findAnagrams(String s, String p) {
    4.  
    5. ​    Map map = new HashMap<>();
    6.  
    7. ​    int count = 0;
    8.  
    9. ​    List result = new ArrayList<>();
    10.  
    11. ​    for(int i=0; i
    12.  
    13. ​      Integer temp = map.get(p.charAt(i));
    14.  
    15. ​      map.put(p.charAt(i), temp==null? 1: temp+1);
    16.  
    17. ​      if(temp==null) count++;
    18.  
    19. ​    }
    20.  
    21. ​    int p1=0, p2=0;
    22.  
    23. ​    boolean flag;
    24.  
    25. ​    while(p2
    26.  
    27. ​      // 迭代p2
    28.  
    29. ​      Integer temp2 = map.get(s.charAt(p2));
    30.  
    31. ​      if(temp2==null){ // 包含p2的都不可能,因此结束
    32.  
    33. ​        flag = false;
    34.  
    35. ​      }else{
    36.  
    37. ​        flag = true;
    38.  
    39. ​        map.put(s.charAt(p2), temp2-1);
    40.  
    41. ​        if(temp2==1)count--;
    42.  
    43. ​      }
    44.  
    45. ​      p2++;
    46.  
    47. ​      
    48.  
    49. ​      // 迭代p1, 根据p2情况进行迭代
    50.  
    51. ​      // 1.若p2存在, 则当p2-p1==p.length()时才进入
    52.  
    53. ​      // 若p2不存在, 则迭代至p1==p2
    54.  
    55. ​      while(flag? p2-p1==p.length(): p11){ // 只有p2-1时有null判断
    56.  
    57. ​        if(count==0)result.add(p1);
    58.  
    59. ​        // 将p1位置给去除
    60.  
    61. ​        Integer temp1 = map.get(s.charAt(p1)); 
    62.  
    63. ​        if(temp1==0)count++;
    64.  
    65. ​        map.put(s.charAt(p1), temp1+1);
    66.  
    67. ​        p1++;
    68.  
    69. ​      }
    70.  
    71. ​      if(!flag)p1++; // p1=p2-1时候一定为null, 跳过
    72.  
    73. ​    } // 主迭代结束
    74.  
    75. ​    return result;
    76.  
    77.   }
    78.  
    79. }

    2 - 使用数组题解：注解

    1. class Solution {
    2.  
    3.   public List findAnagrams(String s, String p) {
    4.  
    5. ​    int sLen = s.length(), pLen = p.length();
    6.  
    7.  
    8.  
    9. ​    if (sLen < pLen) {
    10.  
    11. ​      return new ArrayList();
    12.  
    13. ​    }
    14.  
    15.  
    16.  
    17. ​    List ans = new ArrayList();
    18.  
    19. ​    int[] count = new int[26];
    20.  
    21. ​    for (int i = 0; i < pLen; ++i) {
    22.  
    23. ​      ++count[s.charAt(i) - 'a'];
    24.  
    25. ​      --count[p.charAt(i) - 'a'];
    26.  
    27. ​    }
    28.  
    29.  
    30.  
    31. ​    int differ = 0;
    32.  
    33. ​    for (int j = 0; j < 26; ++j) {
    34.  
    35. ​      if (count[j] != 0) {
    36.  
    37. ​        ++differ;
    38.  
    39. ​      }
    40.  
    41. ​    }
    42.  
    43.  
    44.  
    45. ​    if (differ == 0) {
    46.  
    47. ​      ans.add(0);
    48.  
    49. ​    }
    50.  
    51.  
    52.  
    53. ​    for (int i = 0; i < sLen - pLen; ++i) {
    54.  
    55. ​      if (count[s.charAt(i) - 'a'] == 1) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
    56.  
    57. ​        --differ;
    58.  
    59. ​      } else if (count[s.charAt(i) - 'a'] == 0) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
    60.  
    61. ​        ++differ;
    62.  
    63. ​      }
    64.  
    65. ​      --count[s.charAt(i) - 'a'];
    66.  
    67. ​      if (count[s.charAt(i + pLen) - 'a'] == -1) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
    68.  
    69. ​        --differ;
    70.  
    71. ​      } else if (count[s.charAt(i + pLen) - 'a'] == 0) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
    72.  
    73. ​        ++differ;
    74.  
    75. ​      }
    76.  
    77. ​      ++count[s.charAt(i + pLen) - 'a'];
    78.  
    79. ​      
    80.  
    81. ​      if (differ == 0) {
    82.  
    83. ​        ans.add(i + 1);
    84.  
    85. ​      }
    86.  
    87. ​    }
    88.  
    89.  
    90.  
    91. ​    return ans;
    92.  
    93.   }
    94.  
    95. }

    四 - 例题2：最小覆盖子串

    题目索引：https://leetcode.cn/problems/minimum-window-substring/description/

    给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

    1 - 思路

    例子：s = "ADOBECODEBANC", t = "ABC"

    使用双指针：

    （1）左指针用来将map和count恢复

    （2）右指针用来将map对应的value减一，并改变count

    当count=0时，说明此时符合条件，则将此时的子串记录下来。

    2 - 题解：详细注解

    维护一个数量count和map, 先迭代t将map填充,然后让count = map.size

    （1）p2遍历到的如果在map里就将map里对应元素-1, 如果刚好减到0就count-1

    （2）如果count==0, 则开始遍历p1,

      每次让p1对应到map的元素+1, 每次迭代判断长度, 若小于min则更新

    1. class Solution {
    2.     public static String minWindow(String s, String t) {
    3.         Map map = new HashMap<>();
    4.         int min=Integer.MAX_VALUE, index=0,  count;
    5.         Integer temp;
    6.         for(int i=0; i
    7.             temp = map.get(t.charAt(i));
    8.             map.put(t.charAt(i), temp==null? 1: temp+1);
    9.         }
    10.         count = map.size();
    11.         int p1=0, p2=0;
    12.         for(;p2
    13.             // 添加p2位置
    14.             temp = map.get(s.charAt(p2));
    15.             if(temp==null)continue;
    16.             // 如果为1说明减完p2元素会归0, 则count变化
    17.             map.put(s.charAt(p2), temp-1);
    18.             if(temp==1) count--;
    19.             // 迭代p1
    20.             while(count==0){
    21.                 if(p2-p1+1
    22.                     min = p2-p1+1;
    23.                     index = p1;
    24.                 }
    25.                 // 去掉当前p1的元素
    26.                 temp = map.get(s.charAt(p1));
    27.                 p1++;
    28.                 if(temp==null)continue;
    29.                 map.put(s.charAt(p1-1), temp+1);
    30.                 if(temp==0) count++;
    31.             }
    32.         }
    33.         if(min == Integer.MAX_VALUE)return "";
    34.         return s.substring(index, index+min);
    35.     }
    36. }

    五 - 结尾

    感谢你看到这里，如果感觉内容不错的话请点赞支持一下！

    如果小伙伴对我的讲解有疑问，欢迎评论区讨论。

  • 相关阅读:
    【更新】囚生CYの备忘录（20221121-）
    数学建模学习（92）：gurobipy详细入门教程【MLP、MIP模型、仓库调度模型、单/多目标优化、敏感性分析】
    Java安全之Tomcat6 Filter内存马
    【无标题】积鼎CFD VirtualFlow：航空及汽车燃油晃动流体仿真计算及试验对比
    web请求cookie中expires总结
    【ElasticSearch】6亿文档存储的ES集群调优实战
    Pyside6/PyQt6如何添加右键菜单，源码示例
    力扣经典题目解析--旋转图像(字节二面)
    Sentinel基础应用
    SQL SERVER查询生命周期
  • 原文地址：https://blog.csdn.net/m0_56988741/article/details/134452837