java基础-滑动窗口算法

简介: java基础-滑动窗口算法

正文


小伙伴们,你们好呀!我是老寇!


跟我看两道题


删除有序数组中的重复项I


111.png


class Solution {
    public int removeDuplicates(int[] nums) {
      int len = nums.length;
      if(len < 2) return len;
      int j = 0;
      for(int i = 0; i < len; i++)
        if(nums[j] != nums[i])  nums[++j] = nums[i];
      return j + 1;
    }
}

 

333.png


删除有序数组中的重复项 II


222.png


过程分析(例1)


111.png

111.png

222.png

333.png

class Solution {
    public int removeDuplicates(int[] nums) {
      int len = nums.length,slow = 2;
      for(int fast = 2;fast < len; fast++)
        if(nums[fast] != nums[slow - 2]) nums[slow++] = nums[fast]; 
      return slow;
    }
}


111.png


滑动窗口是基于暴力解法的优化,其强大的思想被应用在很多地方,比如我们熟知的网关限流算法,其中有滑动窗口算法,滑动窗口算法有个缺点,就是临界的问题,现在都采用令牌桶算法来限流,感兴趣的小伙伴可以看我之前的博客springcloud之gateway限流。


做这类题目时,需要找到循环不变量,这是解题的关键。(我理解的循环不变量是一个if条件)


区间不同的定义决定了不同的初始化逻辑、遍历过程中的逻辑。


最后问一句,你们是用什么画算法的过程图的?欢迎在评论下留言!!!


目录
相关文章
|
2月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
92 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
1天前
|
缓存 算法 搜索推荐
Java中的算法优化与复杂度分析
在Java开发中,理解和优化算法的时间复杂度和空间复杂度是提升程序性能的关键。通过合理选择数据结构、避免重复计算、应用分治法等策略,可以显著提高算法效率。在实际开发中,应该根据具体需求和场景,选择合适的优化方法,从而编写出高效、可靠的代码。
15 6
|
2月前
|
存储 缓存 Java
java基础:IO流 理论与代码示例(详解、idea设置统一utf-8编码问题)
这篇文章详细介绍了Java中的IO流,包括字符与字节的概念、编码格式、File类的使用、IO流的分类和原理,以及通过代码示例展示了各种流的应用,如节点流、处理流、缓存流、转换流、对象流和随机访问文件流。同时,还探讨了IDEA中设置项目编码格式的方法,以及如何处理序列化和反序列化问题。
91 1
java基础:IO流 理论与代码示例(详解、idea设置统一utf-8编码问题)
|
2月前
|
消息中间件 Java Kafka
Flink-08 Flink Java 3分钟上手 滑动窗口 SlidingWindow 时间驱动 事件驱动 TimeWindow CountWindow GlobalWindow
Flink-08 Flink Java 3分钟上手 滑动窗口 SlidingWindow 时间驱动 事件驱动 TimeWindow CountWindow GlobalWindow
84 7
|
2月前
|
算法 搜索推荐 Java
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
这篇文章介绍了如何使用Java后端技术,结合Graphics2D和Echarts等工具,生成包含个性化信息和图表的海报,并提供了详细的代码实现和GitHub项目链接。
156 0
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
|
2月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
93 2
|
3月前
|
安全 Java API
【Java面试题汇总】Java基础篇——String+集合+泛型+IO+异常+反射(2023版)
String常量池、String、StringBuffer、Stringbuilder有什么区别、List与Set的区别、ArrayList和LinkedList的区别、HashMap底层原理、ConcurrentHashMap、HashMap和Hashtable的区别、泛型擦除、ABA问题、IO多路复用、BIO、NIO、O、异常处理机制、反射
|
2月前
|
算法 Java Linux
java制作海报一:java使用Graphics2D 在图片上写字,文字换行算法详解
这篇文章介绍了如何在Java中使用Graphics2D在图片上绘制文字,并实现自动换行的功能。
152 0
|
2月前
|
算法 Java 测试技术
数据结构 —— Java自定义代码实现顺序表,包含测试用例以及ArrayList的使用以及相关算法题
文章详细介绍了如何用Java自定义实现一个顺序表类,包括插入、删除、获取数据元素、求数据个数等功能,并对顺序表进行了测试,最后还提及了Java中自带的顺序表实现类ArrayList。
35 0
|
4月前
|
设计模式 缓存 算法
揭秘策略模式:如何用Java设计模式轻松切换算法?
【8月更文挑战第30天】设计模式是解决软件开发中特定问题的可重用方案。其中,策略模式是一种常用的行为型模式,允许在运行时选择算法行为。它通过定义一系列可互换的算法来封装具体的实现,使算法的变化与客户端分离。例如,在电商系统中,可以通过定义 `DiscountStrategy` 接口和多种折扣策略类(如 `FidelityDiscount`、`BulkDiscount` 和 `NoDiscount`),在运行时动态切换不同的折扣逻辑。这样,`ShoppingCart` 类无需关心具体折扣计算细节,只需设置不同的策略即可实现灵活的价格计算,符合开闭原则并提高代码的可维护性和扩展性。
72 2