不忘初心,
牢记使命。

Python版数据结构与算法

2021-05-13 大聪明 0评论 184 1喜欢

数据结构

引子

未来简史: 数据主义 Dataism

问题的求解: What Why How 基于有穷观点的能行方法

图灵机计算模型

算法和计算复杂性

可计算问题:算法的难易程度

不可计算问题:边界或极限

突破极限:SETI@home、光子计算、智慧众包科研项目

算法分析:计算资源消耗,何为计算资源?存储空间或内存,执行时间。

算法时间度量指标

问题的规模影响算法执行时间

数量级函数 大O表示法 O(n)

例子:T(n) = 5n^2 + 27n +1005 O(n^2)

其他因素: 最好 最差 平均

常见的大O数量级函数 O(1) log(n) O(n) n*log(n) n^2 n^3 2^n

"变位词"问题

abcd dcba

  1. 逐个对比 O(n^2)
  2. 排序对比 O(nlogn)
  3. 暴力穷尽 。。。。
  4. 计数比较 对每个字母出现的次数进行计数 最后对比 O(n) 空间换时间

Python数据类型的性能

让最常用的操作性能最好

pop 最好不要pop(0) 他要把所有的数据都后移一位 时间复杂度很高

线性结构Liner Structure

线性结构是一种有序数据项的集合,其中每个数据项都要唯一的前驱和后继。

数据项的增减方式不同构成了不同的数据结构

栈Stack

一种有次序的数据项集合。在栈中,数据项的加入和移除只发生在同一端。这一端叫栈顶top,另一端叫栈底base。

栈的特性:反转次序

操作

# ADT.py
"""
要掌握思想
栈和队列
"""
# 栈:先进后出的数据结构,栈顶和栈尾。随便选取列表的一端设置位栈顶或栈底。这里把最后一个元素选为栈顶,这种性能会好一点。
# 用列表实现:我们定义列表开始的位置为栈底,末尾为栈顶。
# Stack() 创建一个空栈。它不需要参数,并返回一个空栈。
# push()


class Stack(object):

    def __init__(self):
        self.items = []

    def push(self,item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        """从栈返回顶部项,但不会删除它。不需要参数,不修改栈。"""
        return len(self.items) - 1

    def isEmpty(self):
        return self.items == []

    def size(self):
        return len(self.items)


if __name__ == '__main__':
    stack = Stack()
    stack.push(1)
    stack.push(2)
    stack.push(3)
    print('栈顶元素下标',stack.peek())
    print(stack.isEmpty())
    print(f'元素个数{stack.size()}')

栈的应用:简单的括号匹配

括号必须正确匹配,

每个开括号“(” 必须对应一个闭括号 “)”;

要正确嵌套。

# 导入栈包
from ADT import Stack


def is_kuohao(s):
    # 创建一个空栈
    stack = Stack()

    for i in s:
        if i == '(':
            # 如果是左括号,入栈
            stack.push(i)
        else:
            # 如果是右括号,则出栈一个左括号,他们俩一对
            if stack.isEmpty():
                # 如果此时栈已空,则直接返回False,因为已经匹配不了了
                return False
            # 不为空才出栈
            stack.pop()

    return stack.isEmpty()


s = input()

print(is_kuohao(s))

栈的应用:混合括号匹配

"""
括号混合存在的情况
"""
# 导入栈包
from ADT import Stack


def match(a, b):
    opens = '{[('
    closes = '}])'
    return opens.index(a)==closes.index(b)


def par_check(s):
    # 创建一个空栈
    stack = Stack()

    for i in s:
        if i in '({[':
            # 如果是左括号,入栈
            stack.push(i)
        else:
            # 如果是右括号,则出栈一个左括号,并检测他们俩是不是一对
            if stack.isEmpty():
                # 如果此时栈已空,则直接返回False,因为已经匹配不了了
                return False
            # 不为空才出栈
            if not match(stack.pop(), i):
                return False

    return stack.isEmpty()


s = input()

print(par_check(s))

栈的应用:进制转换

"""
给定一个十进制数,把他转换成k进制
除k求余法
"""
from ADT import Stack


def digit(base, k):
    arr = '0123456789ABCDEF'
    res = ''
    stack = Stack()
    while base != 0:
        stack.push(arr[base % k])
        base = base // k
    while not stack.isEmpty():
        res += stack.pop()
    return int(res)


print(digit(100, 16))  # 64
print(int('64', 16))  # 100

栈的应用:表达式

中缀表达式:运算符在中间,例如A+B。如果含有其他运算符再要考虑优先级,优先级是人为规定的。

例如A+B*C,为了让计算机具有更强的辨识度,给表达式全部加上括号,这样就无需考虑运算符的优先级而只需考虑括号即可。

例如(A+(B*C)),即全括号表达式。

前缀表达式:为了方便优先级的表示,把运算符放在操作数的前边。

后缀表达式:为了方便优先级的表示,把运算符放在操作数的后边。

中缀表达式 前缀表达式 后缀表达式
A+B*C +A*BC ABC*+

前缀和后缀可以省去括号了。离运算符最近的先操作。计算机里通常勇后缀表达式。

中缀表达式转换位前缀表达式或后缀表达式

(A+(B*C))

看子表达式(B*C)的右括号,运算符一道右括号位置代替他,再删掉左括号得到后缀表达式。

通用转换

从左到右依次扫描,把操作符暂存到一个栈中

if 操作数 直接添加到后缀表达式的末尾

if 左括号 压入opstack栈顶

if 右括号 反复弹出opstack栈顶

操作符加入到输出列表末尾知道碰到左括号

if 操作符 压入opstack栈顶 要比较其与栈顶操作符的优先级 优先级高的在栈顶

"""后缀表达式"""
from ADT import Stack


def hou_ex(ex):
    res = ''
    prec = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 3}
    stack = Stack()
    for s in ex:
        if s not in '()+-*/':
            res += s
            res += ' '
        elif s == '(':
            stack.push(s)
        elif s == ')':
            opt = stack.pop()
            while opt != '(':
                res += opt
                res += ' '
                opt = stack.pop()
        elif s in '+-*/':
            while not stack.isEmpty() and prec[stack.peek()] > prec[s]:
                if stack.peek() == '(':
                    break
                res += stack.pop()
                res += ' '
            stack.push(s)
    while not stack.isEmpty():
        res += stack.pop()
        res += ' '
    return res


