python数据结构
·
python数据结构
Welcome to unique_Hang’s blog.
鲁迅说过：看unique_Hang博客的人颜值都很高！
打不开图片可以鼠标右键点击“复制图片地址”在新窗口中打开
作者邮箱：unique_hang@qq.com
喜欢的小伙伴可以关注我的b站账号(https://space.bilibili.com/290100464)
1.栈 -> 列表
class Stack():
def __init__(self):
self.items = []
def push(self,item):
self.items.append(item)
def peek(self):
return self.items[len(self.items)-1]
def isEmpty(self):
return self.items == []
def size(self):
return len(self.items)
def pop(self):
return self.items.pop()
括号匹配
左括号入栈，右括号与栈顶比较
def matchs(open,close):
opens = '([{'
closes = ')]}'
return opens.index(open) == closes.index(close)
def parChecker(symbolStoring):
S=Stack()
for i in symbolStoring:
if i in '([{':
S.push(i)
else:
if S.isEmpty():
return False
top = S.pop()
if not matchs(top,i):
return False
if S.isEmpty():
return True
print( parChecker('(([[({})]])){}'))
后缀表达式
eg:输入：tokens = [“2”,“1”,“+”,“3”,“*”]输出：9。解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
遇到数字入栈，遇到符号则弹出栈中两个数字进行运算。
class Stack:
def __init__(self):
self.items = []
def push(self,item):
self.items.append(item)
def pop(self):
return self.items.pop()
def size(self):
return len(self.items)
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
mystack = Stack()
for i in tokens:
if i in '+-*/':
a= int(mystack.pop())
b= int(mystack.pop())
if i == '+':
tmp = b+a
if i == '-':
tmp = b-a
if i == '*':
tmp = b*a
if i == '/':
tmp = b/a
mystack.push(tmp)
else:
mystack.push(i)
return int(mystack.pop())
2.队列 -> 列表
队列是一种有次序的数据集合，其特征是：新数据项的添加总发生在一端（通常称为“尾rear”）端；而现存数据项的移除总发生在另一端（通常称为“首front”）
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self,item):
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
热土豆问题
队首始终是持有土豆的人，传递了num次后，将队首的人移除，不再入队如此反复，直到队列中剩余1人
####热土豆问题###
def hotPotato(namelist,num):
Q = Queue()
for name in namelist:
Q.enqueue(name)
while Q.size() > 1:
for i in range(num):
tmp = Q.dequeue()
Q.enqueue(tmp)
Q.dequeue()
return Q.dequeue()
print(hotPotato(['1','2','3','4','5','6'],5))
3.双端队列 -> 列表
双端队列Deque是一种有次序的数据集，跟队列相似，其两端可以称作“首“”“尾”，但deque数项可从首入也以中数据项既可以从队首加入，也可以从队尾加入；数据项也可以从两端移除。
class Deque():
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def addRear(self,item):
self.items.insert(0,item)
def addFront(self,item):
self.items.append(item)
def size(self):
return len(self.items)
def removeRear(self):
return self.items.pop(0)
def removeFront(self):
return self.items.pop()
回文问题
#####回文#####
def huiwen(lst):
DQ = Deque()
for i in lst:
DQ.addRear(i)
while DQ.size() > 1:
if DQ.removeRear() != DQ.removeFront():
return False
return True
print(huiwen('tootoot'))
4.无序表的链表
一种数据项按照相对位置存放的数据集
class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
class UnorderedList:
def __init__(self):
self.head = None #self.head是Node类型
def isEmpty(self):
return self.head == None
def add(self,item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
def length(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
def search(self,item):
current = self.head
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
def remove(self,item):
current = self.head
previous = None
found = False
while not found:
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
if previous == None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())
5.有序表
class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
class OrderedList:
def __init__(self):
self.head = None
def search(self,item):
current = self.head
found = False
stop = False
while current != None and not found and not stop:
if current.getData() == item:
found = True
else:
if current.getData() > item:
stop = True
else:
current = current.getNext()
return found
def add(self,item):
current = self.head
previous = None
stop = False
while current != None and not stop:
if current.getData() > item:
stop = True
else:
previous = current
current = current.getNext()
temp = Node(item)
if previous == None:
temp.setNext(self.head)
self.head = temp
else:
temp.setNext(current)
previous.setNext(temp)
def isEmpty(self):
return self.head == None
def length(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
def traverse(self):
current = self.head
while current != None:
print(current.getData())
current = current.getNext()
6.递归
递归三定律：
1，递归算法必须有一个基本结束条件（最小规模问题的直接解决）
2，递归算法必须能改变状态向基本结束条件演进（减小问题规模）
3，递归算法必须调用自身（解决减小了规模的相同问题）
7.查找
顺序查找:o(n)
有序表
def orderedSequentialSearch(alist, item):
pos = 0
found = False
stop = False
while pos < len(alist) and not found and not stop:
if alist[pos] == item:
found = True
else:
if alist[pos] > item:
stop = True
else:
pos = pos+1
return found
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(orderedSequentialSearch(testlist, 3))
print(orderedSequentialSearch(testlist, 13))
无序表
def sequentialSearch(alist, item):
pos = 0
found = False
while pos < len(alist) and not found:
if alist[pos] == item:
found = True
else:
pos = pos+1
return found
testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 3))
print(sequentialSearch(testlist, 13))
二分查找:o(log n)
适用的前提：有序表
def binarySearch(alist, item):
first = 0
last = len(alist)-1
found = False
while first<=last and not found:
midpoint = (first + last)//2
if alist[midpoint] == item:
found = True
else:
if item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1
return found
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binarySearch(testlist, 3))
print(binarySearch(testlist, 13))
散列查找：o(1) -> 字典
实现从数据项到存储槽名称的转换的，称为散列函数
有一种常用的散列方法是“求余数”，将数据项除以散列表的大小，得到的余数作为槽号。
冲突解决方案：
解决散列的一种方法就是为冲突的数据项再找一个开放的空槽来保存，最简单的就是从冲突的槽开始往后扫描，直到碰到一个空槽 ，如果到散列表尾部还未找到，则从首部接着扫描。
- 线性探测 ：数据项位置+1
- 跳跃式探测：数据项位置+n。注意的是skip的取值，不能被散列表大小整除，否则会产生周期，造成很多空槽永远无法探测到
- 数据项链：将容纳单个数据项的槽扩展为容纳数据项集合（或者对数据项链表的引用）
#简单的线性探测
class HashTable:
def __init__(self):
self.size = 11
self.slots = [None] * self.size
self.data = [None] * self.size
def put(self,key,data):
hashvalue = self.hashfunction(key,len(self.slots))
if self.slots[hashvalue] == None:
self.slots[hashvalue] = key
self.data[hashvalue] = data
else:
if self.slots[hashvalue] == key:
self.data[hashvalue] = data #replace
else:
nextslot = self.rehash(hashvalue,len(self.slots))
while self.slots[nextslot] != None and \
self.slots[nextslot] != key:
nextslot = self.rehash(nextslot,len(self.slots))
if self.slots[nextslot] == None:
self.slots[nextslot]=key
self.data[nextslot]=data
else:
self.data[nextslot] = data #replace
def hashfunction(self,key,size):
return key%size
def rehash(self,oldhash,size):
return (oldhash+1)%size
def get(self,key):
startslot = self.hashfunction(key,len(self.slots))
data = None
stop = False
found = False
position = startslot
while self.slots[position] != None and \
not found and not stop:
if self.slots[position] == key:
found = True
data = self.data[position]
else:
position=self.rehash(position,len(self.slots))
if position == startslot:
stop = True
return data
def __getitem__(self,key):
return self.get(key)
def __setitem__(self,key,data):
self.put(key,data)
H=HashTable()
H[54]="cat"
H[26]="dog"
H[93]="lion"
H[17]="tiger"
H[77]="bird"
H[31]="cow"
H[44]="goat"
H[55]="pig"
H[20]="chicken"
print(H.slots)
print(H.data)
print(H[20])
print(H[17])
H[20]='duck'
print(H[20])
print(H[99])
8.排序算法
冒泡排序:o(n^2)
每趟包括了多次两两相邻比较，并将逆序的数据项互换位置，最终能将本趟的最大项就位.
优势：无需任何额外的存储空间开销
def bubbleSort(alist):
for passnum in range(len(alist)-1,0,-1):
for i in range(passnum):
if alist[i]>alist[i+1]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp
alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)
选择排序:o(n^2)
每趟仅进行1次交换，记录最大项的所在位置，最后再跟本趟最后一项交换
def selectionSort(alist):
for fillslot in range(len(alist)-1,0,-1):
positionOfMax=0
for location in range(1,fillslot+1):
if alist[location]>alist[positionOfMax]:
positionOfMax = location
temp = alist[fillslot]
alist[fillslot] = alist[positionOfMax]
alist[positionOfMax] = temp
alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)
插入排序:o(n^2)
插入排序维持一个已排好序的子列表，其位置始终在列表的前部，然后逐步扩大这个子列表直到全表
具体思路：
需要让31插入，先于93比较，93向后挪，再与77比较，77向后挪……以此类推
def insertionSort(alist):
for index in range(1,len(alist)):
currentvalue = alist[index]
position = index
while position>0 and alist[position-1]>currentvalue:
alist[position]=alist[position-1]
position = position-1
alist[position]=currentvalue
alist = [54,26,93,17,77,31,44,55,20]
insertionSort(alist)
print(alist)
谢尔排序:o(n^1.5)
谢尔排序以插入排序作为基础，对无序表进行“间隔”划分子列表，每个子列表都执行插入排序
子列表的间隔一般从n/2开始，每趟倍增：n/4, n/8……直到1
eg:间隔为3的子列表，子列表分别插入排序后的整体状况更接近有序。（每一行黑色的为一个子列表）
def shellSort(alist):
sublistcount = len(alist)//2
while sublistcount > 0:
for startposition in range(sublistcount):
gapInsertionSort(alist,startposition,sublistcount)
print("After increments of size",sublistcount,
"The list is",alist)
sublistcount = sublistcount // 2
def gapInsertionSort(alist,start,gap):
for i in range(start+gap,len(alist),gap):
currentvalue = alist[i]
position = i
while position>=gap and alist[position-gap]>currentvalue:
alist[position]=alist[position-gap]
position = position-gap
alist[position]=currentvalue
alist = [54,26,93,17,77,31,44,55,20]
shellSort(alist)
print(alist)
归并排序:o(n*log n)
归并排序是递归算法，思路是将数据表持续分裂为两半，对两半分别进行归并排序
- 递归的基本结束条件是：数据表仅有1个数据项，自然是排好序的；
- 缩小规模：将数据表分裂为相等的两半，规模减为原来的二分之一
- 调用自身：将两半分别调用自身排序，然后将分别排好序的两半进行归并，得到排好序的数据表
缺点：使用了额外1倍的存储空间用于归并。
def mergeSort(alist):
print("Splitting ",alist)
if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i=0
j=0
k=0
while i<len(lefthalf) and j<len(righthalf):
if lefthalf[i]<righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1
while i<len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1
while j<len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
print("Merging ",alist)
alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)
快速排序：o(n*log n)
快速排序是一个递归算法，思路是依据一个“中值”数据项来把数据表分为两半：小于中值的一半和大于中值的一半，然后每部分分别进行快速排序（递归） 。
递归三要素”如下 ：
- 基本结束条件：数据表仅有1个数据项，自然是排好序的
- 缩小规模：根据“中值”，将数据表分为两半，最好情况是相等规模的两半
- 调用自身：将两半分别调用自身进行排序（排序基本操作在分裂过程中）
def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1)
def quickSortHelper(alist,first,last):
if first<last:
splitpoint = partition(alist,first,last)
quickSortHelper(alist,first,splitpoint-1)
quickSortHelper(alist,splitpoint+1,last)
def partition(alist,first,last):
pivotvalue = alist[first]
leftmark = first+1
rightmark = last
done = False
while not done:
while leftmark <= rightmark and \
alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1
while alist[rightmark] >= pivotvalue and \
rightmark >= leftmark:
rightmark = rightmark -1
if rightmark < leftmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp
temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp
return rightmark
alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)
“堆排序”算法：O(nlog n)
二叉堆来进行排序 ，详见“树 -> 优先队列”
9.树
嵌套列表法
嵌套列表实现二叉树：[root,left,right]
优点：子树的结构与树相同，是一种递归数据结构很容易扩展到多叉树，仅需要增加列表元素即可 。
def BinaryTree(r):
return [r, [], []]
def insertLeft(root,newBranch):
t = root.pop(1)
if len(t) > 1:
root.insert(1,[newBranch,t,[]])
else:
root.insert(1,[newBranch, [], []])
return root
def insertRight(root,newBranch):
t = root.pop(2)
if len(t) > 1:
root.insert(2,[newBranch,[],t])
else:
root.insert(2,[newBranch,[],[]])
return root
def getRootVal(root):
return root[0]
def setRootVal(root,newVal):
root[0] = newVal
def getLeftChild(root):
return root[1]
def getRightChild(root):
return root[2]
r = BinaryTree(3)
insertLeft(r,4)
insertLeft(r,5)
insertRight(r,6)
insertRight(r,7)
l = getLeftChild(r)
print(l)
setRootVal(l,9)
print(r)
insertLeft(l,11)
print(r)
print(getRightChild(getRightChild(r)))
链表实现
class BinaryTree:
def __init__(self,rootObj):
self.key = rootObj
self.leftChild = None
self.rightChild = None
def insertLeft(self,newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t
def insertRight(self,newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t
def getRightChild(self):
return self.rightChild
def getLeftChild(self):
return self.leftChild
def setRootVal(self,obj):
self.key = obj
def getRootVal(self):
return self.key
r = BinaryTree('a')
print(r.getRootVal())
print(r.getLeftChild())
r.insertLeft('b')
print(r.getLeftChild())
print(r.getLeftChild().getRootVal())
r.insertRight('c')
print(r.getRightChild())
print(r.getRightChild().getRootVal())
r.getRightChild().setRootVal('hello')
print(r.getRightChild().getRootVal())
二叉树的遍历
三种遍历方式：
- 前序遍历（preorder）：先访问根节点，再递归地前序访问左子树、最后前序访问右子树；
- 中序遍历（inorder）：先递归地中序访问左子树，再访问根节点，最后中序访问右子树；
- 后序遍历（postorder）：先递归地后序访问左子树，再后序访问右子树，最后访问根节点。
二叉树最大深度
深度优先搜索，计算左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为 ：max(l,r)+1 ，递归计算。
def deepfind(tree):
if tree:
leftdeep = deepfind(tree.left)
rightdeep = deepfind(tree.right)
return max(leftdeep,rightdeep)+1
else:
return 0
优先队列
但在优先队列内部，数据项的次序却是由“优先级”来确定 ，高优先级的数据项排在队首，而低优先级的数据项则排在后面。这样，优先队列的入队操作就比较复杂，需要将数据项根据其优先级尽量挤到队列前方。
二叉堆Binary Heap实现优先队列（入队、出队复杂度都为o(log n)）
-
insert(key)：新key加在列表末尾，显然无法保持“堆”次序虽然对其它路径的次序没有影响，但对于其到根的路径可能破坏次序 。需要将新key沿着路径来“上浮”到其正确位置注意：新key的“上浮”不会影响其它路径节点的“堆”次序 。
-
delMin()：移走整个堆中最小的key:根节点heapList[1]，将新的根节点沿着一条路径“下沉”，直到比两个子节点都小 ，如果比子节点大，那么选择较小的子节点交换下沉 。
-
buildHeap(lst)方法：从无序表生成“堆”
用“下沉”法，能够将总代价控制在O(n) ，
二叉堆的实现
class BinHeap:
def __init__(self):
self.heapList = [0]
self.currentSize = 0
def percUp(self,i):
while i // 2 > 0:
if self.heapList[i] < self.heapList[i // 2]:
tmp = self.heapList[i // 2]
self.heapList[i // 2] = self.heapList[i]
self.heapList[i] = tmp
i = i // 2
def insert(self,k):
self.heapList.append(k)
self.currentSize = self.currentSize + 1
self.percUp(self.currentSize)
def percDown(self,i):
while (i * 2) <= self.currentSize:
mc = self.minChild(i)
if self.heapList[i] > self.heapList[mc]:
tmp = self.heapList[i]
self.heapList[i] = self.heapList[mc]
self.heapList[mc] = tmp
i = mc
def minChild(self,i):
if i * 2 + 1 > self.currentSize:
return i * 2
else:
if self.heapList[i*2] < self.heapList[i*2+1]:
return i * 2
else:
return i * 2 + 1
def delMin(self):
retval = self.heapList[1]
self.heapList[1] = self.heapList[self.currentSize]
self.currentSize = self.currentSize - 1
self.heapList.pop()
self.percDown(1)
return retval
def buildHeap(self,alist):
i = len(alist) // 2
self.currentSize = len(alist)
self.heapList = [0] + alist[:]
while (i > 0):
self.percDown(i)
i = i - 1
bh = BinHeap()
bh.buildHeap([9,5,6,2,3])
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
二叉查找树
比父节点小的key都出现在左子树，比父节点大的key都出现在右子树。
按照70,31,93,94,14,23,73的顺序插入：首先插入的70成为树根，31比70小，放到左子节点，93比70大，放到右子节点，94比93大，放到右子节点，14比31小，放到左子节点，23比14大，放到其右73比93小，放到其左
class TreeNode:
def __init__(self,key,val,left=None,right=None,parent=None):
self.key = key
self.payload = val
self.leftChild = left
self.rightChild = right
self.parent = parent
def hasLeftChild(self):
return self.leftChild
def hasRightChild(self):
return self.rightChild
def isLeftChild(self):
return self.parent and self.parent.leftChild == self
def isRightChild(self):
return self.parent and self.parent.rightChild == self
def isRoot(self):
return not self.parent
def isLeaf(self):
return not (self.rightChild or self.leftChild)
def hasAnyChildren(self):
return self.rightChild or self.leftChild
def hasBothChildren(self):
return self.rightChild and self.leftChild
def replaceNodeData(self,key,value,lc,rc):
self.key = key
self.payload = value
self.leftChild = lc
self.rightChild = rc
if self.hasLeftChild():
self.leftChild.parent = self
if self.hasRightChild():
self.rightChild.parent = self
class BinarySearchTree:
def __init__(self):
self.root = None
self.size = 0
def length(self):
return self.size
def __len__(self):
return self.size
def __iter__(self):
return self.root.__iter__()
def put(self,key,val):
if self.root:
self._put(key,val,self.root)
else:
self.root = TreeNode(key,val)
self.size = self.size + 1
def _put(self,key,val,currentNode):
if key < currentNode.key:
if currentNode.hasLeftChild():
self._put(key,val,currentNode.leftChild)
else:
currentNode.leftChild = TreeNode(key,val,parent=currentNode)
else:
if currentNode.hasRightChild():
self._put(key,val,currentNode.rightChild)
else:
currentNode.rightChild = TreeNode(key,val,parent=currentNode)
def __setitem__(self,k,v):
self.put(k,v)
def get(self,key):
if self.root:
res = self._get(key,self.root)
if res:
return res.payload
else:
return None
else:
return None
def _get(self,key,currentNode):
if not currentNode:
return None
elif currentNode.key == key:
return currentNode
elif key < currentNode.key:
return self._get(key,currentNode.leftChild)
else:
return self._get(key,currentNode.rightChild)
def __getitem__(self,key):
return self.get(key)
def __contains__(self,key):
if self._get(key,self.root):
return True
else:
return False
def delete(self,key):
if self.size > 1:
nodeToRemove = self._get(key,self.root)
if nodeToRemove:
self.remove(nodeToRemove)
self.size = self.size-1
else:
raise KeyError('Error, key not in tree')
elif self.size == 1 and self.root.key == key:
self.root = None
self.size = self.size - 1
else:
raise KeyError('Error, key not in tree')
def __delitem__(self,key):
self.delete(key)
def spliceOut(self):
if self.isLeaf():
if self.isLeftChild():
self.parent.leftChild = None
else:
self.parent.rightChild = None
elif self.hasAnyChildren():
if self.hasLeftChild():
if self.isLeftChild():
self.parent.leftChild = self.leftChild
else:
self.parent.rightChild = self.leftChild
self.leftChild.parent = self.parent
else:
if self.isLeftChild():
self.parent.leftChild = self.rightChild
else:
self.parent.rightChild = self.rightChild
self.rightChild.parent = self.parent
def findSuccessor(self):
succ = None
if self.hasRightChild():
succ = self.rightChild.findMin()
else:
if self.parent:
if self.isLeftChild():
succ = self.parent
else:
self.parent.rightChild = None
succ = self.parent.findSuccessor()
self.parent.rightChild = self
return succ
def findMin(self):
current = self
while current.hasLeftChild():
current = current.leftChild
return current
def remove(self,currentNode):
if currentNode.isLeaf(): #leaf
if currentNode == currentNode.parent.leftChild:
currentNode.parent.leftChild = None
else:
currentNode.parent.rightChild = None
elif currentNode.hasBothChildren(): #interior
succ = currentNode.findSuccessor()
succ.spliceOut()
currentNode.key = succ.key
currentNode.payload = succ.payload
else: # this node has one child
if currentNode.hasLeftChild():
if currentNode.isLeftChild():
currentNode.leftChild.parent = currentNode.parent
currentNode.parent.leftChild = currentNode.leftChild
elif currentNode.isRightChild():
currentNode.leftChild.parent = currentNode.parent
currentNode.parent.rightChild = currentNode.leftChild
else:
currentNode.replaceNodeData(currentNode.leftChild.key,
currentNode.leftChild.payload,
currentNode.leftChild.leftChild,
currentNode.leftChild.rightChild)
else:
if currentNode.isLeftChild():
currentNode.rightChild.parent = currentNode.parent
currentNode.parent.leftChild = currentNode.rightChild
elif currentNode.isRightChild():
currentNode.rightChild.parent = currentNode.parent
currentNode.parent.rightChild = currentNode.rightChild
else:
currentNode.replaceNodeData(currentNode.rightChild.key,
currentNode.rightChild.payload,
currentNode.rightChild.leftChild,
currentNode.rightChild.rightChild)
mytree = BinarySearchTree()
mytree[3]=“red”
mytree[4]=“blue”
mytree[6]=“yellow”
mytree[2]=“at”
print(3 in mytree)
print(mytree[6])
del mytree[2]
print(mytree[2])
平衡二叉查找树：AVL树 o(log n)
AVL树的实现中，需要对每个节点跟踪“平衡因子balancefactor”参数 ，平衡因子是根据节点的左右子树的高度来定义的，确切地说，是左右子树高度差： balanceFactor = height(leftSubTree) − height(rightSubTree)，如果平衡因子大于0，称为“左重left-heavy”，小于零称为“右重right-heavy”，平衡因子等于0，则称作平衡。有节点的平衡因子超出此范围，则需要一个重新平衡的过程，要保持BST的性质！
力扣笔记
双指针
盛最多水的容器
思路：在初始时，左右指针分别指向数组的左右两端，我们移动 数字较小的那个指针 。
class Solution:
def maxArea(self, height: List[int]) -> int:
i = 0
j = len(height) - 1
max = 0
while(i!=j):
if height[i] > height[j]:
tmp = height[j] * (j-i)
if tmp > max:
max = tmp
j = j-1
else:
tmp = height[i] * (j-i)
if tmp > max:
max = tmp
i = i+1
return max
动态规划：
53. 最大子数组和
思路：上方数组是输入，下方为构建的新数组，第二个元素开始从左到右判断前一个值是否大于零，若大于零则加在当前位置给新数组，否则把当前值给数组。
eg：1的前一个为-2，则把当前值1给数组；-3的前一个值为1大于0，则前一个值与当前值相加；4的前一个值为-2小于零，则把当前值4给数组……
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1,len(nums)):
if nums[i-1] > 0:
nums[i] = nums[i] + nums[i-1]
return max(nums)
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
0
0- 0
已为社区贡献4条内容
所有评论(0)