网站建设朋友圈素材,青白江建设网站,wordpress去掉title前空格及keywords最后的逗号,做单页购物网站用什么好目录 什么是双指针?问题1#xff1a;移动零问题2#xff1a;复写零问题3#xff1a;快乐数问题4#xff1a;盛最多水的容器问题5#xff1a;有效三角形个数问题6#xff1a;查找总价格和为目标值的两个商品(两数之和)问题7#xff1a;三数之和问题8#xff1a;四数之和… 目录 什么是双指针?问题1移动零问题2复写零问题3快乐数问题4盛最多水的容器问题5有效三角形个数问题6查找总价格和为目标值的两个商品(两数之和)问题7三数之和问题8四数之和总结 什么是双指针?
双指针算法是一种常见的解决问题的技巧通常使用两个变量在链表或者数组中进行迭代、遍历从而达到解决问题的目的。光说理论太抽象我们来几道题目吧~~
问题1移动零
力扣链接移动零 分析一下题目要求 将给定数组中所有的0移动到数组的末尾也就是将数组分成两个区域前半部分是非零元素后半部分都是零并且保持非零元素的相对顺序如示例1非零元素的顺序1312处理之后非零元素的顺序也要是1312
解题思路 既然是双指针算法那我们就定义两个指针咯这里的指针我们是指数组下标 定义两个指针destcur dest已经处理好的区间内非0元素的最后一个位置 cur从左往右遍历数组 dest初始为-1表示刚开始还没非0元素cur初始为0 在扫描的过程中一直让数组保持下面这个状态就好了 图解 代码实现
public void moveZeroes(int[] nums) {//双指针:定义dest和cur,dest初始值为-1//dest的作用:非0元素的最后一个位置,也就是[0,dest]的区间是非0元素//cur的作用:从左往右扫描数组,遍历数组int dest -1;for (int cur 0; cur nums.length; cur) {if (nums[cur] ! 0) {//cur遇到非0元素,先交换dest1位置和cur位置的元素,再dest,curint tmp nums[dest 1];nums[dest 1] nums[cur];nums[cur] tmp; dest;}}
}问题2复写零
力扣链接复写零 分析一下题目要求 所谓复写也就是让我们抄一遍数组的内容遇到非零的直接抄这个数遇到零抄两遍零题目要求我们在原数组上进行操作也就是说不能重新开辟一个新的数组 解题思路 先找到最后一个需要被复写的数然后从后往前进行复写如果从前往后后面的数会被覆盖掉。 如何找到最后一个被复写的数还是利用双指针算法如图 根据cur位置的值判断dest向前走一步还是两步走完判断dest是否到达结束位置dest是否arr.length-1如果dest没有到达结束位置则让cur。重复上面的步骤当dest到达最后位置时cur指向的就是最后一个被复写的数要注意的是dest的位置可能是arr.length-1也可能是arr.length如果destarr.length如下图需要处理这个边界问题 处理办法arr[arr.length - 1] 0;dest - 2;cur- -; 接下来就可以从后往前开始复写了拿下图举例
代码实现 public void duplicateZeros(int[] arr) {int cur 0;//指向最后一个位置int dest -1;//dest指结果中,最后需要复写的位置,开始时不知道dest在哪,所以-1//先找到最后一个被复写的数while (cur arr.length) {if (arr[cur] 0) {dest 2;} else {dest;}if (dest arr.length - 1) {break;}cur;}//边界情况,可能出现:最后要复写两个0,第二个0在arr.length这个位置if (dest arr.length) {arr[arr.length - 1] 0;dest - 2;cur--;}while (cur 0) {if (arr[cur] ! 0) {arr[dest] arr[cur];dest--;} else {arr[dest--] 0;arr[dest--] 0;}cur--;}}问题3快乐数
力扣链接快乐数 题目要求题目让我们判断给定的数是不是快乐数快乐数每次都对这个数进行一次操作让它的值替换为它每一位的数的平方之和重复这个操作判断最终结果是不是变成1或者无限循环变不到1 解题思路有点类似之前写过的判断链表是否成环题目说明了结果是1或者无限循环但是其实1也是无限循环1重复上述操作结果永远都是1所以我们可以使用快慢指针的思想当两个指针相遇时判断两个指针指向的数是不是1即可如果不熟悉判断链表是否成环可以看这篇哦链表OJ 代码实现
//返回n的每一位的平方之和
public int func(int n) {int sum 0;while (n ! 0) {int t n % 10;sum t * t;n / 10;}return sum;
}public boolean isHappy(int n) {int fast func(n);int slow n;while (fast ! slow) {slow func(slow);fast func(func(fast));}return fast 1;
}问题4盛最多水的容器
力扣链接盛最多水的容器 题目要求 给定了n条垂线题目要找出两条线与X轴构成的容器最多能盛水的容积 解题思路 容积V h*w其中h指高度也就是两条线的最短的那条w指宽度 如图
代码实现
public int maxArea(int[] height) {//根据规律:向内枚举时,要么宽度肯定减小,但是高度只能是不变或减小(木桶效应)int left 0;int right height.length - 1;int maxV 0;int V 0;while (left right) {V (right - left) * Math.min(height[left], height[right]);if (V maxV) {maxV V;}//让高度小的移动,高度小也叫说明容积小,不符合要求if (height[left] height[right]) {left;} else {right--;}}return maxV;
}问题5有效三角形个数
力扣链接有效三角形个数 题目要求 给定非负整数数组在数组中挑3个能组成三角形数求有几种挑法 解题思路
代码实现 public int triangleNumber(int[] nums) {// 利用单调性,使用双指针算法int count 0;int[] ret nums;Arrays.sort(ret);// 先排个序int flg ret.length - 1;//固定好flg,表示最大的数while (flg 2) {//固定好flg之后,再利用双指针int left 0;int right flg - 1;while (left right) {if (ret[left] ret[right] ret[flg]) {count (right - left);right--;} else {left;}}flg--;}return count;}问题6查找总价格和为目标值的两个商品(两数之和)
力扣链接查找总价格和为目标值的两个商品 题目要求 给定数组和target题目说明了已经排好序了求数组中和为target的两个数以数组的形式返回这两个数即可 解题思路 定义双指针leftright分别指向第一个和最后一个元素求两个指针指向的元素之和如果小于target说明要大一点让left同理如果大于target说明要小一点~~让right–当两个值等于target此时可以返回了 代码实现 public int[] twoSum(int[] price, int target) {int[] ret new int[2];//返回的数组//定义双指针left,rightint left 0;int right price.length - 1;while (left right) {int sum price[left] price[right];if (sum target) {left;} else if (sum target) {right--;} else {ret[0] price[left];ret[1] price[right];break;}}return ret;}问题7三数之和
力扣链接三数之和 题目要求 给定整数数组判断是否存在相加和为0的三个数这三个数的下标不能重复也就是说这三个数下标是不一样的返回所有的三元组答案不能是重复的三元组 解题思路 找到之后left和right继续移动解决了不漏的问题能够把所有的三元组都找出来但是并没有满足题目要求不能重复解决办法就是当找到两个数后记录left和right的值left和right跳过重复的数另外固定的数a下标是flg也要跳过重复的数 代码实现 public ListListInteger threeSum(int[] nums) {Arrays.sort(nums);//先排序int flg 0;//固定一个的数ListListInteger ret new ArrayList();// 返回的Listwhile (flg nums.length-2) {//双指针算法,left,rightint left flg 1;//左指针int right nums.length - 1;//右指针int a nums[flg];//双指针找目标值和为-a的两个数if(a0) {//小优化,大于0了,后面的都是0的数,肯定找不到-abreak;}//双指针算法,思路和求两数之和一样while (left right) {if (nums[left] nums[right] (-a)) {left;} else if (nums[left] nums[right] (-a)) {right--;} else {ListInteger list new ArrayList();list.add(a);list.add(nums[left]);list.add(nums[right]);ret.add(list);//// 找到结果之后,left,right跳过重复元素,避免越界int leftNumber nums[left];int rightNumber nums[right];while (nums[left] leftNumber left nums.length - 1) {left;}while (nums[right] rightNumber right 0) {right--;}}}// flg也要跳过重复的元素,flg不能越界while (nums[flg] a(flg nums.length-2)) {flg;}}return ret;}问题8四数之和
力扣链接四数之和 题目要求 在给定数组中找出4个和为target的数这四个数的下标不能重复 解题思路 明白了两数之和跟三数之和后四数之和的思路就很简单了先排序固定一个数a最左边或者最右边的数都是一样的然后在后面的区间按照三数之和的思路固定一个数b按照两数之和找出和为target-a-b的两个数 同样的left、right、flg1、flg2也要跳过重复的数 代码实现 public ListListInteger fourSum(int[] nums, int target) {Arrays.sort(nums);ListListInteger ret new ArrayList();// 返回的Listfor (int i 0; i nums.length; ) {//固定数afor (int j i 1; j nums.length; ) {//固定数bint left j 1;int right nums.length - 1;long aim (long) target - (nums[i] nums[j]);//abwhile (left right) {if (nums[left] nums[right] aim) {left;} else if (nums[left] nums[right] aim) {right--;} else {ListInteger list new ArrayList();list.add(nums[left]);list.add(nums[right]);list.add(nums[i]);list.add(nums[j]);ret.add(list);//处理细节,去重int leftNumber nums[left];int rightNumber nums[right];while (nums[left] leftNumber left nums.length - 1) {left;}while (nums[right] rightNumber right 0) {right--;}}}j;while ((j nums.length - 2) nums[j - 1] nums[j]) {j;}}i;while ((i nums.length - 3) nums[i - 1] nums[i]) {i;}}return ret;总结
遇到数组划分问题按要求将数组分划分几个区域或者如果数组存在单调性有序的时我们可以考虑双指针算法~~
