双指针(C++)

文章目录

  • 1、移动零
  • 2、复写零
  • 3、快乐数
  • 4、盛最多水的容器
  • 5、有效三角形的个数
  • 6、和为s的两个数
  • 7、三数之和
  • 8、四数之和


需要理解的是,双指针并非只有指针,双指针的意思是两个位置。比如对于数组来说,两个下标也是双指针。当然,也可以说,双指针是一种思想。

关于详细的考量,会在题目中展现。常用指针名字:dest和src,left和right,prev和cur,slow和fast

1、移动零

链接

在这里插入图片描述

题目要求很清晰,要求0全部在最后,0前面全部是非0数,那么这时候双指针的作用区分就很明确。左指针的左边都是非0数,左指针的右边则是0。这是一个初步的整体划分,先定义 左右指针为a和b

接下来想想逐步的操作,两个下标位置,也就是两个int数,指向两个数组里的数,然后判断是否为0;一方为0,就要交换一下,让0来到a的右边,也就是让b的位置的数字是0,然后继续遍历。这样一想,随着逐渐的往后走,b指针的右边就是待处理的部分,而ab之间是0,a左边则是非0数;这样3个区间就划分好了。

a指针指向非0数,左边都是非0数,所以a指针指向最后一个非0数,b指针左边都是0,右边是待处理的,所以b指针指向最后一个0;如果走完整个空间,就没有待处理的部分了。

数组最初的位置可以不是0,我们可以让a指针初始化为-1。因为最一开始我们并不知道是否有非0数,所以不如让a为-1,b位置是0,b开始判断是否为0;如果num[b]是0,那么b就++,a不动,这样ab之间就有0了;如果是非0,那就得交换一下,但是需要a指针往前走一步再交换,不能这样访问num[-1],而且如果一直是非0数,a++后再去交换,就相当于是原地交换数值,不发生变化。

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

2、复写零

链接

在这里插入图片描述

这道题一个简单的思路是再开一个数组,一个指针指向原数组,另一个指向新数组,原数组只要出现0,新数组内就写两个0,不是就写一个,直到新数组全部填完。假设是数组[1, 0, 2, 3],a指针指向原数组,b指针指向新开的初始化好的数组。a为1,b就填1;a走到0,b填两个0,b来到第二个0,a来到2;a为2,b填2。

两个数组的情况转成一个的。需要注意的是,0后的数字不能直接覆盖掉,而只是写两遍0,然后接着下一个数字。所以我们得保证其它数字不会被覆盖掉。像这样不能覆盖的问题,有一个常用想法就是从后向前走。为了不被覆盖,先把要复写的数确定下来,这样b指针指向最后一个位置,a指针指向前面某个位置,无论怎样,a都每次往前走一步,而如果有0,b就走两步,否则走一步。

在找最后一个要复写的数的过程中,a指针指向0位置,而b指针指向-1。我们定义b指针是指向结果的,也就是原数组的某个数在结果中应当待的位置,a为非0,b就一步;a为0,b就走两步;当b走到末尾时,也就是结果数组中最后一个数的位置,而此时a应当指向填写这个位置的数。综合考虑,b在-1位置是合适的。可以代入例子来观察。在每一次b指针走动后都去判断是否到了最后一个位置,到了就退出循环,没到就让a++。

但是按照这个思路,还是有问题,这个问题就越界问题。b指针不会乖乖地到数组末尾停止,而是可能会越界。如果在后面,a位置的数都是非0数,那么b不会越界,因为它会乖乖地走到末尾,然后一判断,等于n - 1,那就退出;一旦越界,就说明a指向了一个0,b在n - 2的位置,然后走两步来到了n,所以b只会越界到n位置,因为如果在n - 1时就会退出,也不会走到n + 1位置。面对这个情况,就和归并排序处理边界情况一样,简单操作一下即可:将数组最后一个位置置为0,然后a往前走一步,b往前走两步,回到正确的位置,并继续往前判断并填写。

