经典Leetcode接雨水问题来啦，这个问题被归到了双指针专题里，更神奇的是我居然之前接过雨水，我甚至没有任何印象了。巧合的是，接雨水是这个专题唯一一个Hard，来看一看吧。
42. Trapping Rain Water[Hard]
思路：大名鼎鼎的接雨水也不过如此。就是个典型的双指针，从外向里统计一下两边的最高点，然后每个位置容量即为左右边界的最小值减去其自身高度即可。
瞄一眼之前的思路，想想当时还是备战亚马逊之前的日子，实属有点怀念
LeetCodeGOGOGO刷题记07——备战Amazon（Online_Assessment前的终章）_亚马逊online assessment的代码题-CSDN博客
/*
Author Owen_Q
*/
public class RainWaterTrapper {
public static int trap(int[] height) {
int len = height.length;
int[] leftHeight = new int[len];
int[] rightHeight = new int[len];
leftHeight[0] = height[0];
rightHeight[len - 1] = height[len - 1];
for (int i = 1; i < len; i++) {
leftHeight[i] = Math.max(height[i], leftHeight[i - 1]);
rightHeight[len - i - 1] = Math.max(height[len - i - 1], rightHeight[len - i]);
}
int ans = 0;
for (int i = 0; i < len; i++) {
ans += Math.min(leftHeight[i], rightHeight[i]) - height[i];
}
return ans;
}
}
283. Move Zeroes[Easy]
思路：将数组中所有的0移动到数组的最右侧。用一个指针记录一下左侧第一个零的位置，然后每次遇到非零则与最左侧零交换即可。
/*
Author Owen_Q
*/
public class ZerosMover {
public static void moveZeroes(int[] nums) {
int current = 0;
int left = 0;
for (int num : nums) {
if (num != 0) {
if (current > left) {
int temp = nums[left];
nums[left] = nums[current];
nums[current] = temp;
}
left++;
}
current++;
}
}
}
其实说实话，也没发现这个Easy题比上面的Hard接雨水要简单多少，可能都太简单了导致没什么区别了吧。
但这时间消耗也确实有点过大了，想想看有没有什么别的思路
多想一点：变交换为移位
分析一下这题的主要开销就在交换元素上，交换元素包含三次赋值，如果但其实我们完全可以看到非0就往左移，后面补0，就可以将交换的三次赋值降低为移位的单词赋值了。此外，比较操作也可以直接去除，直接无脑拷贝，这样又可以省去一个指针的维护和比较成本，成功将此题降级为单指针问题
/*
Author Owen_Q
*/
public class ZerosMover {
public static void moveZeroesMove(int[] nums) {
//int current = 0;
int left = 0;
int len = nums.length;
for (int num : nums) {
if (num != 0) {
//if (current > left) {
//int temp = nums[left];
nums[left] = num;
//nums[current] = temp;
//}
left++;
}
//current++;
}
for (int i = left; i < len; i++) {
nums[i] = 0;
}
}
}
效果还是挺明显的
11. Container With Most Water [Medium]
思路：给定n个位置的高度，要求任选两个接最多的水，这个和前面接雨水的题有异曲同工之妙。不同的是接雨水是求和，而这题是选区域。相同的点就是都是双指针。不过由于要选区域，这题的双指针可以不用预处理，而是从边上往两边移动，每次只需要移动低的那边，移到下一个高处即可。
/*
Author Owen_Q
*/
public class WaterContainer {
public static int maxArea(int[] height) {
int len = height.length;
int left = 0;
int right = len - 1;
int ans = (right - left) * Math.min(height[left], height[right]);
while (left < right) {
if (height[left] <= height[right]) {
int currentHeight = height[left];
while (height[left] <= currentHeight && left < right) {
left++;
}
} else {
int currentHeight = height[right];
while (height[right] <= currentHeight && left < right) {
right--;
}
}
ans = Math.max(ans, (right - left) * Math.min(height[left], height[right]));
}
return ans;
}
}
15. 3Sum[Medium]
思路：三数和问题，想想之前的两数和问题，当时那题在哈希专题，搜索单个值，然后哈希判断另一个值是否在数组中。
Leetcode百题斩-哈希-1. Two Sum[Easy]-CSDN博客
当时那题最大的困难点在于判断哈希出来的元素是否为当前元素，解决方式是先枚举后哈希，即枚举完的值再添加到哈希中，避免哈希到自己，毕竟先哈希谁效果都一样。但是这一题相同的困境出现了，如果枚举前两个数，哈希第三个数，那么就无法知道哈希出来的值是否是前两个数自身。如果，而两个数更无法通过先枚举后哈希的方式，唯一的办法就是记录每个值实际的位置，但又存在单个值多个位置的情况，可能还需要考虑用set数组的方式进行存储。
那不如换一个思路，毕竟这题被划在了双指针专题。同样还是双层枚举，不过最后一层哈希改为指针，虽然多了一层指针移动的复杂度，但是可以明确知道遍历到的位置。外层指针刚好和内层枚举形成双指针。
/*
Author Owen_Q
*/
public class ThreeSum {
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
int len = nums.length;
int p1 = 0;
while (p1 < len - 2) {
int p2 = p1 + 1;
int p3 = len - 1;
while (p2 < p3) {
int currentSum = nums[p1] + nums[p2] + nums[p3];
if (currentSum == 0) {
result.add(Arrays.asList(nums[p1], nums[p2], nums[p3]));
}
if (currentSum <= 0) {
do {
p2++;
} while (p2 < p3 && nums[p2] == nums[p2 - 1]);
} else {
do {
p3--;
} while (p2 < p3 && nums[p3] == nums[p3 + 1]);
}
}
do {
p1++;
} while (p1 < len - 2 && nums[p1] == nums[p1 - 1]);
}
return result;
}
}
完结撒花
