题解 | #编程题2#

编程题2

http://www.nowcoder.com/practice/dcc301bc11a7420b88afdbd272299809

贪心算法,按照题目的描述 增加一个修正策略 然后滑动

#include <iostream>
// 滑动窗口 贪心
using namespace std;

int getMax(string &s, int m, char target) {
    int left = 0, right = 0;
    int result = 0, index = 0;
    int n = s.size();

    while (right < n) {
        if (s[right] == target) {
            right++;
        } else {
            index++;
            right++;
            // 这里因为用了一次修正所以 right往后移动一次
            while (index > m) {
                // 超过修正次数了
                if(s[left] != target) {
                    index--;
                }
                left++;
            }
        }
        
        result = max(result, right - left);            
    }
    
    return result;
}

int main() {
    int n, m;
    string str;
    cin >> n >> m;
    cin >> str;
    
    if (m >= n) {
        cout << n << endl;
    } else {
        cout << max(getMax(str, m, 'a'), getMax(str, m, 'b')) << endl;
    }
    
    return 0;
}
全部评论

相关推荐

07-09 19:25
门头沟学院 Java
这是要把每一个投校招的都开盒吗?
26届之耻将大局逆转:裁人的时候一次性追回餐费
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务