优选算法精品——双指针

移动零

算法原理:

1.数组划分,数组分块

2.双指针算法

(利用数组下标来充当指针)

两个指针的作用:

cur:从左往右扫描数组,遍历数组

dest:已处理的区间内,非零元素的最后一个位置


代码实现:

cur 从前往后遍历的过程中:

1.遇到0元素:cur++;

2.遇到 非零元素:

swap(dest + 1, cur);
dest++, cur++;

class Solution {public void move(int[] nums) {for (int cur = 0, dest = -1; cur < nums.length; cur++) {if (nums[cur] != 0) {dest++;// 交换当前元素与目标位置的元素int temp = nums[cur];nums[cur] = nums[dest];nums[dest] = temp;}}}
}

复写零

2.算法原理

解法:双指针算法

先根据“异地”操作,然后优化成双指针下的“就地”操作,先找到最后一个“复写”的数;

双指针算法

1.先判断 cur位置的值

2. 决定dest向后移动一步或者两步

3.判断一下dest是否已经到结束为止

4. cur++

1.5处理一下边界情况

代码:

class Solution {public void duplicateZeros(int[] arr) {int n = arr.length;int top = 0;int i = -1;while (top < n) {i++;if (arr[i] != 0) {top++;} else {top += 2;}}int j = n - 1;if (top == n + 1) {arr[j] = 0;j--;i--;} while (j >= 0) {arr[j] = arr[i];j--;if (arr[i] == 0) {arr[j] = arr[i];j--;} i--;}}
}

快乐数

题目解析:

2.算法原理

2.1第一种情况不是快乐树,那么最后值不为一,且会返回到原来值,形成一个环

2.2第二种情况是快乐树,那么最后值为一,形成一个全是一的环

因此,我们只需要采用快慢指针法,判断他们相遇时环中值是否为一,若为一则是快乐树,反之

3.代码实现

class Solution {public int bitSum(int n) {int sum = 0;while (n > 0) { // 确保 n 大于 0int t = n % 10;sum += t * t;n = n / 10;}return sum;}public boolean isHappy(int n) {int slow = n;int fast = bitSum(n);while (slow != fast) {slow = bitSum(slow); // 更新 slowfast = bitSum(bitSum(fast)); // 更新 fast}return slow == 1; // 检查 slow 是否到达 1}
}

解析:

  1. bitSum 方法:循环条件现在正确检查 n > 0,确保我们能处理完所有的数字位。

  2. isHappy 方法

