从零开始的Python ACM Ch.2：时间复杂度、栈、面向对象及链表

列表与字典的时间复杂度

列表的ls.append()复杂度是O(n)，字典的插入dt['key'] = value的复杂度是O(1)。Python自带的字典排序ls.sort()复杂度是O(nlogn)（这个排序算法是用C语言写的，基本上自己在Python里面写的排序算法都没有它快

栈(Stack)

基本操作：

• 压栈 stack.append(element)
• 出栈 del stack[-1]
• 判断是否为空 len(stack) == 0

面向对象的Python编程

以栈对象为例

class Stack:
    def __init__(self, x, y):		# 构造类里面的函数，在每次实例化的同时会自动调用__init__函数
        self.x = x
        self.y = y
        self.summary = x + y
s = Stack(3, 4)	# 得到一个Stack类型的实例（实例化）
print(s.x, s.y, s.summary)

'''
=== Output ===
3 4 7
'''

更深一步，在对象里面定义对象的方法

class Stack:
    def __init__(self, x, y):		# 构造类里面的函数，在每次实例化的同时会自动调用__init__函数
        self.x = x
        self.y = y

    def summary(self):
        return self.x + self.y

    def reset(self):
        self.x = 0
        self.b = 0


s = Stack(3, 4)  # 得到一个Stack类型的实例（实例化）
print(s.summary())

'''
=== Output ===
7
'''

例题

创建一个类型Rect（矩形），能执行以下代码

r1 = Rect(10, 20)
print(r1.width)		# 10
print(r1.height)	# 20
print(r1.area())	# 200
print(r1.length())	# 60

r2 = Rect(5, 6)
print(r2.area())

我的题解：

class Rect:
    def __init__(self, width, height):
        self.width = width
        self.height = height

    def area(self):
        return self.width * self.height

    def length(self):
        return (self.width + self.height) * 2


r1 = Rect(10, 20)
print(r1.width)		# 10
print(r1.height)  # 20
print(r1.area())  # 200
print(r1.length())  # 60

r2 = Rect(5, 6)
print(r2.area())

'''
=== Output ===
10
20
200
60
30
'''

例题：使用列表模拟栈

class Stack:
    def __init__(self):
        self.data = []

    def enquen(self, value):
        self.data.append(value)
    
    def dequen(self):
        value = self.data[-1]
        del self.data[-1]
        return value

    def isEnpty(self):
        return len(self.data) == 0

对栈进行操作：

import random

class Stack:
    def __init__(self):
        self.data = []

    def enquen(self, value):
        self.data.append(value)
    
    def dequen(self):
        value = self.data[-1]
        del self.data[-1]
        return value

    def isEmpty(self):
        return len(self.data) == 0

if __name__ == '__main__':
    stack = Stack()
    for i in range(100):
        stack.enquen(random.randint(0,100))
    print(stack.data)
    for i in range(10):
        value = stack.dequen()
        print(value, end=' ')
    print('\n')
    print(stack.data)
    
'''
=== Output ===
[3, 88, 78, 41, 28, 81, 33, 91, 86, 17, 57, 39, 17, 17, 98, 69, 65, 86, 83, 60, 67, 10, 95, 8, 66, 37, 10, 64, 41, 79, 39, 57, 32, 44, 62, 28, 32, 75, 41, 42, 87, 8, 7, 82, 85, 54, 2, 13, 96, 70, 1, 25, 47, 10, 75, 29, 92, 60, 29, 73, 24, 76, 5, 70, 62, 5, 85, 54, 25, 44, 37, 53, 11, 39, 25, 67, 37, 6, 99, 58, 97, 33, 26, 35, 50, 73, 48, 49, 16, 89, 2, 86, 28, 10, 89, 91, 1, 81, 9, 26]
26 9 81 1 91 89 10 28 86 2

[3, 88, 78, 41, 28, 81, 33, 91, 86, 17, 57, 39, 17, 17, 98, 69, 65, 86, 83, 60, 67, 10, 95, 8, 66, 37, 10, 64, 41, 79, 39, 57, 32, 44, 62, 28, 32, 75, 41, 42, 87, 8, 7, 82, 85, 54, 2, 13, 96, 70, 1, 25, 47, 10, 75, 29, 92, 60, 29, 73, 24, 76, 5, 70, 62, 5, 85, 54, 25, 44, 37, 53, 11, 39, 25, 67, 37, 6, 99, 58, 97, 33, 26, 35, 50, 73, 48, 49, 16, 89]
'''

