你如何处理 leetcode 中超出时间限制的错误？

Question

最近开始解决 leetcode 问题，我试图实现一个 linked list 但我一直收到超出时间限制的错误。我该如何解决这个问题？该代码在样本输入情况下运行得非常好，但我认为它在边缘情况下会失败。在经历了各种代码变体之后，我还没有想出更好的方法来实现链表。这是我的代码

class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
class MyLinkedList:

    def __init__(self):
        self.head =None

    def get(self, index: int) -> int:
        temp = self.head 
        
        if index == 0:
            return temp.data 
        pos = 0
        while temp is not None:
            if pos == index:
                return temp.data
                break
            # return temp.data
            temp = temp.next
            pos+=1
            
        if temp == None:
            return -1
            

    def addAtHead(self, val: int) -> None:
        new_node = Node(val)
        new_node.next = self.head
        self.head = new_node
        

    def addAtTail(self, val: int) -> None:
        new_node = Node(val)
        temp = self.head 
        if self.head is None:
            self.head = new_node
        while temp.next is not None:
            temp = temp.next
        temp.next =new_node
        

    def addAtIndex(self, index: int, val: int) -> None:
        new_node = Node(val)
        temp = self.head 
        if index ==0:
            new_node.next=temp
            self.head = new_node
        pos = 0
        while temp is not None:
            if pos == index:
                break
            prev = temp
            temp = temp.next
            pos+=1
            prev.next =new_node
            new_node.next=temp
        

    def deleteAtIndex(self, index: int) -> None:
        if self.head is None:
            return -1
        if index ==0:
            self.head = self.head.next
            return self.head
        pos =0
        curr = self.head
        prev=self.head 
        temp = self.head
        while curr is not None:
            if pos == index:
                temp = curr.next
                break
            prev = curr
            curr =curr.next
            pos+=1
        prev.next=temp
        return prev

这是一个示例输入测试用例：

["MyLinkedList","addAtHead","addAtHead","addAtHead","addAtIndex","deleteAtIndex","addAtHead","addAtTail","get","addAtHead","addAtIndex","addAtHead"]
[[],[7],[2],[1],[3,0],[2],[6],[4],[4],[4],[5,0],[6]]

Answer 1

您可以进行一些优化！

给尾巴一个参考。如果你这样做，你就不必遍历列表到 addAtTail
一定要用单向链表吗？如果不尝试使用 doubly-linked 列表并始终计算列表的大小。为什么这有用？

假设你有一个包含 60 个元素的链表，你想在索引 50 处添加。如果你从尾部开始往回走不是更好吗？

我不会添加代码示例，因为有大量关于此主题的资源。祝你好运！

Answer 2

参考添加 link to problem, you have to login and skip first 3 introduction steps to see problem text. If you can't see text, here is an image 文本。

对您的代码进行了 5-7 次修复，主要错误在 addAtIndex() 和 deleteAtIndex() 中，其他函数包含小错误或拼写错误。有些错误导致无限循环，这就是为什么 LeetCode 服务器上出现 Time Exceeded 错误。

更正后的代码片段如下。将其文本与您的原始文本进行比较（例如 Windows 下的命令行 windiff original.py corrected.py）以查看有何不同。

还在代码片段中包含了几个在您的原始代码中失败的测试用例。

Try it online!

class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
class MyLinkedList:

    def __init__(self):
        self.head =None

    def get(self, index: int) -> int:
        temp = self.head
        if temp is None:
            return -1
        if index == 0:
            return temp.data 
        pos = 0
        while temp is not None:
            if pos == index:
                return temp.data
                break
            # return temp.data
            temp = temp.next
            pos+=1
            
        if temp == None:
            return -1
            
    def toList(self):
        r = []
        for i in range(1 << 30):
            v = self.get(i)
            if v == -1:
                return r
            r.append(v)
        
    def addAtHead(self, val: int) -> None:
        new_node = Node(val)
        new_node.next = self.head
        self.head = new_node
        

    def addAtTail(self, val: int) -> None:
        new_node = Node(val)
        temp = self.head 
        if self.head is None:
            self.head = new_node
            return
        while temp.next is not None:
            temp = temp.next
        temp.next =new_node
        

    def addAtIndex(self, index: int, val: int) -> None:
        new_node = Node(val)
        temp = self.head 
        if index ==0:
            new_node.next=temp
            self.head = new_node
            return
        pos = 0
        while True:
            if pos == index:
                prev.next = new_node
                new_node.next = temp
                break
            if temp is None:
                break
            prev = temp
            temp = temp.next
            pos+=1
        

    def deleteAtIndex(self, index: int) -> None:
        if self.head is None:
            return
        if index ==0:
            self.head = self.head.next
            return
        pos =0
        curr = self.head
        prev=self.head 
        temp = self.head
        while curr is not None:
            if pos == index:
                temp = curr.next
                prev.next=temp
                break
            prev = curr
            curr =curr.next
            pos+=1
        

