算法:双指针标题训练

---

算法:双指针

移动零

定义两个指针,slow和fast.用这两个指针把整个数组分成三块.
[0,slow]为非零元素,[slow+1,fast-1]为0元素,[fast,num.length]为未处理的元素.
初始环境下slow=-1,fast=0,由于此时还没有对数组举行处理.
用fast遍历整个数组:

• 当fast指向的元素不为0时,此时让slow++,并交换fast与slow所指向的元素.交换完毕后fast++,继承向后处理元素.
  
• 当fast指向的元素为0时,直接fast++.
  

1. class Solution {
2.     public void moveZeroes(int[] nums) {
3.         int slow = -1;
4.         int fast = 0;
5.         while(fast < nums.length) {
6.             if(nums[fast] != 0) {
7.                 slow++;
8.                 int tmp = nums[fast];
9.                 nums[fast] = nums[slow];
10.                 nums[slow] = tmp;
11.             }
12.             fast++;
13.         }
14.     }
15. }

复制代码

复写零

这道标题假如没有要求空间复杂度为O(1)的话,那确实是简单题.直接申请一块数组,遍历,然后放进去,最后把数组的引用交换一下就行了.
但是实际上,这道题照旧有点难度的,需要考虑的细节环境很多,本身上手写写就知道了.
办理这道题,最关键的就是找到数组中最后一个要被修改的数,我们可以利用双指针来找.

• 定义两个指针slow和fast并初始化为0.利用slow向后遍历数组,当slow遇到0时,fast向后移动两步,slow向后移动一步.当slow指向的元素不为零时,fast和slow都向后移动一步.重复上述过程,直到fast大于数组长度.
  
• 循环竣事后,此时fast和slow多移动了一步,所以要减掉.在这里还需要考虑fast向后移动了两步的环境(slow指向了0元素,而此时fast已经位于数组的最后一个元素了),判断一下fast是否越界,假如越界,修改fast的指向,让fast指向数组的最后一个元素,由于这时slow指向的元素肯定是0,所以我们可以将数组的最后一位修改成0,之后让slow和fast向前移动一位.
  
• 当步伐运行到这里时,全部的特殊环境我们就都处理完了.接下来就是简单的移动和赋值了,这里就不再赘述了~
  

1. class Solution {
2.     public void duplicateZeros(int[] arr) {
3.         int fast = 0;
4.         int slow = 0;
5.         while(fast < arr.length) {
6.             if(arr[slow] == 0) fast++;
7.             fast++;
8.             slow++;
9.         }
10.         --slow;
11.         --fast;
12.         if(fast == arr.length) {
13.             fast = arr.length-1;
14.             arr[fast--] = arr[slow--];
15.         }
16.         while(slow >= 0) {
17.             if(arr[slow] == 0) {
18.                 arr[fast--] = 0;
19.             }
20.             arr[fast--] = arr[slow--];
21.         }
22.     }
23. }

复制代码

也可以看看宫水三叶大佬写的代码,大佬在力扣上写了题解,可以去看看.

1. class Solution {
2.     public void duplicateZeros(int[] arr) {
3.         int n = arr.length, i = 0, j = 0;
4.         while (j < n) {
5.             if (arr[i] == 0) j++;
6.             i++; j++;
7.         }
8.         i--; j--;
9.         while (i >= 0) {
10.             if (j < n) arr[j] = arr[i];
11.             if (arr[i] == 0 && --j >= 0) arr[j] = 0;
12.             i--; j--;
13.         }
14.     }
15. }
17. 作者：宫水三叶
18. 链接：https://leetcode.cn/problems/duplicate-zeros/solutions/1607062/by-ac_oier-zivq/
19. 来源：力扣（LeetCode）
20. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复制代码

快乐数

这道题条件给的很全,假如标题没给"重复这个过程直到这个数变为1,也大概是无限循环但始终变不到1"这个条件.
那么就需要好好的想一想了,上面的条件是可以证实出来的.运用到了数学上的思想"鸽巢原理",这个放到最后再写吧,先写题解~

• "将一个正整数替换为它每个位置上的数字的平方和"这个我们可以把它写成一个方法,方便调用,写法也很简单,这里就不写了.
  
