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 回答