我有一个作业，给我一个包含字母“R”和“K”的字符串S，例如“RRRRKKKKRK”。
我需要通过将字符i到j翻转到相反的字符来获取该字符串可能容纳的'R'的最大数目。所以:
for(int x = i; x < j; x++)
{
if S[x] = 'R'
{
S[X] = 'S';
}
else
{
S[X] = 'R';
}
}
但是，我只能通过进行上述调用。
因此，对于以上示例:“RRRRKKKKRK”。
您将拥有i = 4和j = 8，这将导致:“RRRRRRRRKR”，然后将在结果字符串中输出R的数目:9。
我的代码部分有效，但在某些情况下无效。任何人都可以找出丢失的内容吗？
样本输入
2
RKKRK
RKKR
样本输出
4
4
我的解决方案
我的解决方案仅在第一种情况下有效，我不知道为完成算法我缺少什么:
int max_R = INT_MIN;
for (int i = 0; i < s.size(); i++)
{
for (int j = i + 1; j < s.size(); j++)
{
int cnt = 0;
string t = s;
if (t[j] == 'R')
{
t[j] = 'K';
}
else
{
t[j] = 'R';
}
for (int b = 0; b < s.size(); b++)
{
if (t[b] == 'R')
{
cnt++;
if (cnt > max_R)
{
max_R = cnt;
}
}
}
}
}
cout << max_R << endl;
最佳答案
尝试仔细考虑您的解决方案。您了解它的作用吗？
首先，让我们忘记输入文件可能包含多个测试，因此让我们摆脱while循环。现在，我们只有两个for循环。第二个显然只是在处理的字符串中计算R。但是第一个做什么呢？
答案是，第一个循环将从第二个循环(即索引为1)开始的所有字母翻转到字符串的末尾。我们可以在第一个测试用例中看到:
RKKRK
这确实是最佳解决方案。字符串变成
RRRKR，我们得到了四个R。但是在第二种情况下:RKKR
字符串变成
RRRK，我们得到三个R。如果我们仅将字母从2翻转到3(即将1索引为2)，我们可以得到具有四个RRRR的R。因此，您的算法总是将字母从索引
1翻转到末尾，但这并不总是最佳的。我们能做些什么？我们如何知道要翻转的字母？好了，有一些聪明的解决方案，但是最简单的就是尝试所有可能的组合!您可以将所有字母从
0翻转到1，计算R的数量，并记住它。返回原始字符串，将字母从0翻转到2，计算R的数量，记住它，依此类推，直到从0翻转到n-1为止。然后，您将字母从1翻转到2，从1翻转到3，等等。答案就是您记住的最大值。这是非常低效的，但这是可行的。在解决算法问题上获得更多实践之后，请回到此任务并尝试找出更有效的解决方案。 (提示:如果您考虑逐步构建最佳答案，那就是通过逐个字符遍历char并将子串
s[0..i]的最佳解决方案转换为s[0..i+1]的最佳解决方案，您可以得出一个非常简单的O(n ^ 2)算法。可以将其增强为O(n)，但此步骤要稍微复杂一些。)这是此解决方案的草图:
def solve(s):
answer = 0
for i in 0..(n-1)
for j in i..(n-1)
t = copy(s) # we will need the original string later
flip(t, i, j) # flip letters from i to j in t
c = count_R(t) # count R's in t
answer = max(answer, c)
return answer
关于c++ - 字符串中的Rs数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29420153/