我需要找到以隨機(jī)順序和數(shù)量（不僅僅是相鄰）對(duì)僅包含字母 X、Y 和 Z 的字符串進(jìn)行排序所需的最小交換量。任意兩個(gè)字符都可以交換。例如，字符串 ZYXZYX 將按 3 次交換排序：ZYXZYX -> XYXZYZ -> XXYZYZ -> XXYYZZ ZZXXYY - 4 次交換，XXXX - 0 次交換。到目前為止，我已經(jīng)有了這個(gè)解決方案，但是排序并沒有以最佳方式對(duì)字符進(jìn)行排序，因此結(jié)果并不總是最小的交換量。此外，解決方案應(yīng)該是 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 回答
開滿天機(jī)
TA貢獻(xiàn)1786條經(jīng)驗(yàn) 獲得超13個(gè)贊
首先對(duì)數(shù)組執(zhí)行一次 O(n) 遍歷并計(jì)算 X、Y 和 Z。根據(jù)計(jì)數(shù)，我們可以在數(shù)組中定義三個(gè)區(qū)域：Rx、Ry 和 Rz。Rx 表示數(shù)組中 X 應(yīng)該所在的索引范圍。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
因此，您所需要的只是再進(jìn)行 5 次 O(n) 次遍歷來修復(fù)每個(gè)可能的排列。從需要 1 次交換的情況開始。然后修復(fù) 2 個(gè)交換箱（如果還有）。
例如，用于查找和修復(fù) 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++
每個(gè)排列的運(yùn)行時(shí)間為 O(n)，總運(yùn)行時(shí)間為 O(n)。
正確性的正式證明留給讀者作為練習(xí)。我只會(huì)注意到情況 XZY、YXZ 和 ZYX 以一次交換的成本修復(fù)兩個(gè)元素（效率 2），而情況 YZX 和 ZXY 以兩次交換的成本修復(fù)三個(gè)元素（效率 1.5）。因此，首先找到并修復(fù)有效的情況（并且僅根據(jù)需要執(zhí)行低效的情況）應(yīng)該給出最佳答案。
紅糖糍粑
TA貢獻(xiàn)1815條經(jīng)驗(yàn) 獲得超6個(gè)贊
這可以使用廣度優(yōu)先搜索來解決，例如使用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貢獻(xiàn)1785條經(jīng)驗(yàn) 獲得超8個(gè)贊
IMVHO 用于排序此類字符串的交換次數(shù)為零。我們得到 X、Y 和 Z (nx, ny, nz) 的計(jì)數(shù)。然后我們用 X 填充前 nx 個(gè)元素，用“Y”填充接下來的 ny 元素，用“Z”填充其余的元素。復(fù)雜度為 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
對(duì)于更一般的情況，當(dāng)列表的元素可以取值時(shí)，m復(fù)雜度將為 o(m * n)。
添加回答
舉報(bào)
0/150
提交
取消