def test():
    for itest, (meths, args) in enumerate([
        (["MyLinkedList","addAtHead","deleteAtIndex","addAtHead","addAtHead","addAtHead","addAtHead","addAtHead","addAtTail","get","deleteAtIndex","deleteAtIndex"],
         [[],[2],[1],[2],[7],[3],[2],[5],[5],[5],[6],[4]]),
        (["MyLinkedList","addAtHead","addAtTail","addAtIndex","get","deleteAtIndex","get","get","deleteAtIndex","deleteAtIndex","get","deleteAtIndex","get"],
         [[],[1],[3],[1,2],[1],[1],[1],[3],[3],[0],[0],[0],[0]]),
        (["MyLinkedList","addAtIndex","get"],
         [[],[1,0],[0]]),
        (["MyLinkedList","addAtHead","addAtHead","addAtHead","addAtIndex","deleteAtIndex","addAtHead","addAtTail","get","addAtHead","addAtIndex","addAtHead"],
         [[],[7],[2],[1],[3,0],[2],[6],[4],[4],[4],[5,0],[6]]),
    ]):
        print('Test', itest)
        obj = None
        for meth, arg in zip(meths, args):
            print(meth, arg)
            if meth == 'MyLinkedList':
                obj = MyLinkedList(*arg)
            else:
                print('Result:', getattr(obj, meth)(*arg))
            print(obj.toList())

test()

输出：

Test 0
MyLinkedList []
[]
addAtHead [2]
Result: None
[2]
deleteAtIndex [1]
Result: None
[2]
addAtHead [2]
Result: None
[2, 2]
addAtHead [7]
Result: None
[7, 2, 2]
addAtHead [3]
Result: None
[3, 7, 2, 2]
addAtHead [2]
Result: None
[2, 3, 7, 2, 2]
addAtHead [5]
Result: None
[5, 2, 3, 7, 2, 2]
addAtTail [5]
Result: None
[5, 2, 3, 7, 2, 2, 5]
get [5]
Result: 2
[5, 2, 3, 7, 2, 2, 5]
deleteAtIndex [6]
Result: None
[5, 2, 3, 7, 2, 2]
deleteAtIndex [4]
Result: None
[5, 2, 3, 7, 2]
Test 1
MyLinkedList []
[]
addAtHead [1]
Result: None
[1]
addAtTail [3]
Result: None
[1, 3]
addAtIndex [1, 2]
Result: None
[1, 2, 3]
get [1]
Result: 2
[1, 2, 3]
deleteAtIndex [1]
Result: None
[1, 3]
get [1]
Result: 3
[1, 3]
get [3]
Result: -1
[1, 3]
deleteAtIndex [3]
Result: None
[1, 3]
deleteAtIndex [0]
Result: None
[3]
get [0]
Result: 3
[3]
deleteAtIndex [0]
Result: None
[]
get [0]
Result: -1
[]
Test 2
MyLinkedList []
[]
addAtIndex [1, 0]
Result: None
[]
get [0]
Result: -1
[]
Test 3
MyLinkedList []
[]
addAtHead [7]
Result: None
[7]
addAtHead [2]
Result: None
[2, 7]
addAtHead [1]
Result: None
[1, 2, 7]
addAtIndex [3, 0]
Result: None
[1, 2, 7, 0]
deleteAtIndex [2]
Result: None
[1, 2, 0]
addAtHead [6]
Result: None
[6, 1, 2, 0]
addAtTail [4]
Result: None
[6, 1, 2, 0, 4]
get [4]
Result: 4
[6, 1, 2, 0, 4]
addAtHead [4]
Result: None
[4, 6, 1, 2, 0, 4]
addAtIndex [5, 0]
Result: None
[4, 6, 1, 2, 0, 0, 4]
addAtHead [6]
Result: None
[6, 4, 6, 1, 2, 0, 0, 4]

你如何处理 leetcode 中超出时间限制的错误？

How do you handle time limit exceeded errors in leetcode?

python

algorithm

linked-list

data-structures

python-3.x