LeetCode 热题 HOT 100:滑动窗口专题

2023-11-14

LeetCode 热题 HOT 100:https://leetcode.cn/problem-list/2cktkvj/



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

题目链接:https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // key 值为字符,value 值为字符位置 +1,加 1 表示从字符位置的后一个才开始不重复
        Map<Character, Integer> map = new HashMap<>();
        int start = 0; // 滑动窗口的左指针
        int maxLen = 0; // 最大长度
        for(int end = 0; end < s.length(); end ++){
            char ch = s.charAt(end);
            if(map.containsKey(ch)){ // 如果当前元素与窗口中的元素重复,那么更新start。
                // 若遇到 abba 这种字符串,当遍历到第二个 b 时,start 指向第二个 b。
                // 继续遍历到 a 是,map 中 a 的 value 指向第一个 b, 因此需要比较大小
                start = Math.max(start, map.get(ch));
            }
            map.put(ch, end + 1); // 无论是否更新 start,都会更新其 map 数据结构和结果 maxLen
            maxLen = Math.max(maxLen, end - start + 1);
        }
        return maxLen;
    }
}

128. 最长连续序列

题目链接:https://leetcode.cn/problems/longest-consecutive-sequence/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        Set<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) { // 先去重再排序
            set.add(nums[i]);
        }
        int co = 0;
        for (Integer num : set) {
            nums[co++] = num;
        }
        return sliderWindows(nums, set.size());
    }

    public int sliderWindows(int[] nums, int len){
        int start = 0;
        int max = 1;
        for (int end = 1; end < len; end ++) {
            if(nums[end] - nums[end-1] != 1){
                start = end; 
            }
            max = Math.max(max, end - start + 1);
        }
        return max;
    }
}

239. 滑动窗口最大值

题目链接:https://leetcode.cn/problems/sliding-window-maximum/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

通过优先队列模拟堆结构:

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        int[] arr = new int[len-k+1];
        // 优先队列采用大顶堆的结构:存储当前元素和下标索引
        PriorityQueue<int[]> heaps = new PriorityQueue<>((arr1, arr2) -> arr2[0]-arr1[0]);
        
        for(int i = 0; i < k; i ++){
            heaps.add(new int[]{nums[i], i}); // 尾部添加元素
        }
        
        int co = 0;
        arr[co++] = heaps.peek()[0];
        for(int i = k; i < len; i ++){
            heaps.add(new int[]{nums[i], i});
            while(heaps.peek()[1] <= i-k){ 
                // 当数组是 3,1,-1,4 时,滑动窗口大小为 3,当遍历到 4 时堆顶元素 4 已经失效
                // 更大的元素进队时,栈顶元素不用出队了,避免了频繁的出队
                // 当 4 也失效出堆,假设 3 是堆中的最大值,当 4 出堆时调整堆,3 变成堆顶,最终也会根据索引超出范围将 3 出堆。
                heaps.poll(); // 从堆顶出堆,并调整堆
            }
            arr[co++] = heaps.peek()[0];
        }
        return arr;
    }
}

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

题目链接:https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

分别设置比较串和待比较串的窗口,窗口为 26 个字母的出现的次数,遍历比较即可得出结果:

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if(s.length() < p.length()){ // 如果 p 的长度大于待比较的 s 长度,则不存在异位词
            return res;
        }
        int sLen = s.length();
        int pLen = p.length();
        int[] sWin = new int[26];
        int[] pWin = new int[26];

        for(int i = 0; i < pLen; i ++){
            sWin[s.charAt(i) - 'a']++;
            pWin[p.charAt(i) - 'a']++;
        }

        if(Arrays.equals(sWin, pWin)){
            res.add(0);
        }

        for(int i = pLen; i < sLen; i ++){
            sWin[s.charAt(i-pLen) - 'a'] --;
            sWin[s.charAt(i) - 'a'] ++;
            if(Arrays.equals(sWin, pWin)){
                res.add(i-pLen+1);
            }
        }
        return res;
    }
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

