双指针习题篇(上)
双指针习题篇(上)
文章目录
- 双指针习题篇(上)
- 1.移动零
- 题目描述：
- 算法原理：
- 算法流程：
- 代码实现：
- 2.复写零
- 题目描述：
- 算法原理：
- 算法流程：
- 代码实现：
- 3.快乐数
- 题目描述：
- 算法原理：
- 算法流程：
- 代码实现：
- 4.盛最水多的容器
- 题目描述：
- 算法原理：
- 解法一：暴力枚举（超时）O(N^2^)
- 算法思路：
- 算法代码：
- 解法二：利用单调性，使用双指针来解决问题 O(N)
- 算法思路：
- 代码实现：
1.移动零
题目描述：
给定⼀个数组
nums，编写⼀个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。
⽰例 1:
输⼊:
nums= [0,1,0,3,12] 输出: [1,3,12,0,0]
⽰例 2:
输⼊:
nums= [0] 输出: [0]
算法原理：
数组划分，数组分块（将一个数组分为非0和0两部分）
首先我们可以想到用双指针算法（利用数组下标来充当指针）
两个指针的作用：
cur:从左往右扫描数组，遍历数组（cur前是处理过的元素，cur后是待处理的元素）
dest:已处理的区间内，非零元素的最后一个位置（在处理过的元素中，继续划分，前是非零元素，后是为零元素）
整个数组被划分为三部分：
[0,dest]——非零元素
[dest+1,cur-1]——零元素
[cur,n-1]——待处理元素
算法流程：
1.初始化 cur = 0 （从头到尾遍历数组）， dest = -1 （因为刚开始我们不知道最后⼀个非零元素是否存在，因此初始化为 -1，来记录非零数序列的最后⼀个位置 ）
2.cur从前往后遍历的过程中：
（1）.遇到0元素:
cur ++ ；（2）.遇到非零元素:
swap(dest+1,cur); dest++,cur++;
-
因为
dest指向的位置是非零元素区间的最后⼀个位置，如果扫描到⼀个新的非零元素，那么它的位置应该在dest + 1的位置上，因此dest先自增 1 ； -
dest++之后，指向的元素就是零元素（因为非零元素区间末尾的后⼀个元素就是0 ），因此可以交换到cur所处的位置上，实现[0, dest]的元素全部都是非零元素,[dest + 1, cur - 1]的元素全是零。
双指针的思想是快排中最核心的一步：数据划分
代码实现：
class Solution
{
public:
void moveZeroes(vector<int>& nums)
{
for(int cur = 0, dest = -1; cur < nums.size(); cur++)
if(nums[cur]) // 处理⾮零元素
swap(nums[++dest], nums[cur]);
}
};
2.复写零
题目描述：
给你⼀个⻓度固定的整数数组 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]
算法原理：
解法（原地复写 - 双指针）：先根据”异地“操作，然后优化成双指针下的”就地“操作。
算法流程：
如果「从前向后」进行原地复写操作的话，由于 0 的出现会复写两次，导致没有复写的数「被覆盖掉」。因此我们选择「从后往前」的复写策略。
但是「从后向前」复写的时候，我们需要找到「最后⼀个复写的数」，因此我们的大体流程分两步：
1.先找到最后⼀个“复写”的数；
双指针算法
(1).先判断
cur位置的值；(2).决定
dest向后移动一步或者两步；(3).判断一下
dest是否已经结束；(4).
cur++.
- 处理边界情况(当cur=0时，dest“复写零”可能发生越界)
(1).让
n-1位置的元素等于零；(2).
cur- -;(3).
dest-=2;
- “从后向前” 完成复写操作。
从
cur位置开始往前遍历原数组，依次还原出复写后的结果数组：(1).判断
cur位置的值：
如果是零：
dest以及dest - 1位置修改成0，dest -= 2；如果非零：
dest位置修改成复写 ，dest -= 1；(2).
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--;
}
}
}
};
时间复杂度为O(N)
3.快乐数
快乐数的定义：
- 对于⼀个正整数，每⼀次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1 。
- 如果这个过程**结果为 1 **，那么这个数就是快乐数。
- 如果
n是 快乐数 就返回true；不是，则返回false。
题目描述：
编写⼀个算法来判断⼀个数
n是不是快乐数。示例 1：
输⼊：
n = 19 输出：
true解释：
19 -> 1 * 1 + 9 * 9 = 82
82 -> 8 * 8 + 2 * 2 = 68
68 -> 6 * 6 + 8 * 8 = 100
100 -> 1 * 1 + 0 * 0 + 0 * 0 = 1例 2：
输⼊：
n = 2 输出：
false提示：
- 1 <=
n<= 231 - 1解释：（这⾥省去计算过程，只列出转换后的数）
2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16往后就不必再计算了，因为出现了重复的数字，最后结果肯定不会是 1
算法原理：
- 情况一：一直在 1 中死循环，即 1 -> 1 -> 1 -> 1…
- 情况二：在历史的数据中死循环，但始终变不到 1.
由这两个死循环我们可以联想到之前学过的判断链表是否有环的解决方法——快慢双指针。
快慢双指针:
1.定义快慢指针；
2.慢指针每次向后移动一步，快指针每次向后移动两步；
3.判断相遇时候的值即可。
这里我们可以用一个数来代替指针，一次操作（对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和）就相当于走了一步。不过为什么它这里一定会成环？
鸽巢原理（抽屉原理）：有
n个巢，n+1个鸽子，——>至少有一个巢里面的鸽子数大于1
简单证明：
因为n的最大值为231 - 1=21474 83647，我们选⼀个比它更大的数 99999 99999
所选的数经过⼀次变化之后的最大值为 9^2 * 10 = 810 。也就是说变化的区间在[1, 810]之间；
根据「鸽巢原理」，⼀个数变化 811 次之后，必然会形成⼀个循环；
因此，变化的过程最终会走到⼀个圈里面，因此可以用「快慢指针」来解决。
算法流程：
为了方便叙述，将「对于一个正整数，每⼀次将该数替换为它每个位置上的数字的平方和」这⼀个操作记为 x 操作；
根据上述的题目分析，我们可以知道，当重复执行 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;
}
};
4.盛最水多的容器
题目描述：
给定⼀个长度为
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 。（8-1）*7=49。
算法原理：
解法一：暴力枚举（超时）O(N2)
算法思路：
枚举出能构成的所有容器，找出其中容积最大的值。
容器容积的计算方式：
设两指针
i,j，分别指向⽔槽板的最左端以及最右端，此时容器的宽度为j - i。由于容器的⾼度由两板中的短板决定，因此可得容积公式 ：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)
算法思路：
设两个指针
left，right分别指向容器的左右两个端点，此时容器的容积 :
v = (right - left) * min( height[right], height[left])容器的左边界为
height[left],右边界为height[right]。为了方便叙述，我们假设「左边边界」小于「右边边界」。
如果此时我们固定⼀个边界，改变另⼀个边界，水的容积会有如下变化形式：
假设height[left]>height[right]，固定右端点，向内枚举，宽度一定变小；
要是在向内枚举的过程中遇到一个小于height[right]的height,那么高度也会变小，v就会变小；
要是遇到一个大于height[right]的height，那么高度不变，v变小。
由此可见，向内枚举，v一定变小。所以我们可以
right- -跳过这个边界，继续用上述方法去判断下⼀个左右边界。当我们不断重复上述过程，每次都可以舍去大量不必要的枚举过程，直到 left 与 right 相遇。期间产生的所有的容积里面的最大值，就是最终答案。
代码实现：
class Solution {
public:
int maxArea(vector<int>& height)
{
int left=0,right=height.size()-1,ret=0;
while(left<right)
{
int v=min(height[left],height[right])*(right-left);
ret=max(ret,v);
//移动指针
if(height[left]<height[right])
left++;
else
right--;
}
return ret;
}
};