LeetCode 热题 100 Day02

滑动窗口模块

滑动窗口类问题:总能找到一个窗口,从前往后移动来查找结果值。

这个窗口的大小可能是固定的,也可能是变化的。但窗口的大小一定是有限的。

https://www.cnblogs.com/huansky/p/13488234.html

Leetcode 3. 无重复字符的最长子串

题意理解:

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

        我们采用滑动窗口来解决这道问题,其中:滑动窗口用来查找不重复子串。

解题思路:

        找到一个位置i,开始扩展滑动窗口,len++,当出现重复元素时,记录不重复子串长度,i位置向后移一位。

1.滑动窗口解题

public int lengthOfLongestSubstring(String s) {
        int maxLen=0;
        HashSet<Character> set=new HashSet<>();
        for(int i=0;i<s.length();i++){
            int j=i;
            while(j<s.length()&&(!set.contains(s.charAt(j)))){
                set.add(s.charAt(j));
                j++;
            }
            maxLen=Math.max(maxLen,set.size());
            set=new HashSet<>();
        }
        return maxLen;
    }

2.复杂度分析

时间复杂度:O(n^2),遍历元素和遍历滑动窗口的时间耗费

空间复杂度:O(n), 所有set的空间损耗。

Leetcode 438. 找到字符串中所有字母异位词

题意理解

        给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。

        

        给定一个目标字符串p,在字符串s中寻找其异位词的位置下标。

        则s中存在和p相同长度的子串,且子串的组成相同,返回该子串的位置即可。

        此处采用滑动窗口来解题。

解题思路

        采用滑动窗口解题,其中窗口大小等于p的长度

        将窗口从0下标开始向后移动,每次取窗口里的子串进行判断        

        窗口子串是否是p的异位词

        是怎将窗口位置下标加入结果集,否则不加入

        将窗口继续向后移动。

1.滑动窗口解题

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result=new ArrayList<>();
        int window=p.length();
        for(int i=0;i<s.length()-window+1;i++){
            String str=s.substring(i,i+window);
            if(isAllotopicWord(str,p)){
                result.add(i);
            }
        }
        return  result;
    }

    public boolean isAllotopicWord(String str,String target){
        int[] letter=new int[26];
        for(int i=0;i<str.length();i++)
            letter[str.charAt(i)-'a']+=1;
        for(int i=0;i<target.length();i++)
            letter[target.charAt(i)-'a']-=1;
        for(int i=0;i<letter.length;i++)
            if(letter[i]!=0) return false;
        return true;
    }

2.复杂度分析

时间复杂度:O(n^2)

空间复杂度:O(n)

子串模块

子串:

子串类题目通常解决方法有:滑动窗口、双指针等

特别要注意一些边界判断,容易出错

再就是如何优化时间|空间复杂度。

Leetcode 560. 和为 K 的子数组

题意理解:

        给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。

        查找有多少个连续的子序列和为k。是子串遍历的一类问题。

解题思路:

        遍历所有的连续子串,若子串长度==k,则result++

        特别的注意:

        当子串和大于k时,不代表遍历停止,后续的负数可能使其仍然满足一个子串。

        如:1,-1,0

        k=0

        则满足规则的子串有: 1,-1          1,-1,0           0

1.子串遍历解题

public int subarraySum(int[] nums, int k) {
        int result=0;
        for(int i=0;i<nums.length;i++){
            int sum=0;
            for(int j=i;j<nums.length;j++){
               sum+=nums[j];
               if(sum==k) result++;
            }
        }
        return  result;
    }

2.复杂度分析

时间复杂度:O(n^2)

空间复杂度:O(1)

Leetcode 239. 滑动窗口最大值

题意理解:  

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

解题思路:

        选中一个1起始位置,如0, 则获得第一个滑动窗口: 1,3 ,-1   此时max=3

        向下滑动一个位置,此时要有一个数加入,一个数被丢弃

        使用队列来维持窗口中的最大值。使最大值总是出现在队列尾端。

        比最大值小的值维护在,队首。

这道题目的难点在于:最大的数被移出窗口后,如何从剩下的值中获得最大值

