我在一次竞赛中被问到这个问题。
给定一个仅包含 M 和 L 的字符串,我们可以将任何“M”更改为“L”或将任何“L”更改为“M”。该函数的目标是计算为了实现所需的最长 M 间隔长度 K 而必须进行的最小更改次数。
例如,给定 S = "MLMMMLM"且 K = 3,函数应返回 1。我们可以更改位置 4(从 0 开始计数)的字母,得到“MLMMMLM”,其中字母“M”的最长间隔为正好三个字符长。
再举个例子,给定 S = "MLMMMLMMMM"且 K = 2,函数应返回 2。例如,我们可以修改位置 2 和 7 处的字母,得到字符串“MLLMMLMLMM”,它满足所需的要求属性。
这是我到目前为止所尝试过的,但我没有得到正确的输出: 我正在遍历字符串,每当最长的字符数超过 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;
}
最佳答案
这个算法有两个部分,因为我们想要获得等于 K 的最长字符间隔。
我们已经有了一个 >= K 的间隔,所以现在我们需要适本地更改一些字符,以便我们贪婪地更改每个第 (k + 1) 个字符,然后再次从 0 开始计数。
现在,如果间隔小于 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;
}
关于java - 使最长字符间隔等于 K 所需的最少操作,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50106081/