目录
1. 移动零
1.1 算法原理
双指针:
- cur: 从左向右扫描数组
- dest: 非 0 数据的最后一个位置
划分区间: [0, dest] = 非 0 [dest + 1, cur - 1] => 0 [cur, n - 1] 待处理
情况处理:
- nums[cur] == 0, cur++
- nums[cur] != 0, swap(++dest, cur)
1.2 算法代码
class Solution {
public void moveZeroes(int[] nums) {
// [0, dest] => 非 0
// [dest + 1, cur - 1] => 0
// [cur, n - 1] => 未处理
int dest = -1, cur = 0, n = nums.length;
while(cur < n) {
if(nums[cur] != 0) swap(nums, ++dest, cur);
cur++;
}
}
void swap(int[] nums, int x, int y) {
int t = nums[x];
nums[x] = nums[y];
nums[y] = t;
}
}2. 复写零
2.1 算法原理
核心: 双指针 => 从后往前完成复写操作
- 找到最后一个要复写的数(位置) => 双指针
cur: 最后一个要复写的数 dest: 最后一个进行复写的位置
1.1 判断一下 cur 位置的值
1.2 决定 dest 往后走几步
1.2.1 arr[cur] != 0 --> dest += 1
1.2.2 arr[cur] == 0 --> dest += 2
1.3 判断 dest 是否已经到结束位置(dest >= n - 1 时, 结束)
1.4 if(dest 没有结束) cur++;
else break;
- 根据 cur 位置的值, 从后(dest 位置)往前进行复写零操作
2.1 若 cur 非零, arr[dest--] = arr[cur--]
2.2 若 cur 为零, arr[dest] = arr[dest - 1] = arr[cur--], dest -= 2;
2.2 算法代码
class Solution {
public void duplicateZeros(int[] arr) {
// cur -> 当前位置
// dest -> 最后一个要复写的位置
int cur = 0, dest = -1, n = arr.length;
while(dest < n - 1) {
if(arr[cur] == 0) dest += 2;
else dest += 1;
if(dest >= n - 1) break;
cur++;
}
// 处理边界情况
if(dest >= n) {
arr[n - 1] = 0;
dest -= 2;
cur--;
}
// 从后往前, 完成复写操作
while(cur >= 0) {
if(arr[cur] == 0) {
arr[dest] = arr[dest - 1] = 0;
dest -= 2;
}else {
arr[dest] = arr[cur];
dest -= 1;
}
cur--;
}
}
}3. 快乐数
3.1 算法原理
解法: 快慢双指针
问题转换: 链表是否带环
- 定义快慢双指针
- 快指针每次移动两步
- 慢指针每次移动一步
- 由题意得, 两个指针一定会相遇
- 若相遇时值为 1, 则为快乐数.
3.2 算法代码
class Solution {
public boolean isHappy(int n) {
// 初始化 => 保证 slow 和 fast 初始时不相等
int slow = n, fast = f(n);
// 快慢双指针 => 是否带环
while(slow != fast) {
slow = f(slow);
fast = f(f(fast));
}
return slow == 1;
}
// 对 n 的每个 bit 位进行平方求和操作
public int f(int n) {
int ret = 0;
while(n != 0) {
ret += Math.pow(n % 10, 2);
n /= 10;
}
return ret;
}
}4. 盛水最多的容器
4.1 算法原理
- 解法一: 暴力枚举 --> O(N^2) 超时
- 解法二: 利用单调性 --> O(N)
解法二过程:
1. 定义 left 和 right 指针, 分别指向数组的头和尾
2. 若 arr[left] < arr[right] 则 left++;
若 arr[right] < arr[left] 则 right--;
(因为指针一旦进行移动, 宽必定减小,
所以向内枚举时, 要保留值("高")更大的指针, 仅移动值("高")更小的指针)
4.2 算法代码
class Solution {
public int maxArea(int[] height) {
int n = height.length;
int ret = 0, left = 0, right = n - 1;
while(left != right) {
ret = Math.max((right - left) * Math.min(height[right], height[left]), ret);
if(height[left] < height[right]) left++;
else right--;
}
return ret;
}
}5. 有效三角形的个数
5.1 算法原理
核心: 对数组排序后, 使用双指针, 对暴力解法进行优化
- 对数组进行排序
- 固定最大的数
- 利用双指针, 在最大数的左区间中, 快速选出可以组成三角形的个数
5.2 算法代码
class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int n = nums.length, ret = 0;
for(int i = n - 1; i >= 2; i--) {
int right = i - 1, left = 0;
while(right != left) {
if(nums[left] != 0 && nums[right] + nums[left] > nums[i]) {
ret += right - left;
right--;
}else left++;
}
}
return ret;
}
}6. 剑指 offer：和为 s 的两个数(原)
6.1 算法原理
给出的数组就是排好序的数组, 直接 right, left 双指针快速定位和为 s 的两个数.
6.2 算法代码
class Solution {
public int[] twoSum(int[] price, int target) {
int left = 0, right = price.length - 1;
while(left != right) {
if(price[left] + price[right] > target) right--;
else if(price[left] + price[right] < target) left++;
else return new int[]{price[left], price[right]};
}
return price;
}
}END
标签：arr,专题,cur,dest,int,算法,right,left,指针 From： https://blog.csdn.net/2401_83595513/article/details/144415213