class Solution {
public:void duplicateZeros(vector<int>& arr) {int n = arr.size();int prev = 0, cur = -1;while(cur < n){if(arr[prev]) ++cur;else cur += 2;if(cur >= n - 1) break;++prev;}if(cur == n){arr[n - 1] = 0;cur -= 2;--prev;}while(cur >= 0){if(arr[prev]) arr[cur--] = arr[prev--];else{arr[cur--] = 0;arr[cur--] = 0;--prev;}}}
};

3、快乐数

链接

在这里插入图片描述

这道题是怎么和双指针有关的?

先看一下题。快乐数没有公式,所以我们只能从代码上找思路。一个暴力解法就是直接算,算到1为止。但如果它不是快乐数,要在什么时候停止计算?这就是一个问题,我们要找的就是一个暂停条件。

如果不是快乐数,就会一直循环。对此能想到的停止办法就是参考环形队列,环形链表:定义快慢指针,然后快指针每一步都比慢指针走得多,让快追慢,追上并且在整个过程也没有出现1,就说明这不是快乐数。为什么?fast是如何追上slow的?fast能追上slow说明,fast又走到了开头位置,也就是slow开始的位置,然后追上slow。也就是说,fast走完了一整个循环过程,而这之中都没有出现1,那肯定就不是快乐数。

这里的快慢指针就代表计算出来的数,比如slow计算一次而fast计算两次。由于停止的条件是slow等于fast,所以为了能够进入,fast和slow再初始化时就不能相等,可以让fast先计算一次,反正最后都是会追上slow。

class Solution {
public:int bitSum(int n) {int sum = 0, ret = 0;while (n) {ret = n % 10;sum += ret * ret;n /= 10;}return sum;}bool isHappy(int n) {if(n == 1) return true;int s = n, f = bitSum(n);while(s != f){s = bitSum(s);if(s == 1) return true;f = bitSum(bitSum(f));if(f == 1) return true;}return false;}
};

也可以不在while里写判断,出来判断return s == 1或者判断f。

4、盛最多水的容器

链接

在这里插入图片描述

这道题是一道练习,只放代码,不写思路。

class Solution {
public:int maxArea(vector<int>& height) {int n = height.size();int l = 0, r = n - 1;int res = 0;while(left < right){res = max(res, (r - l) * min(height[l], height[r]));if(height[l] > height[r]) --r;else ++l;}return res;}
};

5、有效三角形的个数

链接

在这里插入图片描述

由于三角形三条边需要满足a + b > c,所以O(N)的时间复杂度难以实现,即使固定住一个数,另外两个数也得挨个查看是否满足条件,不过这之中可以减少一些重复的遍历。

首先为了方便后序的遍历,先从小到大排序一下;然后从后往前走,固定最大的那个数,设定k为n - 1,剩下两个数就从前面这几个数中挑,所以k必然要至少为2,留出来两个数,设定前面两个数为i和j,如果nums[i] + nums[j] > nums[k],那就满足条件,当然也可以改成减法判断,这样就避免数值过大。

k固定后,i和j在运动。为了更有效地判断所有可能,让i = 0,j = k - 1,所以此时就能看出来,j肯定是k前面的最大数字,接着判断,如果不满足条件,j不需要更改,因为已经最大了,那么就增加i,直到满足条件就停下。此时nums[i] nums[j] nums[k]就是能组合成三角形的三条边,并且i继续增加也肯定满足条件,所以此时就可以直接加上 j - i,这就是从在j和k固定的情况下,符合条件的所有三元组个数。

这次结束后,j就往前走一步,继续按照上面的步骤去判断。k当然还是固定的,j变成第二个大的数,那么i?i其实也不用改变位置,因为之前更大的j和i前面的数字相加都不满足条件,那么现在更小的j也更不可能满足,所以只移动j就行了,然后从i现在的位置开始继续往后挨个判断。

这样的做法也是嵌套循环,只是减少了一些循环次数。对于k固定后,i和j的变化,以及三角形判断,还有更快的办法,这需要用到一些别的公式,可自行看力扣解析。

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());int n = nums.size(), count = 0;int i = 0, j = 0, k = 0;for(k = n - 1; k >= 2; --k){i = 0, j = k - 1;while(i < j){if(nums[i] + nums[j] > nums[k]){count += j - i;--j;}else ++i;}}return count;}
};

