[Java][算法 双指针]Day 02---LeetCode 热题 100---04~07

LeetCode 热题 100---04~07

第一题：移动零

思路

找到每一个为0的元素 然后移到数组的最后  但是需要注意的是  要在给定的数组原地进行修改  并且其他非零元素的相对顺序不能改变  我们采用双指针法

定义两个指针i和j  i和j一开始分别都在0索引位置  然后判断j所在位置元素数值  如果等于0 则往下走一位 反之 则将数值赋值到i位置 j和i同时向下走一位

这样子 i总在j后面  j所到的非零元素 都会按照相对顺序依次赋值到i的位置  当j走到重点  i必然还没走到重点（除非整个数组没有0元素） 此时j会停止 而其他非零元素已经全部到达i的前方位置

接下来只需要遍历一遍i~j  将这部分的元素置零即可  大致过程如下（最后将两箭头之间的元素置零即可）

第二题：盛最多水的容器

解法一  暴力法（超时）

最简单直接的方法就是双重for嵌套  依次遍历 两两求体积 最后取最大值即可

思路是可行的 但是在数据量大的情况下 时间超时也是没办法的

class Solution {public int maxArea(int[] height) {if(height.length==1 || height.length==0) return 0;int max=0;for (int i = 0; i < height.length; i++) {for(int j=i+1;j<height.length;j++){int v=(j-i)*Math.min(height[i],height[j]);if(v>max) max=v;}}return max;}
}

解法二 双指针法

首先  我们直到  求两个板子能装水的体积 就是 Min（板A，板B）*AB之间的距离

那么 按照这个思路  我们让AB分别从数组最两端开始 那么可以确定的是我们之后每次都只向内移动变化 那么 AB之间的距离 这个变量就是单调递减的  那么剩下的变化因素就是 Min（板A，板B）

A,B板的移动 都会影响该数值   现在我们来分析 假设我们A板是较短的那块板子

当我们移动A板  即移动短板  A'板的长度可能长于也可能短于A板

如果A'短于A板子 那么Min（A',B）肯定是A'  比Min（A,B）小  AB距离变小 那么整个体积肯定减小

如果A'长于A板子  那么Min（A',B）等于A'或者B（需要看A'和B哪个长）  但是无论如何肯定会比Min（A，B）大  但是AB之间的距离减小 所以最后两者的乘积 体积V的变化情况就不一定了 所以是可能变大 可能变小 可能不变

当我们移动B板  即移动短板  B'板的长度可能长于也可能短于B板

如果B'短于B板子 那么Min（A,B'）可能是A也可能是B'   比Min（A,B）小  AB距离变小 那么整个体积肯定减小

如果B'长于B板子  因为短板效应 那么Min（A,B'）还是等于A  但是AB之间距离减小 所以体积一定减小

综上  移动长版  体积一定减小  移动短板  体积可能变大

所以 我们双指针可以分别从两端开始  每次移动短的那一块 然后记录出最大体积值即可

class Solution {public int maxArea(int[] height) {if(height.length==0||height.length==1) return 0;int i=0;int v=0;int j=height.length-1;int max=0;while(i<j){if(height[i]>height[j]){v=height[j]*(j-i);j--;}else{v=height[i]*(j-i);i++;}if(v>max) max=v;}return max;}
}

第三题：三数之和

思路

首先是要记得特殊情况直接判断length小于3和数组为null直接范围[]

然后 如果整个数组的最小数都大于0 那么也可以直接返回  所以这就需要我们实现排序

然后对于正常情况  即我们要找到三个数  使其和等于0  最简单直接的 当然是for循环的嵌套 

很容易理解和实现 但是时间复杂度肯定是很大的

为了简化寻找的过程 我们只需要一个循环数 其他的都用固定表达式表示即可

假设我们对数组进行了排序   我们让i从0开始遍历  然后定义变量j=i+1 g=length-1作为双指针  我们在用i遍历的时候  每到一个位置 我们需要在j和g之间遍历找数据

每次计算出nums[i]+nums[j]+nums[g]来判断是否等于0  因为整个数组是有序的 那么我们就可以根据和0的大小比较来直到该如何移动j和g 小于动j  大于动g

（思想类似于[Java][算法 哈希]Day 01---LeetCode 热题 100---01~03-CSDN博客中第一大题的移动思想）

class Solution {public List<List<Integer>> threeSum(int[] nums) {if(nums.length<3||nums==null) return new ArrayList<>();List<List<Integer>> list=new ArrayList<>();Arrays.sort(nums);int i=0;for(i=0;i<nums.length;i++){// 去重if(i>0 && nums[i]==nums[i-1]) continue;int j=i+1,g=nums.length-1;if(nums[i]>0) break;while(j<g){int sum=nums[i]+nums[j]+nums[g];if(sum==0){list.add(Arrays.asList(nums[i],nums[j],nums[g]));while(j < g && nums[j] == nums[j+1]) {j++;}while(j< g && nums[g] == nums[g-1]){g--;}j++;g--;}else if(sum>0){g--;}else if(sum<0){j++;}}}return list;}
}

第四题：接雨水

思路

对于这个题目 我们不应该集中想法去整体求值 而应该去想办法如何单独求出每一个的值 然后相加

对于每一个位置 i 能达到的水柱高度和其左边的最高柱子、右边的最高柱子有关，我们分别称这两个柱子高度为 l_max 和 r_max；位置 i 最大的水柱高度就是 min(l_max, r_max)*height[i]

根据这个思路 我们就知道 需要在遍历的时候  找到该位置的左右两边的最高的柱子  然后又选左右两边最高的中的较小的那个

解法一：暴力法

int trap(int[] height) {int n = height.length;int res = 0;for (int i = 1; i < n - 1; i++) {int l_max = 0, r_max = 0;// 找右边最高的柱子for (int j = i; j < n; j++)r_max = Math.max(r_max, height[j]);// 找左边最高的柱子for (int j = i; j >= 0; j--)l_max = Math.max(l_max, height[j]);// 如果自己就是最高的话，// l_max == r_max == height[i]res += Math.min(l_max, r_max) - height[i];}return res;
}

 解法二：双指针法

我们利用双指针  一个从最左边移动 一个从最右边移动 边走边算的模式 

每次走到一个点 先比较该点数值和历史记录的最大值  用于及时更新最大值

更新完最大值之后 比较两边的最大值  取出较小的那个进行计算 最后再移动小的那个

（因为计算是去小数值的 那么计算完之后代表该次计算完成  只有移动小的才能保证不忽略 不重复）

class Solution {int trap(int[] height) {int left = 0, right = height.length - 1;int l_max = 0, r_max = 0;int res = 0;while (left < right) {l_max = Math.max(l_max, height[left]);r_max = Math.max(r_max, height[right]);// res += min(l_max, r_max) - height[i]if (l_max < r_max) {res += l_max - height[left];left++;} else {res += r_max - height[right];right--;}}return res;}
}