本帖最后由 michael_llh 于 2016-12-26 16:51 编辑
今天我们简单介绍一个算法中常用的一个技巧，不算是算法题的分享，但是我们也归类到这里和大家分享。
Two Pointer 双指针技术，那么这个是什么意思呢？ 首先我们需要明白一点，快慢指针一般是用在数组或者是字符串中，我们定义了两个指针，其中一个指针指向这个数组或者字符串的开头，另外一个指针指向这个数组或者字符串的末尾，构成双指针。
OK，明白了概念，那么我们看下它的简单应用。
Problem： 给定给一个字符串数组，反转这个数组并输出。
题意很简单，很好理解，那么我们看下没有利用双指针和利用双指针来实现的俄两种方式。
（实现语言：C++） <font size="4" face="Helvetica">#include <iostream>
using namespace std;
#include <cstring>
void swap(char str[], int i, int j){
char temp;
temp = str[i];
str[i] = str[j];
str[j] = temp;
}
int main()
{
char s[20] = "1 2 3 4 5 6 7 8 9";
cout << "===== with no two pointer method reverse =====" << endl;
int n = strlen(s);
for (int i = 0; i < n / 2; i++) {
swap(s, i, n - i - 1);
}
cout << s << endl;
cout << "===== with two pointer method reverse =====" << endl;
int i = 0, j = strlen(s)-1;
while (i < j) {
swap(s, i, j);
i++;
j--;
}
cout << s << endl;
}</font>
这里要注意一个问题，strlen函数得到的是字符串的长度，但是我们对于数组而言我们的计数是从0开始的，所以要注意减去1。如果使用的是C++的string类型，直接使用str.length，同样也要减去1.
对于双指针的应用我们还可以引申出很多，比如说排序好的数组进行折半查找，另外比如快慢指针也是双指针，可以用来判断单链表是否有环，以及它的入口点在哪里，同时还可以用来找有序链表的中位数。很多应用，后面有机会再进行延展。
| 
楼主
标题置顶
标题高亮
