滑动窗口算法(C语言版讲解)

2024-02-27 00:12| 来源: 网络整理| 查看: 265

滑动窗口算法（C语言讲解）

滑动窗口算法主要用于解决字符串查找对应排序的题型。

算法的基本思路

1.辅助算法 :快慢指针

由于要运用快慢指针的思想，这里读者需要先了解快慢指针。

typedef struct node{ int data; struct node *next; }Node; //设head为已创建好的线性链表,k为快指针, m为慢指针; Node * head, *k, *m; void OutLink(Node *head) { Node *k, *m; k = head->next->next;//每次走两个next; m = head->next;//每次走一个next; }

因快慢指针的特性，我们常常可以用它来判断链表是否存在环。

如果能够理解快慢指针那今天的这个算法你也就解决了。

2.主算法 :滑动窗口

滑动窗口顾名思义就是以窗口的形式进行移动查找。

先看题目: 输入字符串S,请从S查找到最长无重复字母的子串的长度。(例：S = "abcdbgf", 输出 : 4)

如果使用暴力算法的话时间复杂度为O(N^2),显然效率很慢。

由于是查找最值所以我们需要对字符串进行遍历查找,在遍历循环的过程我们需要两个指针right，left，将right,keft初始化为0。(注：此指针并非C语言的指针,该指针表示字符数组的下标指针)，通过指针right我们可以遍历查找到最长对应要求的子串长度(遍历到存在重复字母种类为止),如果运气好在right的后续遍历中不存在更优的子串那它就是最终答案，运气不好的话后续的遍历可能就存在更优的子串，为了保证找到最长的子串我们还需要对剩下的字符串进行遍历查找，看是否能找出跟优的子串，这时需要left去遍历S(左窗体的右移)，遍历到遇到重复字母的下标为止(跳过找到的子串，向后遍历)，以此循环直到right遍历完S字符串。

解决函数如下:

首先需要定义结构体Map用于记录26个字母各自出现的个数 typedef struct{ char key;//字母 int count;//出现个数 }Map; 还需要对结构体数组进行初始化 void InitMap(Map *Window) { char ch; int i, count = 0; for(i='a';i

【本文地址】

滑动窗口算法(C语言版讲解)

滑动窗口算法(C语言版讲解)

今日新闻

推荐新闻