ex = list(input().strip().split())
print(hou_ex(ex))
# 11 + 2 * 3

后缀表达式求值

"""后缀表达式求值"""
from ADT import Stack


def compute(x, y, opt):
    if opt == '+':
        return x + y
    elif opt == '-':
        return x - y
    elif opt == '*':
        return x * y
    else:
        return x / y


def hou_value(ex):
    stack = Stack()
    for s in ex:
        if s not in '+-*/':
            stack.push(s)
        else:
            b = int(stack.pop())
            a = int(stack.pop())
            stack.push(compute(a, b, s))
    return stack.pop()


ex = list(input().strip().split())
print(hou_value(ex))
# 11 2 3 * +

队列Queue

队列是一种有次序 的集合,其特征是:新数据项的添加总发生在一端,尾端rear;现存数据项的移除发生在另一端,首端front。

# ADT.py
# 队列:先进先出。队头和队尾。
# 我们定义列表开始位置为队头,末尾为队尾。
class Queue(object):
    def __init__(self):
        self.items = []

    def enqueue(self,item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

    def isEmpty(self):
        return self.items == []

    def size(self):
        return len(self.items)


if __name__ == '__main__':

    q = Queue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())

约瑟夫问题

n个人做一圈,编号从1开始,第一个人手里有个东西,在自己手里放一秒后传给下一个人,每计时k秒后东西在谁手里谁就出局,最后剩下的为胜者。
到第k秒时就停止传,在他手里就是他,不往下一个人传。

"""
n个人做一圈,编号从1开始,第一个人手里有个东西,在自己手里放一秒后传给下一个人,每计时k秒后东西在谁手里谁就出局,最后剩下的为胜者。
到第k秒时就停止传,在他手里就是他,不往下一个人传。
"""
from ADT import Queue


def joseph(person, second):
    queue = Queue()
    for i in range(1, person+1):
        queue.enqueue(i)
    while queue.size() > 1:
        for j in range(second-1):
            queue.enqueue(queue.dequeue())
        queue.dequeue()
    return queue.dequeue()


n, k = map(int, input().split())
print(joseph(n, k))

模拟算法:打印任务

对象:打印任务、打印队列、打印机

过程:生成和提交打印任务

时间:

双端队列Deque

一种有次序的数据集,尾部和头部都可以进行数据项的增加和删除。

# ADT.py
# 双端队列:队列的头和尾都可插入数据或去除数据。提供栈和队列共有的属性。
class Deque():
    def __init__(self):
        self.items = []

    def addFront(self, item):
        self.items.insert(0, item)

    def addRear(self, item):
        self.items.append(item)

    def removeFront(self):
        return self.items.pop()

    def removeRear(self):
        return self.items.pop(0)

    def isEmpty(self):  
        return self.items == []

    def size(self):
        return len(self.items)


if __name__ == '__main__':

    dq = Deque()
    dq.addFront(1)
    dq.addFront(2)
    dq.addFront(3)

    # print(dq.removeFront())
    # print(dq.removeFront())
    # print(dq.removeFront())
    print(dq.removeRear())
    print(dq.removeRear())
    print(dq.removeRear())

回文检查

