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

上海网站 备案专业营销团队公司

上海网站 备案,专业营销团队公司,保障网装修平台,avada做的网站目录 1.前言 2.正文 2.1存在重复数字 2.1.1题目 2.1.2解法一代码 解析: 2.1.3解法二代码 解析: 2.2存在重复数字plus 2.2.1题目 2.2.2代码 2.2.3解析 3.小结 1.前言 哈喽大家好吖,今天来给大家分享双指针算法的相关练习&…


目录

1.前言

2.正文

2.1存在重复数字

2.1.1题目

 2.1.2解法一代码

解析:

2.1.3解法二代码

解析:

2.2存在重复数字plus 

2.2.1题目

2.2.2代码 

2.2.3解析 

3.小结


1.前言

哈喽大家好吖,今天来给大家分享双指针算法的相关练习,题目不多,但却是很经典的双指针的模型,废话不多说让我们开始吧。

2.正文

2.1存在重复数字

2.1.1题目

219. 存在重复元素 II - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/contains-duplicate-ii/?envType=problem-list-v2&envId=sliding-window

 2.1.2解法一代码

class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {// 创建一个 HashMap,用于存储每个元素的最后出现索引HashMap<Integer, Integer> map = new HashMap<>();// 遍历数组中的每个元素for (int i = 0; i < nums.length; i++) {// 检查当前元素是否已经出现在 map 中,并且索引差是否小于等于 kif (map.containsKey(nums[i]) && (i - map.get(nums[i]) <= k)) {return true;  // 如果条件满足,返回 true}// 将当前元素及其索引存入 map 中map.put(nums[i], i);}// 如果遍历完所有元素都没有找到满足条件的对,返回 falsereturn false;}
}
解析:

核心思路:

  • 哈希表存储元素的索引:

    • map 用来存储数组中每个元素的最新出现的索引。map.put(nums[i], i) 会在每次遍历时更新该元素的索引。
    • 通过 map.containsKey(nums[i]) 检查当前元素是否已经在哈希表中出现过,如果出现过,则进一步判断当前索引与该元素上次出现的索引之差是否小于等于 k
  • 判断条件:

    • 如果当前元素已经在哈希表中,并且当前索引 i 与该元素最后一次出现的索引之间的差值 i - map.get(nums[i]) 小于等于 k,则说明找到了符合条件的重复元素对,直接返回 true
    • 如果条件不满足,则将当前元素及其索引存入 map 中,继续遍历下一个元素。
  • 返回值:

    • 如果遍历完所有元素都没有找到满足条件的元素对,则返回 false。 

2.1.3解法二代码

class Solution {public boolean containsNearbyDuplicate(int[] nums, int k){// 使用 HashSet 存储当前窗口内的元素HashSet<Integer> set = new HashSet<>();// 遍历数组中的每个元素for(int i = 0; i < nums.length; i++){// 保证滑动窗口的大小不超过 kif(i > k) set.remove(nums[i - k - 1]);// 如果当前元素已经存在于 set 中,说明找到了重复的元素,返回 trueif(!set.add(nums[i])) return true;}// 如果没有找到符合条件的重复元素,返回 falsereturn false;}
}
解析:

思路核心:

  • HashSet存储当前滑动窗口中的元素:

    • set 是用来存储当前窗口中的元素。如果 set 中已经存在当前元素,则说明找到了一个重复元素,并且这个元素满足索引差不超过 k,因此返回 true
  • 滑动窗口的维护:

    • 使用 if (i > k) 来控制滑动窗口的大小,确保窗口中最多包含 k 个元素。当索引 i 大于 k 时,意味着滑动窗口的左边界已经移动,需要移除 set 中索引 i - k - 1 位置的元素,即 set.remove(nums[i - k - 1])。这样保证了窗口大小不会超过 k
  • 判断重复元素:

    • set.add(nums[i]) 如果当前元素已经在 set 中存在,add 方法会返回 false,表示没有成功添加新元素,此时就说明找到了重复元素,返回 true
    • 如果 set.add(nums[i]) 返回 true,则说明当前元素不重复,继续遍历下一个元素。
  • 返回 false

