目录
1. 移动零
1.1 算法原理
1.2 算法代码
2. 复写零
2.1 算法原理
2.2 算法代码
3. 快乐数
3.1 算法原理
3.2 算法代码
4. 盛水最多的容器
4.1 算法原理
4.2 算法代码
5. 有效三角形的个数
5.1 算法原理
5.2 算法代码
6. 剑指 offer：和为 s 的两个数(原)
6.1 算法原理
6.2 算法代码
1. 移动零
283. 移动零 - 力扣（LeetCode）
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. 复写零
1089. 复写零 - 力扣（LeetCode）
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. 快乐数
202. 快乐数 - 力扣（LeetCode）
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. 盛水最多的容器
11. 盛最多水的容器 - 力扣（LeetCode）
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. 有效三角形的个数
611. 有效三角形的个数 - 力扣（LeetCode）
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 的两个数(原)
LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）
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
