【算法一周目】双指针(1)

目录

1.双指针介绍

2.移动零

解题思路

 C++代码实现

3.复写零

解题思路

C++代码实现

4.快乐数

解题思路

C++代码实现

5.盛水最多的容器

解题思路

C++代码实现


1.双指针介绍

常见的双指针有两种形式,一种是对撞指针,一种是快慢指针。

对撞指针:一般用于顺序结构中,也称左右指针。

  • 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。
  • 对撞指针的终止条件⼀般是两个指针相遇或者错开(也可能在循环内部找到结果直接跳出循环),也就是:

left == right (两个指针指向同⼀个位置);
left > right (两个指针错开);

快慢指针:又称为龟兔赛跑算法,其基本思想就是使用两个移动速度不同的指针数组或链表等序列结构上移动。

这种方法对于处理环形链表或数组非常有用。其实不单单是环形链表或者是数组,如果我们要研究的问题出现循环往复的情况时,均可考虑使用快慢指针的思想。

快慢指针的实现方式有很多种,最常用的一种是:一次循环中,每次让慢指针向后移动一位,而快的指针向后移动两位,实现一快一慢。

2.移动零

题目链接:283. 移动零
题目描述:给定一个数组nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

解题思路

这题我们使用双指针解决,需要一个cur指针和一个dest指针,将数组划分成3个区间,[0, dest]的元素全部是非0元素[dest + 1, cur - 1]的元素全是0[cur -1, n - 1]的元素是待处理的

具体流程如下:

