题解 | #牛牛的AC#

思路

题目分析

1. 题目给出了一个只包含字符"A"和"C"的字符串，并且给出一个可修改"A"为"C"或改"C"为"A"的机会次数k
2. 我们需要利用k次的修改机会，获得一个最长的字符相同的子串，返回其最长长度

• 方法一：暴力统计
  • 我们将每一个字符变换的位置作为起点，进行一次从起点往后数长度的尝试，其中遇到与起点不同的字符则利用给出的k次机会，用完为止，统计一次长度。每一个起点都这样进行统计，最终获得最大的长度值
• 方法二：滑动窗口
  • 我们给定两个计数器a和c，分别记录我们遇到的"A"和"C"字符的次数
  • 滑动窗口右端指针r进行遍历，遇到对应的字符就在对应的计数器上累加
  • 当a和c均比k小时，我们知道a+c即目前访问到窗口右端的最长的长度值
  • 当a和c有一个比k小时，我们可以知道其中一个字符可以借助k次机会实现转换，a+c仍可以认为是目前访问到窗口右端的最长的长度值
  • 当a和c均比k大时，我们通过k次机会无法完成修正，此时需要滑动窗口左指针r开始移动，将一部分的字符退出窗口，并修改对应的计数器，直到退出到a和c计数器有一个小于等于k为止。此时a+c是目前窗口中的最长的长度值。
  • 最终结果返回一次记录a+c最长的一次值。

方法一：暴力统计

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param k int整型 
     * @param s string字符串 
     * @return int整型
     */
    int Solve(int k, string s) {
        // write code here
        int next = 0;
        int n = s.size();
        int mx = 0;
        while(next < n) {
            int flag = 0;            // 指导next指针指向当前发生字符不一致变化的第一个位置
            int step = k;            // 可以修改字符的次数
            char c = s[next];        // 从当前字符作为起点，并将其后的字符改成这个字符c
            int tempL = 0;           // 每一次以字符c为起点，尝试用k次修改可以得到的长度
            int i;                   // 从c字符开始的遍历指针
            for(i = next; step >= 0 && i < n; i++) {    // 每次i要从next指向的地方作为一轮修改起点
                tempL++;                                // 访问一个字符就更新一次长度
                if(c == s[i]) continue;                 // 如果字符一致，则只增加tempL长度即可
                if(flag == 0) next = i;                 // 如果字符不一致，则将next标记在第一次出现不一致的位置
                step--;                                 // 字符不一致相当于消耗了一次修改机会，step需要-1
                flag = 1;                               // 设置flag=1来限制next的标注行为
            }
            if(step == -1) tempL--;                     // step==-1则说明多修改了一次，因为我们在循环中允许step=0并且不修改字符，但是跳出循环的条件必须是多修改一次，因此这多的一次需要减回去
            mx = max(mx, tempL);                        // 统计mx值
            if(i == n) break;                           // 跳出外层while循环的标志
        }
        return mx;
    }
};

复杂度分析

• 时间复杂度：，经历了双重循环统计
• 空间复杂度：，没有额外空间申请

方法二：滑动窗口

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param k int整型 
     * @param s string字符串 
     * @return int整型
     */
    int Solve(int k, string s) {
        // write code here
        int n = s.size();
        int a = 0;                           // A字符计数器
        int c = 0;                           // C字符计数器
        int mx = 0;
        for(int l = 0, r = 0; r < n; r++) {  // 窗口右端增长
            if(s[r] == 'A') a++;             // 判断窗口右端的字符，增长对应计数器
            else c++;
            while(a > k && c > k){           // 超过k值调节能力范围，需要缩小窗口，窗口左端缩小
                if(s[l] == 'A') a--;         // 判断窗口左端的字符，缩小对应计数器
                else c--;
                l++;
            }
            mx = max(mx, a+c);               // 更新mx值
        }
        return mx;
    }
};

复杂度分析

• 时间复杂度：，一次遍历可以实现统计
• 空间复杂度：，没有额外空间申请