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)
	// 提交时改名为trap
	public 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-1
		for (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)
	// 提交时改名为trap
	public 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;
	}

}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/222347.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Isaac Sim教程04 Isaac Sim的高级使用

Isaac Sim教程04 Isaac Sim的高级使用

Isaac Sim 高级使用 版权信息 Copyright 2023 Herman YeAuromix. All rights reserved.This course and all of its associated content, including but not limited to text, images, videos, and any other materials, are protected by copyright law. The author holds…
阅读更多...
EI论文复现：考虑源荷不确定性的含风电-电力系统低碳调度程序代码！

EI论文复现：考虑源荷不确定性的含风电-电力系统低碳调度程序代码！

本程序参考论文《考虑源荷不确定性的含风电-电力系统低碳调度》&#xff0c;程序中考虑了源荷的不确定性&#xff0c;引入模糊机会约束规划来求解不确定性模型&#xff0c;对做相关研究方向的小伙伴非常有帮助&#xff0c;程序算例丰富、注释清晰、干货满满&#xff0c;下面对文…
阅读更多...
JAVA刷题之数组的总结和思路分享

JAVA刷题之数组的总结和思路分享

꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN …
阅读更多...
Amazon Code Whisperer 的正式使用，全新 AI 代码工具等你发现！（内附详细安装步骤图解）

Amazon Code Whisperer 的正式使用，全新 AI 代码工具等你发现！（内附详细安装步骤图解）

文章作者&#xff1a;稚始稚终 关于 Code Whisperer Code Whisperer&#xff0c;亚马逊推出的实时 AI 编程助手&#xff0c;是一项基于机器学习的服务&#xff0c;它可以分析开发者在集成开发环境&#xff08;IDE&#xff09;中的注释和代码&#xff0c;并根据其内容生成多种代…
阅读更多...
【LeetCode:2646. 最小化旅行的价格总和 | DFS + DP】

【LeetCode:2646. 最小化旅行的价格总和 | DFS + DP】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…
阅读更多...
【开发问题解决方法记录】04.dian 权限表单优化

【开发问题解决方法记录】04.dian 权限表单优化

权限表单优化方向&#xff1a; 父级权限从晶点权限表获取做成列表下拉选中 权限名称和编码一行两列 页面id从 select * from APEX_APPLICATION_PAGES where APPLICATION_ID304; 中获取 【遇到的问题1】 DG可以获取到页面信息&#xff0c;但是表和应用程序无法获取到 【问…
阅读更多...
机器学习-逻辑回归

机器学习-逻辑回归

一、引言 逻辑回归&#xff08;Logistic Regression&#xff09;是一种广泛应用于分类问题的监督学习算法。尽管名字中含有“回归”二字&#xff0c;但这并不意味着它用于解决回归问题。相反&#xff0c;逻辑回归专注于解决二元或多元分类问题&#xff0c;如邮件是垃圾邮件还是…
阅读更多...
TSMaster添加注释

TSMaster添加注释

当我们在回放报文的时候&#xff0c;会遇到一些需要添加注释&#xff0c;有以下几种办法进行注释 报文运行时手动注释 在图形窗口回放报文&#xff0c;正在抓取报文或者进行报文回放。工具栏选择添加实时注释&#xff0c;这种办法需要手速快&#xff0c;而且时间对的不是很准…
阅读更多...
App内存优化

App内存优化

一、内存优化介绍 1.背景介绍 内存是大问题但缺乏关注压实骆驼的最后一个稻草&#xff08;堆栈溢出&#xff09; 2.内存问题 内存抖动&#xff1a;锯齿状、GC导致卡顿内存泄露&#xff1a;可用内存减少、频繁GC内存溢出&#xff1a;OOM&#xff0c;程序异常 二、优化工具选…
阅读更多...
jvs智能bi新增：数据集添加sql自定义节点、添加websocket任务进度动态展示等等

jvs智能bi新增：数据集添加sql自定义节点、添加websocket任务进度动态展示等等

智能bi更新功能 新增: 1.数据集添加sql自定义输入节点&#xff0c;支持mysql Oracle数据源&#xff1b; 用户可以从这些数据源中获取数据&#xff0c;并通过SQL语句对数据进行自定义处理和分析。可以帮助用户更加灵活地处理和分析数据&#xff0c;满足各种个性化的需求。 2.…
阅读更多...
识别低效io引起的free buffer waits

识别低效io引起的free buffer waits