6、和为s的两个数

链接

在这里插入图片描述
在这里插入图片描述

这道题可以用双指针来完成,但更多人想到的是哈希吧?这道题只写双指针的思路,哈希方法只写代码。

双指针的思路脱胎于暴力枚举。枚举就是算所有的数字,看看有没有符合要求的,而双指针就是有所选择地计算。

数组本身是升序的。定义ab两个位置,分别指向最小数和最大数,如果将ab相加后依然小于目标值,那么最大值不需要变,因为它已经最大了,所以只需要改变让a++,a指向的值变大,再次判断;如果大于目标值,那就让b–。如果等于,就找到了,直接返回。这里仍然使用减法来判断。

class Solution {
public:vector<int> FindNumbersWithSum(vector<int> array, int sum) {if(array.empty()) return {};int l = 0, r = array.size() - 1;int res = 0;while(l < r){res = sum - array[l];if(res < array[r]) --r;else if(res > array[r]) ++l;else return {array[l], array[r]};}return {};}
};
class Solution {
public:vector<int> FindNumbersWithSum(vector<int> array, int sum) {if(array.empty()) return {};unordered_map<int, int> um;int n = array.size(), ret = 0;for(int i = 0; i < n; i++){ret = sum - array[i];if(um.find(ret) == um.end()){um[array[i]] = i;}else return {ret, array[i]};}return {};}
};

无论从时间还是空间上来看,双指针都明显优于哈希表。

7、三数之和

链接

在这里插入图片描述

两数之和为起点。

仔细看一下题,三个数不能相等,并且有相同的三元组只能有一个,比如-1 0 1和1 0 -1,只有有一个作为结果,另一个抛弃。

可以看出来,我们需要去重,在操作之前先对数组排序。用set去重是可行的,但这里不用多用别的容器,仅在这个数组上边判断边去重。

这道题与 和为s的两个数思路很像,我们先固定一个数,在剩下的区间内找符合条件的两个数即可,并且要找到所有的符合条件的组合;三个数都需要去重。不过如果我们固定的数是一个正数,那么它肯定不可能有对应的组合,因为后面的数都是正数,不可能相加为0。

另外一个重要的问题是越界,在代码中体现:

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int n = nums.size();int i = 0, j = 0, k = 0;int sum = 0;sort(nums.begin(), nums.end());vector<vector<int>> res;while(i < n){if(nums[i] > 0) break;//小优化j = i + 1, k = n - 1;while(j < k){sum = nums[i] + nums[j] + nums[k];if(sum > 0) --k;//大于就让最大的数k减小else if(sum < 0) ++j;//小于就让较小的j增加, 因为i固定else{res.push_back({nums[i], nums[j++], nums[k--]});//去重 while(j < k && nums[k] == nums[k + 1]) --k;while(j < k && nums[j] == nums[j - 1]) ++j;}}//i去重, 如果是for循环就把i++给去掉, 要不会越界++i;while(i < n && nums[i] == nums[i - 1]) i++;//i < n, 防止后面都是0, i直接出去了}return res;}
};

去重操作可以根据自己的思路去改变写代码的位置。

8、四数之和

链接

在这里插入图片描述
经历了和为s的两个数以及三数之和,四数之和也有所思路。三数之和以及四数之和都有一个基于暴力而升级的解法,就是排序 + set去重 + 暴力枚举。

四数之和也是利用双指针,或者说多指针。先固定一个数a,然后再固定一个数b,这样就剩下两个数了,然后运用找两数的方法去做。

