算法每日练 -- 双指针篇(持续更新中)

介绍:

        常见的双指针有两种形式,一种是对撞指针(左右指针),一种是快慢指针(前后指针)。需要注意这里的双指针不是 int* 之类的类型指针,而是使用数组下标模拟地址来进行遍历的方式。

对撞指针:

  • 对撞指针一般用于顺序结构中。
  • 对撞指针从两端向中间移动,一个指针从最左端开始,另一个从最又端开始,然后逐渐往中间逼近。
  • 对撞指针的终止条件一般是两个指针相遇或者错开(也可能是在循环内部找到结果直接跳出循环),也就是left == right(两个指针指向同一个位置)或者left > right(两个指针错开)。

 快慢指针:

        快慢指针又称为龟兔赛跑算法,其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。这种方法对于处理环形链表或数组非常有用。其实不单单是环形链表或者是数组,如果我们要研究的问题出现循环往复的情况时,都可以考虑使用快慢指针的思想。

练习

1、移动零

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

提示:

  • 1 <= nums.length <= 10^4
  • -2^31 <= nums[i] <= 2^31 - 1

 算法原理:

        本道题采用的是快排思想:数组分块的方法,数组分块是一种常见题型,主要是根据一种划分方式,将数组的内容分成左右两部分。这种类型的题目一般使用双指针来解决。

思路:

        在本题中,我们可以用一个 cur 来扫描整个数组,另一个 dest 来记录非零元素序列的最后一个位置。根据 cur 在扫描过程中,遇到的不同情况,分类处理,实现数组划分。在 cur 遍历期间,使[ 0, dest ]的元素全部都是非零元素,[ dest+1, cur-1 ]的元素全为0。

  1. 初始化 cur = 0(用来遍历数组),dest = -1(指向非零元素的最后一个位置)。因为刚开始我们不知道最后一个非零元素在什么位置,因此初始化为-1。
  2. cur 依次往后遍历元素,遍历到的元素会分为两种情况:
  • 遇到的元素值为0,此时 cur 直接 ++。因为我们的目标是让[ dest+1, cur-1 ]内的元素全部为0,因此当 cur 遇到 0 的时候,直接 ++,就可以让 0 在 cur-1 的位置上,从而保持在[ dest+1, cur-1 ]内。
  • 遇到的元素值不为0,此时 dest++,并且交换 cur 位置和 dest 位置的元素,之后让cur++,扫描下一个元素。

        因为 dest 指向的位置是非零元素区间的最后一个位置,如果扫描到一个新的非零元素,那么它的位置应该在 dest+1 的位置上,因此 dest 先++;

        dest++ 之后,指向的元素就是 0 元素(因为非零元素区间末尾最后一个元素就是0),因此可以交换到cur所处的位置上,实现[ 0, dest ]的元素全部都是非零元素,[ dest+1, cur-1 ]的元素都是0。

代码演示:

class Solution {
public:void moveZeroes(vector<int>& nums) {int cur = -1;int dest = 0;for(size_t dest = 0; dest<nums.size();dest++){if(nums[dest] != 0){cur++;std::swap(nums[cur], nums[dest]);}}}
};

2、复写零

        给你一个长度固定的整数数组 arr ,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。注意:请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改,不要从函数返回任何东西。

提示:

  • 1 <= arr.length <= 10^4
  • 0 <= arr[i] <= 9

解题思路:(原地复写-双指针)

        如果从前向后进行原地复写操作的话,由于0的出现会复写两次,导致没有复写的数会被覆盖掉。因此我们选择从后往前的复写策略。

        而从后往前复写需要我们找到最后一个复写的元素,因此我们的思路可分为两步:

  1.  先找到最后一个复写的元素。
  2.  然后从后向前进行复写操作。

算法流程:

  • 初始化两个指针cur = 0, dest = 0;
  • 找到最后一个复写的元素:当 cur < n 时循环,判断cur位置的元素,如果为0,dest往后移动两位,否则移动一位。判断dest是否已经到结束位置,如果结束就break终止循环;如果没有结束,cur++,继续判断。
  • 判断dest是否越界:如果越界到n位置,执行(n-1位置元素值修改为0,cur向前移动一步,dest位置向前移动两步)。
  • 从cur位置开始往前遍历原数组,因此还原出复写后的结果数组:判断cur位置的值(如果是0,dest以及dest-1位置元素值修改为0,dest-=2;如果是非0,dest位置修改成非0值,dest-=1),cur--,复写下一个位置。

代码演示:

class Solution
{
public:void duplicateZeros(vector<int>& arr){// 1. 先找到最后⼀个数int cur = 0, dest = -1, n = arr.size();while (cur < n){if (arr[cur]) dest++;else dest += 2;if (dest >= n - 1) break;cur++;}// 2. 处理⼀下边界情况if (dest == n){arr[n - 1] = 0;cur--; dest -= 2;}// 3. 从后向前完成复写操作while (cur >= 0){if (arr[cur]) arr[dest--] = arr[cur--];else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}}
};

3、快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为:

