制定网站建设规划书,南昌二手网站开发方案,上海企业信用信息公示系统,做团购网站哪家好些介绍#xff1a; 常见的双指针有两种形式#xff0c;一种是对撞指针#xff08;左右指针#xff09;#xff0c;一种是快慢指针#xff08;前后指针#xff09;。需要注意这里的双指针不是 int* 之类的类型指针#xff0c;而是使用数组下标模拟地址来进行遍历的方式。 …介绍 常见的双指针有两种形式一种是对撞指针左右指针一种是快慢指针前后指针。需要注意这里的双指针不是 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 ]的元素全部都是非零元素[ dest1, cur-1 ]的元素全为0。
初始化 cur 0(用来遍历数组)dest -1(指向非零元素的最后一个位置)。因为刚开始我们不知道最后一个非零元素在什么位置因此初始化为-1。cur 依次往后遍历元素遍历到的元素会分为两种情况
遇到的元素值为0此时 cur 直接 。因为我们的目标是让[ dest1, cur-1 ]内的元素全部为0因此当 cur 遇到 0 的时候直接 就可以让 0 在 cur-1 的位置上从而保持在[ dest1, cur-1 ]内。遇到的元素值不为0此时 dest并且交换 cur 位置和 dest 位置的元素之后让cur扫描下一个元素。 因为 dest 指向的位置是非零元素区间的最后一个位置如果扫描到一个新的非零元素那么它的位置应该在 dest1 的位置上因此 dest 先 dest 之后指向的元素就是 0 元素(因为非零元素区间末尾最后一个元素就是0)因此可以交换到cur所处的位置上实现[ 0, dest ]的元素全部都是非零元素[ dest1, cur-1 ]的元素都是0。
代码演示
class Solution {
public:void moveZeroes(vectorint nums) {int cur -1;int dest 0;for(size_t dest 0; destnums.size();dest){if(nums[dest] ! 0){cur;std::swap(nums[cur], nums[dest]);}}}
}; 2、复写零 给你一个长度固定的整数数组 arr 请你将该数组中出现的每个零都复写一遍并将其余的元素向右平移。注意请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改不要从函数返回任何东西。
提示
1 arr.length 10^40 arr[i] 9 解题思路原地复写-双指针 如果从前向后进行原地复写操作的话由于0的出现会复写两次导致没有复写的数会被覆盖掉。因此我们选择从后往前的复写策略。 而从后往前复写需要我们找到最后一个复写的元素因此我们的思路可分为两步 先找到最后一个复写的元素。 然后从后向前进行复写操作。
算法流程
初始化两个指针cur 0 dest 0找到最后一个复写的元素当 cur n 时循环判断cur位置的元素如果为0dest往后移动两位否则移动一位。判断dest是否已经到结束位置如果结束就break终止循环如果没有结束cur继续判断。判断dest是否越界如果越界到n位置执行n-1位置元素值修改为0cur向前移动一步dest位置向前移动两步。从cur位置开始往前遍历原数组因此还原出复写后的结果数组判断cur位置的值如果是0dest以及dest-1位置元素值修改为0dest-2如果是非0dest位置修改成非0值dest-1cur--复写下一个位置。
代码演示
class Solution
{
public:void duplicateZeros(vectorint 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;}
};