回文字符串左右读都一样:abssba

from ADT import Deque


def huiwen(s):
    deque = Deque()
    for i in s:
        deque.addFront(i)
    while deque.size() > 1:
        if deque.removeFront() != deque.removeRear():
            return False
    return True


s = input()
print(huiwen(s))

链表Link

Pyhton为我们提供了列表这种抽象数据类型。

链表:只保持前后位置,不要求数据项依次存放。

# ADT.py
"""
内存
计算机的作用:用来存储和运算二进制的数据
计算机如何计算1+2?
    将1和2的二进制类型的数据加载到计算机内存中,然后使用寄存器进行数值的预算
变量的概念:
    变量就是某一块内存
    内存空间是由两个默认属性:内存空间的大小(bit位,一个bit只能放一个二进制数,1字节是8bit),内存空间的地址。
    kb:1024byte.

顺序表:
    集合中存储的元素是有序的,顺序表可以分为两种形式:单数据类型和多数据类型。
    python中的列表和元组就是多数据类型的顺序表。
链表:相对于顺序表。
"""


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


class Link(object):
    def __init__(self):
        # 构造出一个空链表
        # _head存的只能是空或者第一个节点的地址
        self._head = None

    # 向链表的头部插入一个节点
    def add(self, item):
        # 创建一个新节点
        node = Node(item)
        node.next = self._head  # 先让新节点指向头节点指向的节点
        self._head = node  # 然后让头节点指向新的节点

    # 链表的遍历
    def travel(self):
        # _head在列表创建好后一定是不可变的
        cur = self._head
        while cur != None:
            print(cur.item)
            cur = cur.next

    def isEmpty(self):
        return self._head == None

    def size(self):
        cur = self._head
        count = 0
        while cur:
            count += 1
            cur = cur.next
        return count

    def append(self, item):
        """链表尾部添加元素"""
        node = Node(item)
        if self._head == None:
            """链表为空的话,需要单独处理,直接添加到头部"""
            self._head = node
            return
        cur = self._head
        while cur.next:
            cur = cur.next
        cur.next = node

    def insert(self, pos, item):
        """指定位置添加元素,下标从0开始"""
        cur = self._head
        node = Node(item)
        for i in range(pos - 1):
            cur = cur.next
        node.next = cur.next
        cur.next = node

    def remove(self, item):
        """删除指定节点"""
        cur = self._head
        pre = None
        if cur.item == item:
            # 删除的是第一个节点
            self._head = cur.next
            return
        while cur.next:
            pre = cur
            cur = cur.next
            if cur.item == item:
                pre.next = cur.next

    def search(self, item):
        """查找节点"""
        find = False
        cur = self._head
        while cur:
            if cur.item == item:
                find = True
                return find
            cur = cur.next
        return find

    def reverse(self):
        cur = self._head
        pre = None
        next_node = cur.next
        while cur:
            cur.next = pre
            pre = cur
            cur = next_node
            if cur:
                next_node = cur.next
        self._head = pre


if __name__ == '__main__':
    print('-' * 30)
    link = Link()
    link.add(3)
    link.add(4)
    link.travel()
    print('-' * 30)
    # print(link.isEmpty())
    # print(link.size())
    link.append(7)
    link.travel()
    print(link.search(7))
    print(link.search(1))
    print('-' * 30)
    link.insert(2, 9)
    link.travel()
    print('-' * 30)
    link.remove(9)
    link.travel()
    print('*' * 50)
    # 如何使用两个队列实现一个栈
    alist = [1, 2, 3, 4, 5]
    q1 = Queue()
    for i in alist:
        q1.enqueue(i)
    q2 = Queue()
    # 将q1中的n-1个值去除放出q2中
    while q1.size() > 0:
        while q1.size() > 1:
            q2.enqueue(q1.dequeue())
        print(q1.dequeue())
        q1, q2 = q2, q1
    # 如何实现将单链表倒置
    print('*' * 50)
    link1 = Link()
    link1.append(2)
    link1.append(3)
    link1.append(4)
    link1.append(5)
    link1.append(6)
    link1.travel()
    link1.reverse()
    link1.travel()

递归Recursion

将问题分解为规模更小的相同问题。

最小规模--调用自身--减小规模

递归三定律:

  1. 必须有一个基本结束条件
  2. 改变状态向基本结束条件演进
  3. 调用自身(解决小了规模的相同问题)

函数被调用时,系统会把现场数据压入到系统调用栈中。RecursionError:递归的层数太多,系统调用栈容量有限。调整:sys.setrecursionlimit(3000) 默认1000

递归可视化

用turtle画螺线:

import turtle


t = turtle.Turtle()


def draw(t, line):
    if line > 0:
        t.forward(line)
        t.hideturtle()
        t.right(90)
        draw(t, line-5)


