当前位置: 首页 > article >正文

LeetCode Hot100 - 子串篇

前言

        挑战一个月刷完力扣的hot100,记录一下每题的思路~

        这次是子串相关的题目

(1)560. 和为 K 的子数组

        ①暴力枚举,使用一个变量sum记录以l开头r结尾的情况

class Solution {
    public int subarraySum(int[] nums, int k) {
        int res=0;
        // 枚举每种情况
        for(int l=0;l<nums.length;l++){
            int sum=0; // l开头
            for(int r=l;r<nums.length;r++){ // r结尾
                sum+=nums[r];
                if(sum==k)res++; // 满足条件
            }
        }
        return res;
    }
}

        ②前缀和+map,map记录每种前缀和出现的次数。若位置i的前缀和为pre,map中存在pre-k的前缀和,即存在某位置到i的和为k,统计次数即可

class Solution {
    Map<Integer,Integer> map = new HashMap<>(); // 每种前缀和出现次数
    public int subarraySum(int[] nums, int k) {
        int res=0, pre=0;
        map.put(0,1);
        for(int i=0;i<nums.length;i++){
            pre+=nums[i]; // 开头到i的和
            // map中存在前缀和pre-k,即存在某个位置到i的和为k
            if(map.containsKey(pre-k))res+=map.get(pre-k);
            map.put(pre,map.getOrDefault(pre,0)+1); // 更新前缀和pre的次数
        }
        return res;
    }
}

(2)239. 滑动窗口最大值

        ①优先队列,记录值和下标,按降序(越大越优先),每次移除下标越界元素,取最大值

class Solution {
    // 优先队列,存值和下标,按值降序,即越大优先级越高
    PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->Integer.compare(b[0],a[0]));
    List<Integer> res = new ArrayList<>();
    public int[] maxSlidingWindow(int[] nums, int k) {
        for(int i=0;i<k;i++)pq.offer(new int[]{nums[i],i});
        res.add(pq.peek()[0]); // 第一种情况
        for(int i=k;i<nums.length;i++){
            pq.offer(new int[]{nums[i],i});
            while(pq.peek()[1]<=i-k)pq.poll(); // 移除窗口外元素
            res.add(pq.peek()[0]); // 存最大值
        }
        return res.stream().mapToInt(Integer::intValue).toArray(); // 流式转换
    }
}

        ②单调递减双端队列。若l<r,且nums[l]<nums[r],在后续的窗口中不可能选到l。每次入队为靠后元素,若该元素大于队尾元素,队尾不可能再选到,直接出队。队列保留目前最大值和其后递减较小值。最大值移出滑动窗口时,将其出队

class Solution {
    List<Integer> res = new ArrayList<>();
    Deque<Integer> queue = new ArrayDeque<>(); // 单调递减双端队列
    public int[] maxSlidingWindow(int[] nums, int k) {
        for(int i=0;i<nums.length;i++){
            // 移除窗口的元素刚好为队头,出队
            if(i>=k&&queue.peekFirst()==nums[i-k])queue.pollFirst();
            // 加入当前元素,满足单调递减
            while(!queue.isEmpty()&&queue.peekLast()<nums[i])queue.pollLast();
            queue.addLast(nums[i]);
            // 遍历到k-1时开始取队头,即目前最大值
            if(i>=k-1)res.add(queue.peekFirst());
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }
}

        ③思路同上一种,单调队列记录下标,用于队头下标越界判断,更好理解

class Solution {
    List<Integer> res = new ArrayList<>();
    Deque<Integer> deque = new ArrayDeque<>(); // 单调递减双端队列
    public int[] maxSlidingWindow(int[] nums, int k) {
        for(int i=0;i<nums.length;i++){
            // 加入当前元素,满足单调递减
            while(!deque.isEmpty()&&nums[deque.peekLast()]<nums[i])deque.pollLast();
            deque.addLast(i);
            // 队头出界,移出
            if(i>=k&&deque.peekFirst()<=i-k)deque.pollFirst();
            // 遍历到k-1时开始取队头,即目前最大值
            if(i>=k-1)res.add(nums[deque.peekFirst()]);
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }
}