还一个点:(关键)

  1.  k个数的数列,其中包含最大值x,则x以前的数是没有意义的:
  2. 因为只要能取到x, 一定不会取到x之前的数,因为x最为max,一定比前面的值大
  3. 除此之外:
  4. 新进入的值y:  y前面比它小的值也是没有意义的,若y比x大,则y前面所有的值都是没有意义的废数。

这样的解法本质上是将滑动窗口里的值维护到了一个单调队列里,他总是保持最大值及到当前位置的比它小的值,最大值前面且比它小的数是废数。

1.滑动窗口解题

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length==1||k==1){
            return nums;
        }
        Deque<Integer> queue=new LinkedList<>();
        List<Integer> numbers=new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            //弹出过期数据
            if((!queue.isEmpty())&&queue.peekFirst()==i-k){
                queue.pollFirst();
            }
            //前面比它大
            if(queue.isEmpty()){
                queue.offerLast(i);
            } else if(nums[queue.peekLast()]>nums[i]) {
                queue.offerLast(i);
            }else if(nums[queue.peekLast()]<=nums[i]){
                //前面比它小,全部弹出
                while((!queue.isEmpty())&&nums[queue.peekLast()]<=nums[i]){
                    queue.pollLast();
                }
                queue.offerLast(i);
            }
            if(i>=k-1){
                numbers.add(queue.peekFirst());
            }
        }
        int[] result=new int[numbers.size()];
        for(int i=0;i<numbers.size();i++){
            result[i]=nums[numbers.get(i)];
        }
        return result;
    }
}

2.复杂度分析

时间复杂度:O(n)

空间复杂度:O(n)

Leetcode 76. 最小覆盖子串

题意理解:

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

注意:

  • 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

如果 s 中存在这样的子串,我们保证它是唯一的答案

        及返回s中包含t所有元素的最短子串。此处还是可以用双指针来解决这道题目。

解题思路:

        1.找到一个左指针开头: 即一个t中的元素开头。

        2.找到一个右指针结尾: 即一个t中的元素结尾,且当前滑动窗口包含t中所有元素。

        3.将结果维护在result串中

        4.左指针向右移动,弹出左侧元素,直到左侧开始第一个t中元素

        5.右指针扩展,右边找滑动窗口的结尾。

        6.重复步骤3

一个要注意的点:如何判断s包含t所有元素呢?t中可能有重复元素

比较两个方面:是否右t中元素,s中的对应t中的元素个数要多于或等于t中对应元素的个数

如:s: abcab     t:aab   s中a的个数>=t中a的个数,才能满足条件:s包含t所有元素

上述方法没问题,但是会发生超时问题:优化

还是left和right两个指针

1.right向右拓展,left向right靠近,最终获得最短符合条件的子串

2.用sMap和tMap来维护子串和t串的元素及个数

3.判断tMap所有key满足:sMap.get(c)>tMap.get(c),则[left,right]子串满足要求

4.将结果子串用ansL和ansR维护,其中表示子串的最左位置和最右位置

5.最后返回[ansL,ansR]子串

优化了哪里:

        sMap由right和left实时维护,不用每次在对[left,right]统计,少了一层for循环

        时间复杂度优化了

1.双指针解题

class Solution {
   public String minWindow(String s, String t) {
        int ansL=0,ansR=-1;
        //保存t中元素及个数|s
        Map<Character,Integer> tMap=new HashMap<>();
        Map<Character,Integer> sMap=new HashMap<>();
        for(char c:t.toCharArray()){
            tMap.put(c,tMap.getOrDefault(c,0)+1);
        }
        int left=0,right=0;
        while(right<s.length()){
            if(tMap.containsKey(s.charAt(right)))
                sMap.put(s.charAt(right),sMap.getOrDefault(s.charAt(right),0)+1);
            while(left<=right&&isContains(sMap,tMap)){//right向右移动,left向right缩,最后获得最短子串
                if(ansR==-1||right-left<ansR-ansL) {
                    ansL=left;
                    ansR=right;
                }
                if(tMap.containsKey(s.charAt(left))){
                    sMap.put(s.charAt(left),sMap.getOrDefault(s.charAt(left),0)-1);
                }
                left++;
            }
            right++;
        }
        return ansR-ansL+1<=0?"":s.substring(ansL,ansR+1);
    }
    //判断
    public boolean isContains(Map<Character,Integer> sMap,Map<Character,Integer> tMap){
        for(char key:tMap.keySet()){
            if(tMap.get(key)>sMap.getOrDefault(key,0)) return false;
        }
        return true;
    }
}

