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

leetcode每日一题day17(24.9.27)——每种字符最少取k个

article 2024/9/29 17:24:35

思路：看到题目就想到了搜索，

广搜：满足要求就往后搜，最后返回搜索队列达到过的最大深度，

深搜：一直往一边取，搜索完所有可能，并在此基础上进行剪枝，剪枝方案有如果某一分钟数(在dfs中则为深度)每种都拿满了k个就记录，后续如果有深度到达这个值还没完成就可以剪枝。

看到的别人的精妙构思：对于这种左右取值比较容易想到利用左右指针进行滑窗，但仔细想想就会发现，左右指针移动策略怎么设置都不对，此时其提出的“正难则反”的方案很一针见血，

找取k个难就找剩总数-k个的区间，这样问题就转换为了，找最长的连续的包含每个字符数量不多于总数-k个的区间，这样问题就变成了，清晰的，左右指针移动策略好设置的，滑窗问题

代码：

class Solution {
public:
    int takeCharacters(string s, int k) {
        int cut[3]{-k, -k, -k}, len = s.length(), res = 0;
        for (char i : s)
            cut[i - 'a']++;
        if (cut[0] < 0 || cut[1] < 0 || cut[2] < 0)
            return -1;
        if (cut[0] == 0 && cut[1] == 0 && cut[2] == 0) {
            return len;
        }
        int Left = 0, Right = 0;
        while (Right < len) {
            cut[s[Right++] - 'a']--;
            while (cut[0] < 0 || cut[1] < 0 || cut[2] < 0) {//某一刻不符合要求了，就移动左指针时左右指针夹的永远是，符合要求的区间，左闭右开(即左指针指向区间第一个，右指针指向区间最后一个的后一个)
                cut[s[Left++] - 'a']++;
            }
            res = max(res, Right - Left);
        }
        return len-res;//由于是反转问题，找到的窗口是原本答案的非(即相反区间)
    }
};

结语：核心的正难则反很精髓，下次在尝试滑窗时受阻可以尝试着再用此秘技

查看全文

http://www.kler.cn/news/324880.html