1.初始化cur = 0(用于遍历数组),dest = -1(指向非0元素的最后一个位置,由于刚开始我们不知道最后一个非0元素在什么位置,因此初始化为-1

2.cur依次往后遍历每个元素。

  • 当cur遇到0时,cur++
  • 当cur遇到非0时,dest++,交换dest的位置与cur位置的值

 C++代码实现

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

时间复杂度:O(n)

空间复杂度:O(1)

3.复写零

题目链接:1089. 复写零
题目描述:给定一个固定长度的整数数组arr,在遇到每个零时,将其右移并插入一个零,同时保持数组长度不变。

解题思路

因为数组的0需要复写2次有可能会把后面的非0元素覆盖掉,所以从前往后复写是不可取的,所以我们采取从后往前复写。

具体过程如下:

1.找到最后一个需要复写的元素,这一步需要双指针来解决。

  • 初始化两个指针cur = 0, dest = -1
  • cur的位置为0时,dest += 2非0时dest++
  • 判断dest是否大于等于n - 1(数组最后一个位置),若满足则退出循环
  • cur++,继续循环,直到找到最后一个复写的元素。

2.处理越界情况,当dest == n时,说明cur在数组n - 2位置且元素是0,这时候就要特殊处理,dest--,将arr[dest]置0,dest--,cur--。

3.从后往前复写将arr[cur]复写到arr[dest]若arr[cur]为非0,复写一次,若arr[cur]为0,则复写两次,记得分情况更新cur和dest,直到复写结束。

C++代码实现

class Solution {
public:void duplicateZeros(vector<int>& arr) {int cur = 0, dest = -1, n = arr.size();//1.寻找最后一个需要复写的数while(cur < n){if(arr[cur])dest++;elsedest += 2;if(dest >= n - 1) break;cur++;}                                                                                                                                                                  //2.处理越界情况if(dest == n){dest--;arr[dest--] = 0;cur--;}//3.从后往前复写元素while(cur >= 0){if(arr[cur]){arr[dest--] = arr[cur--];}else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}}
};

时间复杂度:O(n)

空间复杂度:O(1)

4.快乐数

题目链接:202. 快乐数

题目描述:编写一个算法来判断一个数 n 是不是快乐数。

对于n = 2,2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16,进入到循环了。

解题思路

为了方便分析,将“对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和”这一操作记为f操作

由题目可知,当我们对一个数不断进行f操作时,最后一定会进入死循环死循环也分为两种第一种就是一直在1循环,是快乐数第二种就是在历史数据中死循环,但始终变不到1。

由于两种情况只会出现一种,所以我们只需判断是否一直在1循环,就可知此数是不是快乐数。

证明

  • 对于INT_MAX(2^31-1=2147483647),取一个更大的数9999999999,进行f操作后得到最大值810,可以得到f操作得到的值范围是[1, 810]
  • 根据“鸽巢原理”,对一个数进行f操作811次后,必定进入循环。

对此,我们可以得知,无论是什么数,对其进行多次f操作后,必定会形成一个环,所以我们可以使用快慢指针来解决。

具体过程:

1.编写f操作的函数bitsum,将该数替换为它每个位置上的数字的平方和。

2 .初始化快慢指针,slow = n,fast = bitsum(n)

3.当slow != fast时slow向前走一步,fast先前走两步,直到循环结束。

4.判断slow是否等于1,若等于则该数是快乐数。

C++代码实现

class Solution {
public:int bitsum(int n){int ret = 0;while(n){ret += pow(n % 10, 2);n /= 10;}return ret;}bool isHappy(int n) {int slow = n, fast = bitsum(n);while(slow != fast){slow = bitsum(slow);fast = bitsum(bitsum(fast));}return slow == 1;}
};

时间复杂度:O(log n) 在快慢指针法中,求平方和的时间复杂度为对数级别。

空间复杂度:O(1)

5.盛水最多的容器

题目链接:11. 盛最多水的容器

题目描述:给定一个长度为n的整数数组height,有n条垂线,第i条线的两个端点是(i, 0) 和(i, height[i])。
找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。

说明:你不能倾斜容器。

示例 1

  • 输入:[1,8,6,2,5,4,8,3,7]
  • 输出:49
  • 解释:数组中的垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在这个情况下,能够容纳水(表示为蓝色部分)的最大值是49。

解题思路

对于该题,我们很容易就想到使用暴力解法,用两个for循环暴力枚举能构成的所有容器找出其中容积最大的值。

容器计算公式:设两个指针i,j,分别指向容器的最左端和最右端,此时容器的宽度为j - 1,由于容器的高度由较短的高度决定,可得容器公式。

v = (j - i) * min(height[i], height[j])

暴力解法的代码

class Solution {
public:int maxArea(vector<int>& height) {int n = height.size();int ret = 0;// 两层 for 循环枚举出所有可能出现的情况for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {// 计算容积,找出最大的那一个ret = max(ret, min(height[i], height[j]) * (j - i));}}return ret;}
};

但是暴力解法需要遍历所有可能的组合,故时间复杂度是O(n ^ 2),如果提交到leetcode上是会超时,所以我们要寻求最优的解法。

利用双指针来解决,具体过程如下:

1.使用两个指针left和right分别指向容器的左右两个端点,初始化left = 0, right = n - 1。

2.通过左边界height[leftt]右边界height[right]计算出容器的体积v

3.判断左右边界的大小情况,舍去小的边界,若左边界 < 右边界left++反之则right--

4.通过重复上述过程,可以舍去大量不必要的枚举过程直到left与right相遇,整个过程中更新出容器体积的最大值。

证明以上的第三点,为什么不用小的边界去枚举剩下的数,而是直接将其舍去

C++代码实现

class Solution {
public:int maxArea(vector<int>& height) {int left = 0, right = height.size() - 1;int ret = 0;while(left < right){int v = min(height[left], height[right]) * (right - left);ret = max(v, ret);height[left] < height[right] ? left++ : right--;}return ret;}
};

时间复杂度:O(n)

空间复杂度:O(1)


拜拜,下期再见😏

摸鱼ing😴✨🎞

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

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

相关文章

ARXML汽车可扩展标记性语言规范讲解

ARXML: Automotive Extensible Markup Language &#xff08;汽车可扩展标记语言&#xff09; xmlns: Xml name space &#xff08;xml 命名空间&#xff09; xsd: Xml Schema Definition (xml 架构定义) 1、XML与HTML的区别&#xff0c;可扩展。 可扩展&#xff0c;主要是…

自监督学习:机器学习的未来新方向

引言 自监督学习&#xff08;Self-Supervised Learning, SSL&#xff09;是近年来机器学习领域的一个重要发展方向&#xff0c;迅速成为许多研究和应用的热点。与传统的监督学习不同&#xff0c;自监督学习利用未标注数据&#xff0c;通过设计自我生成标签的任务&#xff0c;帮…

FFMPEG录屏(22)--- Linux 下基于X11枚举所有显示屏,并获取大小和截图等信息

众人拾柴火焰高&#xff0c;github给个star行不行&#xff1f; open-traa/traa traa is a versatile project aimed at recording anything, anywhere. The primary focus is to provide robust solutions for various recording scenarios, making it a highly adaptable tool…

多媒体信息检索

文章目录 一、绪论二、文本检索 (Text Retrieval)(一) 索引1.倒排索引2.TF-IDF (二) 信息检索模型 (IR模型&#xff0c;Information Retrieval)1.布尔模型 (Boolean模型)(1)扩展的布尔模型 (两个词)(2)P-Norm模型 (多个词) 2.向量空间模型 (Vector Space Model&#xff0c;VSM)…

MySql-8.0.40安装详细教程

文章目录 原创下载安装包安装配置初始化MySQL数据库安装mysql服务并启动启动MySQL服务连接MySQL配置环境变量 原创 MySql-8.0.26安装详细教程&#xff08;保姆级&#xff09; 下载安装包 MySQL Community Downloads 直接到选择MySQL Community Server版本页面 MySQL Commun…

openai Realtime API (实时语音)

https://openai.com/index/introducing-the-realtime-api/ 官方demo https://github.com/openai/openai-realtime-console 官方demo使用到的插件 https://github.com/openai/openai-realtime-api-beta?tabreadme-ov-file 装包配置 修改yarn.lock 这个包是从github下载的 &q…

杨辉三角-一维数组与二维数组解法

这种问题是很有规律的 这里 总结一下 这类问题输出&#xff1a;对称 且数据相同的很多 就比如首位都是1 如果计算中间值遇到困难 可以试着把边界值单独输出 一维数组 // // Created by 徐昌真 on 2024/11/11. // #include <stdio.h> //一维数组 int main() {int n; /…

无人机反制技术与方法:主动防御,被动防御技术原理详解

无人机反制技术与方法主要分为主动防御和被动防御两大类&#xff0c;以下是关于这两类防御技术的原理详解&#xff1a; 主动防御技术原理 主动防御系统旨在通过直接干扰或摧毁来攻击入侵的无人机。这类系统通常包括电子干扰、激光武器、定向能武器以及硬杀伤手段&#xff08;如…

计算机毕业设计Python+图神经网络考研院校推荐系统 考研分数线预测 考研推荐系统 考研爬虫 考研大数据 Hadoop 大数据毕设 机器学习 深度学习

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…

小白初入Android_studio所遇到的坑以及怎么解决

1. 安装Android_studio 参考&#xff1a;Android Studio 安装配置教程 - Windows(详细版)-CSDN博客 Android Studio超级详细讲解下载、安装配置教程&#xff08;建议收藏&#xff09;_androidstudio-CSDN博客 想下旧版本的android_studio的地址&#xff08;仅供参考&#xf…

020_Servlet_Mysql学生选课系统(新版)_lwplus87

摘 要 随着在校大学生人数的不断增加&#xff0c;教务系统的数据量也不断的上涨。针对学生选课这一环节&#xff0c;本系统从学生网上自主选课以及课程发布两个大方面进行了设计&#xff0c;基本实现了学生的在线信息查询、选课功能以及教师对课程信息发布的管理等功能&…

Vue Cli 脚手架目录文件介绍

小试牛刀 //vetur高亮; vuetab 快速生成 <template><div class"box">我是个盒子<button click"fn">按钮</button></div> </template><script> export default {methods:{fn(){alert("Hello Vue")}} …

[安洵杯 2019]easy_web 详细题解

知识点: 编码转换 命令执行 linux空格_关键字绕过 打开页面 发现url 是 /index.php?imgTXpVek5UTTFNbVUzTURabE5qYz0&cmd 有img参数和cmd参数 cmd参数是没赋值的,随便赋值为123456 页面没有反应 鼠标移动到图片下面时发现有东西,当然直接查看页面源代码也可以发现 尝…

完整培训教程:骨折图像分割

骨折图像分割系统源码&#xff06;数据集分享 [yolov8-seg-efficientViT&#xff06;yolov8-seg-C2f-CloAtt等50全套改进创新点发刊_一键训练教程_Web前端展示] 1.研究背景与意义 项目参考ILSVRC ImageNet Large Scale Visual Recognition Challenge 项目来源AAAI Global A…

文本语义分块、RAG 系统的分块难题:小型语言模型如何找到最佳断点

文本语义分块、RAG 系统的分块难题&#xff1a;小型语言模型如何找到最佳断点&#xff1f; 转自jina最新的关于文本语义分块的分享和模型 之前我们聊过RAG 里文档分块 (Chunking) 的挑战&#xff0c;也介绍了 迟分 (Late Chunking) 的概念&#xff0c;它可以在向量化的时候减…

物联网技术及其在智慧城市中的应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 物联网技术及其在智慧城市中的应用 物联网技术及其在智慧城市中的应用 物联网技术及其在智慧城市中的应用 引言 物联网概述 定义…

新的服务器Centos7.6 安卓基础的环境配置(新服务器可直接粘贴使用配置)

常见的基础服务器配置之Centos命令 正常来说都是安装一个docker基本上很多问题都可以解决了&#xff0c;我基本上都是通过docker去管理一些容器如&#xff1a;mysql、redis、mongoDB等之类的镜像&#xff0c;还有一些中间件如kafka。下面就安装一个 docker 和 nginx 的相关配置…

金属箔电阻

6.金属箔电阻如何实现“高精度” 电阻的阻值会受到各种“应力”影响而发生改变&#xff0c;离开稳定性的高精度是没有意义的。 例如&#xff0c;电阻出厂时的精度时0.01%&#xff0c;为了实现精度付出了高昂的费用&#xff0c;但在几个月的存储或几百个小时的负载后阻值的变化…

在Django中安装、配置、使用CKEditor5,并将CKEditor5录入的文章展现出来,实现一个简单博客网站的功能

在Django中可以使用CKEditor4和CKEditor5两个版本&#xff0c;分别对应软件包django-ckeditor和django-ckeditor-5。原来使用的是CKEditor4&#xff0c;python manager.py makemigrations时总是提示CKEditor4有安全风险&#xff0c;建议升级到CKEditor5。故卸载了CKEditor4&…

C语言 | Leetcode C语言题解之第559题N叉树的最大深度

题目&#xff1a; 题解&#xff1a; /*** Definition for a Node.* struct Node {* int val;* int numChildren;* struct Node** children;* };*/int maxDepth(struct Node* root) {if (!root) {return 0;}int depth 0;// 创建空队列const int qCap 10e4 1;str…