数据结构
引子
未来简史： 数据主义 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
- 逐个对比 O(n^2)
- 排序对比 O(nlogn)
- 暴力穷尽 。。。。
- 计数比较 对每个字母出现的次数进行计数 最后对比 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
将问题分解为规模更小的相同问题。
最小规模--调用自身--减小规模
递归三定律：
- 必须有一个基本结束条件
- 改变状态向基本结束条件演进
- 调用自身（解决小了规模的相同问题）
函数被调用时，系统会把现场数据压入到系统调用栈中。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))
