算法day07

发布于:2024-05-16 ⋅ 阅读:(74) ⋅ 点赞:(0)

 第一题

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)
 {
 // 进窗⼝ + 维护 count
 String 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)
 {
 // 出窗⼝ + 维护 count
 String 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:本次的内容就到这里了,如果大家感兴趣的话就请一键三连哦!!!