本文主要是介绍算法day07，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
第一题
30. 串联所有单词的子串
上题题意如下：
将w数组里面的字符串随机排列，只要在s字符串中找到相对应的w组成的字符串，则返回s中对应字符串首位元素的第一个下标；
有上述题意所知，解题思路如上一题故事，本题采用hash表和滑动窗口的模型；
首先对于words字符串数组进行处理：
由于这里面的字符串的长度一样，所以我们将每一个字符串一组放在hash1表中，并记录其存放的个数；
其次就是对s字符串的处理分析：
如下图所示：
由于我们存放在hash1中的字符串的长度是len，所以我们在开始左右指针进行移动时，从s的第一个位置和第二个位置开始移动时，结果是不一样的；所以我们分别要从其实位置为0->len-1，分别开始移动左右指针；
且接下来分析右指针所移动的随后判断结束点，如下图所示，
最理想的结果莫过于移动到上图n处，但是也可能移动到m和a处，所以最后的right指针应该移动范围是right+len < n;
关于分析综上所述：
解题步骤如下：
步骤一：
使用hash表来存放words和s里面的字符串；
步骤二：
左右指针移动，移动的长度是words里面字符串的长度；
步骤三：
滑动窗口执行的次数，即外循环，len次；
代码如下所示：
class Solution
{public List<Integer> findSubstring(String s, String[] words) {List<Integer> ret = new ArrayList<Integer>();// 保存字典中所有单词的频次Map<String, Integer> hash1 = new HashMap<String, 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++) // 执⾏次数{// 保存窗⼝内所有单词的频次Map<String, Integer> hash2 = new HashMap<String, 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;}
}第二题
题目如上图所示：
本题我们采用滑动窗口和hash表的解题方法：
步骤一：
将t字符串里面的字符放在hash2表中，使用hash2记录每一个元素出现的次数，并使用kinds变量来记录t字符串中字符的种类；
同时定义左右指针；
步骤二：
进窗口：
右指针移动一位，将所指的字符存于hash1表中，并记录当前所指元素出现在hash表中的次数；同时使用count来记录hash1表中的有效种类；（使用两个hash中同一个元素存放的次数相同时，我们就判定该元素满足t字符串中的种类饱和，故此count++）
步骤三：判断：
当有效种类count==kinds时，记录当前左指针的位置为满足条件字符串的首位置，同时记录当前窗口的长度，最后进行出窗口操作；
左指针所指的元素的两个hash值相同时，count--，同时该元素的hash值-1，左指针左移；
步骤四：
返回数值；
代码如下所示：
class Solution {public String minWindow(String s, String t) {char[] s1 = s.toCharArray();char[] t1 = t.toCharArray();int[] hash2 = new int[128];int kinds = 0;//表示t中元素的种类for(char ch: t1){if(hash2[ch] == 0){kinds++;}hash2[ch] ++;}int[] hash1 = new int[128];int minLen = Integer.MAX_VALUE,begin = -1;for(int left = 0,right = 0,count = 0;right < s1.length;right++){char in = s1[right];hash1[in]++;if(hash2[in] == hash1[in]){count++ ;}while(kinds == count){if(right-left+1 < minLen){begin = left;minLen = right-left+1;}char out = s1[left++];if(hash2[out] == hash1[out]){count--;}hash1[out]--;}}if(begin == -1){return new String();}else{return s.substring(begin,begin+minLen);}} }
ps：本次的内容就到这里了，如果大家感兴趣的话就请一键三连哦！！！
这篇关于算法day07的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