例题：匹配括号

已知一串由小括号( )组成的字符串，试判断该字符串中的括号组合是否合法

我的题解（时间复杂度O(n^2)，因为replace要先查找再替换，进行了两次遍历：

s = ()()()(((())))))()
result = -1

while True:
    if "()" not in s:
        result = False
        break
    if len(s) == 0:
        result = True
        break
    s.replace('()','')
print(result)

优化版（利用栈的特性）：

class Stack:
    def __init__(self):
        self.data = []

    def enquen(self, value):
        self.data.append(value)

    def dequen(self):
        value = self.data[-1]
        del self.data[-1]
        return value

    def isEmpty(self):
        return len(self.data) == 0


s = '()()()(((())))))()'

if __name__ == '__main__':
    result=-1
    stack=Stack()
    for c in s:
        if c == '(':
            stack.enquen('(')
        else:
            if stack.isEmpty():
                result=False
                break
            stack.dequen()
        result=stack.isEmpty()
    print(result)

例题：匹配括号（升级版）

在上一题的基础上，括号不只有小括号了，还有中括号[]和花括号{}，同样判断括号对是否合法

class Stack:
    def __init__(self):
        self.data = []

    def enquen(self, value):
        self.data.append(value)

    def dequen(self):
        value = self.data[-1]
        del self.data[-1]
        return value

    def isEmpty(self):
        return len(self.data) == 0


s = '()(((())))))){{}}}}[[]]]]]])'

if __name__ == '__main__':
    result = -1
    stack = Stack()
    for c in s:
        if c in "([{":
            stack.enquen(c)
        else:
            if stack.isEmpty():
                result = False
                break
            value = stack.dequen()
            if (c == ')' and value == '(') or (c == ']' and value == '[') or (c == '}' and value == '{'):
                pass
            else:
                result = False
                break
        result = stack.isEmpty()
    print(result)

all()/any()的用法

官方说明

all()

Return True if bool(x) is True for all values x in the iterable.

If the iterable is empty, return True.

=========================================================================

any()

Return True if bool(x) is True for any x in the iterable.

If the iterable is empty, return False.

应用举例

dt = {1: 0, 2: 0, 3: 1}
print(all(dt.values()))
print(any(dt.values()))

'''
=== Output ===
False
True
'''

因为字典里面不全是1，在Python里面，1代表True，不全为1所以为False，但是对于any函数，里面一旦出现了True就返回True，所以这里是True

链表

链表里面的基本单位是结点(node)，单链表只存储值和下一节点的位置，双链表保存到一个上一节点的位置

class Node:		# 单链表
    def __init__(self, value, next):
        self.value = value
        self.next = next
        
class Node:		# 双链表
    def __init__(self, value, prev, next):
        self.value = value
        self.next = next
        self.prev = prev

用双链表模拟栈

class Node:		# 双链表
    def __init__(self, value, prev = None, next = None):
        self.value = value
        self.prev = prev
        self.next = next
        
class Stack:
    def __init__(self):
        self.tail = None
        
    def enquen(self, value):
        node = Node(value)
        node.prev = self.tail
        if self.tail:
            self.tail.next = node
            self.tail = node

    def dequen(self):
        self.tail = self.tail.prev
        if self.tail:
        	self.tail.next = None
	
    def isEmpty(self):
        self.tail == None