(转)leetcode:Find All Anagrams in a String 滑动窗口方法总结

简介: 今天做了几道滑动窗口的题,稍微总结一下。起因源于早上在leetcode上pick one,随机到了一个easy的题目,想着随便做了,结果半天也找不到最优解,耗时300多ms,A是A了,不过就是暴力罢了。

今天做了几道滑动窗口的题,稍微总结一下。
起因源于早上在leetcode上pick one,随机到了一个easy的题目,想着随便做了,结果半天也找不到最优解,耗时300多ms,A是A了,不过就是暴力罢了。
题目是:Find All Anagrams in a String,链接在https://leetcode.com/problems/find-all-anagrams-in-a-string/ ,题目就不过多解释了。
采用的方法是滑动窗口的方法,可以说这基本是一类方法,leetcode上有几道题都可以用相同的思想,有点类似动态规划,在大致思想步骤一致的前提下,每个题有各自不同的“条件式”。


滑动窗口思想

滑动窗口,就是利用双指针技巧,以及map数据结构,维护一个不断扩展、伸缩的窗口,在窗口内探测记录我们感兴趣的结果。比如这道题目,以用例分析:

Input:
s: “cbaebabacd” p: “abc”

Output:
[0, 6]

首先,先构造一个map,对于p中的每个字符char,都有map[char]++。
然后,初始化一个长度为0的窗口,left = 0,right = 0。第一步先扩展窗口,也就是在right的右边界上做文章。每次right读到一个字符char,都有map[char]–。当map[char]的值大于等于1时,很明显就是窗口中进入了一个p中含有的字符。我们可以取一个变量count,值为p中所有字符的总数。每次有一个p中字符进入窗口,则count–。这样,当count == 0的时候,表明我们的窗口中包含了p中的全部字符,得到一个结果。
当窗口包含一个结果以后,为了进一步遍历,我们需要缩小窗口使窗口不再包含全部的p,同样,如果map[char]>=0,表明一个在p中的字符就要移除窗口,那么count ++,以此类推。
最终代码如下:

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        ArrayList<Integer> result = new ArrayList<>();
        if(s == null || p == null) return result;
        int left = 0,right =0,count = p.length();
        int[] map = new int[256];
        char[] sc = s.toCharArray();
        for (char c : p.toCharArray()) map[c] ++;
        while (right < s.length()) {
            if (map[sc[right++]]-->=1) count --;
            if (count == 0) result.add(left);
            if (right - left == p.length() && map[sc[left++]]++ >=0) count++;
        }
        return result;
    }
}

方法小结

可以说滑动窗口这种思想,关键点在于:
1、map中存储值的意义
2、窗口什么时候扩展和收缩,对应于left和right值什么时候发生变化。
在解题的时候,首先尝试扩展窗口right,看看什么时候包含了一个结果,记录结果。然后缩小左边界left,直到窗口不在包含一个可能解!接着就可以继续扩展窗口了,以此类推。

由此,可以得到一个模板:

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        ArrayList<Integer> result = new ArrayList<>();
        if(s == null || p == null) return result;
        int left = 0,right =0,count = p.length();

        int[] map = new int[256];
        char[] sc = s.toCharArray();
        //初始化map
        for (char c : p.toCharArray()) map[c] ++;
        while (right < s.length()) {
            //1:扩展窗口,窗口中包含一个T中子元素,count--;
            //2:通过count或其他限定值,得到一个可能解。
            //3:只要窗口中有可能解,那么缩小窗口直到不包含可能解。         
        }
        return result;
    }
}

比如leetcode另一个题目 Minimum Window Substring:https://leetcode.com/problems/minimum-window-substring/

用例是:
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.

了解了第一道题目以后,这道题目也很容易思考出来。解题时,按照步骤:

  1. 扩展窗口,窗口中包含一个T中子元素,count–;
  2. 通过count或其他限定值,得到一个可能解。
  3. 只要窗口中有可能解,那么缩小窗口直到不包含可能解。

首先,维护一个map,一个窗口。先看右边界,当窗口扩展包含全部ABC时停下,这个时候必然有count == 0。但是,这个时候的结果字符串可能很长,所以我们要接着缩小左边界。同时,当count == 0时,我们要一直缩小左边界以找到更短的字符串。慢慢count>0了,表明窗口中不包含全部的T了,那么又要扩展窗口。依次类推,最终找到最短字符串。
套用模板,代码如下:

