算法之双指针题型:

双指针例题小总结:

力扣27: 移除元素

力扣题目链接

双指针分为:

快慢双指针:同一个起点,同向出发

相向双指针:从两端出发,方向相反,终会相遇

经典的双指针(快慢双指针) 代码随想录上面有动图,很清楚

 题目:
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

思路:

27.移除元素-双指针法

class Solution {public int removeElement(int[] nums, int val) {// 快慢指针int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {if (nums[fastIndex] != val) {nums[slowIndex] = nums[fastIndex];slowIndex++;}}return slowIndex;}
}

力扣977: 有序数组的平方

力扣题目链接

 题目:给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。示例 1:输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100],排序后,数组变为 [0,1,9,16,100]
示例 2:输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]

也是双指针法(相向指针)

如动画所示:

img

思路:数组其实是有序的, 只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端,不是最左边就是最右边,不可能是中间。此时可以考虑双指针法了,i指向起始位置,j指向终止位置。定义一个新数组result,和A数组一样的大小,让k指向result数组终止位置。如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i]; 。
class Solution {public int[] sortedSquares(int[] nums) {int right = nums.length - 1;int left = 0;int[] result = new int[nums.length];int index = result.length - 1;while (left <= right) {if (nums[left] * nums[left] > nums[right] * nums[right]) {// 正数的相对位置是不变的, 需要调整的是负数平方后的相对位置result[index--] = nums[left] * nums[left];++left;} else {result[index--] = nums[right] * nums[right];--right;}}return result;}
}

力扣209:长度最小的子数组

力扣题目链接

题目:给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。示例:输入:s = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
提示:1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

思路:滑动窗口 实质还是双指针(快慢指针)。

209.长度最小的子数组

class Solution {// 滑动窗口public int minSubArrayLen(int s, int[] nums) {int left = 0;int sum = 0;int result = Integer.MAX_VALUE;for (int right = 0; right < nums.length; right++) {sum += nums[right];while (sum >= s) {result = Math.min(result, right - left + 1);sum -= nums[left++];}}return result == Integer.MAX_VALUE ? 0 : result;}
}

力扣15:三数之和

力扣题目链接(opens new window)

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。

注意: 答案中不可以包含重复的三元组。

示例:

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]

思路:这道题使用双指针做,

代码:

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);// 找出a + b + c = 0// a = nums[i], b = nums[left], c = nums[right]for (int i = 0; i < nums.length; i++) {// 排序之后如果第一个元素已经大于零,那么无论如何组合都不可能凑成三元组,直接返回结果就可以了if (nums[i] > 0) { return result;}if (i > 0 && nums[i] == nums[i - 1]) {  // 去重acontinue;}int left = i + 1;int right = nums.length - 1;while (right > left) {int sum = nums[i] + nums[left] + nums[right];if (sum > 0) {right--;} else if (sum < 0) {left++;} else {result.add(Arrays.asList(nums[i], nums[left], nums[right]));// 去重逻辑应该放在找到一个三元组之后,对b 和 c去重while (right > left && nums[right] == nums[right - 1]) right--;while (right > left && nums[left] == nums[left + 1]) left++;right--; left++;}}}return result;}
}

力扣18:四数之和

力扣题目链接(opens new window)

题意:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。

注意:

答案中不可以包含重复的四元组。

示例: 给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。 满足要求的四元组集合为: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

思路:这道题也是双指针

