基础算法之双指针--Java实现(上)--LeetCode题解:移动零-复写零-快乐数-盛最多的水
这里是Thembefue
今天讲解算法中较为经典的一个算法
本讲解主要通过题目来讲解以理解算法
讲解分为三部分：题目解析 => 算法讲解 => 编写代码
移动零
题目链接： 移动零
题目解析
这题的题目意思还是比较好读懂的 就是将数组出现零的地方移到数组最后面，且数组数字的顺序不能改变，更不能创建新的数组来更改
算法讲解
标题既然是双指针，那么这题肯定是双指针来解决了。
1. 我们先定义两个指针变量：dest和cur。
2. cur从左往右遍历数组。
3. 若是cur指向的元素为非零元素，则将dest和cur指向的元素交换。同时dest才向后移动
以上便是模拟此次过程的代码
如果将上面的某一过程提取出来，会发现此时数组分为了三个区域
那么根据上述的算法讲解，就可以实现代码了
编写代码
class Solution {
public void moveZeroes(int[] nums) {
// 双指针
int dest = 0;
int cur = 0;
while (cur < nums.length) {
if (nums[cur] != 0) {
swap(nums, dest, cur);
dest++;
}
cur++;
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}复写零
题目链接：复写零
题目解析
这道题的意思就是将数组中的零元素复制一个到数组里，但是数组的长度不能改变，我们先根据异地操作来模拟一遍过程。
算法讲解
· 以上便是异地双指针操作的全部过程，但是题目并不能创建额外的空间，所以我们必须使用双指针对原数组进行修改
· 如果单纯地从左向右修改的话，那么就会导致非零数字被覆盖的情况
· 所以我们采用从后往前复写
·首先找到最后一个需要 “复写” 的元素
·先判断 i 指针当前位置的值 => 若为0，则 j 指针往后移两步，否则移动一步。
· 再判断此时 j指针是否走的数组最后一个元素。
· 最后让 i 指针往后移动一步。
· 找到最后一个复写的元素后，不能立刻复写。
· 此时可能会出现特殊情况，就是 j 指针可能指向的不是数组的最后一个元素，而是数组外的位置，这会导致数组越界。
· 所以还需额外判断 => 若确实出现这种情况，这应该先复写一次。
编写代码
class Solution {
public void duplicateZeros(int[] arr) {
int cur = 0;
int dest = -1;
// 找到最后一个需要复写的元素
while (true) {
if (arr[cur] == 0) {
dest += 2;
} else {
dest += 1;
}
if (dest >= arr.length - 1) {
break;
}
cur++;
}
if (dest >= arr.length) {
arr[dest - 1] = 0;
dest -= 2;
cur -= 1;
}
while (cur >= 0) {
if (arr[cur] == 0) {
arr[dest--] = arr[dest--] = 0;
} else {
arr[dest--] = arr[cur];
}
cur--;
}
}
}快乐数
题目链接：快乐数
题目解析
这题的题目意思还是比较好懂的，所以我就不做过多解释了。
有一个至关重要的点就是，如果这个数不是快乐数的话，它是会无限循环的，它不会一直增大，而是会成一个圈，也就永远不会到达1。
示例上的两种情况一一列举出来，可以看到，第二种所示情况成为一个环。
算法讲解
· 这题的核心思路便是快慢指针，即双指针的一种，快指针一次走多步（一般是走两步），慢指针一次走一步。
· 好比操场跑步，配速更快的同学一定会在某一个时间以不同的圈数到达配速更慢的同学的位置，此时两位同学相遇了。
· 利用这个规律，快慢指针若会相遇，则说明此时成环了，也就不是快乐数，否则为快乐数。
· 当然成环了也不一定不是快乐数，若遇到1，则会一直是1，当然这种情况其实就已经可以结束了。
编写代码
class Solution {
public boolean isHappy(int n) {
int slow = n, fast = getNext(n);
while (slow != fast) {
slow = getNext(slow);
fast = getNext(getNext(fast));
}
return slow == 1;
}
private int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
}盛最多水的容器
题目链接：盛最多水的容器
题目解析
这题的本质就是面积，但要求的是最大面积
任取两个数组下标，这两个数组的下标之间的距离构成宽
这两个下标所指向的元素，哪个元素更小，即构成高
算法讲解
· 众所周知，长方形的面积等于高乘宽。
· 有了这个定理，我们再看这题，利用单调性，再利用双指针就可以解决了。
· 我们定义两个指针，一个指向数组的头，另一个指向数组的尾。
· 这两个指针当然会向中间靠近，知道相遇，结束计算。
· 首先，我们要先知道的是，既然两个指针逐渐向中间靠近，那么该长方形的宽只会递减，不会出现增加的情况。
· 其次，就是如何递减了，同时递减？显然不可能。既然该长方形的高是由指针指向的元素且是两个指针的较小的值所构成的，所以，只需要让更小的元素向前或向后移动就好了。
编写代码
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1, max = 0;
while (left < right) {
int tmp = (right - left) * Math.min(height[left], height[right]);
max = Math.max(max, tmp);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return max;
}
}好了，以上就是今天内容的全部讲解，如果有不懂的地方，随时私聊😘
我们下半部分见😁
原文地址：https://blog.csdn.net/Themberfue/article/details/142664290
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！