当前位置：首页 > news >正文

优选算法精品——双指针

news 2024/11/5 1:11:46

移动零

算法原理：

1.数组划分,数组分块

2.双指针算法

(利用数组下标来充当指针)

两个指针的作用:

cur:从左往右扫描数组,遍历数组

dest:已处理的区间内,非零元素的最后一个位置

代码实现：

cur 从前往后遍历的过程中:

1.遇到0元素:cur++;

2.遇到非零元素:

swap(dest + 1, cur);
dest++, cur++;

class Solution {public void move(int[] nums) {for (int cur = 0, dest = -1; cur < nums.length; cur++) {if (nums[cur] != 0) {dest++;// 交换当前元素与目标位置的元素int temp = nums[cur];nums[cur] = nums[dest];nums[dest] = temp;}}}
}

复写零

2.算法原理

解法:双指针算法

先根据“异地”操作,然后优化成双指针下的“就地”操作，先找到最后一个“复写”的数;

双指针算法

1.先判断 cur位置的值

2. 决定dest向后移动一步或者两步

3.判断一下dest是否已经到结束为止

4. cur++

1.5处理一下边界情况

代码：

class Solution {public void duplicateZeros(int[] arr) {int n = arr.length;int top = 0;int i = -1;while (top < n) {i++;if (arr[i] != 0) {top++;} else {top += 2;}}int j = n - 1;if (top == n + 1) {arr[j] = 0;j--;i--;} while (j >= 0) {arr[j] = arr[i];j--;if (arr[i] == 0) {arr[j] = arr[i];j--;} i--;}}
}

快乐数

题目解析：

2.算法原理

2.1第一种情况不是快乐树，那么最后值不为一，且会返回到原来值，形成一个环

2.2第二种情况是快乐树，那么最后值为一，形成一个全是一的环

因此，我们只需要采用快慢指针法，判断他们相遇时环中值是否为一，若为一则是快乐树，反之

3.代码实现

class Solution {public int bitSum(int n) {int sum = 0;while (n > 0) { // 确保 n 大于 0int t = n % 10;sum += t * t;n = n / 10;}return sum;}public boolean isHappy(int n) {int slow = n;int fast = bitSum(n);while (slow != fast) {slow = bitSum(slow); // 更新 slowfast = bitSum(bitSum(fast)); // 更新 fast}return slow == 1; // 检查 slow 是否到达 1}
}

解析：

bitSum 方法：循环条件现在正确检查 n > 0，确保我们能处理完所有的数字位。
isHappy 方法：
- slow 指针初始为 n，会通过数字的平方和序列逐步更新。
- fast 指针通过两次调用 bitSum 来加快循环检测的速度。
- 当 slow 和 fast 相遇时，表示可能出现了循环或达到了 1。

盛水最多的容器：

题目解析：
计算两条直线与x轴围成的水的体积，以最低的线计算高

算法原理：

将各个线的高度看作一个数组，采双指针法，分别计算每个容器的体积，并比较出最大的容器

class Solution {public int maxArea(int[] height) {int left = 0, right = height.length - 1, volume = 0;while (left < right) {int v = Math.min(height[left], height[right]) * (right - left);volume = Math.max(volume, v);// 移动较短的边if (height[left] < height[right]) {left++;} else {right--;}}return volume;}
}

有效三角形的个数

2.算法原理

1.暴力算法：

for(int i=0;i<arr.length;i++){

for(int j=0;j<arr.length;j++){

for(int k=0;k<arr.length;k++){

check(i,j,k);

}

}

}

2.利用单调性，双指针算法

1.先固定最大的数

2.在最大的左区间内使用双指针算法，统计出三元组的个数

1a+b>c left=right,right--;

2.a+b<=c left++

3.代码实现

public int solution{
Arrays.sort(nums);
int ret=0,n=nums.length;
for(int i=n-1;i>=2;i--){
int left=0,right=i-1;
while(left>right){
if(nums[left]+nums[right]>nums[i]){
ret+=right-left;
right--;}else{
left++;
}
}
}
return ret;
}

和为s的两个数字

算法原理：
1.暴力算法

for(int i=0;i<arr.length;i++){

for(int j=0;j<arr.length;j++){

check(i,j);

}

2.双指针（与上题同理）

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int i = 0;int j = nums.size() - 1;//双指针while(i < j){auto s = nums[i] + nums[j];if(s < target)i++;if(s > target)j--;if(s == target)return{nums[i], nums[j]};}return {};}
};