10.2 רשימה מקושרת ורקורסיה פתרון

רשימה מקושרת - מימוש

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


class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, value) -> None:
        new_node = Node(value)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def prepend(self, value) -> None:
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node

    def delete(self, value) -> None:
        if not self.head:
            return
        if self.head.data == value:
            self.head = self.head.next
            return
        current = self.head
        while current.next:
            if current.next.data == value:
                current.next = current.next.next
                return
            current = current.next

    def print_list(self) -> None:
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")


ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.prepend(0)
ll.print_list()   # 0 -> 1 -> 2 -> 3 -> None
ll.delete(2)
ll.print_list()   # 0 -> 1 -> 3 -> None

רקורסיה - פיבונצ'י איטרטיבי

def fib_recursive(n: int) -> int:
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)


def fib_iterative(n: int) -> int:
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b


import time

n = 35
start = time.time()
print(fib_recursive(n))
print(f"recursive: {time.time() - start:.3f}s")

start = time.time()
print(fib_iterative(n))
print(f"iterative: {time.time() - start:.6f}s")

הגרסה האיטרטיבית מהירה בהרבה כי הרקורסיבית מחשבת את אותם ערכים שוב ושוב.

שאלות Leetcode

אין פתרון קוד כאן - פתרו בעצמכם ב-Leetcode. אם תקועים, קראו את הפתרון הרשמי ואז כתבו אותו מחדש בלי להסתכל.