代码:

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);for (int i = 0; i < nums.length; i++) {// nums[i] > target 直接返回, 剪枝操作if (nums[i] > 0 && nums[i] > target) {return result;}if (i > 0 && nums[i - 1] == nums[i]) {    // 对nums[i]去重continue;}for (int j = i + 1; j < nums.length; j++) {if (j > i + 1 && nums[j - 1] == nums[j]) {  // 对nums[j]去重continue;}int left = j + 1;int right = nums.length - 1;while (right > left) {// nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];if (sum > target) {right--;} else if (sum < target) {left++;} else {result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));// 对nums[left]和nums[right]去重while (right > left && nums[right] == nums[right - 1]) right--;while (right > left && nums[left] == nums[left + 1]) left++;left++;right--;}}}}return result;}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

pytorch代码实现之SAConv卷积

SAConv卷积 SAConv卷积模块是一种精度更高、速度更快的“即插即用”卷积&#xff0c;目前很多方法被提出用于降低模型冗余、加速模型推理速度&#xff0c;然而这些方法往往关注于消除不重要的滤波器或构建高效计算单元&#xff0c;反而忽略了特征内部的模式冗余。 原文地址&am…

Linux查端口占用的几种方式

在Linux中&#xff0c;你可以使用以下几种方式来查看端口的占用情况。 一、使用netstat命令 #安装netstat yum -y install net-tools #检测端口占用 netstat -npl | grep 端口# 几种常规用法 netstat -ntlp //查看当前所有tcp端口 netstat -ntulp | grep 80 //查看所有80端…

java设计模式,简单工厂和抽象工厂有什么区别?

java设计模式&#xff0c;简单工厂和抽象工厂有什么区别&#xff1f; 简单工厂模式&#xff1a; 这个模式本身很简单而且使用在业务较简单的情况下。一般用于小项目或者具体产品很少扩展的情况&#xff08;这样工厂类才不用经常更改&#xff09;。 它由三种角色组成&#xf…

MySQL 8.0.34(x64)安装笔记

一、背景 从MySQL 5.6到5.7&#xff0c;再到8.0&#xff0c;版本的跳跃不可谓不大。安装、配置的差别也不可谓不大&#xff0c;特此备忘。 二、过程 &#xff08;1&#xff09;获取MySQL 8.0社区版&#xff08;MySQL Community Server&#xff09;   从 官网 字样 “MySQL …

卡尔曼滤波公式推导(总结)

假设 小车在t时刻的初始状态可以用Pt&#xff08;当前位置&#xff09;&#xff0c;Vt&#xff08;当前速度&#xff09;&#xff0c;Ut表示加速度&#xff1a; 预测&#xff1a; 利用上一个时刻的旧状态和系统的动量模型&#xff08;如加速度&#xff0c;速度等&#xff09;…

扫码支付系统_分账收款系统_设计开发OctShop

在当今&#xff0c;移动支付在我们生活中已经是不可或缺的东西&#xff0c;以微信和支付宝为代表的扫码支付系统正在各种线下消费场景中使用&#xff0c;给我们日常的生活购物消费带来了不少的便利。第一些第三方的扫码支付系统更是集合了各种支付渠道&#xff0c;买家或消费者…

yolov5添加ECA注意力机制

ECA注意力机制简介 论文题目&#xff1a;ECA-Net: Efficient Channel Attention for Deep Convolutional Neural Networks 论文地址&#xff1a;here 基本原理 &#x1f438; ECANet的核心思想是提出了一种不降维的局部跨通道交互策略&#xff0c;有效避免了降维对于通道注意…

一个CVE漏洞预警知识库

CVE 0x01 免责声明 本仓库所涉及的技术、思路和工具仅供安全技术研究&#xff0c;任何人不得将其用于非授权渗透测试&#xff0c;不得将其用于非法用途和盈利&#xff0c;否则后果自行承担。 无exp/poc&#xff0c;部分包含修复方案 0x02 项目导航 2022.12 CVE-2022-3328&a…

Purple Pi OH(Debian/Ubuntu)使用python控制gpio

本文分享的是Purple Pi OH开源主板搭载Debian/Ubuntu系统如何使用python控制gpio。 Purple Pi OH作为一款兼容树莓派的开源主板&#xff0c;采用瑞芯微RK3566 (Cortex-A55) 四核64位超强CPU,主频最高达1.8 GHz,算力高达1Tops&#xff0c;支持INT8/INT16&#xff0c;支持Tensor…

如何保持 SSH 会话不中断?

哈喽大家好&#xff0c;我是咸鱼 不知道小伙伴们有没有遇到过下面的情况&#xff1a; 使用终端&#xff08;XShell、secureCRT 或 MobaXterm 等&#xff09;登录 Linux 服务器之后如果有一段时间没有进行交互&#xff0c;SSH 会话就会断开 如果正在执行一些非后台命令&#…

模电课设:用Multisim简单了解二极管

1 课设内容 1&#xff09;测试二极管伏安特性电路&#xff1b; 2&#xff09;二极管的整流电路及负载对输出电压和纹波的影响&#xff1b; 2 模型搭建 电路一&#xff1a;测试二极管伏安特性的电路如下图所示&#xff0c;结构十分简单&#xff0c;直流电源串联上二极管组成一…

Kafka3.0.0版本——消费者(消费者组原理)

目录 一、消费者组原理1.1、消费者组概述1.2、消费者组图解示例1.3、消费者组注意事项 一、消费者组原理 1.1、消费者组概述 Consumer Group&#xff08;CG&#xff09;&#xff1a;消费者组&#xff0c;由多个consumer组成。形成一个消费者组的条件&#xff0c;是所有消费者…

娱乐时间 —— 用python将图片转为excel十字绘

最近看蛮多朋友在玩&#xff0c;要么只能画比较简单的&#xff0c;要么非常花时间。想了下本质上就是把excel对应的单元格涂色&#xff0c;如果能知道哪些格子要上什么颜色&#xff0c;用编程来实现图片转为excel十字绘应该是很方便的。 图片的每一个像素点都可以数值化&#x…

(3)MyBatis-Plus待开发

常用注解 TableName MyBatis-Plus在确定操作的表时&#xff0c;由BaseMapper的泛型决定即实体类型决定&#xff0c;且默认操作的表名和实体类型的类名一致,如果不一致则会因找不到表报异常 //向表中插入一条数据 Test public void testInsert(){User user new User(null, &…

python如何学习

功能如此强大、高效的Python&#xff0c;却非常的简单好学&#xff0c;这让学它的同学爱不释手&#xff0c;也让越来越多的互联网企业开始用Python来做主要的开发语言&#xff0c;比如谷歌、Facebook&#xff08;现Meta&#xff09;、豆瓣、知乎等知名互联网公司都在使用Python…

【C++】简单理解:将整数(浮点数)转换为字符串(string),将字符串(string)转换为整数(浮点数)方法

用stringstream类&#xff0c;口诀&#xff1a;过滤一下就转化 头文件#include<sstream> 例子&#xff1a;将整数12和浮点数12.34转化为字符串 int main() {int x 12;double d 12.34;string s;//创建一下对象strstringstream str;//过滤一下就转化str << x;st…

day3_C++

day3_C 思维导图用C的类完成数据结构 栈的相关操作用C的类完成数据结构 循环队列的相关操作 思维导图 用C的类完成数据结构 栈的相关操作 stack.h #ifndef STACK_H #define STACK_H#include <iostream> #include <cstring>using namespace std;typedef int datat…

SpringMVC_拦截器

4.拦截器 4.1拦截器概述 概述&#xff1a;一种动态拦截方法调用的机制&#xff0c;在SpringMVC中动态拦截控制器方法的执行实际开发中&#xff0c;静态资源&#xff08;HTML/CSS&#xff09;不需要交给框架处理&#xff0c;需要拦截的是动态资源 4.2图示 图示 4.3案例实现 …

Win11共享文件夹怎么设置

当我们在使用Win11的过程中有时会因为一些操作需要共享文件夹&#xff0c;那么Win11系统该如何设置共享文件夹呢&#xff0c;下面小编就给大家详细介绍一下Win11设置共享文件夹的方法&#xff0c;有需要的小伙伴快来和小编一起看看吧。 Win11设置共享文件夹的方法&#xff1a;…

最后一块石头的重量 II【动态规划】

最后一块石头的重量 II 有一堆石头&#xff0c;用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合&#xff0c;从中选出任意两块石头&#xff0c;然后将它们一起粉碎。假设石头的重量分别为 x 和 y&#xff0c;且 x < y。那么粉碎的可能结果如下&am…