图书网站建设实训心得,wordpress新手基础,东阳网站推广,搜索引擎优化的含义文章目录 1. 串联所有单词的子串题干#xff1a;算法原理代码#xff1a; 2. 最小覆盖子串题干#xff1a;算法原理#xff1a;1、暴力枚举 哈希表2、滑动窗口 哈希表 代码#xff1a; 1. 串联所有单词的子串 原题链接 题干#xff1a;
给定⼀个字符串 s 和⼀个字符串… 文章目录 1. 串联所有单词的子串题干算法原理代码 2. 最小覆盖子串题干算法原理1、暴力枚举 哈希表2、滑动窗口 哈希表 代码 1. 串联所有单词的子串 原题链接 题干
给定⼀个字符串 s 和⼀个字符串数组 words words 中所有字符串 长度相同 s 中的 串联⼦串 是指⼀个包含 words中所有字符串以任意顺序排列连接起来的⼦串 算法原理
这道题和 Day14 中 所写的找到字符串所有字母异位词 很像 找到字符串所有字母异位词
因为 words 中所有字符串 长度相同 所以我们就可以把每一个字符串划分为长度相等的小字符串 并且用别的字母代替
s 中我们也可以根据相同的长度进行划分 这样我们对题目就进行了转化 不过在解题方面有些许的不同
哈希表 需要使用键值对的方式进行存储 MapString, Integerleft 和 right 指针的移动 移动的步长是每个单词的长度len划分窗口的执行次数 由于 s 可以进行不同的划分 我们就可以划分成 len 次 代码
class Solution {public ListInteger findSubstring(String s, String[] words) {ListInteger ret new ArrayListInteger();MapString, Integer hash1 new HashMapString, Integer();//保存字典中所有单词的频次for(String str : words) {hash1.put(str, hash1.getOrDefault(str, 0) 1);}int len words[0].length();int m words.length;for(int i 0; i len; i) {MapString, Integer hash2 new HashMapString, Integer();//保存窗口内所有单词的频次for(int left i, right i, count 0; right len s.length(); right len) {//进窗口 维护 countString in s.substring(right, rightlen);hash2.put(in, hash2.getOrDefault(in, 0) 1);if(hash2.get(in) hash1.getOrDefault(in, 0)) {count;}//判断if(right - left 1 len * m) {//出窗口 维护 countString out s.substring(left, left len);if(hash2.get(out) hash1.getOrDefault(out, 0)) {count--;}hash2.put(out, hash2.get(out) - 1);left len;}//更新结果if(count m) {ret.add(left);}}}return ret;}
}2. 最小覆盖子串 原题链接
题干
有字符串 s 和 t 返回 s 中涵盖 t 中所有字符串的最小子串 寻找的子字符串不少于该字符数量 算法原理
1、暴力枚举 哈希表 2、滑动窗口 哈希表 在暴力解法中leftright 需要返回原来重新遍历
那么right 是否需要回去呢 left 后有以下两种情况
依然符合要求这个时候 right 不用动不符合要求这个时候 right 向后移动
这个时候我们就可以使用滑动窗口来解决问题
left 0 righ 0进窗口 hash1[ in ]判断 check[ hah1,hash2 ] 更新结果 更新起始位置 和 最短长度 出窗口 hash2[ out ]– 优化 我们可以优化判断条件
使用 count 标记有效字符的种类 如果hash2 中 A 的个数 hash1 中 A 的个数才算有效
进窗口 进之后判断 hash2[ in ] hash1[ in ]count出窗口 出之前判断 hash2[ out ] hash1[ out ]count–判断条件 count hash1.size() 代码
class Solution {public String minWindow(String ss, String tt) {char[] s ss.toCharArray();char[] t tt.toCharArray();int[] hash1 new int[128];//数组模拟哈希表 统计 t 中字符出现的频次int kinds 0;//字符 t 中有多少种字符for(char ch : t) {if(hash1[ch] 0) {kinds;}hash1[ch];}int[] hash2 new int[128];//统计窗口中字符的频次int minlen Integer.MAX_VALUE;int begin -1;for(int left 0,right 0, count 0; right s.length; right) {char in s[right];hash2[in];//进窗口 维护chountif(hash2[in] hash1[in]) {count;}while(kinds count) {//判断if(right - left 1 minlen) {//更新结果begin left;minlen right - left 1;}char out s[left];if(hash2[out] hash1[out]) {//出窗口 维护countcount--;}hash2[out]--;}}if(begin -1) {return new String();}else {return ss.substring(begin, begin minlen);}}
}
