60天零基础干翻C++————双指针问题

移动零

题目链接：移动零

本题是典型的双指针算法中的数组划分类型：
以下面为例：
删除该数组所有的0.
下面引入两个指针：

这两个指针将区间分为了三段

初始如图 定义两个指针：

cur会有两种情况：

1. 遇到非零元素。
2. 遇到0元素。
   此时为cur第一种情况：我们需要将dest和cur直接的非零元素移动到dest之前。
   
   dest++后，和cur 互换。然后cur++，持续上述过程。当走到下图所示时
   
   cur指向0，则cur++，dest不变

此时进入cur指向非零元素，cur指向的元素需要移动到dest之前

持续此流程就可以完成。
下面打印出每次交换流程：

打印测试代码：

void Swap(int& a,int& b)
{
	int c = a;
	a = b;
	b = c;
}

void print(vector<int> x)
{
	for (int i = 0; i < x.size(); i++)
	{
		cout <<x.at(i)<<' ';
	}
	cout << endl;
}

void Movezeroes(vector<int>& k)
{
	print(k);
	int cur = 0;
	int dest = -1;

	for (cur = 0; cur < k.size(); cur++)
	{
		if (k[cur] != 0)
		{
			dest++;
			Swap(k[cur], k[dest]);
			print(k);
		}


	}
}


int main()
{
	vector<int> a;
	a.push_back(1);
	a.push_back(2);
	a.push_back(0);
	a.push_back(0);
	a.push_back(0);
	a.push_back(2);
	a.push_back(1);
	a.push_back(0);
	a.push_back(1);

	Movezeroes(a);
	

	return 0;



}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

复写0

题目链接： 复写0

复写0是典型的双指针算法。刚拿到题目可能被简单迷惑。本题如果从前往后会数据覆盖。从后往前的话双指针又指向哪里呢？我们看下面几个例子：

可以看出关键就是要找到复写之后的最后一个数。那么如何找出这个复写的数呢？
此时可以看出 可以将数组分成两个区间

可以看出当0越多，需要的复写空间越。那么我们可以用双指针 用tail统计需要留出多少空间

int head = 0;
	int tail = arr.size()-1;
	while(tail>head)
	{
		if (arr[head] == 0)
		{
			tail--;
			
		}
		++head;                                                 		
	}
1
2
3
4
5
6
7
8
9
10
11

复写占用空间相当于被抛弃的空间，所以遍历不在扫描。

此时的tail所指向的位置就是红色字，tail指向的位置有三种情况

1. tail指向0，该0不需要复写，因为后面空间不够。这是最特殊的情况。
2. tail指向0，需要复写。
3. tail指向非0.
   此时当tail指向0时，我们如何得知是否需要复写就需要单独讨论呢。
   
   我们发现，需要复写时head走到了tail后面。不需要复写时他们相等。这是什么原因呢

先分析第一种情况，tail和head不相等。

当head指向的0是离tail最近的一个时，此时分为两种情况：

1. tail和head指向同一个0；
2. head指向tail之前的0；
   
   因为复写占用的空间是在head和tail之间，所以可以通过tail-head是否为0判断 是否可以复写。显然第一种可以复写，第二种，复写空间为0，不能复写。所以当head和tail同时指向的0不能复写。这种情况我们提前处理，把0当成普通元素。

int cur = tail;
 	int dest = arr.size();

	if (head == tail && arr[cur] == 0 )
	{
		dest--;
		arr[dest] = arr[cur];
		cur--;
	}
1
2
3
4
5
6
7
8
9

后面就是简单的重后往前的复写操作了。

while (dest > 0)
	{
		
		if (arr[cur] == 0)
		{
			dest--;
			arr[dest] = 0;
			
		}
		dest--;
		arr[dest] = arr[cur];
		cur--;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13

快乐数

题目链接：快乐数

1. 根据第一条，我们需要得到余数 的平方和，这个是很容易的

int Add(int n)
{
	int  len = log10(n)+1;

	int sum = 0;
	int tmp = 0;
	for (int i = 1; i < len+1; i++)
	{
		
		tmp = n %10;
		
		sum = sum + tmp * tmp;
		n = n / 10;
	}

	
	return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2. 当出现1时 1单独成环。没有1时，其他数成环
我们只要验证，成环之时，有没有1即可
此处使用快慢指针。快指针走两步，慢指针走一步。在环内部，快慢指针一定会相遇。如果相遇是1，则环内只有1，相遇不是1，则环内一定没用1.因为1，是单独成环，

  bool isHappy(int n) {
int slow = 0;
	int fast = 0;
	slow = n;
	fast = Add(n);// 调用一次Add相当于走一步。
	while (slow != fast)
	{
		slow = Add(slow);
		fast = Add(Add(fast));
	}

	if (slow==1)// 如果等于1.则环内只有1.
	{
		return true;
	}

	return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

盛最多水的容器

题目链接：盛最多水的容器

v= len*wide。显然随着左右指针向中间靠拢，wide一直减少。决定v的只有len。而len由左右最小的数决定。
所以，随着wide的减小决定v的关键就是左右最小的数 len。所以在移动时也应该移动最小的，

图中可以看出，v随着wide变小，最终由min(left,right)决定。所以，最小的移动才能改变v，在wide减少的情况下

  int maxArea(vector<int>& height) {



  int head = 0;//left
    int tail = height.size() - 1;// right
    int high = 0;  // min（rigrht，left）
    int wide = 0;
    int v = 0;
    while (tail > head)
    {
        wide = tail - head;
        high = min(height[tail], height[head]);
        v = Max(wide * high, v);//记录体积最大的情况。
        if (height[tail] > height[head])
        {
            head++;
        }
        else
        {
            tail--;
        }
    }
    return v;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

有效三角形的个数

题目链接：有效三角形的个数

首选需要三个指针分别表示三条边的数值。为了让指针abc指向不重复，我们可以考虑将数组排序。排序有两个好处：

1. 只要让一个指针a指向最大值，那么只需要满足较小b c满足b+c>a.
2. abc 不会重复选择。
   画图说明各个情况 排序完成后
   

分为两大类情况

1. a+b>c 满足情况,此时调小a+b 左移b
   

2. a+b<=c 不满足 此时

1.调小a+b 2. 调小c

1. 调小a+b
   

2. 调小c
   
   注意事项：
   

int triangleNumber(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end());
int head=0;
int Maxtail=nums.size()-1;
int tail=nums.size()-2;
int num=0;
for(Maxtail;Maxtail>1;Maxtail--)
{
    head=0;
    tail=Maxtail-1;
    while(tail>head)
    {
        if(nums[tail]+nums[head]>nums[Maxtail])
        {
           num+=tail-head;
           tail--;
        }
        else
        {
            head++;
        }
    }
}
return num;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

两数之和

题目链接：两数之和

对于有序数组，本质还是谁有问题谁走