程序员必须掌握的数据结构 2

1,266 阅读2分钟

无论是任何程序员,不论是算法,还是其他,都需要掌握一定的数据结构。本文以最优雅的方式,基于Python,完成算法,不要问,背下来就好。代码量更少,更好背。

源码:github.com/SpikeKing

第2篇 栈与队列:括号匹配(栈)、二进制转换(栈)、烫手的山芋(队列)、回文(双端队列)、反转链表(链表);


1. 括号匹配

括号匹配,判断字符串中括号是否匹配。当为左括号时入栈,为右括号时出栈,最后,判断栈是否为空,为空则括号匹配,否则不匹配。Python的list就可以实现的功能。算法共14行。

def par_checker(symbol_str):
    """
    括号匹配,list包含栈的功能
    append是添加,pop是删除
    https://docs.python.org/2/tutorial/datastructures.html
    14行
    :param symbol_str: 符号字符串
    :return: 是否
    """
    s = list()  # python的list可以实现stack功能
    idx = 0
    while idx < len(symbol_str):
        symbol = symbol_str[idx]
        if symbol == '(':
            s.append(symbol)
        elif symbol == ')':
            s.pop()
        idx += 1
    if not s:
        return True
    else:
        return False


def test_of_par_checker():
    print(par_checker('(())'))
    print(par_checker('((()'))
    print(par_checker('(a)()((()))'))


if __name__ == '__main__':
    test_of_par_checker()

2. 二进制转换

将二进制数除以base,输入队列中,再倒序输出,恰好是的功能。将数字添加至字符串中,即可。算法共11行。

def base_converter(num, base):
    """
    将二进制转换为其他进制
    :param num: 数字
    :param base: 基数
    :return: 数字的字符串
    """
    digs = '0123456789ABCDEF'  # 支持16位
    base_stack = list()

    while num > 0:
        rem = num % base
        base_stack.append(rem)
        num //= base  # 递减一直到0

    res_str = ''  # 转换为str
    while base_stack:
        res_str += digs[base_stack.pop()]

    return res_str


if __name__ == '__main__':
    print(base_converter(25, 2))
    print(base_converter(25, 16))

3. 烫手的山芋

点名,点到谁,谁出圈,循环使用队列,最后一个出队。算法共10行。

from queue import Queue


def hot_potato(name_list, num):
    """
    烫手的山芋,循环去除
    :param name_list: 名字列表
    :param num: 循环数
    :return: 最后剩下的人
    """
    q = Queue()

    for name in name_list:
        q.put(name)

    while q.qsize() > 1:
        for i in range(num - 1):  # 每次都死一个循环,最后一个死亡
            live = q.get()
            q.put(live)
        dead = q.get()  # 输出死亡
        print('Dead: {}'.format(dead))

    return q.get()


def test_of_hot_potato():
    name_list = ['Bill', 'David', 'Susan', 'Jane', 'Kent', 'Brad']
    num = 3
    print(hot_potato(name_list, num))


if __name__ == '__main__':
    test_of_hot_potato()

4. 回文

双端队列,队首和队尾的输出是否相等。算法共12行。

from collections import deque


def pal_checker(a_str):
    """
    回文,双端队列
    :param a_str: 输入字符串
    :return: 是否回文
    """
    q_char = deque()

    for ch in a_str:
        q_char.append(ch)

    equal = True

    # while的终止条件长度或者Bool
    while len(q_char) > 1:
        first = q_char.pop()
        last = q_char.popleft()
        if first != last:
            equal = False
            break

    return equal


def test_of_pal_checker():
    print(pal_checker('lsdkjfskf'))
    print(pal_checker('radar'))


if __name__ == '__main__':
    test_of_pal_checker()

5. 链表反转

链表反转,prev_node保留头结点,临时变量next_node,保留当前结点之后的结点。算法共8行。

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


def reverse_list(node_head):
    """
    链表逆序,交换链表
    :param node_head: 链表头
    :return: 新的链表的头结点
    """
    prev_node = None

    while node_head:
        next_node = node_head.next_node
        node_head.next_node = prev_node
        prev_node = node_head
        node_head = next_node

    return prev_node


def init_list():
    n1 = Node(1)
    n2 = Node(2)
    n3 = Node(3)
    n4 = Node(4)
    n5 = Node(5)
    n1.next_node = n2
    n2.next_node = n3
    n3.next_node = n4
    n4.next_node = n5
    return n1


def show_list(node_head):
    head = node_head
    while head:
        print(head.data, end=' ')
        head = head.next_node


def test_of_reverse_list():
    head_node = init_list()
    show_list(head_node)
    print()
    head_node = reverse_list(head_node)
    show_list(head_node)


if __name__ == '__main__':
    test_of_reverse_list()

OK, that's all! Enjoy it!