我有一個帶有字母 A、Z、F、G 的結構。
A與Z有一對，F與G有一對。
例如，我有 AAAFFZZGGFFGGAAAAZZZZ。我需要“彎曲”結構，折疊會成對
A A A F F Z Z G G F F -
* * * * * * |
Z Z Z Z A A A A G G -
上例中為 6 對。
但是我們可以創建這樣的結構：
A A A F F Z Z G G -
* * * |
Z Z Z Z A A A A G G F F -
而 head 是結構的片段，其中不存在對。例如頭 2：
羅茲米亞爾。Na przyk?ad head = 2：
F F
A A A F F Z Z G G / \
* * * * |
Z Z Z Z A A A A \ /
G G
我不知道如何找到可以在此結構中創建的最大對數
uj5u.com熱心網友回復：
您可以從測驗中心的折疊點開始，然后扇出（以之字形方式）使折疊點遠離中心。
然后對于給定的折疊點，計算允許的對。您可以使用切片來創建兩個條帶，一個以相反的順序，然后zip是獲得對的條帶。
當最短條帶的大小小于目前找到的最佳答案的大小時，外部迭代（確定折疊點）可以停止。
這是一個解決方案，它也回傳實際折疊，因此可以列印以進行驗證：
def best_fold(chain):
allowed = set(("AZ","ZA","FG","GF"))
revchain = chain[::-1]
maxnumpairs = 0
fold = chain # This represents "no solution"
n = len(chain)
head = n // 2
for diff in range(n):
head = diff if diff % 2 else -diff
if head - 2 < maxnumpairs or n - head - 2 < maxnumpairs:
break
numpairs = sum(a b in allowed
for a, b in zip(revchain[-head 2:], chain[head 2:])
)
if numpairs > maxnumpairs:
maxnumpairs = numpairs
fold = chain[:head].rjust(n) "\n" revchain[:-head].rjust(n)
return maxnumpairs, fold
以下是如何在示例字串上運行它：
numpairs, fold = best_fold("AAAFFZZGGFFGGAAAAZZZZ")
print(numpairs) # 5
print(fold) # AAAFFZZGGF
# ZZZZAAAAGGF
uj5u.com熱心網友回復：
為了使匹配更快，您可以準備第二個字串 (R)，并將字母翻轉為相應的值。這將允許直接比較配對位置，而不是通過 n^2 次間接比較：
S = "AAAFFZZGGFFGGAAAAZZZZ"
match = str.maketrans("AZFG","ZAGF")
R = S.translate(match) # flipped matching letters
mid = len(S)//2
maxCount,maxPos = 0,0
for d in range(mid 1): # moving away from middle
for p in {mid d,mid-d}: # right them left
pairs = sum(a==b for a,b in zip(S[p-1::-1],R[p:])) # match fold
if pairs>maxCount:
maxCount,maxPos = pairs,p # track best so far and fold position
if p <= maxCount: break # stop when impossible to improve
print(maxCount) # 6 matches
print(maxPos) # folding at 11
print(S[:maxPos].rjust(len(S))) # AAAFFZZGGFF
print(S[maxPos:][::-1].rjust(len(S))) # ZZZZAAAAGG
# ** ** **
uj5u.com熱心網友回復：
我會首先從一個合適的資料型別開始實作您的可創建字串。現在首先要做的是，正如您在評論中提到的那樣，我們可以使用比字串更好的字串列。那么也許像這樣的陣列元組[[Char],[Char]]就足夠了。
從左側或右側折痕也無關緊要，所以為了簡單起見，我們開始；
[ ["A","A","F","F","Z","Z","G","G","F","F","G","G","A","A","A","A","Z","Z","Z","Z"]
, ["A"]
]
然后在每一步；
然后在每一步中，我們都可以將我們的字串列映射到一個折痕元組中，例如
chars.map((_,i,a) => [a.slice(i 1),a.slice(0,i 1).reverse()]比較并計數成對。
為了有效地比較對應的專案是否為有效對，可以使用如下簡單的查找表
{ "A": "Z"
, "Z": "A"
, "G": "F"
, "F": "G"
}
- 最后我們可以過濾最長的
折痕的實作可能是這樣的；
function pairs(cs){
var lut = { "A": "Z"
, "Z": "A"
, "G": "F"
, "F": "G"
};
return cs.map(function(_,i,a){
var crs = [a.slice(i 1),a.slice(0,i 1).reverse()]; // console.log(crs) to see all creases)
return crs[0].reduce( (ps,c,j) => lut[c] === crs[1][j] ? ( ps.res.push([c,crs[1][j],j])
, ps.crs ??= crs.concat(i 1)
, ps
)
: ps
, { res: []
, crs: null
}
);
})
.reduce( (r,d) => r.length ? r[r.length-1].res.length > d.res.length ? r :
r[r.length-1].res.length < d.res.length ? [d] : r.concat(d)
: [d]
, []
);
}
var chars = ["A","A","A","F","F","Z","Z","G","G","F","F","G","G","A","A","A","A","Z","Z","Z","Z"],
result = pairs(chars);
console.log(result);.as-console-wrapper{
max-height: 100% !important;
}現在這是一種簡單的演算法，可能不是最有效的演算法。通過在測驗對上使用復雜的模運算而不使用任何額外的陣列，它可以變得更快，但是我相信這將是一種矯枉過正并且很難解釋的事情。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/417242.html
標籤：
上一篇：無法理解凱撒解密步驟