数据结构与算法学习_Python_笔记
数据结构和算法是计算机技术的基本功之一，北京大学的课程深入浅出，使用Python作为载体简化了编程难度。今天快速浏览了1-17，特将笔记整理如下：
1、针对变位词判断问题，总结了4种算法，并分析其计算复杂度与空间复杂度。
2、针对Python数据类型列表与字典，对其性质、性能、实现进行了解。
3、线性结构初探-栈。Stack。使用栈编写括号识别算法。
'''1 变位词判断问题'''
#写一个目Bool函数判断单词是否为变位关系
#假定不存在大小写问题且长度相等
#方法1 逐字符查询
#单词1的字符依次在2中检查是否存在，每个都找到是变位词，有一个
#找不到就不是变位词
#Python中字符串不可变，先复制到列表list中
def anagramSolution(s1,s2):
alist=list(s2)
pos1=0
stillOK=True
while pos1<len(s1) and stillOK:#对单词1中的每一个字符
pos2=0
found=False
while pos2< len(alist) and not found:#依次查找单词2中每一个字符
if s1[pos1]==s2[pos2]:
found=True
else:
pos2+=1#found
if found:
alist[pos2]=pos1+1#找到，做标记
else:
stillOK=False
pos1+=1
return stillOK
s1="wjk1"
s2="1wkj"
s3="1wje"
print(anagramSolution(s1,s2),anagramSolution(s1,s3))
#每个字符的对比次数1，2，。。。，n，共1/2n(n+1),O(n^2)
#方法2 排序比较
#各自按字母顺序排序，再逐字符比较
def anagramS2(s1,s2):
alist1=list(s1)
alist2=list(s2)
alist1.sort()#实际上排序耗时O(nlogn)以上
alist2.sort()
pos=0
match=True
while pos<len(s1) and match:
if alist1[pos]!=alist2[pos]:#只有一个循环O(n)
match=False
else:
pos+=1
return match
print(anagramS2(s1,s2),anagramS2(s1,s3))
#排序比较的数量级就是排序的数量级
#方法3： 暴力法
#穷尽s1字符全排列，看s2是否出现
#n个字符全排有n!种可能
#方法4 计数比较
#26个字母出现次数都相同，则一定是变位词
def anagramS3(s1,s2):
c1=[0]*26#列表扩张方法
c2=[0]*26
for i in range(len(s1)):
pos=ord(s1[i])-ord('a')#定位到s1中第i个字符相对于a的位置
c1[pos]+=1#计数
for i in range(len(s2)):
pos=ord(s2[i])-ord('a')#定位到s2中第i个字符相对于a的位置
c2[pos]+=1#计数
j=0
stillOK=True
while j<26 and stillOK:
if c1[j]!=c2[j]:
stillOK=False
else:
j+=1
return stillOK
print(anagramS2(s1,s2),anagramS2(s1,s3))
#O(n),2n+26 无敌
#依赖两个长度为26的计数器列表，需要更多存储空间-空间换时间
'''对比Python中list和dict数据类型的性能'''
#dict: add b[k]=v delete-pop has_key update b[k] copy
#List: v=a[i] a[i]=v, O(1); lst.append(v) O(1); lst+=[v] O(n+k)
#list.sort() O(nlogn)
#python list.pop(i)的实现是i后元素向前挪位复制，保证按索引取值和赋值很快O(1)
#dict从key取值，取值赋值，contain(in)最快
#in操作在字典中不随大小增长
#有序数据项的集合，每个数据项都有唯一的前驱和后继
#每个项都有唯一的【前驱】和【后继】
#左端右端，顶端底端
#有的只允许一端添加，有的双端可添加移除，有的中间位置也可
#四种基本结构，共同点是数据项之间只存在先后次序关系
#栈Stack-抽象数据类型
#只在一端加入和移除，后进先出
#离栈底越近保存时间越长-反转次序
#例如浏览器的后退，word的undo
"""
Stack()
push(item)
pop()
peek()窥视栈顶数据项
isEmpty()
size()
"""
#将Stack实现为Python的一个class，选用list来实现
#list[0] list[-1]末端设为栈底
class Stack:
def __init__(self):
self.items=[]
def isEmpty(self):
return self.items==[]
def push(self,item):
self.items.append(item)
# self.items.insert(0,item)-栈顶首端，复杂度o（n）
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
s=Stack()
s.push('a')
s.push(3)
print(s.peek())
#栈的应用
#括号匹配
#最新的左括号应该匹配第一个右括号
def parCheck(str1):#str假设只有(()))
s=Stack()
balanced=True
index=0
while index<len(str1) and balanced:
symbol=str1[index]
if symbol in "([{":
s.push(symbol)
else:
if s.isEmpty():
balanced=False
else:
if (s.peek()=="[" and symbol=="]") or (s.peek()=="{"and symbol=="}") or (s.peek()=="(" and symbol==")"):
s.pop()
else:
balanced=False
index+=1
if balanced and s.isEmpty():
return True
else:
return False
print(parCheck("({{[]}})"),parCheck("([))"))
