河北恒山建设集团网站,.net 微信网站开发,全国icp网站备案审核时间,企业网站建设性能分析Leetcode30. 串联所有单词的子串
题目 Leetcode30. 串联所有单词的子串 解法(滑动窗口)
利用substr函数截取出来的s中截取出一段一段的单词#xff0c;然后和words中比较是否相等。 hash1string, int用来存储words中单词出现的次数left right指针每次移动的步数为wo…Leetcode30. 串联所有单词的子串
题目 Leetcode30. 串联所有单词的子串 解法(滑动窗口)
利用substr函数截取出来的s中截取出一段一段的单词然后和words中比较是否相等。 hash1string, int用来存储words中单词出现的次数left right指针每次移动的步数为wordLen words[i].size()也就是单词的长度边界right wordLen words.size()hash2string, int维护窗口内单词出现次数if(hash1.count(in) hash2[in] hash1[in]) count;if(hash1.count(out) hash2[out] hash1[out]) count--; 代码
class Solution
{
public:vectorint findSubstring(string s, vectorstring words) {vectorint res;unordered_mapstring, int hash1;//保存words里面单词出现的次数for(auto i : words) hash1[i];int wordLen words[0].size(), n words.size();for(int i 0; i wordLen; i){unordered_mapstring, int hash2;//维护窗口中单词出现的次数for(int left i, right i, count 0; right wordLen s.size(); right wordLen){//进窗口 维护countstring in s.substr(right, wordLen);hash2[in];if(hash1.count(in) hash2[in] hash1[in]) count;if(right - left 1 wordLen * n)//判断{//出窗口 维护countstring out s.substr(left, wordLen);if(hash1.count(out) hash2[out] hash1[out]) count--;hash2[out]--;left wordLen;}//更新结果if(n count) res.push_back(left);}}return res;}
};时间复杂度O(N*M) Leetcode76. 最小覆盖子串
题目 Leetcode76. 最小覆盖子串 解法(滑动窗口) left 0, right 0;进窗口hash2[in]判断check(left, right)- 出窗口hash2[out]--更新结果位置每一题都不同本题在判断后 利用count来统计有效字符的种类在check判断的时候用来优化 1. 进窗口之前 当hash2[in] hash1[in] count; 2. 出窗口之后 当hash2[out] hash1[out] count - - ; 3. 判断时 count hash1.size();
代码
class Solution
{
public:string minWindow(string s, string t) {int hash1[128] {0};//统计t中每个字母出现的次数int kinds 0;//统计有效字母的种类for(auto i : t) if(hash1[i] 0) kinds;int hash2[128] {0};//统计窗口内每个字母出现的次数int res INT_MAX;int begin -1;for(int left 0, right 0, count 0; right s.size(); right){char in s[right];if(hash2[in] hash1[in]) count;//进窗口维护countwhile(count kinds)//判断{if(right - left 1 res)//更新结果{res right - left 1;begin left;}char out s[left];if(hash2[out]-- hash1[out]) count--;//出窗口维护count}}return begin -1? : s.substr(begin, res);}
};
