C/C++教程

leetCode第76题最小覆盖字串(滑动窗口算法)

本文主要是介绍leetCode第76题最小覆盖字串(滑动窗口算法),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

大家好,我是魔笑,下面是我分享的滑动窗口算法题,这道题我真是弄了好久,写完,拿到leetCode验证,然后一遍一遍的纠正。真的不容易,最终提交成功,如果对你有帮助,请给个赞啊亲。我们一起加油

题目:

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。

注意:

  • 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串,我们保证它是唯一的答案。

示例 1:

输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"

滑动窗口算法:

* 在滑动窗口类型的问题中都会有两个指针,一个用于「延伸」现有窗口的 r 指针,和一个用于「收缩」窗口的 l 指针。在任意时刻,只有一个指针运动,而另一个保持静止。我们在 s 上滑动窗口,通过移动 r 指针不断扩张窗口。当窗口包含 t 全部所需的字符后,如果能收缩,我们就收缩窗口直到得到最小窗口。

下面是我的解题思路:

*  集合tMap:将所有字符串t中所有的字符放入tMap集合;
*  集合cMap:将左指针和右指针之间的所有属于tMap集合字符放入cMap中,和tMap做对比
*  步骤一,左指针不动,右指针向右移动(窗口在增大),并且将属于s字符串的字符都加入cMap集合中,直到cMap中的字符不少于tMap,并且cMap中每个字符的数量都大于等于tMap数量(满足结果,得到结果),然后步骤二
*  步骤二,右指针不动,左指针向右移动(窗口在缩小),并且从cMap集合中删除右指针所在的字符,直到不满足cMap中每个字符的数量都大于等于tMap数量,然后再重复步骤一。

例如:

*例如:s:"abbc",t:"bc"
* tMap:[a:1,b:1]
* 步骤一:左指针下标是0,右指针下标是-1。
         左指针不动,右指针右移。
         右指针移动到下标是3并且将所有属于tMap元素加入cMap[b:2,c:1],满足条件,
          那么最小字串是“abbc”。

* 步骤二:右指针不动,左指针右移。
          ‘a’不属于tMap(指针增加),左指针下标为1
          当指针是下标1时,‘b’属于cMap,删除cMap中是b的字符(数量减一)指针增加,这时指针是2,
          这时cMap[b:1,c:1]满足条件,那么最小字符串是:"bc"

