1

この問題を解決するために、単純な python アルゴリズムを作成しようとしています。私のコードが機能しない理由を理解するのを手伝ってもらえますか:

問題：

Jakub は 1 次元キーボードを試しています。1 列のキーで構成されます。隣接する 2 つのキー間の距離は 1 です。各キーには、英語のアルファベットの個別の文字が含まれています。Jakub は 1 本の指だけでキーボードを入力します。彼は、特定の単語を入力するときに指を移動する必要がある最小の合計距離はどれくらいかを考えています。

たとえば、キーボードの唯一の行が "qwertyuiop" で、Jakub が "potter" という単語を入力したい場合、彼は指を 'p' から 'o' (距離 1)、'o' から ' t' (距離 4)、't' から 't' (距離 0)、't' から 'e' (距離 2)、および 'e' から 'r' (距離 1) の合計距離1 + 4 + 0 + 2 + 1 = 8 の

文字列キーボードと文字列単語が与えられ、キーボードと Jakub が書きたい単語を記述します。キーボードで単語を入力するために指を動かさなければならない最小距離を返します。

私のコード:

def typingDistance (keyboard, word):
    a=keyboard.find(word[0][:1])
    res=0
    for i in word:
        if keyboard.find(i) != a:
            res+=abs(a-i)
        a = keyboard.find(i)
    return res
4

1 に答える 1

5

問題は、代わりに文字a-iがどこにあるのかをやっているということです。位置を計算して出来上がり！ia-position

def typingDistance (keyboard, word):
    a = keyboard.find(word[0][:1])

    res=0
    for i in word:
        position = keyboard.find(i)
        if position != a:
            res += abs(a-position)
        a = position
    return res

は文字でありword[0]、したがって同じ文字であることに注意してください(単に「a」であるため)。したがって、それを省略することができます：word[0][:1]"a"[:1]

if position != aまた、距離は0とにかくそうする必要がないことに注意してください。

def typingDistance (keyboard, word):
    a = keyboard.find(word[0])

    res=0
    for i in word:
        position = keyboard.find(i)
        res += abs(a-position)
        a = position
    return res

keyboard.find最後に、頻繁に呼び出すのを避けるために、最初に文字 → キーボードのインデックスにマッピングする方がよい場合があることに注意してください。wordこれは、 がよりもはるかに長い場合にのみ役立ちkeyboardますが、学習しているときに取り入れるのは良い習慣です。

def typingDistance(keyboard, word):
    letter2position = {letter: keyboard.index(letter) for letter in keyboard}

    a = letter2position[word[0]]
    res=0
    for i in word:
        position = letter2position[i]
        res += abs(a-position)
        a = position
    return res

letter2position[...]単に置き換えることに注意してくださいkeyboard.find(...)。これは、関数が入力から出力へのマッピングでありletter2position、すべての結果が事前に計算された単なる関数であることに気付いた場合に意味があります..

于 2013-09-22T23:17:56.227 に答える