LeetCode 热题 HOT 100:滑动窗口专题 的相关文章

  • Java EE 6 和单例

    谁能解释一下在 Java EE 6 应用程序中实现 Singleton 的完整过程 我假设我不应该以声明静态变量的典型方式创建单例 而应该使用 Singleton注解 我必须这样做吗 难道只是声明一下的情况 Singleton就是这样 我还
  • 有没有更简单的方法来分割/重建字符串?

    目前我正在使用String split 像这样 String tmp props get i getFullName split String name for int j 1 j lt tmp length j if j gt 1 nam
  • 检查从 arrayadapter 获取的复选框

    我有标题清单 CheckBox 我想控制默认检查哪一个 所以我试图获得正确的视图并检查它 但由于某种原因它不起作用 知道为什么吗 form checkbox item xml
  • 如果在 addHeader 之前写入正文,HttpServletResponse 会丢失标头吗?

    环境 Java HotSpot TM 64 位服务器 VM 内部版本 16 3 b01 混合模式 tomcat6 当我使用HttpServlet发送html页面时 如下所示 resp getWriter append body body i
  • 从另一个进程捕获 system.out 消息

    我有一个 JVM 1 它启动 JVM 2 我希望能够在 JVM 1 中监视来自 JVM 2 的 System out println 调用 直接的方法是 JVM A 执行系统命令来启动 JVM B 然后 JVM A 读取 B 的所有输出 S
  • Eclipse 无法识别 persistence.xml 的内容

    我在 eclipse 中收到以下错误 persistence xml 文件没有可识别的内容 我的 persistence xml 文件在我的应用程序中工作得很好 但 eclipse 一直给我这个错误 我在移动文件并使用 m2eclipse
  • JTree ConvertValueToText 返回在更改时被截断

    我有一个自定义树实现convertValueToText 此实现取决于某些全局状态 如果返回的字符串比先前返回的字符串更长 实际上我认为更宽 因为以像素为单位触发它 则文本将被截断并用 填充 当重绘是由 取消 选择元素或某个元素引起时 情况
  • Eclipse RCP - 将视图与编辑器区域堆叠?

    在开发 Eclipse RCP 应用程序时 是否可以将视图与编辑器区域堆叠在一起 像这样 我有多个列表 表格 我想创建一种预览组合 当通过单击鼠标选择列表上的项目时 我希望我的预览合成显示该项目的数据 如果用户双击某个项目 我想在预览合成后
  • ThreadPoolExecutor 和队列

    我以为使用线程池执行器 http docs oracle com javase 6 docs api java util concurrent ThreadPoolExecutor html我们可以提交Runnables 要在以下位置执行B
  • 用于 Eclipse 的 Resharper [关闭]

    就目前情况而言 这个问题不太适合我们的问答形式 我们希望答案得到事实 参考资料或专业知识的支持 但这个问题可能会引发辩论 争论 民意调查或扩展讨论 如果您觉得这个问题可以改进并可能重新开放 访问帮助中心 help reopen questi
  • SQlite 获取最近的位置(带有纬度和经度)

    我的 SQLite 数据库中存储有纬度和经度的数据 我想获取距我输入的参数最近的位置 例如我当前的位置 纬度 经度等 我知道这在 MySQL 中是可能的 并且我已经做了相当多的研究 SQLite 需要一个自定义外部函数来实现半正弦公式 计算
  • Web 服务客户端的 AXIS 与 JAX-WS

    我决定用Java 实现Web 服务客户端 我已经在 Eclipse 中生成了 Axis 客户端 并使用 wsimport 生成了 JAS WS 客户端 两种解决方案都有效 现在我必须选择一种来继续 在选择其中之一之前我应该 考虑什么 JAX
  • 按钮悬停和按下效果 CSS Javafx

    我是 CSS 新手 为按钮定义了以下 CSS 样式 其中id并且应用了自定义样式 但不应用悬停和按下效果 bevel grey fx background color linear gradient f2f2f2 d6d6d6 linear
  • 在Java内存管理中,“PS”代表什么?

    每当我看到 Java 中对内存的引用时 各种空格总是以 PS 为前缀 PS 是什么意思 它开始困扰我 到目前为止我唯一的猜测是 泳池空间 但这将是多余的 例子 PS伊甸园空间 PS 幸存者空间 PS 终身空间 老一代 PS Perm Gen
  • 对于双核手机,availableProcessors() 返回 1

    我最近购买了一部 Moto Atrix 2 手机 当我尝试查看手机中的处理器规格时 Runtime getRuntime availableProcessors 返回 1 proc cpuinfo 也仅包含有关处理器 0 的信息 出于好奇
  • Eclipse 如何创建一个未解决编译问题的类?

    当我尝试使用 javac 编译此类时 出现编译错误并且未创建 Test class public class Test public static void main String args int x 1L lt this cannot
  • Android - 从渲染线程内结束活动

    下午好 我不熟悉 android 中的活动生命周期 并且一直在尽可能地阅读 但我不知道如何以良好的方式解决以下问题 我有一个使用 GLSurfaceView 的活动来在屏幕上绘制各种内容 在这个 GLSurfaceView 的渲染线程中 我
  • 空检查时可能未初始化错误

    我正在检查变量是否已初始化 但此时 netbeans 给了我variable reader might not have been initialized警告 我该如何解决 抑制这个问题 这是我的代码 摘要 final Reader rea
  • Android Webview:无法调用确定的可见性() - 从未见过 pid 的连接

    我有一个 Android Webview 当我单击链接下载文件 pdf 图像等 时 我收到一条错误消息 Error message Cannot call determinedVisibility never saw a connectio
  • Java有没有类似微软CHESS的工具?

    是否有类似于 Microsoft 的现有 Java 工具CHESS http research microsoft com chess 或者 CHESS 源代码是否开放 以便我可以尝试将其转换为 Java 谷歌的织线工 http code

