1

たとえば、この配列を見てみましょう

ar = [6,3,5,1,2]

それを別の配列に変換したいのですが、特定の位置にアイテムを挿入する (スプライス(i,0,item)) か、特定の位置からアイテムを削除する (スプライス(i,1)) という 2 つの操作のみを使用できます。これらのスプライスの使用量を最小限に抑えるソリューションを探しています。

2 番目の重要な条件は、一意の値を持つ配列を考慮し、配列に double が含まれていないことです。

例えば、

ar1 = [6,3,10,5,1,2];
ar2 = [6,3,1,2,5];

ar から ar1 を取得したい場合、必要なスプライスは ar.splice(2,0,10) だけであることは明らかです。ar2 を取得したい場合は、2 つの splice を実行する必要があります: ar.splice(2,1) と push(5) (2 番目は splice(ar.length,0,5) に等しい)

ちなみに、このタスクには自然な実用的価値があります。たとえば、製品のリストと製品フィルターを想像してみましょう。フィルターの設定を変更すると、リストがそれぞれ変更されます。そして、すべての変更に続いて、美しい遅いjqueryがスライドアップ - スライドダウンアニメーションが続きます。このアニメーションは、上にスライドして特定のアイテムを隠したり、新しいアイテムを挿入して下にスライドしたりする場合があります。タスクは、これらのアニメーションの量を縮小することです。つまり、リストの DOM 操作の量を最小限に抑えようとします。

4

2 に答える 2

2

操作の数は正確に編集距離です (置換を許可しない場合)。レーベンシュタイン距離を調べます。

アルゴリズムを変更してレーベンシュタイン距離を計算し、必要な操作を実際に出力することができます。

于 2013-03-21T11:25:30.253 に答える
1

うまくいけば問題を解決するコードを書きました。このコードは、どういうわけかレーベンシュタイン距離の概念に基づいています。maniekの回答で述べたように、これはこの問題に非常に役立つようです。
簡単にするために、配列の代わりに文字列を使用し、Pythonを使用しました。
元の問題は、同じ整数のセットで構成される同じ長さの2つの配列の同じ問題に簡単に還元されるようです。したがって、最初の文字列とターゲット文字列は同じ長さで、同じ文字セットで構成されていると想定しました。
Pythonコード：

import random
# Create random initial (strin) and target (strout) strings
s = "abcdefghijklmnopqrstuvwxyz"
l = list(s)
random.shuffle(l)
strout = ''.join(l)
random.shuffle(l)
strin = ''.join(l)

# Use it for tests
#strin = "63125798"
#strout = "63512897"

print strin, strout

ins_del = 0
for i in xrange(len(strin)-1, -1, -1):
    if strin[i] != strout[i]:
        if strin[i-1] == strout[i]:
            ii = strout.find(strin[i], 0, i)
            strin = strin[:ii] + strin[i] + strin[ii:i] + strin[i+1:]
            ins_del = ins_del + 1
            #Test output
            print "1:", strin
        else:
            ii = strin.find(strout[i], 0, i-1)
            strin = strin[:ii] + strin[ii+1:i+1] + strout[i] + strin[i+1:]
            ins_del = ins_del + 1
            #Test output
            print "2:", strin

print strin, strout

# Check the result
for i in xrange(0, len(strin)):
    if strin[i] != strout[i]:
        print "error in", i, "-th symbol"

print "Insert/Delite operations = ", ins_del

出力例：

kewlciprdhfmovgyjbtazqusxn qjockmigphbuaztelwvfrsdnxy
2: kewlciprdhfmovgjbtazqusxny
1: kewlciprdhfmovgjbtazqusnxy
2: kewlciprhfmovgjbtazqusdnxy
2: kewlciphfmovgjbtazqursdnxy
2: kewlciphmovgjbtazqufrsdnxy
2: kewlciphmogjbtazquvfrsdnxy
2: kelciphmogjbtazquwvfrsdnxy
2: keciphmogjbtazqulwvfrsdnxy
2: kciphmogjbtazquelwvfrsdnxy
2: kciphmogjbazqutelwvfrsdnxy
2: kciphmogjbaquztelwvfrsdnxy
2: kciphmogjbquaztelwvfrsdnxy
1: qkciphmogjbuaztelwvfrsdnxy
2: qkcipmogjhbuaztelwvfrsdnxy
2: qkcimogjphbuaztelwvfrsdnxy
1: qjkcimogphbuaztelwvfrsdnxy
2: qjkcmoigphbuaztelwvfrsdnxy
1: qjokcmigphbuaztelwvfrsdnxy
1: qjockmigphbuaztelwvfrsdnxy
qjockmigphbuaztelwvfrsdnxy qjockmigphbuaztelwvfrsdnxy
Insert/Delite operations =  19
于 2013-03-22T03:58:40.857 に答える