• 这道题最焦点的地方，在于你怎么判断它无限循环永远到不了1，我们可以利用双指针来帮助我们判断，假如你之前做过环形链表，那么就很轻易想到。
  
• 定义两个指针slow和fast，并初始化为n，起首让fast先走一步(做一次替换,由于之后的循环内需要判断fast和slow是否相当).
  
• 紧接着进入循环,循环条件为fast != 1 || fun(fast) != 1,由于之后fast要一次向后走两步,所以fast的当前值和fast的下一个值都要判断.循环内假如fast与slow相当,说明有环了,直接return false.假如不相当,slow向后走一步,fast向后走两步.
  
• 假如fast走着走着跳出了循环(表示fast可以被替换成1),此时直接return true.
  

1. class Solution {
2.     public static int fun(int n) {
3.         int sum = 0;
4.         while(n > 0) {
5.             int tmp = n%10;
6.             sum += tmp*tmp;
7.             n/=10;
8.         }
9.         return sum;
10.     }
11.     public boolean isHappy(int n) {
12.         int slow = n;
13.         int fast = fun(n);
14.         while(fast != 1 || fun(fast) != 1) {
15.             if(fast == slow) {
16.                 return false;
17.             }
18.             fast = fun(fun(fast));
19.             slow = fun(slow);
20.         }
21.         return true;
22.     }
23. }

复制代码

鸽巢原理讲解:
以下是不太严谨的证实~
举个例子,比如说n = 9999999999.
n颠末一次变换之后n = 9^2*10 = 810.也就是说变换的区间就在[1,810]这个范围内.
假如我们将n变换810次,最差的环境就是[1,810]内全部的数都出现了一次.假如n在此基础上再次变换,那么这个数肯定就会落在这个区间内,此时就形成了环路.
盛最多水的容器

写这道题时,我们就要分析分析了.
设盛水容量为v,底部变长为s,高为h.左指针为left指向最左边,右指针为right指向最右边,两个指针向对方移动.
根据题意,我们可得:

• v = s * h;
  
• s = right - left;
  
• h = min(left,right);
  当我们移动指向的最高的线的指针时,有以下两种环境:
  
• s 减小(两指针之间的距离变短了), 移动后指针的指向的线高于移动前的线,h 不变(由于盛水多少取决于最低的线),那么 v 减小
  
• s 减小,移动后指针的指向的线低于移动前的线,h 不变或减小(由于盛水多少取决于最低的线,移动后的指针指向的线大概比另一个指针指向的线短,也大概在移动后仍然比另一个指针指向的线长),那么 v 减小.
  可以看到,当我们移动指向的最高的线的指针时,v并不会增大.
  

当我们移动指向的最低的线的指针时,有以下两种环境:

• s 减小(两指针之间的距离变短了), 移动后指针的指向的线高于移动前的线,h 增大(由于盛水多少取决于最低的线),那么 v 的厘革不能确定.
  
• s 减小,移动后指针的指向的线低于移动前的线,h 减小(由于盛水多少取决于最低的线),那么 v 减小.
  

综合上述分析,我们可以得到,只有在移动指向的最低的线的指针,并且移动后,指针的指向的线,高于移动前的线时,v才有大概变大.
有了以上的分析,代码就很好写啦~

1. class Solution {
2.     public int maxArea(int[] height) {
3.         int left = 0;
4.         int right = height.length - 1;
5.         int v = 0;
6.         while(left < right) {
7.             int s = Math.min(height[left],height[right]);
8.             int tmp = s*(right-left);
9.             if(tmp > v) {
10.                 v = tmp;
11.             }
12.             if(height[left] == s) {
13.                 left++;
14.             } else {
15.                 right--;
16.             }
17.         }
18.         return v;
19.     }
20. }

复制代码

有用三角形的个数

先给数组排个序.
从后向前固定一个i值(循环1),当left小于right时(循环2),让left和right指向的数相加,判断是否大于i指向的数.

• 大于i,让sum+=right-left; right–;
  
• 小于或等于i,让left向右移.
  
  
  
  

