剑指 Offer（专项突击版）第17|18题
站长
· 阅读数 12
前言
- 现在前端要求变高了,找工作的时可能会碰上算法题,每天刷几道算法题做足准备,今天是《剑指 Offer（专项突击版）》第17|18题。
剑指 Offer II 017. 含有所有字符的最短字符串
给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。
如果 s 中存在多个符合条件的子字符串，返回任意一个。
注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
难度：困难
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'
示例 2：
输入：s = "a", t = "a" 输出："a"
示例 3：
输入：s = "a", t = "aa" 输出："" 解释：t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。
提示：
● 1 <= s.length, t.length <= 105
● s 和 t 由英文字母组成
方法一：滑动窗口
分析：
思路和16的思路相似。
使用两个指针表示字符串中的某个子串（或窗口）的左右边界。用左右两个指针遍历s字符串。
当滑动窗口中的字符不能覆盖t中的字符时，右指针右移，扩大窗口，把右边的字符加入滑动窗口；
当滑动窗口中的字符能覆盖t中的字符时，不断左移左指针，缩小窗口，直到窗口中的字符刚好能覆盖t中的字符，这个时候在左移就不能覆盖t中的字符了，在指针移动的过程中，不断更新最小覆盖子串。
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
//needs-需要覆盖的字符串频数 currentWindow-滑动窗口的字符串频数
const needs = {}, currentWindow = {};
for (let i = 0; i < t.length; ++i) {
needs[t[i]] = needs[t[i]] ? needs[t[i]] + 1 : 1;
}
// 左右指针 matches-滑动窗口中能覆盖的字符种类数
let left = 0, right = 0, matches = 0, res = s, isFound = false;
while (right < s.length) {
const c = s[right];
if(needs[c]) {
currentWindow[c] = currentWindow[c] ? currentWindow[c] + 1 : 1;
if (currentWindow[c] === needs[c]) {
++matches;
}
}
++right;
while (matches === Object.keys(needs).length) {
isFound = true;
res = (right - left) < res.length ? s.slice(left, right) : res;
const leftChar = s[left];
if (needs[leftChar]) {
currentWindow[leftChar] = currentWindow[leftChar] - 1;
if (currentWindow[leftChar] < needs[leftChar]) {
--matches;
}
}
++left;
}
}
return isFound ? res : '';
};
复杂度分析
- 时间复杂度：o(n)，n是s的长度
- 空间复杂度：o(t)，t是字符集的大小
剑指 Offer II 018. 有效的回文
给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。
本题中，将空字符串定义为有效的 回文串 。
难度：简单
示例 1:
输入: s = "A man, a plan, a canal: Panama" 输出: true 解释："amanaplanacanalpanama" 是回文串
示例 2:
输入: s = "race a car" 输出: false 解释："raceacar" 不是回文串
提示：
● 1 <= s.length <= 2 * 105
● 字符串 s 由 ASCII 字符组成
方法一：双指针
分析： 判断一个字符串是不是回文，常用的方法就是使用双指针。
可以定义两个指针，一个指针从第1个字符开始从前向后移动，另一个指针从最后一个字符开始从后向前移动。
如果两个指针指向的字符相同，则同时移动这两个指针以判断它们指向的下一个字符是否相同。这样一直移动下去，直到两个指针相遇。
由于题目要求只考虑字母和数字字符，并忽略大小写，因此先对字符串做处理。
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function(s) {
// 先用正则表达式处理字符串
s = s.replace(/[^a-zA-Z0-9]/g,"").replace(/\s/g,"").toLowerCase();
let i = 0,j = s.length-1;
while(i < j){
if(s[i] != s[j]){
return false;
}
i++;
j--;
}
return true;
};
复杂度分析
- 时间复杂度：O(∣s∣)，其中 ∣s∣ 是字符串 s 的长度。
- 空间复杂度：O(∣s∣)。由于需要将所有的字母和数字字符存放在另一个字符串中，在最坏情况下，新的字符串 s 与原字符串 s 完全相同，因此需要使用 O(∣s∣) 的空间。
so
