java - 使最长字符间隔等于 K 所需的最少操作

Question

我在一次比赛中被问到这个问题。给定一个仅包含 M 和 L 的字符串，我们可以将任何“M”更改为“L”或将任何“L”更改为“M”。此函数的目标是计算我们必须进行的最小更改次数，以实现所需的最长 M 间隔长度 K。
例如，给定S = "MLMMLLM"，K = 3，函数应该返回1。我们可以改变位置4(从0开始)的字母，得到"MLMMMLM"，其中字母"M"的最长间隔为恰好三个字符长。

再比如，给定S = "MLMMMLMMMM"和K = 2，函数应该返回2。我们可以，比如修改2和7位置的字母，得到字符串"MLMMMLMLMM"，满足期望属性(property)。

这是我到目前为止尝试过的方法，但我没有得到正确的输出:我正在遍历字符串，每当最长的字符数超过 K 时，我就会用 L 替换 M。

public static int solution(String S, int K) {

    StringBuilder Str = new StringBuilder(S);

    int longest=0;int minCount=0;
    for(int i=0;i<Str.length();i++){
        char curr=S.charAt(i);
        if(curr=='M'){
            longest=longest+1;
        if(longest>K){
           Str.setCharAt(i, 'L');
           minCount=minCount+1;
           }
        }

        if(curr=='L')
         longest=0;
 }
  if(longest < K){
        longest=0;int indexoflongest=0;minCount=0;
        for(int i=0;i<Str.length();i++){
            char curr=S.charAt(i);
            if(curr=='M'){
            longest=longest+1;
            indexoflongest=i;

            }
            if(curr=='L')
              longest=0;

        }
        Str.setCharAt(indexoflongest, 'M');
        minCount=minCount+1;



    }
  return minCount;
}

Answer 1

这个算法有 2 个部分，因为我们想要得到等于 K 的最长字符间隔。

1. 我们已经有一个 >= K 的间隔，所以现在我们需要适本地更改一些字符，所以我们贪婪地更改每个 (k + 1) 个字符，然后再次从 0 开始计数。

2. 现在，如果间隔小于 K，我将需要在数组上运行一个滑动窗口。在运行这个窗口时，我基本上考虑在这个长度为 K 的窗口中将所有 L 转换为 M。但这会带来增加间隔长度的副作用，因为外面可能有 K，所以这个变量 (int nec) 会跟踪那。所以现在我还必须考虑将(K 长度)窗口外的 2 个可能的 M 转换为 L。

这是完整的 C++ 可运行代码。祝你有美好的一天。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector <int> vi;
typedef pair<int, int> ii;



int change(string s, int k) {
    // handling interval >= k
    bool flag = false;
    int ans = 0;
    int cnt = 0;
    for(int i=0; i<s.size(); i++) {
        if(s[i] == 'M') cnt++;
        else cnt = 0;
        if(cnt == k) flag = true;
        if(cnt > k) s[i] = 'L', ans++, cnt = 0;
    }
    if(flag) return ans;

    // handling max interval < k
    // If the interval is too big.
    if(k > s.size()) {
        cerr << "Can't do it.\n"; exit(0);
    }

    // Sliding window
    cnt = 0;
    for(int i=0; i<k; i++) {
        if(s[i] == 'L') cnt++;
    }
    ans = cnt + (s[k] == 'M'); // new edit
    int nec = 0; // new edit
    for(int i=k; i<s.size(); i++) {
        if(s[i-k] == 'L') cnt--;
        if(s[i] == 'L') cnt++;
        nec = 0;
        if(i-k != 0 && s[i-k-1] == 'M')
            nec++;
        if(i < s.size()-1 && s[i+1] == 'M')
            nec++;
        ans = min(ans, cnt + nec);
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);

    string s;
    int k;

    cin >> s >> k;

    int ans = change(s, k);
    cout << ans << "\n";

    return 0;
}