当然,这个方法也有点暴力。它要处理的问题同样是去重,越界。

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(), nums.end());vector<vector<int>> res;long long ret = 0;int n = nums.size(), sum = 0;int i = 0, j = 0, l = 0, r = 0;while(i < n){j = i + 1;while(j < n){l = j + 1, r = n - 1;ret = (long long)target - nums[j] - nums[i];while(l < r){sum = nums[l] + nums[r];if(sum > ret) --r;else if(sum < ret) ++l;else{res.push_back({nums[i], nums[j], nums[l++], nums[r--]});//去重while(l < r && nums[l] == nums[l - 1]) ++l;while(l < r && nums[r] == nums[r + 1]) --r;}}++j;while(j < n && nums[j] == nums[j - 1]) ++j;}++i;while(i < n && nums[i] == nums[i - 1]) ++i;}return res;}
}

long long是为了解决力扣例子的中的数字超大问题。

结束。

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

如何维持CISSP证书:附免费获取CPE学分的16个官方渠道

CISSP 证书只有三年有效期&#xff08;如2023.11-2026.10&#xff09;&#xff0c;需要每年维护才能续证。持证者需要持续获取 CPE 学分来维持证书&#xff0c;否则证书到期后将失效。本文主要介绍维护CISSP证书的2个必备条件及16个CPE学分官方获取渠道。 1. 证书维持的2个必备…

iOS 实现视图遮罩效果

有时候&#xff0c;我们会遇到这种需求&#xff0c;只讲视图的某个部分展示出来 这时候&#xff0c;我们可以通过设置该视图layer.mask layerb来实现&#xff0c;需要注意的是&#xff0c;这里的layerb必须要设置backgroundColor&#xff0c;渐变layer有colors,否则达不到效果…

欧拉计划第804题:二次多项式计数

题目描述: 第一步,先根据题意直接求解 先利用一元二次方程求根的公式进行推导 x 2 + y x + 41 y 2 − n = 0 x^2 + yx + 41y^2 - n = 0

GPT3 终极指南(二)

原文&#xff1a;zh.annas-archive.org/md5/6de8906c86a2711a5a84c839bec7e073 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 第五章&#xff1a;GPT-3 作为企业创新的下一步 当一个新的创新或技术转变发生时&#xff0c;大公司通常是最后一个采纳的。它们的等级结构…

如何定时打开网站

首先&#xff0c;需要用到的这个工具&#xff1a; 度娘网盘 提取码&#xff1a;qwu2 蓝奏云 提取码&#xff1a;2r1z 1、打开工具按下Ctrl3&#xff0c;切换到定时器模块&#xff0c;左侧右键&#xff0c;选择新建 2、标题叫百度&#xff0c;等下就让它打开百度&#xff0c…

Java | Leetcode Java题解之第64题最小路径和

题目&#xff1a; 题解&#xff1a; class Solution {public int minPathSum(int[][] grid) {if (grid null || grid.length 0 || grid[0].length 0) {return 0;}int rows grid.length, columns grid[0].length;int[][] dp new int[rows][columns];dp[0][0] grid[0][0]…

持续更新|UNIAPP适配APP遇到的问题以及解决方案

在使用UNIAPP开发APP的时候遇到的一些奇奇怪怪问题记录 组件样式丢失 问题&#xff1a;组件引入界面中&#xff0c;在小程序和H5环境下样式正常&#xff0c;而在APP中却出现高度异常问题 解决&#xff1a;增加view标签将组件包裹起来即可正常显示 解决前&#xff1a; 解决后…

Mysql的关联查询以及语句

一、mysql的连接查询 1、等值连接 这里是三张表的等值连接 select rp.role_id,rp.permission_id from role_permission rp, role r, permission p where rp.role_idr.id and rp.permission_idp.id 2、内连接&#xff1a; 角色&#xff1a;系统管理员 是否拥有权限&#xf…

并发编程之线程池的设计和原理

一、线程池 提前创建一系列的线程&#xff0c;保存在这个线程池中&#xff0c;有任务要执行的时候&#xff0c;从线程池中取出线程来执行。没有任务的时候&#xff0c;线程池放回去。 二、为什么要使用线程池 线程使用上的问题: 线程的频繁创建 和 销毁 线程的数量过多&…

51. 【Android教程】JSON 数据解析

在上一节我们学习了 xml 数据格式&#xff0c;如果你觉得 xml 的数据比较冗余&#xff0c;标签、属性等等定义过于复杂&#xff0c;那么这一节我们将继续学习另一种更精简、更高效的数据格式—— Json。它广泛的运用于数据持久化以及网络传输中&#xff0c;这一节我们一起学习 …

ios CI/CD 持续集成 组件化专题五-(自动发布私有库-组件化搭建)

一&#xff1a;手动发布私有库总结 手动发布pod私有库&#xff0c;需要进行如下几步操作&#xff1a; 1、修改完代码之后&#xff0c;需要提交代码push到git仓库。 2、给代码打tag。 3、修改podspec文件的version值&#xff0c;使其和设置的tag一直。 4、命令行执行pod repo…

【C 数据结构】深度优先搜索、广度优先搜索

文章目录 【 1. DFS 深度优先搜索 】1.1 基本原理1.2 C 实现 【 2. BFS 广度优先搜索 】2.1 基本原理2.2 C 实现 【 3. 深度优先生成树、广度优先生成树 】【 4. 深度优先生成森林、广度优先生成森林 】4.1 深度优先生成森林4.2 广度优先生成森林 对存储的图中的顶点进行遍历搜…

Linux专栏08:Linux基本指令之压缩解压缩指令

博客主页&#xff1a;Duck Bro 博客主页系列专栏&#xff1a;Linux专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ Linux基本指令之压缩解压缩指令 编号&#xff1a;08 文章目录 Linu…

【python】python标准化考试系统[单项选择题 简易版](源码)【独一无二】

&#x1f449;博__主&#x1f448;&#xff1a;米码收割机 &#x1f449;技__能&#x1f448;&#xff1a;C/Python语言 &#x1f449;公众号&#x1f448;&#xff1a;测试开发自动化【获取源码商业合作】 &#x1f449;荣__誉&#x1f448;&#xff1a;阿里云博客专家博主、5…

【数据结构】链表专题3

前言 本篇博客我们继续来讨论链表专题&#xff0c;今天的链表算法题是经典中的经典 &#x1f493; 个人主页&#xff1a;小张同学zkf ⏩ 文章专栏&#xff1a;数据结构 若有问题 评论区见&#x1f4dd; &#x1f389;欢迎大家点赞&#x1f44d;收藏⭐文章 目录 1.判断链表是否…

springboot 自动配置源码解读

什么是自动装配 当我们程序依赖第三方功能组件时&#xff0c;不需要手动将这些组件类加载到IOC容器中。例如 当程序需要用到redis时&#xff0c;在pom.xml文件中引入依赖&#xff0c;然后使用依赖注入的方式直接从IOC容器中拿到相应RedisTemplate实例。 SpringBootApplication …

jvm面试题30问

什么是JVM的跨平台&#xff1f; 什么是JVM的语言无关性&#xff1f; 什么是JVM的解释执行 什么是JIT? JIT&#xff1a;在Java编程语言和环境中&#xff0c;即时编译器&#xff08;JIT compiler&#xff0c;just-in-time compiler&#xff09;是一个把Java的字节码&#xff08;…

为什么3D模型材质是透明的?---模大狮模型网

在进行3D建模和渲染过程中&#xff0c;正确的材质设置是保证模型外观逼真和渲染效果良好的关键之一。然而&#xff0c;有时您可能会遇到3D模型材质变成透明的情况&#xff0c;这可能会导致意想不到的效果和渲染结果。本文将探讨一些可能导致3D模型材质变成透明的原因&#xff0…

MySQL 运维篇

回顾基本语句&#xff1a; 数据定义语言(DDL) 这类语言用于定义和修改数据库的结构&#xff0c;包括创建、删除和修改数据库、 表、视图和索引等对象。 主要的语句关键字包括 CREATE 、 DROP 、 ALTER 、 RENAME 、 TRUNCATE 等。 create database 数据库 &#xff1b; cr…

嵌入式Linux 系统组成

三种系统组成图 嵌入式Linux系统和PC完整的操作系统的对比如下&#xff1a; // 可以看到我们嵌入式arm 上的 u-boot 同时替代了 BIOS 和 grub2&#xff08;bootmgr&#xff09;的功能 &#xff0c;下面我们来进行一些详细的介绍 1. BIOS和UEFI的作用&#xff1a; a. 进行硬件自…