当前位置：首页 > article >正文

25.日常算法

article 2025/1/27 20:14:58

1.仅仅反转字母

题目来源
给你一个字符串 s ，根据下述规则反转字符串：
所有非英文字母保留在原有位置。
所有英文字母（小写或大写）位置反转。
返回反转后的 s 。

示例 1：
输入：s = “ab-cd”
输出：“dc-ba”

class Solution {
public:
    string reverseOnlyLetters(string s) {
        int left = 0, right = s.size();
        while (left < right){
            if (!isalpha(s[left])){
                ++left;
                continue;
            }
            if (!isalpha(s[right])){
                --right;
                continue;
            }
            swap(s[left++], s[right--]);
        }
        return s;
    }
};

2. LCR 017. 最小覆盖子串

给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 “” 。如果 s 中存在多个符合条件的子字符串，返回任意一个。
注意：对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
解释：最短子字符串 “BANC” 包含了字符串 t 的所有字符 ‘A’、‘B’、‘C’

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hash;
        for (auto & c : t) hash[c]++;
        int count = 0;
        int left = 0, right = 0;
        string ret = "";
        int minlen = INT_MAX;
        while (right < s.size()){
            if (hash[s[right]] > 0)count++;
            // s中所有的元素都进行--操作
            hash[s[right]]--;
            if (count == t.size()){
                // 只要找到符合条件的，就只需要找到下一个t中有的元素即可，只要hash中值小于0
                // 就说明了是t中没有元素，要么就是t中多有的元素直接跳过
                while (left <= right && (count == t.size() || hash[s[left]] < 0)){
                    // 更新值
                    if (count == t.size() && right - left + 1 < minlen){
                        ret = s.substr(left, right - left + 1);
                        minlen = right - left + 1;
                    }
                    if (hash[s[left]] == 0) count--;
                    hash[s[left]]++;
                    ++left;
                }
            }
            ++right;
        }
        return ret;
    }
};