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

【算法】 滑动窗口—最长无重复子串

        “无重复字符的最长子串”,难度为Medium,看下题目:

        输入一个字符串 s,请计算 s 中不包含重复字符的最长子串长度。

        比如,输入 s = "aabab",算法返回2,因为无重复的最长子串是 "ab" 或者 "ba",长度为2。

        这道题终于有了点新意,不是一套框架就出答案,不过反而更简单了,稍微改一改框架就行了:

package SlidingWindow;import java.util.HashMap;
import java.util.Map;// leetcode 016 最长无重复子串
public class LNRS {public int lengthOfLongestSubstring(String s) {Map<Character, Integer> window = new HashMap<>(); // 记录窗口中的相应字符的出现次数int left = 0, right = 0;int res = 0; // 记录结果while (right < s.length()) {// c 是将要移入窗口的字符char c = s.charAt(right);// 右移窗口right++;// 进行窗口内数据的一系列更新window.put(c, window.getOrDefault(c, 0) + 1);/*** debug 输出的位置***/System.out.println("window:(" + left + ", " + right + ")");/*********************/// 判断左侧窗口是否要收缩while (window.put(c, window.getOrDefault(c, 0)) > 1) { // window need shrink —窗口需要收缩// d 是将要移出窗口的字符char d = s.charAt(left);// 左移窗口left++;// 进行窗口内数据的一系列更新window.put(d, window.getOrDefault(d, 0) - 1);}// 在这里更新答案res = Math.max(res, right - left);}return res;}public static void main(String[] args) {LNRS lnrs = new LNRS();int res = lnrs.lengthOfLongestSubstring("aabab");System.out.println(res);}}

        连 need 和 valid 都不需要,而且更新窗口内数据也只需要简单更新计数器 window 即可。

        当 window[c] 值大于1时,说明窗口中存在重复字符,不符合条件,就该移动 left 缩小窗口了。

        唯一需要注意的是,在哪里更新结果 res 呢?我们要的是最长无重复子串,哪一个阶段可以保证窗口中的字符是没有重复的呢?这里和之前不一样,要在收缩窗口完成后更新 res,因为窗口收缩的 while 条件是存在重复元素,换句话说收缩完成后一定保证窗口中没有重复。

http://www.lryc.cn/news/439263.html

相关文章:

  • SpringBoot2:web开发常用功能实现及原理解析-上传与下载
  • Linux:进程状态和优先级
  • 代码随想录算法训练营day37
  • Java-idea小锤子图标
  • 最强神器Typora 2024(亲测有效)| Markdown 工具推荐
  • 【时时三省】tessy 单元测试 集成测试 专栏 文章阅读说明
  • 力扣刷题(6)
  • TiDB 扩容过程中 PD 生成调度的原理及常见问题丨TiDB 扩缩容指南(一)
  • 匿名管道详解
  • 深度解读MySQL意向锁的工作原理机制与应用场景
  • ZYNQ TCP 协议的远程更新 QSPI Flash
  • 告别繁琐粘贴,CleanClip Mac 版,让复制粘贴变得简单快捷!粘贴队列功能太强大了!
  • 前端基础知识(HTML+CSS+JavaScript)
  • 算力服务器和GPU服务器的区别是什么?
  • 获取Live2d模型
  • 软考架构-层次架构风格
  • Unity射击游戏开发教程:(35)轰炸敌人
  • 【网络】高级IO——select版本TCP服务器
  • 【C++】学完c语言后的c++基础知识补充!(命名空间、输入和输出、缺省函数、函数重载、引用、内联函数代替宏、nullptr代替NULL)
  • uniapp自定义导航栏以及页面加背景
  • MacOS Sonoma(14.x) 大写模式或中文输入法下的英文模式,光标下方永远会出现的CapsLock箭头Icon的去除办法
  • C#基础(10)变长参数和参数默认值
  • Vue转React开发经验分享——hooks写法如何触发react生命周期、如何触发数据更新?
  • 算法入门-贪心1
  • element-plus的面包屑组件el-breadcrumb
  • 推荐几个网盘资源站给大伙,找资源更方便
  • 【Qt】Qml界面中嵌入C++ Widget窗口
  • Python快速入门 —— 第五节:接口开发
  • 利用secureCRT向虚拟机发送文件(secureCRT安装使用教程)
  • AI杂七杂八系列(1)——工程篇