局机关网站建设改进措施,网页访问被拒绝怎么办,放网站的服务器吗,2021年搜索引擎排名一、题目解析1.不符合要求则返回空串()2.子串中重复字符的数量要不少于t中该字符的数量二、算法原理解法1#xff1a;暴力枚举哈希表这里的暴力枚举也可以优化#xff0c;即在包含t中元素处枚举#xff0c;如在A、B和C处开始枚举#xff0c;减少不必要的枚举 解…一、题目解析1.不符合要求则返回空串()2.子串中重复字符的数量要不少于t中该字符的数量二、算法原理解法1暴力枚举哈希表这里的暴力枚举也可以优化即在包含t中元素处枚举如在A、B和C处开始枚举减少不必要的枚举 解法2滑动窗口哈希表check函数判断why为什么能使用滑动窗口 能观察出left和right同向移动left和right的间距就像一个窗口一样框出符合要求的字符串how如何实现滑动窗口1.定义left和right2.check函数判断s的哈希表包含的元素是否大于等于t的哈希表3.进窗口-hash2[in]4.判断-check(hash1,hash2)5.更新结果-更新结果需要记录起始位置和最短长度 出窗口-hash2[out]--解法3滑动窗口哈希表count变量优化判断条件对于check()函数需要遍历两个哈希表所以元素所以可以通过count来记录有效字符的种类通过维护count来实现简便判断1.进窗口-进窗口之后当hash1[in] hash2[in]时count2.出窗口-出窗口之前当hash1[out] hash2[out]时count--3.判断条件-当count kinds(t中有效元素的个数)在理解why后可以先解法2然后再去尝试解法3三、代码示例解法2
bool check(int hash2[], int hash1[]){for (int i A; i Z; i) {if (hash2[i] hash1[i]) return false;}for (int i a; i z; i) {if (hash2[i] hash1[i]) return false;}return true;}public:string minWindow(string s, string t) {int hash2[128]{0}; // s 子串字母的出现次数int hash1[128]{0}; // t 中字母的出现次数for (char c : t) {hash1[c];}int m s.size();int minlen INT_MAX,begin -1;for (int left 0,right 0; right m; right) {hash2[s[right]]; // 右端点字母移入子串while (check(hash2, hash1)) { // 涵盖if (right - left 1 minlen) { // 找到更短的子串minlen right-left1;begin left;}hash2[s[left]]--; // 左端点字母移出子串left;}}return begin 0 ? : s.substr(begin, minlen);}
}; 解法3
string minWindow(string s, string t){int hash1[128] {0};//统计字符串t中每一个字符的频次int kinds 0;//统计有效字符由多少种for(auto ch : t)if(hash1[ch] 0) kinds;int hash2[128] {0};//统计窗口内每个字符的频次int minlen INT_MAX,begin -1;for(int left 0,right 0,count 0;rights.size();right){char in s[right];if(hash2[in] hash1[in]) count;//进窗口维护countwhile(count kinds){if(right-left1minlen){minlen right-left1;begin left;}char out s[left];if(hash2[out]-- hash1[out]) count--;}}if(begin -1) return ;else return s.substr(begin,minlen);} 看到最后如果对您有所帮助还请点赞、收藏和关注我们下期再见