        ④分组+最大前后缀。k个数一组,计算每组最大前后缀。窗口起始值i,若为k的整数倍,即窗口恰好为一组;否则,窗口跨越两个分组,取前一个分组最大后缀和后一个分组最大前缀的最大值

class Solution {
    List<Integer> res = new ArrayList<>();
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] prefixMax=new int[n], suffixMax=new int[n];
        for(int i=0,j=n-1;i<n;i++,j--){
            // 下标为k整数倍,组头
            if(i%k==0)prefixMax[i]=nums[i]; 
            else prefixMax[i]=Math.max(prefixMax[i-1],nums[i]);
            // 数组最后一位或下标后一位为k整数倍,组尾
            if(j==n-1||(j+1)%k==0)suffixMax[j]=nums[j]; 
            else suffixMax[j]=Math.max(suffixMax[j+1],nums[j]);
        }
        // i为窗口起始位置
        // i为k整数倍,窗口恰为一个分组
        // 否则窗口跨越两个分组,取前一个分组最大后缀和后一个分组最大前缀的最大值
        for(int i=0;i<=n-k;i++)res.add(Math.max(suffixMax[i],prefixMax[i+k-1]));
        return res.stream().mapToInt(Integer::intValue).toArray();
    }
}

(3)76. 最小覆盖子串

        滑动窗口。map和count分别记录t和滑动窗口的字符数,check判断count不小于map,即滑动窗口满足条件。r扩张直到check为true,然后收缩l直到不满足,记录最短滑动窗口

class Solution {
    Map<Character,Integer> map = new HashMap<>();
    Map<Character,Integer> count = new HashMap<>();
    public String minWindow(String s, String t) {
        if(s.length()<t.length())return ""; // 长度不够
        int l=0,r=-1,sLen=s.length(),tLen=t.length(); // 滑动窗口
        int resL=-1,resR=-1; // 结果下标
        // t中字符计数
        for(char c:t.toCharArray())map.put(c,map.getOrDefault(c,0)+1);
        // s滑动窗口
        while(r<sLen){
            r++; // 扩张
            if(r<sLen&&map.containsKey(s.charAt(r)))
                count.put(s.charAt(r),count.getOrDefault(s.charAt(r),0)+1);
            while(check()&&l<=r){
                if(resL==-1||r-l<resR-resL){resL=l;resR=r;}
                if(map.containsKey(s.charAt(l)))
                    count.put(s.charAt(l),count.getOrDefault(s.charAt(l),0)-1);
                l++; // 收缩
            }
        }
        return resL==-1?"":s.substring(resL,resR+1);
    }
    // count不小于map个数
    boolean check(){
        for(Character c:map.keySet()){
            if(count.getOrDefault(c,0)<map.get(c))return false;
        }
        return true;
    }
}

总结

        ①子串双指针暴力枚举;map记录每种前缀和出现次数,统计pre-k存在次数

        ②和为K的子串优先队列记录值和下标,值大优先,下标限界;单调递减双端队列,位于前面且更小的值不会再被选中;分组+最大前后缀,预处理分组的前后缀,滑动窗口恰为分组,或跨越两个分组

        ③滑动窗口最大值滑动窗口,r扩张找到满足的情况,l收缩尽可能最短


http://www.kler.cn/a/373327.html

相关文章:

  • Swarm-LIO: Decentralized Swarm LiDAR-inertial Odometry论文翻译
  • vue3父子组件传值,子组件暴漏方法
  • C#与C++交互开发系列(十七):线程安全
  • 使用 Kibana 将地理空间数据导入 Elasticsearch 以供 ES|QL 使用
  • Nginx+Lua脚本+Redis 实现自动封禁访问频率过高IP
  • 批量剪辑视频软件源码搭建全解析,支持OEM
  • 商场紧急预案管理:SpringBoot实现指南
  • 3. 教你用WebSocket构建一个实时聊天应用
  • Chromium 中chrome.fontSettings扩展接口定义c++
  • django中entity.save(using=)的使用
  • 不再输入单号查快递,批量查快递单号信息的新方法,智能排序快递时效并查找时效相同的单号,一站式物流查询解决方案
  • 微服务篇SpringCloud
  • Mysql报错注入之floor报错详解
  • AI学习指南自然语言处理篇-Transformer模型简介
  • 美团2025校招 广告算法工程师 面经
  • Linux基础 -- 文件同步之 rsync 命令的使用
  • golang 高阶函数
  • 各国家的MCC
  • Tomcat异常日志中文乱码怎么解决
  • ELK之路第四步——整合!打通任督二脉
  • 9种 Vuejs 常用事件修饰符与使用指南
  • 《神经网络助力战场车辆及部件损毁识别与评估》
  • 【Moonlight】Sunshine 安装
  • QT——TCP网络调试助手
  • 嵌入式C/C++语言相关知识——C++八股
  • 一个基于.NET8+WPF开源的简单的工作流系统