CSDN每日一题求解

Question

题目名称：豚鼠排名榜

时间限制： 1000ms 内存限制： 256M

题目描述

已知字符A.B,C。每个字符都有自己的权值q。 现不知道权值q，只知道A,B,C的三次比较结果。

输入描述

输入三个字符串表示三次比较的结果

输出描述

输出结果，如果不存在输出”Impossible”

示例

示例1

输入：

A < B
B > C
C > A

输出：

ACB

class Solution:
    def __init__(self) -> None:
        pass
    
    def solution(self, exp1, exp2, exp3):
        relationships = {'A': [], 'B': [], 'C': []}
        
        comparisons = [exp1, exp2, exp3]
        for comparison in comparisons:
            char1, char2 = comparison[0], comparison[2]
            if comparison[1] == '<':
                relationships[char1].append(char2)
            elif comparison[1] == '>':
                relationships[char2].append(char1)
        
        order = []
        visited = set()
        
        def dfs(char):
            visited.add(char)
            for next_char in relationships[char]:
                if next_char not in visited:
                    dfs(next_char)
            order.append(char)
        
        for char in relationships.keys():
            if char not in visited:
                dfs(char)
        
        if len(order) != 3:
            return "Impossible"
        
        return ''.join(order[-1::-1])


if __name__ == "__main__":
    exp1 = input().strip()
    exp2 = input().strip()
    exp3 = input().strip()
    
    sol = Solution()
    result = sol.solution(exp1, exp2, exp3)
    print(result)

通过率只有90%，不知道为啥？

Answer 1

【以下回答由 GPT 生成】

问题已经给出了具体的解决方案，但是通过率只有90%。为了优化代码以提高通过率，我们可以对输入进行校验，确保输入的字符串符合要求。

具体优化方案如下：

1. 添加输入校验功能。我们可以在输入前添加一些校验逻辑，确保输入的字符串格式正确。比如判断输入的字符串长度是否为5，确保输入的第2个字符是"<"或者">"。

优化后的代码如下：

class Solution:
    def __init__(self) -> None:
        pass

    def solution(self, exp1, exp2, exp3):
        # 输入校验
        if not self.validate_input(exp1) or not self.validate_input(exp2) or not self.validate_input(exp3):
            return "Invalid input"

        relationships = {'A': [], 'B': [], 'C': []}

        comparisons = [exp1, exp2, exp3]
        for comparison in comparisons:
            char1, char2 = comparison[0], comparison[2]
            if comparison[1] == '<':
                relationships[char1].append(char2)
            elif comparison[1] == '>':
                relationships[char2].append(char1)

        order = []
        visited = set()

        def dfs(char):
            visited.add(char)
            for next_char in relationships[char]:
                if next_char not in visited:
                    dfs(next_char)
            order.append(char)

        for char in relationships.keys():
            if char not in visited:
                dfs(char)

        if len(order) != 3:
            return "Impossible"

        return ''.join(order[-1::-1])

    def validate_input(self, exp):
        if len(exp) != 5:
            return False
        if exp[1] != "<" and exp[1] != ">":
            return False
        return True


if __name__ == "__main__":
    exp1 = input().strip()
    exp2 = input().strip()
    exp3 = input().strip()

    sol = Solution()
    result = sol.solution(exp1, exp2, exp3)
    print(result)

这样，我们增加了输入校验的功能，确保输入符合要求的格式。重新运行代码，通过率应该会提高。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^