代码:

  public static String minWindow2(String s, String t) {
        int sLength = s.length();
        int tLength = t.length();
        //如果t字符串大于s字符串直接返回
        if (tLength < tLength) {
            return "";
        }
        Map<Character, Integer> tMap = new HashMap();
        Map<Character, Integer> cMap = new HashMap();
        //将t字符串中所有字符放到tMap中,key是字符,value是这个字符的数量
        for (int i = 0; i < tLength; i++) {
            tMap.put(t.charAt(i), (Integer) tMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        int right = -1;
        int left = 0;
        //存放满足条件的最小的左指针和右指针所在的下标
        int leftResult = 1;
        int rightResult = Integer.MAX_VALUE;
        //遍历s字符串
        for (left = 0; left < sLength; left++) {
            //去除不属于t的字符
            if (!tMap.containsKey(s.charAt(left))) {
                continue;
            }
            //"ad ob ec od eb an cb bc aa"
            //右指针不动,左指针向右移动(窗口在缩小)。
            // 并且从原集合中删除右指针所在的字符,直到不满足cMap中每个字符的数量都大于等于tMap数量.
            while (isEquals(tMap, cMap) && left < right) {
                if (right - left + 1 < rightResult - leftResult + 1) {
                    leftResult = left;
                    rightResult = right;
                }
                if (tMap.containsKey(s.charAt(left))) {
                    cMap.put(s.charAt(left), cMap.getOrDefault(s.charAt(left), 0) - 1);
                }
                left++;
            }
            //左指针不动,右指针向右移动(窗口在增大),并且将属于s字符串的字符都加入对比集合中.
            // 直到cMap中的字符不少于tMap,并且cMap中每个字符的数量都大于等于tMap数量.
            while (right + 1 < sLength) {
                if (!tMap.containsKey(s.charAt(right + 1))) {
                    right++;
                    continue;
                }
                //将属于s字符串的字符都加入cMap集合中
                cMap.put(s.charAt(right + 1), (Integer) cMap.getOrDefault(s.charAt(right + 1), 0) + 1);
                if (isEquals(tMap, cMap)) {
                    if (right + 1 - left + 1 < rightResult - leftResult + 1) {
                        leftResult = left;
                        rightResult = right + 1;
                    }
                    right++;
                    break;
                }
                right++;

            }
            //删除左指针所在下标中cMap包含的字符
            if (tMap.containsKey(s.charAt(left))) {
                cMap.put(s.charAt(left), cMap.getOrDefault(s.charAt(left), 0) - 1);
            }

        }
        if (rightResult - leftResult + 1 == Integer.MAX_VALUE) {
            return "";
        }
        return s.substring(leftResult, rightResult + 1);
    }
    /**
        判断cMap中每个字符的数量是否都大于等于tMap数量
    */
    public static boolean isEquals(Map tMap, Map cMap) {
        if (tMap.size() != cMap.size()) {
            return false;
        }
        Iterator iterator = cMap.keySet().iterator();
        while (iterator.hasNext()) {
            Character character = (Character) iterator.next();
            if ((Integer) tMap.get(character) > (Integer) cMap.get(character)) {
                return false;
            }
        }
        return true;
    }

优化后的代码二:

    public static String minWindow3(String s, String t) {
        int sLength = s.length();
        int tLength = t.length();
        //如果t字符串大于s字符串直接返回
        if (tLength < tLength) {
            return "";
        }
        Map<Character, Integer> tMap = new HashMap();
        Map<Character, Integer> cMap = new HashMap();
        //将t字符串中所有字符放到tMap中,key是字符,value是这个字符的数量
        for (int i = 0; i < tLength; i++) {
            tMap.put(t.charAt(i), (Integer) tMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        int right = -1;
        int left = 0;
        //存放满足条件的最小的左指针和右指针所在的下标
        int leftResult = 1;
        int rightResult = Integer.MAX_VALUE;
        while (right + 1 < sLength) {
            if (!tMap.containsKey(s.charAt(right + 1))) {
                right++;
                continue;
            }
            //将属于s字符串的字符都加入cMap集合中
            cMap.put(s.charAt(right + 1), (Integer) cMap.getOrDefault(s.charAt(right + 1), 0) + 1);
            while (isEquals(tMap, cMap) && left <= right+1) {
                if (right+1 - left + 1 < rightResult - leftResult + 1) {
                    leftResult = left;
                    rightResult = right+1;
                }
                //删除左指针所在下标中cMap包含的字符
                if (tMap.containsKey(s.charAt(left))) {
                    cMap.put(s.charAt(left), cMap.getOrDefault(s.charAt(left), 0) - 1);
                }
                left++;
            }
            right++;

        }

        if (rightResult - leftResult + 1 == Integer.MAX_VALUE) {
            return "";
        }
        return s.substring(leftResult, rightResult + 1);
    }
    /**
     * cMap中每个字符的数量都大于等于tMap数量
     */
    public static boolean isEquals(Map tMap, Map cMap) {
        if (tMap.size() != cMap.size()) {
            return false;
        }
        Iterator iterator = cMap.keySet().iterator();
        while (iterator.hasNext()) {
            Character character = (Character) iterator.next();
            if ((Integer) tMap.get(character) > (Integer) cMap.get(character)) {
                return false;
            }
        }
        return true;
    }

如果有什么问题,请多多指教。如果对你有帮助请给一个素质三连,谢谢。

这篇关于leetCode第76题最小覆盖字串(滑动窗口算法)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!