  • 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1,那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ;不是,则返回 false 。

提示:

  • 1 <= n <= 2^31 - 1

题目分析:

        为了方便叙述,我将 “对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和”这一操作记为 x 操作。题目告诉我们,当我们不断重复 x 操作时,计算会出现两种死循环方式:

  • 一种是一直在1中死循环。
  • 另一种是在历史计算的数据中死循环,但始终不会变为1。

        由于上述的两种情况只会出现一种,因此,我们只要能确定循环是在第一种情况还是第二种情况中进行,就可以得到结果。

证明:

  •   我们知道输入的元素最大值为2 ^ 31 - 1 = 2147483647,我们取更大的9999999999,则经过一次变化后的最大值为 9 ^ 2 * 10 = 810,也就是说变化的区间在[ 1, 810 ]之间。
  • 根据鸽巢原理,一个数变化811次之后,必然会形成一个循环;
  • 因此变化的过程最终会走到一个圈里,因此本题可以使用快慢指针解决。

算法思路:

        重复执行 x 操作后,数据会陷入到一个循环中。根据快慢指针的特性,在一个圈中,快指针总是会追上慢指针,也就是说,两个指针总是会在一个位置上相遇,如果相遇位置是1,那么这个数一定是快乐数;如果相遇位置不为1,那么就不是快乐数。

补充知识:如何求一个数n每个位置上的数字的平方和