1. class Solution {
2.     public int triangleNumber(int[] nums) {
3.         int left =0;
4.         int right = 0;
5.         Arrays.sort(nums);
6.         int sum = 0;
7.         for(int i=nums.length - 1;i >= 2;i--) {
8.             right = i-1;
9.             left = 0;
10.             while(left < right) {
11.                 if(nums[left]+nums[right] > nums[i]) {
12.                     sum += right -left;
13.                     right--;
14.                 } else {
15.                     left++;
16.                 }
17.             }
18.         }
19.         return sum;
20.     }
21. }

复制代码

查找总代价为目的值的两个商品

感觉没什么可说的~

1. class Solution {
2.     public int[] twoSum(int[] price, int target) {
3.         int left = 0;
4.         int right = price.length - 1;
5.         while(left < right) {
6.             if(price[left] + price[right] > target) {
7.                 right--;
8.             } else if(price[left] + price[right] < target) {
9.                 left++;
10.             } else{
11.                 return new int[]{price[left],price[right]};
12.             }
13.         }
14.         return null;
15.     }
16. }

复制代码

三数之和

本身写的代码,在最开始new ArrayList<List<Integer>>()的时间不会new,忘了.(厥后发现不消这么麻烦写e)
另有我最开始是在最内层循环里面利用了list.contains(list2),然后超时了qwq.
厥后去看题解,发现还能这样去重!
改了改就成如今这样了,虽然效率照旧很低就是了.

1. class Solution {
2.     public List<List<Integer>> threeSum(int[] nums) {
3.         List<List<Integer>> list = new ArrayList<List<Integer>>();
4.         Arrays.sort(nums);
5.         int left = 0;
6.         int right = nums.length - 1;
7.         for(int i = nums.length-1; i >= 2; i--) {
8.             if(i < nums.length - 1 && nums[i] == nums[i+1]) continue;
9.             right = i - 1;
10.             left = 0;
11.             while(left < right) {
12.                 if(right != i-1 && right >= left +1 && nums[right] == nums[right+1]) {
13.                     right--;
14.                     continue;
15.                 }
16.                 int tmp = nums[left] + nums[right] + nums[i];
17.                 if(tmp > 0) {
18.                     right--;
19.                 } else if(tmp < 0) {
20.                     left++;
21.                 } else {
22.                     ArrayList<Integer> list2 = new ArrayList<>();
23.                     list2.add(nums[left]);
24.                     list2.add(nums[right]);
25.                     list2.add(nums[i]);
26.                     list.add(list2);
27.                     right--;
28.                 }
29.             }
30.         }
31.         return list;
32.     }
33. }

复制代码

看了讲解后:

• List<List<Integer>> list = new ArrayList<List<Integer>>();实在可以写成
  List<List<Integer>> list = new ArrayList<>(); < >里面可以啥都不写.
  
• 当num<0时,此时最大的数都小于0了,肯定三数之和就不大概等于0了,直接跳过.
  
• 第一次见还能这样写: list.add(new ArrayList(Arrays.asList(nums[left],nums[right],nums)));
  
• 当三数和为0时,left和right可以都移动一步(我写的只有right移动一步).
  
• 当三数和为0并且left和right移动后,此时就可以开始去重了,不必在内层循环用if和continue去重(这样多判断了right != i-1),而且我只对right去重了,left照旧要颠末整个循环emmm,虽然也达到了去重的效果(歪打正着,我当时还在想为啥if和continue不能换成while?被本身蠢哭了qwq).实在没必要,直接同时去重就OK了.
  

虽然本身第一次写的代码能通过,但是可优化的地方另有很多.没有大佬写的代码优雅~
以下是改后的代码:

