甘肃兰州做网站,wordpress英文变成中文,网上墓地 wordpress,一级a做爰片免费网站给我看看目录 串联所有单词的⼦串#xff08;hard#xff09;
题目解析
讲解算法原理
编写代码
最⼩覆盖⼦串#xff08;hard#xff09;
题目解析
讲解算法原理
编写代码 串联所有单词的⼦串#xff08;hard#xff09;
题目解析
1.题目链接#xff1a;. - 力扣#…目录 串联所有单词的⼦串hard
题目解析
讲解算法原理
编写代码
最⼩覆盖⼦串hard
题目解析
讲解算法原理
编写代码 串联所有单词的⼦串hard
题目解析
1.题目链接. - 力扣LeetCode
2.题目描述 给定⼀个字符串s和⼀个字符串数组words。words中所有字符串⻓度相同。 s中的串联⼦串是指⼀个包含words中所有字符串以任意顺序排列连接起来的⼦串。 ◦ 例如如果words[)ab),)cd),)ef)]那 么)abcdef))abefcd))cdabef))cdefab))efabcd)和)efcdab)都是串联⼦串。)acdbef)不是串联⼦串因为他不是任何words排列的连接。 返回所有串联字串在s中的开始索引。你可以以任意顺序返回答案。 ⽰例1 输⼊s)barfoothefoobarman),words[)foo),)bar)]输出[0,9] 解释因为words.length2同时words[i].length3连接的⼦字符串的⻓度必须为6。⼦串)barfoo)开始位置是0。它是words中以[)bar),)foo)]顺序排列的连接。 ⼦串)foobar)开始位置是9。它是words中以[)foo),)bar)]顺序排列的连接。输出顺序⽆关紧要。返回[9,0]也是可以的。 ⽰例2 输⼊s)wordgoodgoodgoodbestword),words[)word),)good),)best),)word)]输出[] 解释因为words.length4并且words[i].length4所以串联⼦串的⻓度必须为16。s中没有⼦串⻓度为16并且等于words的任何顺序排列的连接。 所以我们返回⼀个空数组。 ⽰例3 输⼊s)barfoofoobarthefoobarman),words[)bar),)foo),)the)]输出[6,9,12] 解释因为words.length3并且words[i].length3所以串联⼦串的⻓度必须为9。⼦串)foobarthe)开始位置是6。它是words中以[)foo),)bar),)the)]顺序排列的连接。⼦串)barthefoo)开始位置是9。它是words中以[)bar),)the),)foo)]顺序排列的连接。⼦串)thefoobar)开始位置是12。它是words中以[)the),)foo),)bar)]顺序排列的连接。 提⽰ 1s.length104 1words.length5000 1words[i].length30 words[i]和s由⼩写英⽂字⺟组成 讲解算法原理
解法⼀暴⼒解法 算法思路 如果我们把每⼀个单词看成⼀个⼀个字⺟问题就变成了找到「字符串中所有的字⺟异位词」。⽆⾮就是之前处理的对象是⼀个⼀个的字符我们这⾥处理的对象是⼀个⼀个的单词。 编写代码
c算法代码
class Solution
{
public:vectorint findSubstring(string s, vectorstring words) {vectorint ret;unordered_mapstring, int hash1; // 保存 words ⾥⾯所有单词的频次for(auto s : words) hash1[s];int len words[0].size(), m words.size();for(int i 0; i len; i) // 执⾏ len 次{unordered_mapstring, int hash2; // 维护窗⼝内单词的频次for(int left i, right i, count 0; right len s.size();
right len){// 进窗⼝ 维护 countstring in s.substr(right, len);hash2[in];if(hash1.count(in) hash2[in] hash1[in]) count;// 判断if(right - left 1 len * m){// 出窗⼝ 维护 countstring out s.substr(left, len);if(hash1.count(out) hash2[out] hash1[out]) count--;hash2[out]--;left len;}// 更新结果if(count m) ret.push_back(left);}}return ret;}
};
java算法代码
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(), 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, right len);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;}
}
最⼩覆盖⼦串hard
题目解析
1.题目链接. - 力扣LeetCode
2。题目描述 给你⼀个字符串s、⼀个字符串t。返回s中涵盖t所有字符的最⼩⼦串。如果s中不存在涵盖t所有字符的⼦串则返回空字符串。 注意 对于t中重复字符我们寻找的⼦字符串中该字符数量必须不少于t中该字符数量。如果s中存在这样的⼦串我们保证它是唯⼀的答案。 ⽰例1 输⼊s)ADOBECODEBANC),t)ABC)输出)BANC) 解释 最⼩覆盖⼦串)BANC)包含来⾃字符串t的*A*、*B*和*C*。⽰例2 输⼊s)a),t)a)输出)a) 解释 整个字符串s是最⼩覆盖⼦串。⽰例3: 输⼊:s)a),t)aa)输出: 解释: t中两个字符*a*均应包含在s的⼦串中 因此没有符合条件的⼦字符串返回空字符串。 讲解算法原理
解法滑动窗⼝哈希表 算法思路 ◦ 研究对象是连续的区间因此可以尝试使⽤滑动窗⼝的思想来解决。 ◦ 如何判断当前窗⼝内的所有字符是符合要求的呢 我们可以使⽤两个哈希表其中⼀个将⽬标串的信息统计起来另⼀个哈希表动态的维护窗⼝内字符串的信息。 当动态哈希表中包含⽬标串中所有的字符并且对应的个数都不⼩于⽬标串的哈希表中各个字符的个数那么当前的窗⼝就是⼀种可⾏的⽅案。 算法流程 a. 定义两个全局的哈希表 1 号哈希表 hash1 ⽤来记录⼦串的信息 2 号哈希表 hash2 ⽤来记录⽬标串 t 的信息 b. 实现⼀个接⼝函数判断当前窗⼝是否满⾜要求 i. 遍历两个哈希表中对应位置的元素 • 如果 t 中某个字符的数量⼤于窗⼝中字符的数量也就是 2 号哈希表某个位置⼤于 1 号哈希表。说明不匹配返回 false • 如果全都匹配返回 true 。主函数中 a. 先将 t 的信息放⼊ 2 号哈希表中 b. 初始化⼀些变量左右指针 left 0right 0 ⽬标⼦串的⻓度 len INT_MAX ⽬标⼦串的起始位置 retleft 通过⽬标⼦串的起始位置和⻓度我们就能找到结果 c. 当 right ⼩于字符串 s 的⻓度时⼀直下列循环 i. 将当前遍历到的元素扔进 1 号哈希表中 ii. 检测当前窗⼝是否满⾜条件 • 如果满⾜条件 ◦ 判断当前窗⼝是否变⼩。如果变⼩更新⻓度 len 以及字符串的起始位置 retleft ◦ 判断完毕后将左侧元素滑出窗⼝顺便更新 1 号哈希表 ◦ 重复上⾯两个过程直到窗⼝不满⾜条件 iii. right 遍历下⼀个元素 d. 判断 len 的⻓度是否等于 INT_MAX i. 如果相等说明没有匹配返回空串 ii. 如果不想等说明匹配返回 s 中从 retleft 位置往后 len ⻓度的字符串。 编写代码
c算法代码
class Solution
{
public: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; right s.size(); right){char in s[right];if(hash2[in] hash1[in]) count; // 进窗⼝ 维护 countwhile(count kinds) // 判断条件{if(right - left 1 minlen) // 更新结果{minlen right - left 1;begin left;}char out s[left];if(hash2[out]-- hash1[out]) count--; // 出窗⼝ 维护 count }}if(begin -1) return ;else return s.substr(begin, minlen);}
};
java算法代码
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; // 统计有效字符有多少种for(char ch : t)if(hash1[ch] 0) kinds;int[] hash2 new int[128]; // 统计窗⼝内每个字符的频次int minlen Integer.MAX_VALUE, begin -1;for(int left 0, right 0, count 0; right s.length; right){char in s[right];if(hash2[in] hash1[in]) count; // 进窗⼝ 维护 countwhile(count kinds) // 判断条件{if(right - left 1 minlen) // 更新结果{minlen right - left 1;begin left;}char out s[left];if(hash2[out]-- hash1[out]) count--; // 出窗⼝ 维护 count }}if(begin -1) return new String();else return ss.substring(begin, begin minlen);}
}