产生事发时间段的awr报告 Top 5 wait events 这里重点关注&#xff1a; 1.free buffer waits 2.enq_HW-contention 3.enq:tx-row lock contention enq:HW-contention属于水位线的争用&#xff0c;已经透过alter table allocate extent&#xff0c;提前分配空间,这里不做讨论 …
阅读更多...
spring boot+sharding jdbc实现读写分离

spring boot+sharding jdbc实现读写分离

shigen日更文章的博客写手&#xff0c;擅长Java、python、vue、shell等编程语言和各种应用程序、脚本的开发。记录成长&#xff0c;分享认知&#xff0c;留住感动。 在shigen之前的文章中&#xff0c;写到了Springboot mybatis plus实现读写分离&#xff0c;没有sharding-jdbc的…
阅读更多...
怎么修改按SHIFT键关闭Caps Lock功能？

怎么修改按SHIFT键关闭Caps Lock功能？

win11 Step 1> 设置-> 时间和语言Step 2> 输入Step 3> 高级键盘设置Step 4> 语言栏选项 -> 高级设置-> 按CAPS LOCK键 Step 1> 设置-> 时间和语言 Step 2> 输入 Step 3> 高级键盘设置 Step 4> 语言栏选项 -> 高级设置-> 按CAPS LOCK…
阅读更多...
同调群的维度 和 同调群的秩

同调群的维度 和 同调群的秩

同调群的维度是指同调群中非零元素的最小阶数。与线性代数中对向量空间的维度的理解类似。对同调群&#xff0c;k维同调群的维度是k。 同调群的秩是指同调群中的自由部分的维度。同调群通常包含自由部分和挠部分。同调群的秩是指同调群中自由部分的维度。对同调群&#xff0c;…
阅读更多...
python+django教师下乡支教岗位分配管理系统pycharm毕业设计项目推荐

python+django教师下乡支教岗位分配管理系统pycharm毕业设计项目推荐

本课题使用Python语言进行开发。代码层面的操作主要在PyCharm中进行&#xff0c;将系统所使用到的表以及数据存储到MySQL数据库中&#xff0c;方便对数据进行操作本课题基于WEB的开发平台 1.运行环境&#xff1a;python3.7/python3.8。 2.IDE环境&#xff1a;pycharmmysql5.7; …
阅读更多...
多线程（初阶八：计时器Timer）

多线程（初阶八：计时器Timer）

目录 一、标准库中的计时器 1、计时器的概念 2、计时器的简单介绍 二、模拟实现一个计时器 1、思路 &#xff08;1&#xff09;计数器中要存放任务的数据结构 &#xff08;2&#xff09;存放优先级队列中的类型&#xff1a;自定义任务类MyTimerTask &#xff08;3&…
阅读更多...
用python找到音乐数据的位置，并实现音乐下载

用python找到音乐数据的位置，并实现音乐下载

嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! python更多源码/资料/解答/教程等 点击此处跳转文末名片免费获取 需求分析: 有什么需求要实现? 这些需求可以用什么技术实现? 找到音乐数据的位置, 分析 不同音乐的链接有何规律?https://lx-sycdn.kuwo.cn/b784688662c82db8…
阅读更多...
RocketMq环境搭建

RocketMq环境搭建

目录 MQ作用 RocketMQ背景 MQ对比 RocketMQ环境搭建 搭建dashboard可视化界面 MQ作用 异步解耦削峰 RocketMQ背景 ​ RocketMQ是阿里巴巴开源的一个消息中间件&#xff0c;在阿里内部历经了双十一等很多高并发场景的考验&#xff0c;能够处理亿万级别的消息。2016年开源…
阅读更多...
Win10无法删除文件需要管理员权限的解决方法

Win10无法删除文件需要管理员权限的解决方法

在Win10电脑中&#xff0c;用户想要删除不需要的文件&#xff0c;却收到了需要管理员权限才能删除&#xff0c;导致用户自己无法将文件删除掉。下面小编给大家带来Win10系统删除文件需要权限的解决方法&#xff0c;解决后用户在Win10电脑上就能删除任意文件了。 Win10无法删除文…
阅读更多...
TCP协议实现一对一聊天

TCP协议实现一对一聊天

服务端代码&#xff1a; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.net.ServerSocket; import java.net.Socket; import java.util.Scanner;/*** 发送消息线程*/ class Send e…
阅读更多...
最新文章

Copyright @ 2022~2023