public class Solution {
    public String minWindow(String s, String t) {
        int[] map = new int[256];
        int left = 0,right = 0,count = t.length(), minLen = Integer.MAX_VALUE;
        String result = "";
        for (char tc : t.toCharArray()) map[tc]++;
        char[] sc = s.toCharArray();
        while (right < s.length()|| count ==0) {
            if (count == 0){
                if (right-left+1<minLen){
                    minLen = right - left +1;
                    result = s.substring(left,right);
                }
                if (map[sc[left++]]++>=0) count++;
            }else {
                if ( map[sc[right++]]-->=1) count--;
            }

        }
        return result;
    }
}

https://leetcode.com/problems/longest-repeating-character-replacement/
也是一道滑动窗口的题,在解决诸如substring这类问题时,不妨尝试想一想滑动窗口。

目录
相关文章
|
30天前
【LeetCode 26】239.滑动窗口最大值
【LeetCode 26】239.滑动窗口最大值
30 1
|
3月前
for循环和String类下方法的一个练习题
for循环和String类下方法的一个练习题
52 1
|
23天前
|
Java
【编程基础知识】(讲解+示例实战)方法参数的传递机制(值传递及地址传递)以及String类的对象的不可变性
本文深入探讨了Java中方法参数的传递机制,包括值传递和引用传递的区别,以及String类对象的不可变性。通过详细讲解和示例代码,帮助读者理解参数传递的内部原理,并掌握在实际编程中正确处理参数传递的方法。关键词:Java, 方法参数传递, 值传递, 引用传递, String不可变性。
46 1
【编程基础知识】(讲解+示例实战)方法参数的传递机制(值传递及地址传递)以及String类的对象的不可变性
|
4天前
|
JavaScript 前端开发 开发者
|
2月前
|
JavaScript 前端开发 API
javaScript中常用的String方法以及注意点总结
本文总结了JavaScript中常用的String对象的方法及其注意事项,包括大小写转换、字符获取、子字符串截取、字符串拼接、去除空格、替换、分割以及查找字符串中字符的索引等操作。提供了每种方法的使用示例代码,帮助理解它们的具体用法和差异。
37 2
|
3月前
|
JavaScript 算法 前端开发
JS算法必备之String常用操作方法
这篇文章详细介绍了JavaScript中字符串的基本操作,包括创建字符串、访问特定字符、字符串的拼接、位置查找、大小写转换、模式匹配、以及字符串的迭代和格式化等方法。
JS算法必备之String常用操作方法
|
1月前
【LeetCode 04】滑动窗口法总结
【LeetCode 04】滑动窗口法总结
15 0
|
3月前
|
XML Java API
List与String相互转化方法汇总
本文汇总了List与String相互转化的多种方法,包括使用`String.join()`、`StringBuilder`、Java 8的Stream API、Apache Commons Lang3的`StringUtils.join()`以及Guava的`Joiner.on()`方法实现List转String;同时介绍了使用`split()`方法、正则表达式、Apache Commons Lang3的`StringUtils.split()`及Guava的`Splitter.on()`方法实现String转List。
List与String相互转化方法汇总
|
3月前
|
Java API 索引
【Java基础面试二十四】、String类有哪些方法?
这篇文章列举了Java中String类的常用方法,如`charAt()`、`substring()`、`split()`、`trim()`、`indexOf()`、`lastIndexOf()`、`startsWith()`、`endsWith()`、`toUpperCase()`、`toLowerCase()`、`replaceFirst()`和`replaceAll()`,并建议面试时展示对这些方法的熟悉度,同时深入理解部分方法的源码实现。
【Java基础面试二十四】、String类有哪些方法?
|
3月前
|
数据安全/隐私保护
作用域通信对象:session用户在登录时通过`void setAttribute(String name,Object value)`方法设置用户名和密码。点击登录按钮后,跳转到另外一个页面显示用户
该博客文章通过示例演示了如何使用session对象的`setAttribute`和`getAttribute`方法在不同页面间传递和显示用户的用户名和密码信息,并说明了如何设置会话的有效期。
作用域通信对象:session用户在登录时通过`void setAttribute(String name,Object value)`方法设置用户名和密码。点击登录按钮后,跳转到另外一个页面显示用户