2.复杂度分析

时间复杂度:O(n^2)

空间复杂度:O(n)

这道题是一道困难题:难在容易超时。如何对代码优化。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/547199.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

什么是分组分析法

调查数据显示&#xff0c;2019 年年末中国大陆总人口 140005 万人。从年龄构成看&#xff0c;16 至 59 周岁年末人数为 89640 万&#xff0c;占总人口的比重为 64.0%&#xff1b;60 周岁及以上人口 25388 万人&#xff0c;占总人口的 18.1%&#xff0c;其中 65 周岁及以上人口 …

leetcode-链表中间节点

876. 链表的中间结点 题目 给你单链表的头结点 head &#xff0c;请你找出并返回链表的中间结点。 如果有两个中间结点&#xff0c;则返回第二个中间结点。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5] 输出&#xff1a;[3,4,5] 解释&#xff1a;链表只有一个中间…

【办公类-21-16】 20240410三级育婴师 344多选题(题目与答案合并word)

作品展示 背景需求&#xff1a; 前文将APP题库里的育婴师题目下载到EXCEL&#xff0c;并进行手动整理【办公类-21-14】 20240406三级育婴师 344道多选题 UIBOT下载整理-CSDN博客文章浏览阅读287次&#xff0c;点赞8次&#xff0c;收藏9次。【办公类-21-14】 20240406三级育婴师…

银河麒麟高级服务器操作系统adb读写缓慢问题分析

1.问题环境 处理器&#xff1a; HUAWEI Kunpeng 920 5251K 内存&#xff1a; 512 GiB 整机类型/架构&#xff1a; TaiShan 200K (Model 2280K) BIOS版本&#xff1a; Byosoft Corp. 1.81.K 内核版本 4.19.90-23.15.v2101.ky10.aarch64 第三方应用 数据库 2.问题…

基于直方图的图像阈值计算和分割算法FPGA实现,包含tb测试文件和MATLAB辅助验证

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 5.算法完整程序工程 1.算法运行效果图预览 2.算法运行软件版本 VIVADO2019.2 matlab2022a 3.部分核心程序 timescale 1ns / 1ps // // Company: // Engineer: // // Design Name: // …

【浪漫 罗盘时钟 Js、css实现(附源代码) 美化版本】,前端面试必问的HashMap

先自我介绍一下&#xff0c;小编浙江大学毕业&#xff0c;去过华为、字节跳动等大厂&#xff0c;目前阿里P7 深知大多数程序员&#xff0c;想要提升技能&#xff0c;往往是自己摸索成长&#xff0c;但自己不成体系的自学效果低效又漫长&#xff0c;而且极易碰到天花板技术停滞…

vue简单使用三(class样式绑定)

目录 对象的形式绑定&#xff1a; 数组的形式绑定&#xff1a; 内联样式Style 对象的形式绑定&#xff1a; 可以看到class中有两个值 数组的形式绑定&#xff1a; 可以看到也有两个值 内联样式Style style样式设置成功 完整代码&#xff1a; <!DOCTYPE html> <html…

EasyImage2.0 简单图床开源 多功能 简单易用图床系统源码

内容目录 一、详细介绍二、效果展示1.部分代码2.效果图展示 三、学习资料下载 一、详细介绍 支持API 支持仅登录后上传 支持设置图片质量 支持压缩图片大小 支持文字/图片水印 支持设置图片指定宽/高 支持上传图片转换为指定格式 支持限制最低宽度/高度上传 支持上传其他文件格…

攻防世界---misc---适合作为桌面

1.下载附件&#xff0c;是一张图片 2.用Stegsolve打开&#xff0c;打开图片一直点击下面的“>”&#xff0c;知道看到二维码 3.用QR Research解码&#xff0c;得到一串十六进制 4.用winhex转为pyc文件&#xff0c;先把十六进制内容存放在.txt文本中&#xff0c;然后用winhex…

(处理流)转换流与对象流

1.字符编码与解码. (1). 字符编码 : 将字符&#xff0c;字符串&#xff0c;字符数组------&#xff1e; 字节&#xff0c;字节数组. (2). 字节&#xff0c;字节数组------&#xff1e;字符&#xff0c;字符串&#xff0c;字符数组. 如果希望程序在读取文件时(也就是解码)不…

