欢迎光临散文网 会员登陆 & 注册

424. 替换后的最长重复字符 | 滑动窗口题型

2020-04-21 11:28 作者:有木乘舟  | 我要投稿

分析:这题求的是重复字符的最长连续子串。我们先将题目拆解成两个部分:

  • 当k=0时,求重复字符的最长连续子串

  • 当0<k<10^4时,替换窗口中k个字符,使子串保持连续重复

当k=0时,这题可转化为简单的求重复字符的最长连续子串,窗口的长度就是我们需要求出来的答案。针对这一问题,我们可以将窗口问题转化为两个判断依据:

  • 当右指针指向的字符与当前窗口内的子串字符相同时,向右扩充窗口(将右指针字符添加进窗口,窗口大小+1)

  • 否则,向右平移窗口(移除窗口最左边字符,左指针+1,窗口大小不变)

图片来自@migoo

  具体的实现中,当right指向的字符是非重复字符时,我们可以直接将窗口移动到当前字符right这个位置,然后重新开始计算字符长度。

  要注意理解,滑动窗口题型中的哈希表存储的信息,我们知道滑动窗口的本质是动态规划思想,也就是使用额外的空间存储重复的信息,利用空间换时间的方式来降低时间复杂度,因此哈希表存储的信息十分关键。

  在这个问题中,哈希表里存储的是当前窗口中重复字符的个数。

  当 0<k<10^4 时,我们可以通过将窗口中的k个字符进行替换,来使窗口中的子串均为重复字符。

  因此判断条件变成了:如果当前窗口中出现次数最多的字符个数+K大于当前子串长度,意味着子串还可以增加,因此进行窗口扩充操作(left不变,right++);反之,将窗口向右平移(left++,right++,并将left对应的字符移除)。

  另一和424相似的题,这一题仅仅只是把任意字符换成了 0,1数字,其他条件不变。

  我们只需要将计算窗口中的数量最多的字符换成计算窗口中的1的数量即可


424. 替换后的最长重复字符 | 滑动窗口题型的评论 (共 条)

分享到微博请遵守国家法律