2

タスクは、数字のシーケンスを見つけることです。これは、ある数字で転置するか、反転してから転置することができ、別の等しいまたはより大きな数字のセット内にネストされます。入力はテキストファイルからです。数値がそのまままたは転置されている場合は、見つかった場所の開始インデックスを出力し、反転または反転して転置されている場合は、インデックスに続いて反転を出力します。

例 - 検索する数値が 67654 の場合、45432 (2 だけ転置) または 32345 (反転) または 54567 (反転して 2 だけ転置) として見つかります。

Input    
67654      
14676545  
43234545679    
905    
#

最初の行は検索対象 (67654) で、残りの行は検索対象です。

Output    
3    
7    
10 inverted    
14 inverted

私の考えは、探す数字とその数字が反転した場合の各数字の違いである数字のリストを作成することでした。たとえば、67654 はリスト [-1, 1, 1, 1] を作成します。次に、文字列の各桁をループして検索しますが、スライディング ウィンドウを使用して表示されるかどうかを確認します。逆立ちも同じようにしました。

diffs = [int(name[x]) - int(name[x + 1]) for x in range(0, len(name) - 1)] #name stores the fist line of input
invertedName = ''.join([str(9-int(x)) for x in name])

currDiffs = []
for i in range(len(name)-1):
    currDiffs.append(int(piece[i]) - int(piece[i+1])) #piece is the string being searched

for i in range(len(name)- 1, len(piece) - 1):
    currDiffs.pop(0)
    currDiffs.append(int(piece[i]) - int(piece[i+1]))
    Compare(diffs,currDiffs) # check if theyre the same

このように答えていると、ほとんどすべての答えが間違っていることに気づきます。私のアプローチを修正する方法、または何か問題があるかどうかについての提案をいただければ幸いです。

4

1 に答える 1

0

これは最もパフォーマンスの高いソリューションではありませんが、うまくいくようです:

def find_diffs(inval):
    inval = map(int, inval)
    plain = [i - inval[0] for i in inval[1:]]
    return plain, [-i for i in plain]


def check(inval, against):
    inval_diff, _ = find_diffs(inval)
    print against, inval
    for i in range(0, len(against) - len(inval) + 1):
        test, inverted_test = find_diffs(against[i: i + len(inval)])
        if test == inval_diff:
            print i
        elif test == inval_inverted_diff:
            print i, "inverted"

inval = '67654'

check(inval, '14676545')
check(inval, '43234545679')
check(inval, '1467654543234545679905')

出力

14676545 67654
2
43234545679 67654
1 inverted
5 inverted
1467654543234545679905 67654
2
6
9 inverted
13 inverted

それで、これは何をしているのですか？

ここでの考え方は、与えられた入力に対して、最初の値が常に 0 であり、残りの値が最初の値との差である値のリストに入力を変換できるということです。例えば：

1234 => 0, 1, 2, 3
5463 => 0, -1, 1, -2
6667 => 0, 0, 0, 1

同様に、比較する任意の数値に対してこれを行うことができます。したがって、比較するには、比較対象の数値から最初の N 個の数値を取得します。ここで、N はソース数値の長さです。

最後の例では、送信元番号は 67654 であるため、長さは 5 です。against番号は 1467654543234545679905 であるため、最初の 5 桁は 14676 です。

上記の差分公式を使用すると、次のようになります。

67654 => 0, 1, 0, -1, -2
14676 => 0, 3, 5, 6, 5

したがって、これは一致しません。これを続けてagainst、リストを使い果たすまで番号の開始インデックスをスライドさせます。

他に考慮すべき唯一のことは、反転です。反転チェックの場合は、差分リストの各数値に -1 を掛けるだけです。オフセットは一定なので問題ありません。

オフセット値が必要な場合は、少し複雑になります。

于 2013-09-22T06:52:28.953 に答える