嘿，每個人都在面試中遇到過這個問題，似乎無法找出最好的解決方法。任何幫助將非常感激。
問題：
給你一個字串 S。字串的每個字符都是“W”或“R”。
- W代表一朵白色的花。
- R代表一朵紅色的花
如果所有白色花朵都在所有紅色花朵的左側，則認為一根繩子是美麗的。你可以用紅色的花代替任何白色的花，反之亦然。
你的任務是找到使字串 S 漂亮所需的最少替換次數。
示例案例：
1.）輸入：“RWRW”
輸出：2（“WWRR”或“WWWW”或“RRRR”）
2.）輸入：“RRRR”
輸出：0（“RRRR”）
3.) 輸入：“RWWWRR”
輸出：1（“WWWWRR”）
uj5u.com熱心網友回復：
這可以通過保持 O(1) 狀態的陣列一次性解決。
我們通過找到拆分陣列的最佳位置來做到這一點，這樣在解決方案中，左邊的所有花都是白色的，右邊的所有花都是紅色的。這與從 0 到 N 中找到 i 相同，即最小化 i 左側的紅色花朵數量加上 i 右側的白色花朵數量，因為這是我們必須更改的花朵數量才能拆分陣列在我。
假設陣列的長度為N，總共有R朵紅花（所以NR紅花），設r[i]為i左邊的紅花數，r'[i]為到的紅花數i 的右側，對于帶有 w[i] 和 w'[i] 的白花也是如此。
我們想找到 i 使得 r[i] w'[i] 最小化（i 左邊的紅色花朵的數量加上 i 右邊的白色花朵的數量——這些是我們想要的必須改變）。但是 w'[i] w[i] = (NR)，并且 r[i] w[i] = i，所以 r[i] w'[i] = r[i] (Ni)- (Rr[i]) = 2r[i] - i (N - R)。
因此我們需要找到最小化 2r[i] - i (N - R) 的 i。由于 NR 是恒定的，這與找到 i 使得 2r[i] - i 最小化相同。當我們處理完整個陣列時，我們有了 R 的值，并且可以構造回傳值。
這是一些使用此方法的 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)
uj5u.com熱心網友回復：
這看起來像一個動態規劃問題。讓
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]))
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424333.html
上一篇：如何對符合特定條件的串列進行分組