1. class Solution {
2.     public List<List<Integer>> threeSum(int[] nums) {
3.         List<List<Integer>> list = new ArrayList<>();
4.         Arrays.sort(nums);
5.         int left = 0;
6.         int right = nums.length - 1;
7.         for (int i = nums.length - 1; i >= 2; i--) {
8.             if (nums[i] < 0)
9.                 break;
10.             if (i < nums.length - 1 && nums[i] == nums[i + 1])
11.                 continue;
12.             right = i - 1;
13.             left = 0;
14.             while (left < right) {
15.                 int tmp = nums[left] + nums[right] + nums[i];
16.                 if (tmp > 0) {
17.                     right--;
18.                 } else if (tmp < 0) {
19.                     left++;
20.                 } else {
21.                     list.add(new ArrayList<Integer>(Arrays.asList(nums[left],nums[right],nums[i])));
22.                     right--;
23.                     left++;
24.                     while (right > left && nums[right] == nums[right + 1]) {
25.                         right--;
26.                     }
27.                     while (right > left && nums[left] == nums[left - 1]) {
28.                         left++;
29.                     }
30.                 }
31.             }
32.         }
33.         return list;
34.     }
35. }

复制代码

四数之和

本身写出来的,中心改了好频频,终于过了~
跟上一题很像.
本身写的代码:

1. class Solution {
2.     public List<List<Integer>> fourSum(int[] nums, int target) {
3.         List<List<Integer>> list = new ArrayList<>();
4.         Arrays.sort(nums);
6.         if (nums[nums.length - 1] < 0 && target > 0) {
7.             return list;
8.         }
10.         for (int i = 0; i < nums.length - 3; i++) {
11.             if (nums[i] > 0 && target <= 0) {
12.                 break;
13.             }
14.             if (i != 0) {
15.                 while (i < nums.length - 3 && nums[i] == nums[i - 1]) {
16.                     i++;
17.                 }
18.             }
19.             for (int j = i + 1; j < nums.length - 2; j++) {
20.                 if (j != i + 1) {
21.                     while (j < nums.length - 2 && nums[j] == nums[j - 1]) {
22.                         j++;
23.                     }
24.                 }
26.                 int left = j + 1;
27.                 int right = nums.length - 1;
28.                 while (left < right) {
29.                     long sum = nums[left] + nums[right] + nums[i] + nums[j];
30.                     if (sum > target) {
31.                         right--;
32.                     } else if (sum < target) {
33.                         left++;
34.                     } else {
35.                         list.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right])));
36.                         left++;
37.                         right--;
38.                         while (left < right && nums[left] == nums[left - 1]) {
39.                             left++;
40.                         }
41.                         while (left < right && nums[right] == nums[right + 1]) {
42.                             right--;
43.                         }
44.                     }
46.                 }
47.             }
48.         }
49.         return list;
50.     }
51. }

复制代码

看了讲解后:

• 去重操纵可以放在最后写
  

改子女码:

1. class Solution {
2.     public List<List<Integer>> fourSum(int[] nums, int target) {
3.         List<List<Integer>> list = new ArrayList<>();
4.         Arrays.sort(nums);
6.         if (nums[nums.length - 1] < 0 && target > 0) {
7.             return list;
8.         }
10.         for (int i = 0; i < nums.length - 3;) {
11.             if (nums[i] > 0 && target <= 0) {
12.                 break;
13.             }
14.             for (int j = i + 1; j < nums.length - 2;) {
15.                 int left = j + 1;
16.                 int right = nums.length - 1;
17.                 while (left < right) {
18.                     int sum = nums[left] + nums[right] + nums[i] + nums[j];
19.                     if (sum > target) {
20.                         right--;
21.                     } else if (sum < target) {
22.                         left++;
23.                     } else {
24.                         list.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right])));
25.                         left++;
26.                         right--;
27.                         while (left < right && nums[left] == nums[left - 1]) {
28.                             left++;
29.                         }
30.                         while (left < right && nums[right] == nums[right + 1]) {
31.                             right--;
32.                         }
33.                     }
35.                 }
36.                 j++;
37.                 while (j < nums.length - 2 && nums[j] == nums[j - 1]) {
38.                     j++;
39.                 }
40.             }
41.             i++;
42.             while (i < nums.length - 3 && nums[i] == nums[i - 1]) {
43.                 i++;
44.             }
45.         }
46.         return list;
47.     }
48. }

复制代码

总结

利用双指针:

• 一样平常是在数组中利用,通常需要对数组举行排序.
  
• 数据要有单调性.
  
• 利用双指针可以把时间复杂度降一维.O(n3)变O(n2);
  

本文到这里就竣事啦~

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。