基于HackerRan的DNA健康检测算法的Python实现

Question

我试图用python解决Determining DNA Health challenge from Hackerrank。（我必须补充一下，我对Python3有些陌生。还在学习语言）

对于测试用例7、8和9，我的解决方案失败，并显示“错误答案”。在

当我在本地运行以下代码时，我可以确认对于这些测试用例，我的实现产生了预期的输出。在

我想知道有什么问题。在

我现在有点困惑。我的实现有问题吗？如果是这样的话，为什么它会为28个测试用例生成正确的答案，但在这3个测试用例中却失败了？或者这是来自Hacker Rank的一个误导/混淆的结果信息，因为我碰巧知道，从我从阅读讨论中学到的，人们发现这3个测试用例（7、8和9）有问题。在

任何帮助都将不胜感激。在

下面是我写的代码：

from bisect import bisect_left
from bisect import bisect_right
import sys
from unittest.mock import right

class TrieNode(object):

    def __init__(self):
        self.subnodes = {}
        self.isTerminal = False
        self.indexList = []
        self.healthList = []

    def addSubnode(self, aChar):
        if (self.subnodes.get(aChar)):
            return self.subnodes[aChar]
        else:
            newNode = TrieNode()
            self.subnodes[aChar] = newNode
            return newNode

    def addIndexAndValue(self, index, health):
        self.isTerminal = True
        self.indexList.append(index)
        lastHealth = 0
        healthLength = len(self.healthList)
        if (healthLength>0):
            lastHealth = self.healthList[healthLength-1]
        self.healthList.append(lastHealth + health)

    def getSubnodeFor(self, aChar):
        return self.subnodes.get(aChar)

    def getValueForIndexes(self, startIndex, endIndex):
        listSize = len(self.indexList)
        if listSize < 1:
            return 0
        elif listSize == 1:
            if startIndex <= self.indexList[0] and endIndex >= self.indexList[0]:
                return self.healthList[0]
            else:
                return 0 
        else: # listSize > 1  
            rightInd = bisect_left(self.indexList, endIndex)
            if rightInd < listSize and endIndex < self.indexList[0]:
                return 0

            big = 0

            if rightInd >= listSize:
                big = self.healthList[listSize - 1]
            else:
                if endIndex >= self.indexList[rightInd]:
                    big = self.healthList[rightInd]
                else:
                    big = self.healthList[rightInd-1]

            leftInd = bisect_left(self.indexList, startIndex)            

            small = 0
            if leftInd >= listSize:
                return 0
            else:
                if startIndex <= self.indexList[leftInd]:
                    if (leftInd > 0):
                        small = self.healthList[leftInd - 1]
                    else:
                        small = 0
                else:
                    small = self.healthList[leftInd]

            return big - small

class Trie(object):

    def __init__(self):
        self.root = TrieNode()

    def getRoot(self):
        return self.root

    def createTrie(self, genes, healths):
        for i in range(len(genes)):
            node = self.root
            for c in genes[i]:
                node = node.addSubnode(c)
            node.addIndexAndValue(i, healths[i])


def calculateHealth(trie, d, first, last):
    total = 0
    dLength = len(d)
    for i in range(0, dLength):
        node = trie.getRoot()
        for j in range(i, dLength):
            node = node.getSubnodeFor(d[j])
            if node != None:
                if node.isTerminal:
                    val = node.getValueForIndexes(first, last)
                    total = total + val
            else:
                break 
    return total


def readFromFile(aFileName):

    inputArr = None
    with open('../hackerRank/src/' + aFileName, encoding='utf-8') as aFile:
        inputArr = aFile.read().splitlines()
    return inputArr


def runFor(fileName, minimumValue, maximumValue):
    inp = readFromFile(fileName)
    n = inp[0]
    genes = inp[1].rstrip().split()
    healths = list(map(int, inp[2].rstrip().split()))
    trie = Trie()
    trie.createTrie(genes, healths)
    s = int(inp[3])
    minVal = sys.maxsize
    maxVal = -1

    for fItr in range(s):
        line = inp[fItr+4].split()
        first = int(line[0])
        last = int(line[1])
        d = line[2]

        val = calculateHealth(trie, d, first, last)

        if val < minVal:
            minVal = val

        if val > maxVal:
            maxVal = val


    print (minVal,maxVal)
    assert minimumValue == minVal
    assert maximumValue == maxVal



# TextX.txt 's are simple text files, which hold test data for regarding test case
# following the file name are real expected numbers for each relevant test case
# I got those from hacker rank
runFor('Test2.txt', 15806635, 20688978289)
runFor('Test7.txt', 0, 7353994)
runFor('Test8.txt', 0, 8652768)
runFor('Test9.txt', 0, 9920592)
runFor('Test33.txt', 11674463, 11674463)

Answer 1

可以在以下位置找到一个可能有帮助的参考： https://gist.github.com/josephmisiti/940cee03c97f031188ba7eac74d03a4f

请看他写的笔记。在

这是我一直在使用的输入。在

六 a、b、c、a、b 1 2 3 4 5 6 三 1 5 caaab公司 0 4 xyz公司 2 4 bcdybc