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条件)


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


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


目录
相关文章
|
1天前
|
算法 Java 机器人
Java数据结构与算法:动态规划之斐波那契数列
Java数据结构与算法:动态规划之斐波那契数列
|
1天前
|
算法 安全 Java
Java数据结构与算法:并发数据结构ConcurrentLinkedQueue
Java数据结构与算法:并发数据结构ConcurrentLinkedQueue
|
2天前
|
算法 Java
基于java雪花算法工具类SnowflakeIdUtils-来自chatGPT
基于java雪花算法工具类SnowflakeIdUtils-来自chatGPT
10 3
|
2天前
|
安全 Java
|
20小时前
|
存储 算法 安全
Java中的DES和3DES加密算法详解
Java中的DES和3DES加密算法详解
9 1
|
1天前
|
搜索推荐 算法 Java
Java数据结构与算法:排序算法之冒泡排序
Java数据结构与算法:排序算法之冒泡排序
|
1天前
|
搜索推荐 算法 Java
Java数据结构与算法:排序算法之归并排序
Java数据结构与算法:排序算法之归并排序
|
1天前
|
搜索推荐 算法 Java
Java数据结构与算法:排序算法之插入排序
Java数据结构与算法:排序算法之插入排序
|
1天前
|
搜索推荐 算法 Java
Java数据结构与算法:排序算法之快速排序
Java数据结构与算法:排序算法之快速排序
|
1天前
|
算法 Java 机器人
Java数据结构与算法:查找算法之二分查找
Java数据结构与算法:查找算法之二分查找