OpenHarmony开发实例:【分布式游戏鉴权应用】

1.介绍 本文将介绍分布式游戏鉴权应用。操作过程为&#xff1a; 设备A点击“开始游戏”按钮&#xff0c;开始搜索周边设备。 设备A显示周边设备&#xff0c;点击设备B并发起连接请求&#xff0c;远程拉起设备B的FA。 设备B收到请求后&#xff0c;选择是否允许“开启游戏”。…

《R语言与农业数据统计分析及建模》学习——数据读入

一、工作目录 # 获取当前工作目录 getwd()# 改变工作目录为指定路径下的文件夹 # 注意工作目录的表达方式 setwd(D:/R_class) setwd(D:\\R_class) 二、文件路径 读取文件中的数据首先要确定文件路径&#xff0c;如果文件不在工作目录下&#xff0c;则必须使用绝对路径 1、文…

STL —— stack、queue

博主首页&#xff1a; 有趣的中国人 专栏首页&#xff1a; C专栏 目录 1. 容器适配器 2. 栈的模拟实现 3. 队列的模拟实现 4. 双端队列deque 4.1 deque的原理介绍 4.2 deque的缺陷 4.3 为什么选择deque作为stack和queue的底层默认容器 本篇文章主要讲解 stack 和 queue …

MDK-ARM Keil5.38 下载安装环境搭建

一、keil软件介绍 KEIL是公司的名称&#xff0c;有时候也指KEIL公司的所有软件开发工具&#xff0c;目前2005年Keil由ARM公司收购&#xff0c;成为ARM的公司之一。 MDK&#xff08;Microcontroller Development Kit&#xff09; 也称MDK-ARM、KEIL MDK、RealView MDK、KEIL For…

IDEA 设置类注释模板作者、日期、描述等信息(推荐标准!)

idea注释模版配置 idea作为越来越多程序员使用的开发工具&#xff0c;平时的代码注释也非常的关键&#xff0c;类上注释和方法上注释每次换电脑或者新同事入职都要统一修改&#xff0c;找了网上好多教程都写的乱七八糟的啥都有&#xff0c;为方便统一就自己写一个操作方法&…

【yolov5小技巧(2)】---将yolov5中的特征图以热力图的方式进行可视化

文章目录 &#x1f680;&#x1f680;&#x1f680;前言一、1️⃣ 将特征图可视化的文章CFPNet二、2️⃣yolov5自带的特征图可视化工具三、3️⃣如何将特征图转换成热力图 &#x1f440;&#x1f389;&#x1f4dc;系列文章目录 【yolov5小技巧(1)】—可视化并统计目标检测中的…

Leetcode二叉树刷题

给你一个二叉树的根节点 root &#xff0c; 检查它是否轴对称。 示例 1&#xff1a; 输入&#xff1a;root [1,2,2,3,4,4,3] 输出&#xff1a;true public boolean isSymmetric(TreeNode root) {if(rootnull)return true;return compare(root.left,root.right);}public boole…

Python学习笔记(37)——用xlwings库生成excel

老规矩先pip入xlwings库 STEP1:下载xlwings库 windowsr>>cmd>>pip install xlwings (如果需要不同版本可以到pypi上搜&#xff09; STEP2:完成EXCEL初级创建 请打开您的编写软件~~~~~&#xff08;小编的显示结果为PYCHARM编写的&#xff0c;因为颜色标注好看(…

113.PyQt5_QtPrintSupport_打印操作

我 的 个 人 主 页&#xff1a;&#x1f449;&#x1f449; 失心疯的个人主页 &#x1f448;&#x1f448; 入 门 教 程 推 荐 &#xff1a;&#x1f449;&#x1f449; Python零基础入门教程合集 &#x1f448;&#x1f448; 虚 拟 环 境 搭 建 &#xff1a;&#x1f449;&…

光电传感器的工作原理简介

光电传感器是一种利用光电效应将光信号转换为电信号的传感器。 工作原理 光照射&#xff1a;光电传感器通过光源&#xff08;如LED或激光&#xff09;照射在其表面。 光电转换&#xff1a;光线与传感器材料发生光电反应&#xff0c;产生电信号。这种转换过程涉及到光子与电子的…