    • slow 指针初始为 n,会通过数字的平方和序列逐步更新。
    • fast 指针通过两次调用 bitSum 来加快循环检测的速度。
    • 当 slow 和 fast 相遇时,表示可能出现了循环或达到了 1。

盛水最多的容器:

题目解析:
计算两条直线与x轴围成的水的体积,以最低的线计算高

算法原理:

将各个线的高度看作一个数组,采双指针法,分别计算每个容器的体积,并比较出最大的容器

class Solution {public int maxArea(int[] height) {int left = 0, right = height.length - 1, volume = 0;while (left < right) {int v = Math.min(height[left], height[right]) * (right - left);volume = Math.max(volume, v);// 移动较短的边if (height[left] < height[right]) {left++;} else {right--;}}return volume;}
}

有效三角形的个数

2.算法原理

1.暴力算法:

for(int i=0;i<arr.length;i++){

for(int j=0;j<arr.length;j++){

for(int k=0;k<arr.length;k++){

check(i,j,k);

}

}

}

2.利用单调性,双指针算法

1.先固定最大的数

2.在最大的左区间内使用双指针算法,统计出三元组的个数

1a+b>c  left=right,right--;

2.a+b<=c  left++

3.代码实现

public int solution{
Arrays.sort(nums);
int ret=0,n=nums.length;
for(int i=n-1;i>=2;i--){
int left=0,right=i-1;
while(left>right){
if(nums[left]+nums[right]>nums[i]){
ret+=right-left;
right--;}else{
left++;
}
}
}
return ret;
}

和为s的两个数字

算法原理:
1.暴力算法

for(int i=0;i<arr.length;i++){

for(int j=0;j<arr.length;j++){

check(i,j);

}

}

2.双指针(与上题同理)

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int i = 0;int j = nums.size() - 1;//双指针while(i < j){auto s = nums[i] + nums[j];if(s < target)i++;if(s > target)j--;if(s == target)return{nums[i], nums[j]};}return {};}
};

到这里竹竹零就要和大家说再见了

9a90bc9fb4c3409c9569951569288f5a.png

希望时光不负赶路人,愿我们做最好的自己!!!

如果您觉得有失偏颇请您在评论区指正,如果您觉得不错的话留个好评再走吧!!

您的鼓励就是对我最大的支持!  ! !

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

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

相关文章

音视频入门基础:FLV专题(22)——FFmpeg源码中,获取FLV文件音频信息的实现(中)

本文接着《音视频入门基础&#xff1a;FLV专题&#xff08;21&#xff09;——FFmpeg源码中&#xff0c;获取FLV文件音频信息的实现&#xff08;上&#xff09;》&#xff0c;继续讲解FFmpeg获取FLV文件的音频信息到底是从哪个地方获取的。本文的一级标题从“四”开始。 四、音…

一个由Deno和React驱动的静态网站生成器

大家好&#xff0c;今天给大家分享一个由 Deno React 驱动的静态网站生成器Pagic。 项目介绍 Pagic 是一个由 Deno React 驱动的静态网站生成器。它配置简单&#xff0c;支持将 md/tsx 文件渲染成静态页面&#xff0c;而且还有大量的官方或第三方主题和插件可供扩展。 核心…

已解决,部署GPTSoVITS报错‘AsyncRequest‘ object has no attribute ‘_json_response_data‘

部署GPTSoVITS过程中&#xff0c;开启一键三连进程发生&#xff0c;报错AsyncRequest object has no attribute _json_response_data 具体报错内容为 (GPTSoVITS) PS D:\Code\GPT-SoVITS-beta0706> python webui.py Running on local URL: http://0.0.0.0:9874 IMPORTANT:…

Chrome 130 版本开发者工具(DevTools)更新内容

Chrome 130 版本开发者工具&#xff08;DevTools&#xff09;更新内容 一、网络&#xff08;Network&#xff09;面板更新 1. 重新定义网络过滤器 网络面板获新增了一些过滤条件&#xff0c;这些过滤条件是根据反馈重新设计的&#xff0c;特定于类型的过滤条件保持不变&…

Java之包,抽象类,接口

目录 包 导入包 静态导入 将类放入包 常见的系统包 抽象类 语法规则 注意事项&#xff1a; 抽象类的作用 接口 实现多个接口 接口间的继承 接口使用实例 &#xff08;法一&#xff09;实现Comparable接口的compareTo()方法 &#xff08;法二&#xff09;实现Comp…

【linux】HTTPS 协议原理

1. 了解 HTTPS 协议原理 &#xff08;一&#xff09;认识 HTTPS HTTPS 也是一种应用层协议&#xff0c;是在 HTTP 协议的基础上引入了一个加密层 因为 HTTP协议的内容都是按照文本的方式进行传输的&#xff0c;这个过程中&#xff0c;可能会出现一些篡改的情况 &#xff08;…

sql server 文件备份恢复

备份情况 在备份 lys_log_1324.bak 日志文件前&#xff0c;删除table_1表 现在恢复文件 恢复文件&#xff08;使用norecovery&#xff09; RESTORE DATABASE [lys] FILE Nlys, FILE Nlys_02 FROM DISK ND:\liyuanshuai\lys_filegroup.bak WITH FILE 1, NORECOVERY, …

Docker-安装

操作系统&#xff1a;Ubuntu 20.04.6 LTS 更新apt sudo apt update 删除旧版本docker sudo apt-get remove docker docker-engine docker.io 安装docker sudo apt install docker.io 查看docker版本 docker --version 启动docker 启动docker sudo systemctl start docker 启用…

CM API方式设置YARN队列资源

简述 对于CDH版本我们可以参考Fayson的文章,本次是CDP7.1.7 CM7.4.4 ,下面只演示一个设置队列容量百分比的示例,其他请参考cloudera官网。 获取cookies文件 生成cookies.txt文件 curl -i -k -v -c cookies.txt -u admin:admin http://192.168.242.100:7180/api/v44/clusters …

Openlayers高级交互(18/20):根据feature,将图形适配到最可视化窗口

本示例的目的是介绍如何在vue+openlayers中使用extent,使用feature fit的方式来适配窗口。当加载到页面上几个图形要充分展示在窗口的时候,可以用这种方式来平铺到页面中。 效果图 专栏名称内容介绍Openlayers基础实战 (72篇)专栏提供73篇文章,为小白群体提供基础知识及示…

鸿蒙HarmonyOS开发:给应用添加基础类型通知和进度条类型通知(API 12)

文章目录 一、通知介绍1、通知表现形式2、通知结构3、请求通知授权 二、创建通知1、发布基础类型通知2、发布进度类型通知3、更新通知4、移除通知 三、设置通知通道1、通知通道类型 四、创建通知组五、为通知添加行为意图1、导入模块。2、创建WantAgentInfo信息。4、创建WantAg…

Armv8的安全启动

目录 1. Trust Firmware 2. TF-A启动流程 3. TF-M启动流程 3.1 BL1 3.2 BL2 4.小结 在之前汽车信息安全 -- 再谈车规MCU的安全启动文章里&#xff0c;我们详细描述了TC3xx 、RH850、NXPS32K3的安全启动流程&#xff0c;而在车控类ECU中&#xff0c;我们也基本按照这个流程…

CAN总线学习笔记(1、CAN总线定义)

CAN总线学习笔记&#xff08;1、CAN总线定义&#xff09; 江协科技CAN总线入门教程视频学习笔记 CAN特性 两根通信线&#xff08;CAN_H\CAN_L&#xff09;,两根线&#xff0c;无需工地 差分信号&#xff0c;抗干扰能力强 高速CAN&#xff08;ISO11898&#xff09;&#xff…

【算法】【优选算法】双指针(下)

目录 一、611.有效三⻆形的个数1.1 左右指针解法1.2 暴力解法 二、LCR 179.查找总价格为目标值的两个商品2.1 左右指针解法2.2 暴力解法 三、15.三数之和3.1 左右指针解法3.2 暴力解法 四、18.四数之和4.1 左右指针解法4.2 暴力解法 一、611.有效三⻆形的个数 题目链接&#x…

Docker 镜像体积优化实践:从基础镜像重建到层压缩的全流程指南

​ 由于最近在发布的时候发现docker镜像体积变得越来越大&#xff0c;导致整个打包发布流程变得非常耗时了。所以又接到一个差事&#xff0c;优化最终镜像体积。顺便也记录一下docker镜像体积优化的一些步骤。 大概步骤可以分为以下几个步骤&#xff1a; 重做基础镜像&#x…

路径规划 | ROS中多个路径规划算法可视化与性能对比分析

目录 0 专栏介绍1 引言2 禁用局部规划器3 路径规划定性对比实验3.1 加载路径规划器和可视化插件3.2 设置起点和终点3.3 选择规划器规划3.4 不同规划器对比3.5 路径保存和加载 4 路径规划定量对比实验4.1 计算规划耗时4.2 计算规划长度4.3 计算拓展节点数4.4 计算路径曲率4.5 计…

十四届蓝桥杯STEMA考试Python真题试卷第二套第五题

来源:十四届蓝桥杯STEMA考试Python真题试卷第二套编程第五题 本题属于迷宫类问题,适合用DFS算法解决,解析中给出了Python中 map() 和列表推导式的应用技巧。最后介绍了DFS算法的两种常见实现方式——递归实现、栈实现,应用场景——迷宫类问题、图的连通性、树的遍历、拓朴排…

【CSS】——基础入门常见操作

阿华代码&#xff0c;不是逆风&#xff0c;就是我疯 你们的点赞收藏是我前进最大的动力&#xff01;&#xff01; 希望本文内容能够帮助到你&#xff01;&#xff01; 目录 一&#xff1a;CSS引入 二&#xff1a;CSS对元素进行美化 1&#xff1a;style修饰 2&#xff1a;选…

RV1126-SDK学习之OSD实现原理

RV1126-SDK学习之OSD实现原理 前言 本文简单记录一下我在学习RV1126的SDK当中OSD绘制的原理的过程。 在学习OSD的过程当中&#xff0c;可能需要补充的基础知识&#xff1a; OSD是什么&#xff1f; BMP图像文件格式大致组成&#xff1f; 图像调色&#xff08;Palette&#…

Vehicle OS软件平台解决方案

在智能汽车快速迭代的趋势之下&#xff0c;广义操作系统Vehicle OS应运而生&#xff0c;针对应用软件开发周期缩短和底层硬件迭代速度加快的背景&#xff0c;Vehicle OS将应用软件开发和底层硬件迭代解耦。它降低了迭代工作量并节约成本&#xff0c;用标准化的接口来助力软件定…