【双指针】滑动窗口经典例题 力扣

这篇具有很好参考价值的文章主要介绍了【双指针】滑动窗口经典例题 力扣。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

无重复的最长子串LC3 中等

题目链接

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
 

提示:
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

代码:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int right = 0;
        int len = s.length();
        Map<Character,Integer> windows = new HashMap<>();//记录窗口中每个字符出现的次数
        int res = 0;
        while(right<=len-1){// 扩 
            char c = s.charAt(right);
            windows.put(c,windows.getOrDefault(c,0)+1);
            right++;
            while(windows.get(c)>1){// 缩
                char c2 = s.charAt(left);
                windows.put(c2,windows.getOrDefault(c2,0)-1);
                left++;
            }
            res = Math.max(res,right-left);// 更新
        }
        return res;
    }
}

找到字符串中所有子母异位词LC438 中等

题目链接

给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。

示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

代码:

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        HashMap<Character,Integer> window = new HashMap<>();// 窗口中的字母数量
        HashMap<Character,Integer> need = new HashMap<>();  // 所需各字母数量
        for(int i = 0; i < p.length();i++)
            need.put(p.charAt(i),need.getOrDefault(p.charAt(i),0)+1);
        
        int l = 0; // 左指针
        int r = 0; // 右指针
        int len = s.length();
        int succSum = 0;
        while(r < len){// 扩
            char c1 = s.charAt(r);
            r++;
            if(need.containsKey(c1)){
                window.put(c1,window.getOrDefault(c1,0)+1);
                if(window.get(c1).equals(need.get(c1))){ // 注意equal而不是==
                    succSum++;
                }
            }
            while(r-l > p.length()){// 缩

                char c2 = s.charAt(l);
                l++;
                if(need.containsKey(c2)){
                    if(window.get(c2).equals(need.get(c2))){// 注意equal而不是==
                        succSum--;
                    }
                    window.put(c2,window.getOrDefault(c2,0)-1);
                }
            }
            if(succSum == need.size()){
                result.add(l);
            }   

        }
        return result;
    }
}

字符串的排列LC567 中等

题目链接

给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false 。

换句话说,s1 的排列之一是 s2 的 子串 。

示例 1:
输入:s1 = "ab" s2 = "eidbaooo"
输出:true
解释:s2 包含 s1 的排列之一 ("ba").

示例 2:
输入:s1= "ab" s2 = "eidboaoo"
输出:false
 

提示:
1 <= s1.length, s2.length <= 104
s1 和 s2 仅包含小写字母

代码:

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int left = 0,right = 0;
        int s1len = s1.length();
        int s2len = s2.length();
        int vaild = 0;
        HashMap<Character,Integer> window = new HashMap<>();
        HashMap<Character,Integer> need = new HashMap<>();

        for(int i = 0; i < s1len;i++){
            char c = s1.charAt(i);
            need.put(c,need.getOrDefault(c,0)+1);
        }

        while(right<s2len){
            char c1 = s2.charAt(right);
            right++;

            if(need.containsKey(c1)){
                window.put(c1,window.getOrDefault(c1,0)+1);
                if(window.get(c1).equals(need.get(c1))){
                    vaild++;
                }
            }
            while(right-left > s1len){
                char c2 = s2.charAt(left);
                left++;
                if(need.containsKey(c2)){
                    if(window.getOrDefault(c2,0).equals(need.get(c2))){
                        vaild--;
                    }
                    window.put(c2,window.getOrDefault(c2,0)-1);
                }
            }
            if(vaild==need.size())return true;
        }
        return false;
    }
}

滑动窗口的最大值LC239 困难

题目链接

给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1:
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2:
输入:nums = [1], k = 1
输出:[1]

代码:
单调队列:思路链接Labuladong

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {


        List<Integer> re = new ArrayList<>();
        Windows windows = new Windows();
        for(int i = 0; i < nums.length; i++){
            if(i<k-1){
                windows.push(nums[i]);
            }else{
                windows.push(nums[i]);
                re.add(windows.getMax());
                windows.pop(nums[i-k+1]);     
            }
        }
        int[] rearr = new int[re.size()];
		for (int i = 0; i < re.size(); i++) {
			rearr[i] = re.get(i);
		}
		return rearr;

    }
}

class Windows{
    // 单调队列,始终满足从大到小顺序,队尾放入元素时,删除前面比自己小的元素
    LinkedList<Integer> list = new LinkedList<>();

    void push(int a){ // 队尾放入元素时,删除前面比自己小的元素
        while(!list.isEmpty() && a > list.getLast()){
            list.removeLast();
        }
        list.addLast(a);
    }

    void pop(int i){ // 删除的元素刚好是第一个(最大元素)时,才真正触发删除
        if(list.getFirst()==i){
            list.removeFirst();
        }
    }

    int getMax(){
        return list.getFirst();
    }
}

参考:https://labuladong.github.io/algo/di-ling-zh-bfe1b/wo-xie-le–f02cd/文章来源地址https://www.toymoban.com/news/detail-728478.html

