测试人社区

数据结构与算法公开课一

递归

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)


def fibonacci2(n):
    # 使用空间换时间
    data = {}

    def fibonacci(n):
        if n == 0:
            return 0
        if n == 1:
            return 1

        if n in data:
            return data[n]
        else:
            r = fibonacci(n - 1) + fibonacci(n - 2)
            data[n] = r
            return r
    return fibonacci(n)


def test_fibonacci():
    assert fibonacci(6) == 8
    assert fibonacci(12) == 144
    assert fibonacci(100) == 354224848179261915075
    # 100 = 99 + 98 ==> 99 = 98 + 97


def test_fibonacci2():
    assert fibonacci2(6) == 8
    assert fibonacci2(12) == 144
    assert fibonacci2(100) == 354224848179261915075
    # 100 = 99 + 98 ==> 99 = 98 + 97

多叉树

from typing import List


class Node:
    def __init__(self, data):
        """
        多叉树
        :param data:
        """
        self.data = data
        # self.right self.left
        self.children: List[Node] = []

    def travel(self, node=None, depth=1, root=True):
        if root:
            node = self
        if node is None:
            return

        yield node, depth
        depth += 1
        for child in node.children:
            yield from self.travel(child, depth, False)
        depth -= 1

    def mindmap(self):
        content = []
        content.append('@startmindmap')
        for node, depth in self.travel():
            content.append(f'{"*" * depth} {node.data}')

        content.append('@endmindmap')
        return '\n'.join(content)


def test_mindmap():
    root = Node(0)
    node_1 = Node(1)
    node_2 = Node(2)
    node_3 = Node(3)
    node_4 = Node(4)
    node_5 = Node(5)
    node_6 = Node(6)

    node_4.children.append(node_6)

    node_3.children.append(node_4)
    node_3.children.append(node_5)

    node_1.children.append(node_2)
    node_1.children.append(node_3)

    root.children.append(node_1)
    print()
    max_depth = 0
    for node, depth in root.travel():
        print(' ' * depth + " " + str(node.data))

    print(root.mindmap())

思维导图

优惠券