剑指 Offer（专项突击版）第15|16题
站长
· 阅读数 14
前言
- 现在前端要求变高了,找工作的时可能会碰上算法题,每天刷几道算法题做足准备,今天是《剑指 Offer（专项突击版）》第15|16题。
剑指 Offer II 015. 字符串中的所有变位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
变位词 指字母相同，但排列不同的字符串。
难度：中等
示例 1：
输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的变位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的变位词。
示例 2：
输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的变位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的变位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的变位词。
提示:
● 1 <= s.length, p.length <= 3 * 104
● s 和 p 仅包含小写字母
方法一：滑动窗口
分析：
首先统计p字符串字符出现次数，同时初始化s字符串哈希表（长度与p一致）。
模拟一个定长（p.length）的活动窗口，并统计两个哈希表中的字符是否一致。
每当在子字符串中添加一个字母，则把s哈希表中该字母对应的值加1；
每当从子字符串中删除一个字母，则把s哈希表中该字母对应的值减1。如果两个哈希表中的字符一致，那么由两个指针定位的子字符串是字符串p的一个变位词。把对应的下标添加到结果中。
/**
* @param {string} s
* @param {string} p
* @return {number[]}
*/
var findAnagrams = function(s, p) {
const sLen = s.length, pLen = p.length;
if(sLen < pLen) {
return [];
}
const ans = [];
const sCount = new Array(26).fill(0);
const pCount = new Array(26).fill(0);
for (let i = 0; i < pLen; ++i) {
sCount[s[i].charCodeAt() - 'a'.charCodeAt()]++;
pCount[p[i].charCodeAt() - 'a'.charCodeAt()]++;
}
if (sCount.toString() === pCount.toString()) {
ans.push(0);
}
for (let i = 0; i < sLen - pLen; ++i) {
sCount[s[i].charCodeAt() - 'a'.charCodeAt()]--;
sCount[s[i + pLen].charCodeAt() - 'a'.charCodeAt()]++;
if (sCount.toString() === pCount.toString()) {
ans.push(i + 1);
}
}
return ans;
};
复杂度分析
- 时间复杂度：O(m+(n−m)×Σ)，其中 n 为字符串 s 的长度，m 为字符串 p 的长度，Σ 为所有可能的字符数。需要 O(m) 来统计字符串 p 中每种字母的数量；需要 O(m) 来初始化滑动窗口；需要判断 n−m+1个滑动窗口中每种字母的数量是否与字符串 p 中每种字母的数量相同，每次判断需要 O(Σ) 。因为 s 和 p 仅包含小写字母，所以 Σ=26。
- 空间复杂度：O(Σ)。用于存储字符串 p 和滑动窗口中每种字母的数量。
方法二：优化滑动窗口
在方法一的基础上，我们不再分别统计滑动窗口和字符串 p 中每种字母的数量，而是统计滑动窗口和字符串 p 中每种字母数量的差；并引入变量 differ 来记录当前窗口与字符串 p 中数量不同的字母的个数，并在滑动窗口的过程中维护它。
在判断滑动窗口中每种字母的数量与字符串 pp 中每种字母的数量是否相同时，只需要判断 differ 是否为零即可。
var findAnagrams = function(s, p) {
const sLen = s.length, pLen = p.length;
if (sLen < pLen) {
return [];
}
const ans = [];
const count = Array(26).fill(0);
for (let i = 0; i < pLen; ++i) {
++count[s[i].charCodeAt() - 'a'.charCodeAt()];
--count[p[i].charCodeAt() - 'a'.charCodeAt()];
}
let differ = 0;
for (let j = 0; j < 26; ++j) {
if (count[j] !== 0) {
++differ;
}
}
if (differ === 0) {
ans.push(0);
}
for (let i = 0; i < sLen - pLen; ++i) {
if (count[s[i].charCodeAt() - 'a'.charCodeAt()] === 1) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
--differ;
} else if (count[s[i].charCodeAt() - 'a'.charCodeAt()] === 0) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
++differ;
}
--count[s[i].charCodeAt() - 'a'.charCodeAt()];
if (count[s[i + pLen].charCodeAt() - 'a'.charCodeAt()] === -1) { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
--differ;
} else if (count[s[i + pLen].charCodeAt() - 'a'.charCodeAt()] === 0) { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
++differ;
}
++count[s[i + pLen].charCodeAt() - 'a'.charCodeAt()];
if (differ === 0) {
ans.push(i + 1);
}
}
return ans;
};
复杂度分析
- 时间复杂度：O(n+m+Σ)。
- 空间复杂度：O(Σ)。
剑指 Offer II 016. 不含重复字符的最长子字符串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。
难度：中等
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子字符串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子字符串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = "" 输出: 0
提示：
● 0 <= s.length <= 5 * 104
● s 由英文字母、数字、符号和空格组成
方法一：滑动窗口
使用两个指针表示字符串中的某个子串（或窗口）的左右边界。
如果两个指针之间的子字符串不包含重复的字符，由于目标是找出最长的子字符串，因此可以向右移动第2个指针，在子字符串的最右边增加新的字符，然后判断新的字符在子字符串中有没有重复出现。
如果两个指针之间的子字符串中包含重复的字符，则可以向右移动第1个指针，删除子字符串中最左边的字符。
在字符串"babcca"中找不含重复字符的子字符串的过程如下图所示
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let left = 0, right = 0;
let res = 0; // 记录结果
let window = new Map();
while (right < s.length) {
let c = s[right];
right++;
// 进行窗口内数据的一系列更新
if (window.has(c)) {
window.set(c,window.get(c) + 1)
} else {
window.set(c,1)
}
// 判断左侧窗口是否要收缩
while (window.get(c) > 1) {
let d = s[left];
left++;
// 进行窗口内数据的一系列更新
window.set(d,window.get(d) - 1);
}
// 在这里更新答案
res = Math.max(res, right - left);
}
return res;
};
复杂度分析
- 时间复杂度：O(N)，其中 N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。
- 空间复杂度：O(Σ)，其中 Σ 表示字符集（即字符串中可以出现的字符），可以默认为所有 ASCII 码在 [0,128)内的字符，即 Σ=128。
so
