微信公众号做特效的网站,html教程菜鸟,专做短篇的网站,冯站长之家官网一 - 前言 介绍#xff1a;大家好啊#xff0c;我是hitzaki辰。 社区#xff1a;#xff08;完全免费、欢迎加入#xff09;日常打卡、学习交流、资源共享的知识星球。 自媒体#xff1a;我会在b站/抖音更新视频讲解 或 一些纯技术外的分享#xff0c;账号同名#xff… 一 - 前言 介绍大家好啊我是hitzaki辰。 社区完全免费、欢迎加入日常打卡、学习交流、资源共享的知识星球。 自媒体我会在b站/抖音更新视频讲解 或 一些纯技术外的分享账号同名hitzaki辰。 正文开始抓紧上车
二 - 异位词问题概述
1 - 异位词是什么 1比如 abc 和 bca就是一个异构词 2异构词的简单判断 1长度相等 2每个字母的数量都相等 2 - 判断异位词 对于需要比较的字符串s和t使用哈希表可以很方便的判断异位词维护1个count和一个哈希表。 1关键代码1解读 - 迭代s串 对字符串s的所有字符都进行哈希此时map对应每个字符的数量count代表字符的种类。 MapCharacter, Integer map new HashMap();
int count 0;
for(int i0; ip.length(); i){Integer temp map.get(p.charAt(i));map.put(p.charAt(i), tempnull? 1: temp1);if(tempnull) count;
} 比如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 - 使用哈希表题解详细注解
class Solution {public ListInteger findAnagrams(String s, String p) { MapCharacter, Integer map new HashMap(); int count 0; ListInteger result new ArrayList(); for(int i0; ip.length(); i){ Integer temp map.get(p.charAt(i)); map.put(p.charAt(i), tempnull? 1: temp1); if(tempnull) count; } int p10, p20; boolean flag; while(p2s.length()){ // 迭代p2 Integer temp2 map.get(s.charAt(p2)); if(temp2null){ // 包含p2的都不可能,因此结束 flag false; }else{ flag true; map.put(s.charAt(p2), temp2-1); if(temp21)count--; } p2; // 迭代p1, 根据p2情况进行迭代 // 1.若p2存在, 则当p2-p1p.length()时才进入 // 若p2不存在, 则迭代至p1p2 while(flag? p2-p1p.length(): p1p2-1){ // 只有p2-1时有null判断 if(count0)result.add(p1); // 将p1位置给去除 Integer temp1 map.get(s.charAt(p1)); if(temp10)count; map.put(s.charAt(p1), temp11); p1; } if(!flag)p1; // p1p2-1时候一定为null, 跳过 } // 主迭代结束 return result;}}
2 - 使用数组题解注解
class Solution {public ListInteger findAnagrams(String s, String p) { int sLen s.length(), pLen p.length(); if (sLen pLen) { return new ArrayListInteger(); } ListInteger ans new ArrayListInteger(); int[] count new int[26]; for (int i 0; i pLen; i) { count[s.charAt(i) - a]; --count[p.charAt(i) - a]; } int differ 0; for (int j 0; j 26; j) { if (count[j] ! 0) { differ; } } if (differ 0) { ans.add(0); } for (int i 0; i sLen - pLen; i) { if (count[s.charAt(i) - a] 1) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同 --differ; } else if (count[s.charAt(i) - a] 0) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同 differ; } --count[s.charAt(i) - a]; if (count[s.charAt(i pLen) - a] -1) { // 窗口中字母 s[ipLen] 的数量与字符串 p 中的数量从不同变得相同 --differ; } else if (count[s.charAt(i pLen) - a] 0) { // 窗口中字母 s[ipLen] 的数量与字符串 p 中的数量从相同变得不同 differ; } count[s.charAt(i pLen) - a]; if (differ 0) { ans.add(i 1); } } return ans;}} 四 - 例题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 当count0时说明此时符合条件则将此时的子串记录下来。 2 - 题解详细注解 维护一个数量count和map, 先迭代t将map填充,然后让count map.size 1p2遍历到的如果在map里就将map里对应元素-1, 如果刚好减到0就count-1 2如果count0, 则开始遍历p1, 每次让p1对应到map的元素1, 每次迭代判断长度, 若小于min则更新 class Solution {public static String minWindow(String s, String t) {MapCharacter, Integer map new HashMap();int minInteger.MAX_VALUE, index0, count;Integer temp;for(int i0; it.length(); i){temp map.get(t.charAt(i));map.put(t.charAt(i), tempnull? 1: temp1);}count map.size();int p10, p20;for(;p2s.length();p2){// 添加p2位置temp map.get(s.charAt(p2));if(tempnull)continue;// 如果为1说明减完p2元素会归0, 则count变化map.put(s.charAt(p2), temp-1);if(temp1) count--;// 迭代p1while(count0){if(p2-p11min) {min p2-p11;index p1;}// 去掉当前p1的元素temp map.get(s.charAt(p1));p1;if(tempnull)continue;map.put(s.charAt(p1-1), temp1);if(temp0) count;}}if(min Integer.MAX_VALUE)return ;return s.substring(index, indexmin);}
}
五 - 结尾 感谢你看到这里如果感觉内容不错的话请点赞支持一下 如果小伙伴对我的讲解有疑问欢迎评论区讨论。