随机推荐

  • 版本号比较 [java]

    原文地址 java版本号比较 思路 将版本号按点分割 并转成数字类型 放入list 取两个版本位数的最大数 如 1 0 1为3位 1 0 0 1为4位 将位数不够的版本进行补全 不够部分补成0 从第一位开始比较 出现大于情况返回1 出现小于
  • 为什么米聊干不过微信

    1 核心功能不稳定 2 广播太多用户体验差 3 取名太局限 4 发展新朋友能力有限 5 运营能力差
  • C++set容器set和multiset区别

    C set容器set和multiset区别 学习目标 掌握set和multiset的区别 区别 set不可以插入重复数据 而multiset可以 set插入数据的同时会返回插入结果 表示插入是否成功 multiset不会检测数据 因此可以插
  • QT 自定义信号和槽

    好久没有静下心来思考了 每天靠工作驱动 忙碌但不踏实 QT信号与槽机制一直在用 也会用 但只是知其然不知其所以然 今天临近下班给自己点清醒的时间 详细了解了下 总结如下 信号与槽机制是QT中不同对象相互通信的一种方法 有两种写法 第一种是S
  • Cassandra创建键空间(Keyspace)

    Cassandra查询语言 CQL 可帮助开发人员与Cassandra沟通交互 Cassandra查询语言的语法与SQL非常相似 什么是键空间 Keyspace 键空间 Keyspace 是用于保存列族 用户定义类型的对象 键空间 Keys
  • ios 超签签名服务器搭建(超签)

    为什么要搭建签名服务器吗 因为应用不能上架App Store 使用企业签名频繁掉签造成客户流失 用户体验不好 ios安装的app有几种方式吗 1 App Store 安装 符合法律法规的能走app Store的app 2 企业签名安装 灰色
  • Paxos算法细节详解(一)--通过现实世界描述算法

    Paxos算法细节详解 一 通过现实世界描述算法 Paxos分析 最近研究paxos算法 看了许多相关的文章 概念还是很模糊 觉得还是没有掌握paxos算法的精髓 所以花了3天时间分析了libpaxos3的所有代码 此代码可以从https
  • SpringBoot_5

    SpringBoot对静态资源的映射规则 如果我们需用给web项目中添加css js html文件的话 我们会发现此时没有webapp目录 由于springboot是以jar包的方式打包程序的因此是没有webapp目录的 那么我们的css
  • VMware虚拟机从一台电脑复制到另一台电脑

    在一台电脑上利用虚拟机创建了centos 如果想在家里的电脑虚拟机上也运行centos 不用再重新安装以及漫长的安装等待了 可以利用先前在虚拟机上安装centos生成的 vmx文件和 vmdk文件 拷贝到U盘 再重新导入到新电脑就可以了 省
  • DBMS_STATS分析表 (zt) dbms_stats.set_table_stats 手工设置统计信息

    作用 DBMS STATS GATHER TABLE STATS统计表 列 索引的统计信息 DBMS STATS GATHER TABLE STATS的语法如下 DBMS STATS GATHER TABLE STATS ownname V
  • 关于React + Antd 按需引入样式未生效问题

    第一步 npm install antd 安装antd 第二步 在根目录下创建 babelrc文件 配置按需引入需要用到的plugin npm install save dev import babel import presets bab
  • 跨服务器共享文件,不同服务器之间实现文件共享

    不同服务器之间实现文件共享 内容精选 换一换 表1列出了弹性文件服务的常用功能 在使用弹性文件服务之前 建议您先通过常用概念介绍了解NFS CIFS等基本概念 以便更好地理解弹性文件服务提供的功能 表示该类型的文件系统支持该功能 表示该类型
  • 自定义指令的说明和注册

    自定义指令说明 Vue3 除了核心功能默认内置的指令 v model 和 v show Vue 也允许注册自定义指令 v xxx 注意 代码复用和抽象的主要形式是组件 然而 有的情况下 你仍然需要对普通 DOM 元素进行底层操作 这时候就会
  • Linux/多线程的同步与互斥

    线程安全 多个执行流对资源进行争抢访问 但不会产生数据二义性 线程安全的实现 同步 互斥 同步 通过条件判断实现对临界资源访问的合理性 互斥 通过同一时间对临界资源的唯一访问 实现对临界资源访问的安全性 互斥锁 互斥的实现 互斥锁 在多任务
  • 第一次使用Eclipse:编写简单的Java小程序

    通过前部分的学习 了解了Java的安装和配置 那么从现在开始 要开始自己着手编写Java程序 学习一门编程语言 学会编写的第一个程序一般都是写一个输出 hello World 语句的小程序来表示自己开始学习这门语言 那么这篇教程也不例外 因
  • fsnotify 与 too many open files

    fsnotify fsnotify 是用来监听文件 目录变化的一个 golang 开源库 在 Linux 系统使用中 遇到了too many open files问题 首次尝试 通常 有 2 处配置太小 会触发too many open f
  • 最惊艳的sql

    select from girls where age between 18 and 20 and boyfriend is null order by cup desc
  • 不管人工智能发展如何 开发者都有必要了解 Linux 内核

    Linux内核在计算机世界的地位有目共睹 称它为计算机世界的基石也不为过 而且它还是全球最大的开源项目 几乎最知名的科技公司都参与其中 包括谷歌 Red Hat SUSE Intel Facebook 甲骨文和华为等 当然还包括Linux的
  • 将cmd中输出数据 保存为TXT文本

    原文 http blog sina com cn s blog 6d2d58cd0100x7zw html 在使用Windows XP中的cmd exe工具时 有时候我们想要把我们的输入命令及结果保存起来 但是用复制的方法过于麻烦 有时输出
  • LeetCode 热题 HOT 100:滑动窗口专题

    LeetCode 热题 HOT 100 https leetcode cn problem list 2cktkvj 文章目录 3 无重复字符的最长子串 128 最长连续序列 239 滑动窗口最大值 438 找到字符串中所有字母异位词 3