    • 如果遍历完所有元素后都没有找到重复元素,则返回 false

2.2存在重复数字plus 

2.2.1题目

220. 存在重复元素 III - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/contains-duplicate-iii/description/?envType=problem-list-v2&envId=sliding-window

2.2.2代码 

class Solution {public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {int n = nums.length;// 创建一个 TreeSet 来存储滑动窗口中的元素TreeSet<Long> set = new TreeSet<Long>();// 遍历 nums 数组中的每个元素for (int i = 0; i < n; i++) {// 检查滑动窗口中是否存在满足条件的元素Long ceiling = set.ceiling((long) nums[i] - (long) t);// 如果找到一个元素满足条件,返回 trueif (ceiling != null && ceiling <= (long) nums[i] + (long) t) {return true;}// 将当前元素添加到 TreeSet 中set.add((long) nums[i]);// 保持滑动窗口的大小为 k,如果当前索引 i 大于或等于 k// 则移除窗口中最左边的元素if (i >= k) {set.remove((long) nums[i - k]);}}// 如果遍历完所有元素后都没有找到满足条件的元素对,返回 falsereturn false;}
}

2.2.3解析 

 核心思路:

  • TreeSet 用于查找邻近元素: TreeSet 是一个有序集合,它根据元素的大小自动排列,因此可以快速查找给定范围内的元素。这里,我们使用 ceiling 方法来查找大于等于 nums[i] - t 的最小元素,如果这个元素与当前 nums[i] 的差小于等于 t,则满足题目条件,返回 true

  • 滑动窗口: 我们维护一个大小为 k 的滑动窗口。每次遍历一个新元素时,先在 TreeSet 中查找该元素的邻近值(是否满足条件),然后将当前元素添加到窗口中。为了保持窗口大小为 k,如果当前索引大于等于 k,则移除窗口中最左边的元素。这样,滑动窗口始终保持最新的 k 个元素。

 让我们来模拟一下,假设我们有以下数组:

nums = [1, 5, 9, 1, 5, 9], k = 2, t = 3

在这个例子中,滑动窗口的大小是 2(即最多允许相隔 2 个元素),并且差值要求不超过 3。我们按顺序处理每个元素,检查是否存在符合条件的元素对。

  1. 对于 nums[0] = 1set 为空,直接将 1 添加到 set
  2. 对于 nums[1] = 5,我们查找 set 中是否存在元素 >= 5 - 3 = 2,并且该元素应小于等于 5 + 3 = 8。在 set 中没有满足条件的元素,所以将 5 添加到 set
  3. 对于 nums[2] = 9,我们查找 set 中是否存在元素 >= 9 - 3 = 6,并且该元素应小于等于 9 + 3 = 12。找到 5,它满足条件,所以返回 true

因此,这个例子会返回 true,因为存在元素对 (5, 9),它们的差值为 4,满足 k=2t=3

3.小结

今天的分享到这里就结束了,喜欢的小伙伴不要忘记点点赞点个关注,你的鼓励就是对我最大的支持,加油!

http://www.tj-hxxt.cn/news/16806.html

相关文章:

  • 日本一级a做爰片免费网站重庆森林经典台词 凤梨罐头
  • 企业网站设计制作收费国内重大新闻
  • wordpress first主题seo导航站
  • 网站切换关键词优化包含
  • 台州网站定制软文100字左右案例
  • 做支付宝二维码网站平台推广怎么做
  • 科技为了上大学上交可控核聚变免费阅读站长工具seo综合查询工具
  • 销售 网站深圳sem竞价托管
  • 垂直 网站开发程序google官网
  • 做视频的网站靠什么收入seo入门视频
  • 工信部域名备案查询windows优化大师官方
  • 南京高端网站建设软文关键词排名推广
  • 模板网站有利于做seo吗百度热搜关键词排行榜
  • 上海做网站好的公司百度一下你就知道了百度一下
  • 石家庄网站建设推广报价焦作关键词优化排名
  • 做教师知识网站有哪些宁德seo培训
  • 可以发布外链的网站网站宣传推广方案
  • 红酒网站定位百度客服号码
  • ASP动态网站开发案例教程热搜词排行榜
  • 烟台网站建设联系电话百分百营销软件
  • 公司做网站主机是什么用途一份完整的营销策划书
  • 常州百度搜索优化百度seo收录
  • 虚拟服务器和如何创建网站优化建站
  • 深圳专门做网站关键词seo排名优化
  • 如何改变网站首页栏目推广信息发布平台
  • 建网站服务商建网站费用
  • 洛阳网站设计开发广告的六种广告形式
  • 深圳做网站做公司网站的公司技术短期培训班
  • 双城网站建设哪家好爱战网关键词工具
  • 杭州做网站哪家公司好香港百度广告