  • 把数n的每一位提取出来:循环迭代(int t = n % 10;  n/=10取掉原来的个位),直到n变为0。
  • 提取每一位的时候,用一个变量tmp来记录这一位的平方与之前提取位数的平方和:tmp = tmp + t * t;

代码演示:

class Solution
{
public:int bitSum(int n) // 返回 n 这个数每⼀位上的平⽅和{int sum = 0;while (n){int t = n % 10;sum += t * t;n /= 10;}return sum;}bool isHappy(int n){int slow = n, fast = bitSum(n);while (slow != fast){slow = bitSum(slow);fast = bitSum(bitSum(fast));}return slow == 1;}
};

 

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

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

相关文章

理解鸿蒙app 开发中的 context

是什么 Context是应用中对象的上下文&#xff0c;其提供了应用的一些基础信息&#xff0c;例如resourceManager&#xff08;资源管理&#xff09;、applicationInfo&#xff08;当前应用信息&#xff09;、dir&#xff08;应用文件路径&#xff09;、area&#xff08;文件分区…

贝尔不等式,路径积分与AB(Aharonov-Bohm)效应

贝尔不等式、路径积分与Aharonov-Bohm&#xff08;AB&#xff09;效应 这些概念分别源于量子力学不同的理论分支和思想实验&#xff0c;但它们都揭示了量子力学的奇异性质&#xff0c;包括非局域性、相位效应和波粒二象性。以下详细解析每一概念&#xff0c;并探讨其相互联系。…

python 爬虫 入门 六、Selenium

Selenium本来是一个自动测试工具&#xff0c;用于模拟用户对网站进行操作。在爬虫领域也有其用处。 一、下载安装Selenium及附属插件 pip install Selenium 安装完成后还需要安装一个浏览器驱动&#xff0c;来让python能启动浏览器。 如果是Edge或者其他基于Chromium的浏览器…

Linux(CentOS)yum update -y 事故

CentOS版本&#xff1a;CentOS 7 事情经过&#xff1a; 1、安装好CentOS 7&#xff0c;系统自带JDK8&#xff0c;版本为&#xff1a;1.8.0_181 2、安装好JDK17&#xff0c;版本为&#xff1a;17.0.13 3、为了安装MySQL执行了 yum update -y&#xff08;这个时候不知道该命令的…

uniapp uni-calendar日历实现考勤统计功能

根据日历组件代码结构 构成相应结构的状态统计数据 list 再遍历到每日的子组件中 <view class"uni-calendar__weeks-item" v-for"(weeks,weeksIndex) in item" :key"weeksIndex"><calendar-item class"uni-calendar-item--hook&q…

环境配置与搭建

安装pytorch 官网连链接&#xff1a;https://pytorch.org/ 特殊包名 cv2 pip install opencv-python sklearn pip install scikit-learnPIL pip install Pillow使用jupyter notebook pip install jupyter安装显卡驱动 Windows Linux 视频教程&#xff1a; 【ubuntu2…

【数据库实验一】数据库及数据库中表的建立实验

目录 实验1 学习RDBMS的使用和创建数据库 一、 实验目的 二、实验内容 三、实验环境 四、实验前准备 五、实验步骤 六、实验结果 七、评价分析及心得体会 实验2 定义表和数据库完整性 一、 实验目的 二、实验内容 三、实验环境 四、实验前准备 五、实验步骤 六…

SpringBoot健身房管理:技术与实践

2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统&#xff0c;它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等&#xff0c;非常…

CulturalBench :一个旨在评估大型语言模型在全球不同文化背景下知识掌握情况的基准测试数据集

2024-10-04&#xff0c;为了提升大型语言模型在不同文化背景下的实用性&#xff0c;华盛顿大学、艾伦人工智能研究所等机构联合创建了CulturalBench。这个数据集包含1,227个由人类编写和验证的问题&#xff0c;覆盖了包括被边缘化地区在内的45个全球区域。CulturalBench的推出&…

python登录功能实现

一.用python实现基本的登录功能 #-----------------1.基本登录功能------------------- nameinput("qq账号&#xff1a;") if name"jc":passwdinput("密码&#xff1a;")if passwd"123456":print("登录成功")else:print(&q…

如何使用Python管理环境变量

文章目录 📖 介绍 📖🏡 演示环境 🏡📒 环境变量 📒📝 环境变量简介📝 Python 中的环境变量操作📝 获取环境变量📝 设置环境变量🔖 临时设置🔖 永久设置📝 删除环境变量📝 临时删除📝 永久删除📝 小结⚓️ 相关链接 ⚓️📖 介绍 📖 环境变量…

设置允许多用户远程登录 Windows 云服务器

操作场景 本文档以 Windows Server 2016 操作系统云服务器为例&#xff0c;指导您配置多用户远程登录 Windows 云服务器。 注意&#xff1a; 微软提供的多用户远程登录功能试用期为120天&#xff0c;若未购买多用户登录授权&#xff08;RDS CALs&#xff09;&#xff0c;则试…

喜报!景联文科技成功通过DCMM数据管理能力成熟度二级认证

10月30日&#xff0c;中国电子信息行业联合会公示了新一批DCMM贯标企业&#xff0c;景联文科技成功通过DCMM数据管理能力成熟度二级认证&#xff08;乙方认证&#xff09;。 DCMM是《数据管理能力成熟度评估模型》的简称&#xff0c;是我国在数据管理领域首个正式发布的国家标准…

Android setContentView执行流程(1)-生成DecorView

setContentView的流程主要就是讲在Activity的onCreate方法中调用setContentView方法之后&#xff0c;我们自定义的xml文件加载的过程&#xff0c;学习它可以让我们对整个View树的理解更加透彻&#xff0c;并且通过源码的学习&#xff0c;我们可以从根本上理解一些问题&#xff…

《操作系统 - 清华大学》2 -1:操作系统的启动

文章目录 0. 内容摘要1. 计算机体系机构概述2.启动2.1 启动时计算机内存和磁盘布局2.2. 内存映射 3. 系统调用、异常、中断3.1 定义3.2 背景3.3 中断、异常和系统调用的不同点3.3.1 源头3.3.2 处理时间3.3.3 响应 0. 内容摘要 两部分的内容 第一部分是启动。知道操作系统怎么是…

在服务器里安装2个conda

1、安装新的conda 下载地址&#xff1a;Index of /anaconda/archive/ | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror 本文选择&#xff1a;Anaconda3-2023.03-1-Linux-x86_64.sh 安装&#xff1a;Ubuntu安装Anaconda详细步骤&#xff08;Ubuntu22.04.1&#xff…

【系统集成项目管理工程师】知识点汇总

十五矩阵图 ITTO&#xff08;Input - Tools & Techniques - Output&#xff09;一览图 整合管理、范围管理 进度管理、成本管理 成本管理&#xff08;续&#xff09;、质量管理、资源管理 沟通管理、风险管理 风险管理&#xff08;续&#xff09;、采购管理、干系人管理

Java | Leetcode Java题解之第552题学生出勤记录II

题目&#xff1a; 题解&#xff1a; class Solution {static final int MOD 1000000007;public int checkRecord(int n) {long[][] mat {{1, 1, 0, 1, 0, 0},{1, 0, 1, 1, 0, 0},{1, 0, 0, 1, 0, 0},{0, 0, 0, 1, 1, 0},{0, 0, 0, 1, 0, 1},{0, 0, 0, 1, 0, 0}};long[][] re…

极品模板内容付费管理系统(PHP内容知识付费系统)

极品模板内容付费管理系统是一款基于PHP和MySQL技术开发的源码产品&#xff0c;旨在为用户提供一个功能全面、易于管理和扩展的内容付费平台。该系统支持多种付费模式&#xff0c;具备强大的内容管理功能&#xff0c;适合各类内容创作者和企业家构建知识付费、会员服务、在线教…

设计者模式之策略模式

前言 在软件构建过程中&#xff0c;某些对象使用的算法可能多种多样&#xff0c;经常改变&#xff0c;如果将这些算法都写在对象中&#xff0c;将会使对象变得异常复杂&#xff1b;而且有时候支持不频繁使用的算法也是一个性能负担。 如何在运行时根据需要透明地更改对象的算…