class050 双指针技巧与相关题目【算法】
class050 双指针技巧与相关题目【算法】
算法讲解050【必备】双指针技巧与相关题目
code1 922. 按奇偶排序数组 II
// 按奇偶排序数组II
// 给定一个非负整数数组 nums。nums 中一半整数是奇数 ,一半整数是偶数
// 对数组进行排序,以便当 nums[i] 为奇数时,i也是奇数
// 当 nums[i] 为偶数时, i 也是 偶数
// 你可以返回 任何满足上述条件的数组作为答案
// 测试链接 : https://leetcode.cn/problems/sort-array-by-parity-ii/
奇数指针,偶数指针
package class050;// 按奇偶排序数组II
// 给定一个非负整数数组 nums。nums 中一半整数是奇数 ,一半整数是偶数
// 对数组进行排序,以便当 nums[i] 为奇数时,i也是奇数
// 当 nums[i] 为偶数时, i 也是 偶数
// 你可以返回 任何满足上述条件的数组作为答案
// 测试链接 : https://leetcode.cn/problems/sort-array-by-parity-ii/
public class Code01_SortArrayByParityII {// 时间复杂度O(n),额外空间复杂度O(1)public static int[] sortArrayByParityII(int[] nums) {int n = nums.length;for (int odd = 1, even = 0; odd < n && even < n;) {if ((nums[n - 1] & 1) == 1) {swap(nums, odd, n - 1);odd += 2;} else {swap(nums, even, n - 1);even += 2;}}return nums;}public static void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}
code2 287. 寻找重复数
// 寻找重复数
// 给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n)
// 可知至少存在一个重复的整数。
// 假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。
// 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
// 测试链接 : https://leetcode.cn/problems/find-the-duplicate-number/
快指针 慢指针
链表找第一个入环结点
package class050;// 寻找重复数
// 给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n)
// 可知至少存在一个重复的整数。
// 假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。
// 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
// 测试链接 : https://leetcode.cn/problems/find-the-duplicate-number/
public class Code02_FindTheDuplicateNumber {// 时间复杂度O(n),额外空间复杂度O(1)public static int findDuplicate(int[] nums) {if (nums == null || nums.length < 2) {return -1;}int slow = nums[0];int fast = nums[nums[0]];while (slow != fast) {slow = nums[slow];fast = nums[nums[fast]];}// 相遇了,快指针回开头fast = 0;while (slow != fast) {fast = nums[fast];slow = nums[slow];}return slow;}}
code3 42. 接雨水
// 接雨水
// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水
// 测试链接 : https://leetcode.cn/problems/trapping-rain-water/
求i位置:max(min(左侧最大值和右侧最大值)-i位置的高度,0)
package class050;// 接雨水
// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水
// 测试链接 : https://leetcode.cn/problems/trapping-rain-water/
public class Code03_TrappingRainWater {// 辅助数组的解法(不是最优解)// 时间复杂度O(n),额外空间复杂度O(n)// 提交时改名为trappublic static int trap1(int[] nums) {int n = nums.length;int[] lmax = new int[n];int[] rmax = new int[n];lmax[0] = nums[0];// 0~i范围上的最大值,记录在lmax[i]for (int i = 1; i < n; i++) {lmax[i] = Math.max(lmax[i - 1], nums[i]);}rmax[n - 1] = nums[n - 1];// i~n-1范围上的最大值,记录在rmax[i]for (int i = n - 2; i >= 0; i--) {rmax[i] = Math.max(rmax[i + 1], nums[i]);}int ans = 0;// x x// 0 1 2 3...n-2 n-1for (int i = 1; i < n - 1; i++) {ans += Math.max(0, Math.min(lmax[i - 1], rmax[i + 1]) - nums[i]);}return ans;}// 双指针的解法(最优解)// 时间复杂度O(n),额外空间复杂度O(1)// 提交时改名为trappublic static int trap2(int[] nums) {int l = 1, r = nums.length - 2, lmax = nums[0], rmax = nums[nums.length - 1];int ans = 0;while (l <= r) {if (lmax <= rmax) {ans += Math.max(0, lmax - nums[l]);lmax = Math.max(lmax, nums[l++]);} else {ans += Math.max(0, rmax - nums[r]);rmax = Math.max(rmax, nums[r--]);}}return ans;}}
code4 881. 救生艇
// 救生艇
// 给定数组 people
// people[i]表示第 i 个人的体重 ,船的数量不限,每艘船可以承载的最大重量为 limit
// 每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit
// 返回 承载所有人所需的最小船数
// 测试链接 : https://leetcode.cn/problems/boats-to-save-people/
双指针
数组从小到大排序
体重小和体重大一船,或者体重大一船
拓展:两个人体重和只能是偶数才能一船
可以分为奇数数组偶数数组,分别求出再相加
package class050;import java.util.Arrays;// 救生艇
// 给定数组 people
// people[i]表示第 i 个人的体重 ,船的数量不限,每艘船可以承载的最大重量为 limit
// 每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit
// 返回 承载所有人所需的最小船数
// 测试链接 : https://leetcode.cn/problems/boats-to-save-people/
public class Code04_BoatsToSavePeople {// 时间复杂度O(n * logn),因为有排序,额外空间复杂度O(1)public static int numRescueBoats(int[] people, int limit) {Arrays.sort(people);int ans = 0;int l = 0;int r = people.length - 1;int sum = 0;while (l <= r) {sum = l == r ? people[l] : people[l] + people[r];if (sum > limit) {r--;} else {l++;r--;}ans++;}return ans;}}
code5 11. 盛最多水的容器
// 盛最多水的容器
// 给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
// 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水
// 返回容器可以储存的最大水量
// 说明:你不能倾斜容器
// 测试链接 : https://leetcode.cn/problems/container-with-most-water/
双指针l,r
当前height[l]小,l++
否则r–
package class050;// 盛最多水的容器
// 给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
// 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水
// 返回容器可以储存的最大水量
// 说明:你不能倾斜容器
// 测试链接 : https://leetcode.cn/problems/container-with-most-water/
public class Code05_ContainerWithMostWater {// 时间复杂度O(n),额外空间复杂度O(1)public static int maxArea(int[] height) {int ans = 0;for (int l = 0, r = height.length - 1; l < r;) {ans = Math.max(ans, Math.min(height[l], height[r]) * (r - l));if (height[l] <= height[r]) {l++;} else {r--;}}return ans;}}
code6 code6 475. 供暖器
// 供暖器
// 冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
// 在加热器的加热半径范围内的每个房屋都可以获得供暖。
// 现在,给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置
// 请你找出并返回可以覆盖所有房屋的最小加热半径。
// 说明:所有供暖器都遵循你的半径标准,加热的半径也一样。
// 测试链接 : https://leetcode.cn/problems/heaters/
双指针i,j
对于每一个房屋[i]找到最优的供暖器[j],最优半径
package class050;import java.util.Arrays;// 供暖器
// 冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
// 在加热器的加热半径范围内的每个房屋都可以获得供暖。
// 现在,给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置
// 请你找出并返回可以覆盖所有房屋的最小加热半径。
// 说明:所有供暖器都遵循你的半径标准,加热的半径也一样。
// 测试链接 : https://leetcode.cn/problems/heaters/
public class Code06_Heaters {// 时间复杂度O(n * logn),因为有排序,额外空间复杂度O(1)public static int findRadius(int[] houses, int[] heaters) {Arrays.sort(houses);Arrays.sort(heaters);int ans = 0;for (int i = 0, j = 0; i < houses.length; i++) {// i号房屋// j号供暖器while (!best(houses, heaters, i, j)) {j++;}ans = Math.max(ans, Math.abs(heaters[j] - houses[i]));}return ans;}// 这个函数含义:// 当前的地点houses[i]由heaters[j]来供暖是最优的吗?// 当前的地点houses[i]由heaters[j]来供暖,产生的半径是a// 当前的地点houses[i]由heaters[j + 1]来供暖,产生的半径是b// 如果a < b, 说明是最优,供暖不应该跳下一个位置// 如果a >= b, 说明不是最优,应该跳下一个位置public static boolean best(int[] houses, int[] heaters, int i, int j) {return j == heaters.length - 1 ||Math.abs(heaters[j] - houses[i]) < Math.abs(heaters[j + 1] - houses[i]);}}
code7 41. 缺失的第一个正数
// 缺失的第一个正数
// 给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
// 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
// 测试链接 : https://leetcode.cn/problems/first-missing-positive/
双指针
l:表示l左侧的位置上放好l+1的值
r:垃圾区;最好预期1…r的值都有
①nums[l]=l+1,l++
②nums[l]<=l,垃圾
③nums[l]>r,垃圾
④nums[nums[l]-1]=nums[l],重复垃圾
⑤交换(l,nums[l]-1)
返回l+1
package class050;// 缺失的第一个正数
// 给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
// 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
// 测试链接 : https://leetcode.cn/problems/first-missing-positive/
public class Code07_FirstMissingPositive {// 时间复杂度O(n),额外空间复杂度O(1)public static int firstMissingPositive(int[] arr) {// l的左边,都是做到i位置上放着i+1的区域// 永远盯着l位置的数字看,看能不能扩充(l++)int l = 0;// [r....]垃圾区// 最好的状况下,认为1~r是可以收集全的,每个数字收集1个,不能有垃圾// 有垃圾呢?预期就会变差(r--)int r = arr.length;while (l < r) {if (arr[l] == l + 1) {l++;} else if (arr[l] <= l || arr[l] > r || arr[arr[l] - 1] == arr[l]) {swap(arr, l, --r);} else {swap(arr, l, arr[l] - 1);}}return l + 1;}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}}
相关文章:

class050 双指针技巧与相关题目【算法】
class050 双指针技巧与相关题目【算法】 算法讲解050【必备】双指针技巧与相关题目 code1 922. 按奇偶排序数组 II // 按奇偶排序数组II // 给定一个非负整数数组 nums。nums 中一半整数是奇数 ,一半整数是偶数 // 对数组进行排序,以便当 nums[i] 为…...

计算机操作系统4
1.什么是进程同步 2.什么是进程互斥 3.进程互斥的实现方法(软件) 4.进程互斥的实现方法(硬件) 5.遵循原则 6.总结: 线程是一个基本的cpu执行单元,也是程序执行流的最小单位。 调度算法:先来先服务FCFS、短作业优先、高响应比优先、时间片…...
【ASP.NET CORE】EntityFrameworkCore 数据迁移
如果数据库中已经有数据结构,可以使用Scaffold-DbContext来同步model,-connection是字符串,-outputdir 是输入文件夹名称,举例的脚本使用的是sqlserver数据库 通用 Scaffold-DbContext -Connection "DatabaseAddress;Data …...
说说React jsx转换成真实DOM的过程?
在React中,JSX(JavaScript XML)是一种语法糖,用于描述用户界面的结构和组件关系。当你编写React组件并包含JS JSX解析:React中的JSX代码首先会被解析成JavaScript对象。这个过程通常是通过Babel等工具进行的࿰…...

MongoDB知识总结
这里写自定义目录标题 MongoDB基本介绍MongoDB基本操作数据库相关集合相关增删改查 MongoDB基本介绍 简单介绍 MongoDB是一个基于分布式文件存储的数据库。由C语言编写。旨在为WEB应用提供可扩展的高性能数据存储解决方案。 MongoDB是一个介于关系数据库和非关系数据库之间的产…...
【LeeCode】1.两数之和
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回…...
Python 作业答疑_6.15~6.18
一、Python 一班 1. 比较字符串 1.1 问题描述 比较两个字符串A和B,字符串A和B中的字符都是大写字母,确定A中是否包含B中所有的字符。 1.2 问题示例 例如,给出A"ABCD",B"ACD",返回True&#x…...

Diffusion 公式推导
Diffusion:通过扩散和逆扩散过程生成图像的生成式模型 中已经对 diffusion 的原理进行了直观地梳理,本文对其中的数学推导进行讲解,还是基于 DDPM。 目录 一. 预备知识1. 重参数技巧2. 高斯分布的可加性3. 扩散递推式的由来 二. 扩散过程1. 背…...

【C语言快速学习基础篇】之一基础类型、进制转换、数据位宽
文章目录 一、基础类型(根据系统不同占用字节数会有变化)1.1、有符号整形1.2、无符号整形1.3、字符型1.4、浮点型1.5、布尔型 二、进制转换2.1、二进制2.2、八进制2.3、十进制2.4、十六进制2.5、N进制2.6、进制转换关系对应表 三、数据位宽3.1、位3.2、字节3.3、字3.4、双字3.5…...

使用GPT-4V解决Pycharm设置问题
pycharm如何实现关联,用中文回答 在PyCharm中关联PDF文件类型,您可以按照以下步骤操作: 1. 打开PyCharm设置:点击菜单栏中的“File”(文件),然后选择“Settings”(设置)。…...
qt 安装
目录 前言 一、QT在线安装包下载 1.官方网站: 2.镜像(清华大学) 二、QT安装 1.更换安装源 2.安装界面 3.组件选择(重点) 参考 Qt2023新版保姆级 安装教程 前言 本文主要介绍2023新版QT安装过程,…...

【论文合集】在非欧空间中的图嵌入方法(Graph Embedding in Non-Euclidean Space)
文章目录 1. Hyperbolic Models1.1 Hyperbolic Graph Attention Network1.2 Poincar Embeddings for Learning Hierarchical Representations.1.3 Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometry1.4 Hyperbolic Graph Convolutional Neural Net…...

锐捷EWEB网管系统 RCE漏洞复现
0x01 产品简介 锐捷网管系统是由北京锐捷数据时代科技有限公司开发的新一代基于云的网络管理软件,以“数据时代创新网管与信息安全”为口号,定位于终端安全、IT运营及企业服务化管理统一解决方案。 0x02 漏洞概述 Ruijie-EWEB 网管系统 flwo.control.php 中的 type 参数存在…...
Clickhouse在货品标签场景的应用
背景 在电商场景中,我们经常需要对货品进行打标签的操作,简单来说就是对货品进行各种分类,按照价格段进行分组,此时运营人员就可以通过价格段捞取到满足条件的商品了,本文就来简单看下这个场景如何在clickhouse中实现…...
CentOS 7 lvm 更换坏盘操作步骤小记 —— 筑梦之路
背景介绍 硬盘容量不足、硬盘坏道太多等不可控的原因需要更换,要求不能丢失数据进行无损替换硬盘。 操作步骤 1. 将硬盘插入机器,上电连接到服务器 2. 在centos 7 系统中检测是否识别出来硬盘 lsblk 3. 给新插入的硬盘分区 parted /dev/sdc mklabel g…...

zabbix的自动发现和注册、proxy代理和SNMP监控
目录 一、zabbix自动发现与自动注册机制: 1、概念 2、zabbix 自动发现与自动注册的部署 二、zabbix的proxy代理功能: 1、工作流程 2、安装部署 三、zabbix-snmp 监控 1、概念 2、安装部署 四、总结: 一、zabbix自动发现与自动注册…...
以Hub为中心节点的网络技术探析
在计算机网络中,Hub是一个重要的组成部分,它作为中心节点,连接着各个站点,实现数据的传输和通信。本文将对以Hub为中心节点的网络进行深入的技术探析。 首先,我们需要了解什么是Hub。在网络术语中,Hub通常…...

百度推送收录工具-免费的各大搜索引擎推送工具
在互联网时代,网站收录是网站建设的重要一环。百度推送工具作为一种提高网站收录速度的方式备受关注。在这个信息爆炸的时代,对于网站管理员和站长们来说,了解并使用一些百度推送工具是非常重要的。本文将重点分享百度批量域名推送工具和百度…...

物流实时数仓ODS层——Mysql到Kafka
目录 1.采集流程 2.项目架构 3.resources目录下的log4j.properties文件 4.依赖 5.ODS层——OdsApp 6.环境入口类——CreateEnvUtil 7.kafka工具类——KafkaUtil 8.启动集群项目 这一层要从Mysql读取数据,分为事实数据和维度数据,将不同类型的数据…...
奇迹mu 架设过程中可能会出现的问题及解决办法
通常我们在架设奇迹的时候,可能会遇见这种问题那种问题,很多用户都不知道该如何解决,今天我们就来系统的说明一下一些常见的问题,帮助遇见这些问题的用户理清一个架设的思路,更清楚的判断问题出在哪里,该如…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...

UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...

微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...

如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...

苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...

分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...