我需要找到以隨機順序和數量（不僅僅是相鄰）對僅包含字母 X、Y 和 Z 的字符串進行排序所需的最小交換量。任意兩個字符都可以交換。例如，字符串 ZYXZYX 將按 3 次交換排序：ZYXZYX -> XYXZYZ -> XXYZYZ -> XXYYZZ ZZXXYY - 4 次交換，XXXX - 0 次交換。到目前為止，我已經有了這個解決方案，但是排序并沒有以最佳方式對字符進行排序，因此結果并不總是最小的交換量。此外，解決方案應該是 O(nlogn)。def solve(s): n = len(s) newS = [*enumerate(s)] sortedS = sorted(newS, key = lambda item:item[1]) counter = 0 vis = {v:False for v in range(n)} print(newS) print(sortedS) for i in range(n): if vis[i] or sortedS[i][0] == i: continue cycle_size = 0 j = i while not vis[j]: vis[j] = True j = sortedS[j][0] cycle_size += 1 if cycle_size > 0: counter += (cycle_size - 1) return counter
3 回答
開滿天機
TA貢獻1786條經驗 獲得超13個贊
首先對數組執行一次 O(n) 遍歷并計算 X、Y 和 Z。根據計數，我們可以在數組中定義三個區域：Rx、Ry 和 Rz。Rx 表示數組中 X 應該所在的索引范圍。Ry 和 Rz 也是如此。
那么就需要考慮 6 種排列：
Rx Ry Rz
X Y Z no swaps needed
X Z Y 1 swap: YZ
Y X Z 1 swap: XY
Y Z X 2 swaps: XZ and XY
Z X Y 2 swaps: XZ and YZ
Z Y X 1 swap: XZ
因此，您所需要的只是再進行 5 次 O(n) 次遍歷來修復每個可能的排列。從需要 1 次交換的情況開始。然后修復 2 個交換箱（如果還有）。
例如，用于查找和修復 XZY 排列的偽代碼是：
y = Ry.start
z = Rz.start
while y <= Ry.end && z <= Rz.end
if array[y] == 'Z' && array[z] == 'Y'
array[y] <--> array[z]
swapCount++
if array[y] != 'Z'
y++
if array[z] != 'Y'
z++
每個排列的運行時間為 O(n)，總運行時間為 O(n)。
正確性的正式證明留給讀者作為練習。我只會注意到情況 XZY、YXZ 和 ZYX 以一次交換的成本修復兩個元素（效率 2），而情況 YZX 和 ZXY 以兩次交換的成本修復三個元素（效率 1.5）。因此，首先找到并修復有效的情況（并且僅根據需要執行低效的情況）應該給出最佳答案。
紅糖糍粑
TA貢獻1815條經驗 獲得超6個贊
這可以使用廣度優先搜索來解決，例如使用Raymond Hettinger 的謎題求解器（求解器的完整代碼位于頁面底部）：
class SwapXYZ(Puzzle):? ??
? ? def __init__(self, pos):
? ? ? ? self.pos = [x for x in pos]
? ? ? ? self.goal = sorted(pos)
? ??
? ? def __repr__(self):
? ? ? ? return repr(''.join(self.pos))
? ??
? ? def isgoal(self):
? ? ? ? return self.pos == self.goal
? ??
? ? def __iter__(self):
? ? ? ? for i in range(len(self.pos)):
? ? ? ? ? ? for j in range(i+1, len(self.pos)):
? ? ? ? ? ? ? ? move = self.pos[:]
? ? ? ? ? ? ? ? temp = move[i]
? ? ? ? ? ? ? ? move[i] = move[j]
? ? ? ? ? ? ? ? move[j] = temp
? ? ? ? ? ? ? ? yield SwapXYZ(''.join(move))
SwapXYZ("ZYXZYX").solve()
# ['ZYXZYX', 'XYXZYZ', 'XXYZYZ', 'XXYYZZ']
慕的地10843
TA貢獻1785條經驗 獲得超8個贊
IMVHO 用于排序此類字符串的交換次數為零。我們得到 X、Y 和 Z (nx, ny, nz) 的計數。然后我們用 X 填充前 nx 個元素，用“Y”填充接下來的 ny 元素，用“Z”填充其余的元素。復雜度為 o(n)
def sortxyz(a):
nx = ny = nz = 0
for i in range(len(a)):
if a[i] == 'X':
nx += 1
elif a[i] == 'Y':
ny += 1
else:
nz += 1
return ''.join(['X'] * nx + ['Y'] * ny + ['Z'] * nz)
print(sortxyz('YXXZXZYYX'))
XXXXYYYZZ
對于更一般的情況，當列表的元素可以取值時，m復雜度將為 o(m * n)。
添加回答
舉報
0/150
提交
取消