qq免费搭建网站,广告网站有哪些,网站建设培训公司,厚街做网站价格顾得泉#xff1a;个人主页
个人专栏#xff1a;《Linux操作系统》 《C/C》 《LeedCode刷题》
键盘敲烂#xff0c;年薪百万#xff01; 双指针简介 常见的双指针有两种形式#xff0c;一种是对撞指针#xff0c;一种是左右指针。
对撞指针:一般用于顺序结构中…
顾得泉个人主页
个人专栏《Linux操作系统》 《C/C》 《LeedCode刷题》
键盘敲烂年薪百万 双指针简介 常见的双指针有两种形式一种是对撞指针一种是左右指针。
对撞指针:一般用于顺序结构中也称左右指针。 对撞指针从两端向中间移动。一个指针从最左端开始另一个从最右端开始。然后逐渐往中间逼近。 对撞指针的终止条件一般是两个指针相遇或者错开也可能在循环内部找到拿果直接跳出循 环)也就是: left right(两个指针指向同一个位置) left right(两个指针错开)
快慢指针:又称为龟兔赛跑算法其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。 这种方法对于处理环形链表或数组非常有用。 其实不单单是环形链表或者是数组如果我们要研究的问题出现循环往复的情况时均可考虑使用快慢指针的思想。 快慢指针的实现方式有很多种最常用的—种就是:在一次循环中每次让慢的指针向后移动一位而快的指针往后移动两位实现一快一慢。 一、移动零
题目链接移动零
题目描述 给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。 请注意 必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums [0]
输出: [0]
提示:
1 nums.length 104-231 nums[i] 231 - 1
解法
算法思路: 在本题中我们可以用一个cur 指针来扫描整个数组另一个dest指针用来记录非零数序列的最后一个位置。根据cur在扫描的过程中遇到的不同情况分类处理实现数组的划分。在cur遍历期间使[0 dest]的元素全部都是非零元素[dest 1 cur - 1]的元素全是零。
算法流程: a.初始化 cur 0(用来遍历数组)dest -1(指向非零元素序列的最后一个位置。因为刚开始我们不知道最后一个非零元素在什么位置因此初始化为-1) b.cur依次往后遍历每个元素遍历到的元素会有下面两种情况 i.遇到的元素是0 cur直接。因为我们的目标是让[dest 1 cur - 1]内的元素全都是零因此当cur遇到o的时候直接就可以让 o_在cur - 1的位置上从而在[dest 1, cur - 1]内; ii.遇到的元素不是0dest并且交换cur位置和dest位置的元素之后让cur扫描下一个元素。 因为dest指向的位置是非零元素区间的最后一个位置如果扫描到一个新的非零元素那么它的位置应该在dest 1的位置上因此dest先自增1; dest之后指向的元素就是0元素因为非零元素区间末尾的后一个元素就是0)因此可以交换到cur所处的位置上实现[0dest]的元素全部都是非零元素[dest 1 cur - 1]的元素全是零
代码实现
class Solution {
public:void moveZeroes(vectorint nums) {int dest -1, cur 0;while(cur nums.size()){if(nums[cur])swap(nums[dest],nums[cur]);cur;}}
}; 二、复写零
题目链接复写零
题目描述 给你一个长度固定的整数数组 arr 请你将该数组中出现的每个零都复写一遍并将其余的元素向右平移。 注意请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改不要从函数返回任何东西。
示例 1
输入arr [1,0,2,3,0,4,5,0]
输出[1,0,0,2,3,0,0,4]
解释调用函数后输入的数组将被修改为[1,0,0,2,3,0,0,4]
示例 2
输入arr [1,2,3]
输出[1,2,3]
解释调用函数后输入的数组将被修改为[1,2,3]提示
1 arr.length 1040 arr[i] 9
解法
算法思路: 如果「从前向后」进行原地复写操作的话由于/的出现会复写两次导致没有复写的数「被覆盖掉」。因此我们选择「从后往前」的复写策略。 但是「从后向前」复写的时候我们需要找到「最后一个复写的数」因此我们的大体流程分两步: i.先找到最后一个复写的数; ii.然后从后向前进行复写操作
算法流程:
a.初始化两个指针cur0, dest 0;
b.找到最后一个复写的数︰ i. 当cur n的时候一直执行下面循环: 判断cur位置的元素: 如果是0的话dest往后移动两位;。否则dest往后移动一位 判断dest时候已经到结束位置如果结束就终止循环; 如果没有结束cur继续判断
c.判断dest是否越界到n的位置: i.如果越界执行下面三步: 1. n - 1位置的值修改成0; 2. cur向移动一步; 3. dest向前移动两步
d. 从cur位置开始往前遍历原数组依次还原出复写后的结果数组: i.判断cur位置的值: 1.如果是0 :dest以及dest - 1位置修改成0,dest - 2 2如果非零:dest位置修改成0,dest - 1 ; ii. cur--复写下一个位置
代码实现
class Solution {
public:void duplicateZeros(vectorint arr) {int cur 0, dest -1, n arr.size();for(cur; cur n; cur){if(arr[cur]) dest;elsedest 2;if(dest n - 1)break;}if(dest n){arr[n-1] 0;cur--;dest - 2;}while(cur 0){if(arr[cur])arr[dest--] arr[cur--];else{arr[dest--] 0;arr[dest--] 0;cur--;}}}
}; 三、快乐数
题目链接
题目描述 编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为
对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true 不是则返回 false
示例 1
输入n 19
输出true
解释
12 92 82
82 22 68
62 82 100
12 02 02 1示例 2
输入n 2
输出false提示
1 n 231 - 1
解法
算法思路: 根据上述的题目分析我们可以知道;当重复执行的时候数据会陷入到一个「循环」之中。而「快慢指针」有一个特性。就是在一个圆圈中快指针总是会追上慢指针的也就是说他们总会相遇在一个位置上。如果相遇位置的值是1那么这个数一定是快乐数;如果相遇位置不是1的话那么就不是快乐数。
补充知识: 如何求一个数n每个位置上的数字的平方和
a.把数n每一位的数提取出来: 循环迭代下面步骤: i.int t n % 10提取个位; ii. n / 10干掉个位; 直到n的值变为0 ;
b.提取每一位的时候用一个变量tmp记录这一位的平方与之前提取位数的平方和 tmp tmp t * t
代码实现
class Solution
{
public:int Sum(int 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 Sum(n);while(slow ! fast){slow Sum(slow);fast Sum(Sum(fast));}return slow 1;}
}; 结语今日的刷题分享到这里就结束了希望本篇文章的分享会对大家的学习带来些许帮助如果大家有什么问题欢迎大家在评论区留言~~~
