C++中的二分法和双指针法及常见题目汇总
1. 二分法
二分查找也属于顺序表查找范围，二分查找也叫做折半查找，二分查找的时间效率为(logN)
二分查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功，如果给定值小于中间值，则查找数组的前半段，否则查找数组的后半段。
二分查找只适用于有序数组或者链表
二分法常见题目汇总
一、剑指offer
二、leecode
2. 双指针法
双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同的方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。
换言之，双指针法充分使用了数组有序这一特征，从而在某些情况下能简化一些运算。
1. 双指针法题目分析
- 面试题22: 链表中倒数第k个节点
- 删除链表中的额倒数第N个结点
- 面试题56： 删除链表中的重复节点
- 删除排序数组中的重复项
- 删除排序数组中的重复项2
- 27.移除元素
- 移动零
- 面试题5：替换空格
- 面试题61：扑克牌顺子
- 面试题02.02:返回倒数第k个节点
- 面试题10.01:合并排序的数组
- 面试题25： 合并两个排序的链表
- 比较含退格的字符
- 和为S的两数之和
- 和为S的连续正整数序列
- 三数之和
- 最接近的三数之和
- 四数之和
- 盛水最多的容器
- 链表中环的入口节点
- 旋转链表
- 回文链表
- 问题分析，由于每一行从左到右递增，每一列从上到下递增，因此我们可以考虑左下角元素，从左到右递增，从下到上递减
若需要查找的元素target等于左下角元素，则查找到，若target小于左下角元素，向上移动，若target大于左下角元素，则向右移动
- 代码参考
1 class Solution {
2 public:
3 bool Find(int target, vector<vector<int> > array) {
4 if(array.empty())
5 return 0;
6 int rows=array.size()-1;
7 int cols=0;
8 while(rows>=0&&cols<array[0].size())
9 {
10 if(target>array[rows][cols])
11 ++cols;
12 else if(target<array[rows][cols])
13 --rows;
14 else
15 return true;
16 }
17 return false;
18 }
19 };
- 问题分析
首先要搞定出旋转数组的定义，其是将一个非递减排序的数组的一个旋转，因此，旋转数组是由两个递增的子数组组成，并且第一个子数组中的元素都比第二个子数组中元素大。因此，旋转数组的最小数字一定是第二个递增子数组的头元素。因此寻找旋转数组的最小数字的方法如下：
首先设置三个指针，first指向数组头，mid指向数组中间，last指向数组尾
如果mid>first,则mid在第一个递增的子数组中，最小值在数组的后半部分
如果mid<last，则mid在第二个递增的子数组中，最小值在数组的前半部分
- 参考代码
1 class Solution {
2 public:
3 int minNumberInRotateArray(vector<int> rotateArray) {
4 int first=0;
5 int last=rotateArray.size()-1;
6 int mid=first;
7 while(rotateArray[first]>=rotateArray[last])
8 {
9 if(last-first==1)
10 {
11 mid=last;
12 break;
13 }
14 else
15 {
16 int mid=(first+last)/2;
17 if(rotateArray[first]<=rotateArray[mid])
18 first=mid;
19 else if(rotateArray[last]>=rotateArray[mid])
20 last=mid;
21 }
22 }
23 return rotateArray[mid];
24 }
25 };
- 问题分析
为了统计数字在排序数组中出现的次数，我们可利用二分法，找到第一个出现的k，再找到最后一个出现的k，即可以实现统计数字在排序数组中出现的次数
为了找到第一次出现的k，三个指针，一个指针指向数组头，一个指针指向数组尾，一个指针指向中间。如果中间指针指向的数字等于要查找的k，则判断中间指针的前一个数字是否是k,如果不是k，则找到第一个出现的k，如果是k，则第一个出现的k 在数组的前半部分。如果中间指针指向的数字小于k，则k在数组的后半部分，如果中间指针指向的数字大于k，则k在数组的前半部分
为了找到最后一次出现的k，方法是类似的，不同之处在于，如果中间指针等于k，则判断中间指针的后一个数字是否为k，如果不是k，则找到最后一个k出现的位置，否则，最后一个k出现的位置在数组的后半部分
- 参考代码
1 class Solution {
2 public:
3 //找到第一个出现的k，如果mid==k,则判断mid-1是否为k，如果为k，则第一个出现的k在数组的前半部分
4 //如果不为k，则找到第一个出现的K的位置
5 //如果mid<k，则k在数组的后半部分
6 //如果mid>k，则k在数组的前半部分
7 int getFirstk(vector<int>&data,int k,int begin,int end)
8 {
9 int mid=(begin+end)/2;
10 if(begin>end)
11 return -1;
12 else
13 {
14 mid=(begin+end)/2;
15 if(data[mid]==k)
16 {
17 if(mid==0||(mid>0&&data[mid-1]!=k))
18 return mid;
19 else
20 end=mid-1;
21 }
22 else if(data[mid]>k)
23 end=mid-1;
24 else
25 begin=mid+1;
26 return getFirstk(data,k,begin,end);
27 }
28 }
29 //找到最后一个k出现的位置
30 int getLastk(vector<int>&data,int k,int begin,int end)
31 {
32 int mid;
33 int len=data.size();
34 if(begin>end)
35 return -1;
36 else
37 {
38 mid=(begin+end)/2;
39 if(data[mid]==k)
40 {
41 if((data[mid+1]!=k&&mid<len-1)||mid==len-1)
42 return mid;
43 else
44 begin=mid+1;
45 }
46 else if(data[mid]>k)
47 end=mid-1;
48 else
49 begin=mid+1;
50 return getLastk(data,k,begin,end);
51 }
52 }
53 int GetNumberOfK(vector<int> data ,int k) {
54 if(data.empty())
55 return 0;
56 int first=0;
57 int last=data.size()-1;
58 int firstk=getFirstk(data,k,first,last);
59 int lastk=getLastk(data,k,first,last);
60 int number=0;
61 if(firstk>-1&&lastk>-1)
62 number=lastk-firstk+1;
63 return number;
64 }
65 };
二、leecode刷题
- 问题分析
这道题和前面二维数组的查找是有类似的地方的，二维矩阵从左到右非递增，从上到下非递增，对于左下角元素，从左到右递减，从下到上递增，从左下角元素开始进行扫描，如果当前元素为正，则当前元素以上的元素都比其大，因此都为正，因此向右查找；如果当前元素为负，则从当前元素开始的每一个元素都为负，统计负数的个数并且向上一排寻找
- 代码参考
1 class Solution {
2 public:
3 int countNegatives(vector<vector<int>>& grid) {
4 if(grid.empty())
5 return 0;
6 int row=grid.size()-1;
7 int col=0;
8 int number=0;
9 int rows=grid.size();
10 int cols=grid[0].size();
11 while(row>=0&&col<grid[0].size())
12 {
13 if(grid[row][col]>=0)
14 {
15 ++col;
16 continue;
17 }
18 else
19 {
20 number+=cols-col;
21 --row;
22 }
23
24 }
25 return number;
26 }
27 };
- 题目分析
要寻找比目标字母大的最小字母，采用二分法。
1. 对下标作二分，找到第一个大于target值的下标
2. target可能比letters中的所有元素都小，也可能比letters中的所有元素都大，因此第一个大于target值的下标取值范围为[0,letters.size()]
3. 当left==right时退出，因此循环条件为while(left<right)
4. 当letters[mid]>target，mid可能是结果，因此在数组的前半部分寻找
5. 当letters[mid]<=target，mid不可能是结果，直接舍弃，因此在数组的后半部分寻找
6. 当循环退出时,left==right，若target大于letters中的所有元素，left=letters.size()，此时返回letters[0]
- 参考代码
1 class Solution {
2 public:
3 char nextGreatestLetter(vector<char>& letters, char target) {
4 int left=0;
5 int right=letters.size();
6 while(left<right)
7 {
8 int mid=(left+right)/2;
9 //如果letters[mid]>target，mid是可能结果，在数组的前半部分
10 if(letters[mid]>target)
11 right=mid;
12 //如果letters[mid]<=target，mid不可能是结果，舍去，在数组后半部分
13 else
14 left=mid+1;
15 }
16 //如果target大于数组中的所有元素时，left==letters.size(),返回letters[0]
17 if(left==letters.size())
18 return letters[0];
19 else
20 return letters[left];
21 }
22 };
- 题目分析
对于这道题目，刚开始看到的时候会思考使用暴力法，从头到尾进行求解。但是这样做的时间效率很低，为O(n)，因此尝试找其他新的方法
除了暴力法外，由于其是有序整数数组，因此我们可以思考使用二分法进行求解。
两个指针，一个指针位于数组头，一个指针位于数组尾。
如果nums[mid]==mid，则判断其是否是最小的
如果nums[mid]!=mid,则先判断左边是否有满足条件的。如果左边没有满足条件的，再判断右边是否有满足条件的。
- 参考代码
1 class Solution {
2 public:
3 int findMagicIndex(vector<int>& nums) {
4 if(nums.empty())
5 return -1;
6 return findMinMagicIndex(nums,0,nums.size()-1);
7 }
8 int findMinMagicIndex(vector<int>&nums,int left,int right)
9 {
10 int t;
11 if(left==right)
12 {
13 if(nums[left]==left)
14 return left;
15 else
16 return -1;
17 }
18 int mid=(left+right)/2;
19 if(nums[mid]==mid)
20 {
21 t=findMinMagicIndex(nums,left,mid);
22 return (t==-1)?mid:t;
23 }
24 else
25 {
26 //先从左边找，没有再从右边找
27 int t=findMinMagicIndex(nums,left,mid);
28 if(t!=-1)
29 return t;
30 else
31 return findMinMagicIndex(nums,mid+1,right);
32 }
33 }
34 };
- 题目分析
其是这是一个二分类问题，即需要找到[1,n]中的某个数，以实现这个数之前的所有和叠加小于等于n
即在一个等差数列中，找到一个位置，这个位置之前的所有元素加起来小于等于n
两个指针，一个指向数组头，一个指向数组尾，mid=l+(r-l)/2，而不写成mid=(l+r)/2的原因是:l+r可能造成溢出
cursum=mid*(mid+1)/2，
如果cursum<n，则要查找的位置在mid后面
如果cursum==n，则要查找的位置在mid处
如果cursum>n，则要查找的位置在mid后面
- 代码参考
1 class Solution {
2 public:
3 int arrangeCoins(int n) {
4 if(n<=0)
5 return 0;
6 int l=1,r=n;
7 while(l<=r)
8 {
9 long mid=l+(r-l)/2;//写成mid=(l+r)/2可能存在溢出的问题
10 long cur=mid*(mid+1)/2;
11 if(cur<n)
12 l=mid+1;
13 else if(cur==n)
14 return mid;
15 else
16 r=mid-1;
17 }
18 return l-1;
19 }
20 };
- 题目分析
首先需要保证houses和heaters都是升序的
对于每一个房子左边的暖气，记录他使其成为下一个房子左边最开始计算的暖气
对于每一个房子右边的暖气，则其为最后一个需要计算的暖气
依次为标准滑动遍历房子和暖气
- 参考代码
1 class Solution {
2 public:
3 int findRadius(vector<int>& houses, vector<int>& heaters) {
4 //首先要保证houses和heaters都是升序排列的
5 sort(houses.begin(),houses.end());
6 sort(heaters.begin(),heaters.end());
7 int ans=0;
8 int k=0;
9 for(int i=0;i<houses.size();++i)
10 {
11 int radis=INT_MAX;//先设置到最大：整型下限
12 for(int j=k;j<heaters.size();++j)
13 {
14 //如果其是左边的加热器，则记录器成为下一个房子开始的暖气
15 k=(houses[i]>=heaters[j])?j:k;
16 radis=min(radis,abs(houses[i]-heaters[j]));
17 if(houses[i]<heaters[j])
18 break;
19
20 }
21 //ans记录最大半径
22 ans=max(ans,radis);
23 }
24 return ans;
25 }
26 };
- 题目分析
由题意，版本号在某个之后全部错误，这相当于是一个排序的数组，因此我们采用二分法
两个指针，一个指针begin指向数组头，一个指针end指向数组尾，一个指针mid=begin+(end-begin)/2
如果mid指向数组是true,则错误版本在数组的后半部分
如果mid指向的数组是false，则判断其是否是第一个出现的，如果是第一个出现的，直接返回mid，否则第一个出现错误的位置在数组的前半部分
- 参考代码
1 // The API isBadVersion is defined for you.
2 // bool isBadVersion(int version);
3
4 class Solution {
5 public:
6 int firstBadVersion(int n) {
7 if(n<=0)
8 return 0;
9 int begin=1;
10 int end=n;
11 int mid;
12 int flag=0;
13 while(begin<=end)
14 {
15 mid=begin+(end-begin)/2;
16 if(!isBadVersion(mid))
17 begin=mid+1;
18 else
19 {
20 if(!isBadVersion(mid-1))
21 {
22 flag=mid;
23 break;
24 }
25
26 else
27 end=mid;
28 }
29 }
30 return flag;
31 }
32 };
- 题目分析
很明显这是一个二分查找问题，对于这类问题，我们最主要的就是要知道移动的方向以及返回的条件，我们使用一个实际例子来进行说
- 参考代码
1 class Solution {
2 public:
3 int peakIndexInMountainArray(vector<int>& A) {
4 if(A.empty())
5 return 0;
6 int begin=0;
7 int end=A.size()-1;
8 int mid;
9 while(begin<=end)
10 {
11 mid=begin+(end-begin)/2;
12 if(A[mid]>A[mid-1]&&A[mid]>A[mid+1])
13 return mid;
14 else if(A[mid-1]<A[mid]&&A[mid]<A[mid+1])
15 begin=mid+1;
16 else
17 end=mid-1;
18 }
19 return 0;
20 }
21 };
- 问题分析
其实这本质上是一个二分部查找的搜索问题，只是他是稀疏的，就要排除左边界是空字符串，右边界是空字符串以及mid是空字符串的问题
- 代码参考
1 class Solution {
2 public:
3 int findString(vector<string>& words, string s) {
4 if(words.empty())
5 return -1;
6 int begin=0;
7 int end=words.size()-1;
8 int mid;
9 while(begin<=end)
10 {
11 if(words[begin].size()==0)
12 {
13 ++begin;
14 continue;
15 }
16 if(words[end].size()==0)
17 {
18 --end;
19 continue;
20 }
21 mid=begin+(end-begin)/2;
22 while(words[mid].size()==0)
23 ++mid;
24 if(words[mid]==s)
25 return mid;
26 else if(words[mid]<s)
27 begin=mid+1;
28 else
29 end=mid-1;
30 }
31 return -1;
32 }
33 };
2. 双指针法题目分析
一、剑指offer
- 问题分析
要找到链表中的倒数第k个元素，我们可以采用双指针法，两个指针p,q刚开始都位于链表头，一个指针p先向前走k步，此时指针p,q相差k步，然后同时移动指针p,q，当指针p到达链表尾的时候，指针q到达链表的倒数第k个节点
- 代码参考
1 /**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode(int x) : val(x), next(NULL) {}
7 * };
8 */
9 class Solution {
10 public:
11 ListNode* getKthFromEnd(ListNode* head, int k) {
12 if(head==nullptr)
13 return nullptr;
14 ListNode* p=head;
15 ListNode* q=head;
16 int i=0;
17 while(p!=nullptr)
18 {
19 if(i<k)
20 {
21 p=p->next;
22 ++i;
23 }
24 else
25 {
26 p=p->next;
27 q=q->next;
28 }
29 }
30 return i<k?nullptr:q;
31 }
32 };
- 题目分析
这道题解法其是和找到链表中的倒数第N个结点相似，思路都是使用双指针，一个指针先向前走N步，此时两个指针间隔我们需要的数值，当一个指针到达链表尾的时候，另一个指针到达倒数第N点。
但是删除链表中的倒数第N个结点面临的一个挑战就是，当其到达倒数第N个结点时，要将倒数第N个结点删除，我们就需要找到倒数第N个结点的前一个节点，然后将前一个节点的next指针指向倒数第N个结点的下一个结点。
因此刚开始可以思考直接指向其倒数第N+1个结点，然后将N+1节点的next指针指向next->next指针，但是这样会出现的一个问题就是，若要倒数第N个结点刚好是头结点，这种删除方式就会出错。
因此我们引入了哑节点：哑节点是链表中的一个概念，哑节点是在一个链表的前边添加一个节点，存放的位置是在数据节点之前，头节点之后。好处是加入哑节点止呕可以使所有数据节点都有前驱节点，这样会方便执行链表的操作，看到一篇文章讲有无哑节点的区别，可以参考这个博客https://blog.****.net/muclenerd/article/details/42008855
- 参考代码
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode* removeNthFromEnd(ListNode* head, int n) { 12 if(head==nullptr) 13 return nullptr; 14 ListNode* dummy=new ListNode(0); 15 dummy->next=head; 16 int i=0; 17 ListNode* p=dummy; 18 ListNode* q=dummy; 19 for(int i=0;i<n;++i) 20 { 21 p=p->next; 22 } 23 while(p->next!=nullptr) 24 { 25 p=p->next; 26 q=q->next; 27 } 28 q->next=q->next->next; 29 ListNode* res=dummy->next; 30 delete dummy; 31 return res; } 32 };
- 题目分析
假设有链表如上图所示，我们可以采用双指针来实现删除链表中的重复节点，一个指针指向pHead,一个指针next指向pHead->next
如果pHead->val==next->val,则移动next,否则则又开始递归
- 代码参考
1 /* 2 struct ListNode { 3 int val; 4 struct ListNode *next; 5 ListNode(int x) : 6 val(x), next(NULL) { 7 } 8 }; 9 */ 10 class Solution { 11 public: 12 ListNode* deleteDuplication(ListNode* pHead) 13 { 14 if(pHead==nullptr||pHead->next==nullptr) 15 return pHead; 16 ListNode* next=pHead->next; 17 if(pHead->val==next->val) 18 { 19 while(next&&pHead->val==next->val) 20 next=next->next; 21 return deleteDuplication(next); 22 } 23 else 24 { 25 pHead->next=deleteDuplication(pHead->next); 26 return pHead; 27 } 28 } 29 };
- 思路分析
要实现替换空格，由于替换空格前后字符串的长度会发生变化，因此替换空格后的字符串长度等于原始字符串长度+2*空格数，因此我们从字符串的后面开始复制和替换，首先准备两个指针，p1和p2，p1指向原始字符串的末尾，p2指向替换之后字符串的末尾，如果没有空格，则依次进行复制，碰到空格时，新的字符串依次复制入‘0’，‘2’，‘%’
- 代码参考
1 class Solution { 2 public: 3 // 替换空格后，字符串长度会发生变化，原始字符串长度为originallen, 4 /* 5 newlen=originallen+2*space 6 */ 7 void replaceSpace(char *str,int length) { 8 if(str==nullptr) 9 return; 10 //首先计算原始长度和空格的长度 11 int originallen=0; 12 int space=0; 13 int i=0; 14 while(str[i]!='