字符串中使所有 'X' 个字符位于所有 'Y 个字符左侧的最少替换

Question

嘿，每个人都在面试中遇到过这个问题，但似乎无法找到解决问题的最佳方法。任何帮助将不胜感激。

问题：

给你一个字符串S。字符串的每个字符要么是'W'要么是'R'。

W代表白色花
R代表红色的花

如果所有白色花朵都位于所有红色花朵的左侧，则字符串被认为是美丽。您可以用红色花朵替换任何白色花朵，反之亦然。

你的任务是找到使字符串 S 美丽所必须进行的最少替换次数。

样本案例：

1.) 输入：“RWRW”

输出：2（“WWRR”或“WWWW”或“RRRR”）

2.) 输入：“RRRR”

输出：0（“RRRR”）

3.) 输入：“RWWWRR”

输出：1（“WWWWRR”）

Answer 1

这看起来像一个动态规划问题。让

dp[i][0] = minimum number of changes if the i-th flower is white
dp[i][1] = minimum number of changes if the i-th flower is white

基础状态：

dp[0][0] = int(arr[0] != “W”)
dp[0][1] = int(arr[0] != “R”)

现在，为了计算 dp[i] 的值，我们看一下案例：

如果arr[i] == “R”

如果arr[i-1] == “R”，则arr[i]必须是“R”。
如果arr[i-1] == “W”，则arr[i]可以是“R”或“W”。
arr[i][1] = min(arr[i-1][0], arr[i-1][1])
arr[i][0] = arr[i-1][0] + 1

如果arr[i] == “W”

如果arr[i-1] == “R”，那么arr[i]必须是“R”（所以我们必须修改当前花）。
如果arr[i-1] == “W”，那么arr[i]可以是“R”（需要修改）或者“W”（不需要修改）。
arr[i][0] = arr[i-1][0]
arr[i][1] = min(arr[i-1][0], arr[i-1][1]) + 1

最后你的答案变成min(dp[n-1][0], dp[n-1][1])

简单Python实施：

s = "RWWWRR"
n = len(s)
dp = [[0,0] for i in range(n)]
dp[0][0] = int(s[0] != "W")
dp[0][1] = int(s[0] != "R")
for i in range(1,n):
    if s[i] == "R":
        dp[i][1] = min(dp[i-1])
        dp[i][0] = dp[i-1][0] + 1 
    else:
        dp[i][1] = min(dp[i-1]) + 1 
        dp[i][0] = dp[i-1][0]
    
print(min(dp[n-1]))

Answer 2

这可以通过一次保持 O(1) 状态的数组来解决。

我们通过找到分割数组的最佳位置来做到这一点，这样在解决方案中，左边的所有花都是白色的，右边的所有花都是红色的。这与找到从 0 到 N 的 i 最小化 i 左侧的红色花朵数量加上 i 右侧的白色花朵数量相同，因为这是我们必须更改以拆分数组的花朵数量在 i.

设数组长度为N，共有R朵红花（所以N-R红花），设r[i]为i左边的红花数，r' [i] i右边的红色花朵的数量，w[i]和w'[i]的白色花朵相同。

我们想要找到 i 使得 r[i] + w'[i] 最小化（i 左边的红色花朵的数量加上 i 右边的白色花朵的数量 - 这些是我们必须改变的）。但是 w'[i] + w[i] = (N-R)，并且 r[i] + w[i] = i，所以 r[i] + w'[i] = r[i] + (N-i)-(R-r[i]) = 2r[i] - i + (N - R).

因此我们需要找到最小化 2r[i] - i + (N - R) 的 i。由于 N-R 是常数，这与找到 i 使 2r[i] - i 最小化是一样的。当我们处理完整个数组时，我们有了 R 的值，可以构造 return 值。

下面是一些 python 使用此方法的代码，以及一些测试用例。

def min_changes(A):
    best, besti = 1e12, -1
    r = 0
    for i in range(len(A)+1):
        v = 2 * r - i
        if v < best:
            besti, best = i, v
        if i < len(A):
            r += A[i] == 'R'
    return best + len(A) - r, 'W' * besti + 'R' * (len(A) - besti)

tests = [("RWRW", 2, "RRRR"), ("RRRR", 0, "RRRR"), ("RWWWRR", 1, "WWWWRR")]
for s, n, r in tests:
    gotn, gotr = min_changes(s)
    if gotn != n or gotr != r:
        print("FAILED",)
    print(s, gotn, gotr)

字符串中使所有 'X' 个字符位于所有 'Y 个字符左侧的最少替换

Minimum replacements in a string to make all 'X' chars to the left of all 'Y chars

string

algorithm

replace