到了这里,关于【双指针】滑动窗口经典例题 力扣的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法通关村 —— 滑动窗口经典问题

    目录 滑动窗口经典问题 1. 最长子串专题 1.1 无重复字符的最长子串 1.2 至多包含两个不同字符的最长子串 1.3 至多包含K个不同字符的最长子串 2 长度最小的子数组 3 盛水最多的容器 4 寻找子串异位词 4.1 字符串的排列 4.2 找到字符串中所有字母异位 前面我们已经了解了滑动窗

    2024年02月06日
    浏览(43)
  • 力扣精选算法100题——水果成篮(滑动窗口专题)

    本题链接👉水果成篮 我就按照实例1来进行对这题的理解。 1代表种类类型,这个数组里面有2个种类类型 ps:种类1和种类2 ,只不过种类1是有2个水果,种类2有一个水果,共计3个水果。 本题需要解答:收集水果的最大数目. 但是前提条件: 我们只有2个篮子,每个篮子里只能装

    2024年01月17日
    浏览(41)
  • 算法刷题记录-双指针/滑动窗口(LeetCode)

    思路 根据题目描述,我们可以知道,如果要将某个单词定义为可扩张(stretchy),需要满足如下两个条件: 所以,我们在实现的时候,可以通过两个指针p1和p2,分别指向s和word,分别统计连续的相同字符数量c1和c2,然后再通过上述的两个条件进行判断,即:如果 则表示该单

    2024年02月09日
    浏览(43)
  • 每日OJ题_算法_滑动窗口⑧_力扣76. 最小覆盖子串

    目录 力扣76. 最小覆盖子串 解析及代码 76. 最小覆盖子串 - 力扣(LeetCode) 难度 困难 给你一个字符串  s  、一个字符串  t  。返回  s  中涵盖  t  所有字符的最小子串。如果  s  中不存在涵盖  t  所有字符的子串,则返回空字符串  \\\"\\\"  。 注意: 对于  t  中重复字符,

    2024年01月23日
    浏览(41)
  • 考研算法35天:三元组的最小距离 【双指针,滑动窗口,多路归并】

    多路归并;多路归并算法从理论到应用(易懂)_留恋单行路的博客-CSDN博客 多路归并就是将多个已经归并排序排好序的数组再进行排序(不一定是通过归并排序)。 这道题就是一般做法是先通过排序将三个数组排好然后再进行三指针求最小。但是我们仔细考虑一下,如果我们先

    2024年02月12日
    浏览(38)
  • 力扣精选算法100题——找到字符串中所有字母异位词(滑动窗口专题)

    本题链接👉找到字符串中所有字母异位词 给定2个字符串s和p,找到s中所有p的变位词的字串,就是p是\\\"abc\\\",在s串中找到与p串相等的字串,可以位置不同,但是字母必须相同,比如”bca\\\",\\\"bac\\\"等,都是可以被称之为变位词。最终返回与p串字母相等但排列不同的字符串的初始索引

    2024年01月19日
    浏览(67)
  • Offer必备算法_滑动窗口_八道力扣OJ题详解(由浅到深)

    目录 滑动窗口算法介绍 ①力扣209. 长度最小的子数组 解析及代码 ②力扣3. 无重复字符的最长子串 解析及代码 ③力扣1004. 最大连续1的个数 III 解析及代码 ④力扣1658. 将x减到0的最小操作数 解析及代码 ⑤力扣904. 水果成篮 解析及代码1(使用容器) 解析及代码2(开数组) ⑥

    2024年02月20日
    浏览(47)
  • python - leetcode - 424. 替换后的最长重复字符【经典题解 - 贪心滑动窗口算法】

    描述: 给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符,并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。 在执行上述操作后,返回包含相同字母的最长子字符串的长度。 示例 1: 示例 2: 提示: 1 = s.length = 105 s 仅由大写英文字母组成 0 =

    2024年02月16日
    浏览(47)
  • 每日OJ题_算法_滑动窗口⑦_力扣30. 串联所有单词的子串

    目录 力扣30. 串联所有单词的子串 解析及代码 30. 串联所有单词的子串 - 力扣(LeetCode) 难度 困难 给定一个字符串  s   和一个字符串数组  words 。   words  中所有字符串  长度相同 。   s   中的  串联子串  是指一个包含   words  中所有字符串以任意顺序排列连接起来的

    2024年01月21日
    浏览(45)
  • 算法刷题营【Day2】:: 双指针算法应用:滑动窗口 :209. 长度最小的子数组

    本内容是笔者结合《代码随想录》总结所得,记录学习过程,分享知识! 目录: 1. 开篇例题:209. 长度最小的子数组 2. 题解参考 - - 2.1 方法一:暴力法 - - 2.2 方法二:滑动窗口 3. 方法思路点拨:滑动窗口 - - 3.1 直白解释 - - 3.2 本题思路点拨 4. 相关题集 1. 开篇例题:209. 长度

    2024年02月04日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包