双指针与滑动数组算法总结

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了双指针与滑动数组算法总结，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2339字，纯文字阅读大概需要4分钟。

内容图文

#双指针分类

**1.左右指针
例题：反转链表

class Solution {
public:
ListNode* reverseList(ListNode* head) {
//三个指针分别表示前一个节点，当前节点和下一个节点
ListNode *pre=NULL;
ListNode *cur=head;
ListNode* next；
while(cur)
{
next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}
return pre;
}
};

2.对撞指针（解决有序数组的数字之和或反转数组之类的可以两边开工的问题）
模板：指定指针初始位置，设置指针移动方法，给定结束条件。
例题：反转数组

class Solution {
public:
    void reverse(int []nums){
        int left=0;
        int right=nums.length()-1;
        while(left<right){
          int temp=nums[left];
          nums[left]=nums[right];
          nums[right]=temp;
          }
      }
};

3.快慢指针（两个指针移动速度不一样）**

解决问题：移除元素;判断链表是否含有环;已知链表有环，返回环的起始位置;寻找链表中点;寻找链表倒数第k个元素;

模板：
1.初始位置：慢指针指向第一个元素位置，快指针指向下一个元素位置
2.移动方法：慢指针步数加一，快指针步数加二（反正两个指针的速度要不同）
3.结束条件：两指针重合或快指针先到达终点。

例题：
环形链表

class Solution {

public:

bool CycleList(ListNode *head) {

if(head==NULL)
return false;
//快慢指针,两指针都先指向头结点

ListNode* L=head;

ListNode* R=head;

while(R!=NULL&&R->next!=NULL)

{

L=L->next;//走1步

R=R->next->next;//走两步
//当慢指针遇到快指针时，说明链表存在环
if(L==R)return true;

}

return false;

}

};

滑动窗口

原理：将双层循环变为单层变量循环问题，使两个指针一左一右构成一个窗口.

解决问题：数组，字符串的子元素，字串的问题，例如找到满足xx的最x的区间的xx ，满足查找一定条件的连线区间的性质

模板：初始化left=-1,right=0;[left,right]称为一个窗口
指针移动方法：不断增加right，直到窗口字符串符合要求，停止增加right，增加left缩减窗口直到不符合要求

例题：
最长回文字符串
所谓回文字串，就是一个字符串从左往右读和从右往左读是完全一样的，例如：“a”,“aba”,"abcddcba"是回文字符串，"dffgd"则不是。

本题采用中心扩展的方法，即把给定的字符串的每一个字母当做中心，向两边扩展，但要考虑奇数和偶数。

string findLongestPalindrome(string &s)
{
	const int length=s.size();
	int maxlength=0;
	int start;
 
	for(int i=0;i<length;i++)//长度为奇数
	{
		int j=i-1,k=i+1;
		while(j>=0&&k<length&&s.at(j)==s.at(k))
		{
			if(k-j+1>maxlength)
			{
				maxlength=k-j+1;
				start=j;
			}
			//向两边扩散,j和k包含的元素构成一个滑动窗口，依次扩大窗口
			j--;
			k++;
		}
	}
 
	for(int i=0;i<length;i++)//长度为偶数
	{
		int j=i,k=i+1;
		while(j>=0&&k<length&&s.at(j)==s.at(k))
		{
			if(k-j+1>maxlength)
			{
				maxlength=k-j+1;
				start=j;
			}
			j--;
			k++;
		}
	}
	if(maxlength>0)
		return s.substr(start,maxlength);
	return NULL;
}

内容总结

以上是互联网集市为您收集整理的双指针与滑动数组算法总结全部内容，希望文章能够帮你解决双指针与滑动数组算法总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---