一
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
分析
要想找到不含重复的字串,首先从头开始遍历字符串,用一个hash表存下已经被遍历过的字符的数量,因为时没有重复字符的字串,所以hash表字符数量应当不大于1。所以在往前遍历的时候,如果出现了一个字符数量大于1了,就说明他之前已经被遍历过了,为了保证这个字符的唯一,我们从前往后遍历,直到删去一个字符使得它出现的次数为1.我们就可以定义两个指针,一个在前,一个在后,他们框定了一个范围,就是一个滑动窗口
1 | queue<int> q; |
二
给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false 。
换句话说,s1 的排列之一是 s2 的 子串 。
分析
按照s1的大小在s2中框定一个子串,然后在对比s1和字串是否相同,这点很容易想到,但是又因为题目考察的是排列,我们不可能针对每一种情况下去对子串进行全排列,所以我们考察的对象就只能是在这个字串中字符出现的次数和s1是否相同。
继续优化我们的思路,既然是滑动窗口,不妨进一个字符就统计这个字符的数量,如果这个字符相比s1多了,就让左边界往右收缩,直到这个滑动窗口里面的该字符不大于s1里面的字符。当左右边界的长度刚好等于s1的长度时,就说明找到了一个字串。
滑块里面不可能有其他的字符,因为它的标准数量是零。我们考察的标准是字符的数量,所以和排列顺序没有关系。
1 | vector<int> cnt1(27); |
本文作者: jiangyuhao
本文链接: http://example.com/2022/03/27/%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!