draw(t, 100)
ts = turtle.getscreen()
ts.getcanvas().postscript(file="rtfm.eps")
turtle.done()

分形树:自相似递归图形

树:树干、左小树、右小树。

汉诺塔

将盘片塔从开始柱,经由中间柱,移动到目标柱。

先将上层N-1个盘子从开始经由目标柱移到中间柱;然后将第N个(最大的)盘子,从开始柱移到目标柱;

最后将放置在中间的N-1个盘子经由开始柱移到目标柱。

基本结束条件:一个盘片的移动问题。

def move_disk(disk, from_tower, to_tower):
    # 打印移动的方法
    print(f'把第{disk}个盘子从{from_tower}移动到{to_tower}去;')


def move_tower(height, from_tower, with_tower, to_tower):
    if height >= 1:
        # 第一步,先把n-1个盘子从开始经由目标柱移到中间柱
        move_tower(height-1, from_tower, to_tower, with_tower)
        # 第二步,将第N个(最大的)盘子,从开始柱移到目标柱
        move_disk(height, from_tower, to_tower)
        # 第三步,将放置在中间的N-1个盘子经由开始柱移到目标柱
        move_tower(height-1, with_tower, from_tower, to_tower)
        # 完成


move_tower(3, '#1', '#2', '#3')

探索迷宫

在出发位置寻找咪咕出口分为四种清苦递归:

从开始位置,行东走(如果能走)递归找出口,如果没有出口则向西。。。。。

维护一个map数组,记录走过的位置,走过的不能再走

分治策略

分而治之

把一个大问题,分为若干个小问题,小问题很容易解决,最后再有一个Merge方法合并文原始解

贪心策略

找零兑换问题

先从面额最大的货币开始找,慢慢往下找,但是对于一种特殊的货币就不行:25 21 5 1 63只需3个21就行啦。

可以用递归来解决,但是递归消耗的时间太长,我们会发现,有大量的重复计算。怎么雄安出这些重复计算呢。我们可以用一个表把计算过的中间结果保存起来,再计算之前查表看看是否已经计算过

"""
63分钱  币值有25分 10分 5分 1分  寻找最少的硬币数
"""


class Solution(object):

    def tan_xin(self, coin_kind, change):
        """
        贪心思想,绝大部分币种都生效,但是在处理一种特殊的币种时不生效,
        [1, 5, 10, 21, 25]  63  只需三张21分即可,但是仍会输出6
        :param coin_kind: list[int]
        :param change: int
        :return: int
        """
        coin_kind.sort(reverse=True)
        num = 0
        i = 0
        while i < len(coin_kind):
            # 如果当前所剩金额大于等于当前最大的零钱币种,就用它
            if change >= coin_kind[i]:
                change -= coin_kind[i]
                num += 1
            else:
                i += 1
        return num

    def recursion(self, coin_kind, change):
        """
        递归方法实现,但是这种会极其的耗时间,因为,我们会发现存在大量的重复计算
        怎么解决呢,开一个列表,记录已经寻找过的解,避免重复计算
        :param coin_kind: list[int]
        :param change: int
        :return: int
        """
        min_num = change
        if change in coin_kind:
            # 最小规模,直接返回1
            return 1

        for coin in coin_kind:
            if change >= coin:
                # 问题分解,去求减去coin后的找零最少硬币法,一直递归到change在coin_kind中,
                # 此时很容易直接求得coin的找零最少硬币数为1
                num = 1 + self.recursion(coin_kind, change-coin)
                if num < min_num:
                    # 记录每次递归得到的最小值返回即可
                    min_num = num

        return min_num

    def prune(self, coin_kind, change, coin_memo):
        """
        剪枝,去掉重复计算
        :param coin_kind:
        :param change:
        :param coin_memo:
        :return:
        """
        min_num = change
        if coin_memo[change] > 0:
            # 先查表,如果表中有,直接返回
            return coin_memo[change]

        if change in coin_kind:
            # 最小规模,直接返回1,记录最优解
            coin_memo[change] = 1
            return 1

        for coin in coin_kind:
            if change >= coin:
                num = 1 + self.prune(coin_kind, change-coin, coin_memo)
                if num < min_num:
                    min_num = num
                    # 记录最优解
                    coin_memo[change] = min_num

        return min_num


solution = Solution()
# print(solution.tan_xin([1, 5, 10, 25], 63))
print(solution.prune([1, 5, 10, 25], 63, [0] * 64))  # 0.1毫秒 巨大的提升
# print(solution.recursion([1, 5, 10, 25], 63))  # 大约40秒
# print(solution.tan_xin([1, 5, 10, 21, 25], 63))

发表评论 取消回复

电子邮件地址不会被公开。

请输入正确格式的qq邮箱
请输入以http或https开头的URL,格式如:https://libo_sober.top