剑指 Offer（专项突击版）第17|18题

站长

2023年03月18日 22:04 · 阅读数 40

前言

现在前端要求变高了,找工作的时可能会碰上算法题,每天刷几道算法题做足准备,今天是《剑指 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中的字符了，在指针移动的过程中，不断更新最小覆盖子串。

剑指 Offer（专项突击版）第17|18题

/**
 * @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

剑指 Offer（专项突击版）第17|18题

传送门

转载自:https://juejin.cn/post/7179146924333727801