class AbstractBinarySearchTree(object):
def __init__(self, pHead):
self.root = pHead
self.size = 0
def createNode(self, value, parent, left, right):
self.newNode = withParentNode(value)
self.newNode.parent = parent
self.newNode.left = left
self.newNode.right = right
return self.newNode
def search(self, element):
node = self.root
while node is not None and node.value is not None and node.value != element:
if element < node.value:
node = node.left
else:
node = node.right
return node
def insert(self, element):
if self.root is None:
self.root = self.createNode(element, None, None, None)
self.size += 1
return self.root
insertParentNode = None
searchTempNode = self.root
while searchTempNode is not None and searchTempNode.value is not None:
insertParentNode = searchTempNode
if element < searchTempNode.value:
searchTempNode = searchTempNode.left
else:
searchTempNode = searchTempNode.right
newNode = self.createNode(element, insertParentNode, None, None)
if insertParentNode.value > newNode.value:
insertParentNode.left = newNode
else:
insertParentNode.right = newNode
self.size += 1
return newNode
def delete(self, element):
# 如果该节点既有左子树，又有右子树，则找到该节点右子树的最左节点，来代替它的位置。如果最左节点有右子树，则挂在该节点原来的位置
deleteNode = self.search(element)
if deleteNode is not None:
return self.deleteNode(deleteNode)
else:
return None
def deleteNode(self, delNode):
if delNode is not None:
nodeToReturn = None
if delNode is not None:
if delNode.left is None:
nodeToReturn = self.transplant(delNode, delNode.right)
elif delNode.right is None:
nodeToReturn = self.transplant(delNode, delNode.left)
else:
successorNode = self.getMinimum(delNode.right)
if successorNode.parent != delNode:
self.transplant(successorNode, successorNode.right)
successorNode.right = delNode.right
successorNode.right.parent = successorNode
self.transplant(delNode, successorNode)
successorNode.left = delNode.left
successorNode.left.parent = successorNode
nodeToReturn = successorNode
self.size -= 1
return nodeToReturn
def transplant(self, nodeToReplace, newNode):
if nodeToReplace.parent is None:
self.root = newNode
elif nodeToReplace == nodeToReplace.parent.left:
nodeToReplace.parent.left = newNode
else:
nodeToReplace.parent.right = newNode
if newNode is not None:
newNode.parent = nodeToReplace.parent
return newNode
def getMinimum(self, node):
while node.left is not None:
node = node.left
return node
class AVLNode(object):
def __init__(self, value, parent, left, right, height):
self.value = value
self.parent = parent
self.left = left
self.right = right
self.height = height
class AVLTree(AbstractBinarySearchTree):
def insert(self, element):
newNode = self.insert(element)
return newNode
def rebalance(self, pHead):
while pHead is not None:
parentNode = pHead.parent
leftHeight = -1 if pHead.left is None else pHead.left.height
rightHeight = -1 if pHead.right is None else pHead.right.height
nodeBalance = rightHeight - leftHeight
if nodeBalance == 2:
if pHead.right.right is not None:
pHead = self.avlRotateLeft(pHead)
break
else:
pHead = self.doubleRotateRightLeft(pHead)
break
elif nodeBalance == -2:
if pHead.left.left is not None:
pHead = self.avlRotateRight(pHead)
break
else:
pHead = self.doubleRotateLeftRight(pHead)
break
else:
self.updateHeight(pHead)
pHead = parentNode
def updateHeight(self, pHead):
leftHeight = -1 if pHead.left is None else pHead.left.height
rightHeight = -1 if pHead.right is None else pHead.right.height
pHead.height = 1 + max(leftHeight, rightHeight)
def avlRotateLeft(self, pHead):
temp = self.rotateLeft(pHead)
self.updateHeight(temp.left)
self.updateHeight(temp)
return temp
def avlRotateRight(self, pHead):
temp = self.rotateRight(pHead)
self.updateHeight(temp.right)
self.updateHeight(temp)
return temp
def doubleRotateRightLeft(self, pHead):
pHead.right = self.avlRotateRight(pHead.right)
return self.avlRotateLeft(pHead)
def doubleRotateLeftRight(self, pHead):
pHead.left = self.avlRotateLeft(pHead.left)
return self.avlRotateRight(pHead)
def rotateLeft(self, pHead):
temp = pHead.right
temp.parent = pHead.parent
pHead.right = temp.left
if pHead.right is not None:
pHead.right.parent = pHead
temp.left = pHead
pHead.parent = temp
# temp took over node's place so now its parent should point to temp
if temp.parent is not None:
if pHead == temp.parent.left:
temp.parent.left = temp
else:
temp.parent.right = temp
else:
self.root = temp
return temp
def rotateRight(self, pHead):
temp = pHead.left
temp.parent = pHead.parent
pHead.left = temp.right
if pHead.left is not None:
pHead.left.parent = pHead
temp.right = pHead
pHead.parent = temp
# temp took over node's place so now its parent should point to temp
if temp.parent is not None:
if pHead == temp.parent.left:
temp.parent.left = temp
else:
temp.parent.right = temp
else:
self.root = temp
return temp
def maxLength(alist, aim):
"""给定数组，返回满足累加和为aim的子数组的最大长度"""
if alist == [] or len(alist) == 0:
return 0
mapDict = {}
mapDict.update({0: -1})
maxLen, sumNum = 0, 0
for i in range(len(alist)):
sumNum += alist[i]
if (sumNum - aim) in mapDict.keys():
maxLen = max(i - mapDict.get(sumNum - aim), maxLen)
if sumNum not in mapDict.keys():
mapDict.update({sumNum: i})
return maxLen
def mostEOR(alist):
"""将给定数组进行分组，保证每组的异或和为0，返回最多的子数组数"""
ans, xor = 0, 0
dp = [0] * len(alist)
mapDict = {}
mapDict.update({0: -1})
for i in range(len(alist)):
xor ^= alist[i]
if xor in mapDict.keys():
pre = mapDict.get(xor)
dp[i] = 1 if pre == -1 else dp[pre] + 1
if i > 0:
dp[i] = max(dp[i - 1], dp[i])
mapDict.update({xor: i})
ans = max(ans, dp[i])
return ans
def biggestSubNSTInTree(pHead):
record = [] * 3 # 0 -> size 1 -> min 2 -> max
return posOrder(pHead, record)
def posOrder(pHead, record):
if pHead is None:
record[0] = 0
record[1] = 0
record[2] = 0
return None
value = pHead.value
leftNode = pHead.left
rightNode = pHead.right
lBST = posOrder(leftNode, record)
lSize = record[0]
lMin = record[1]
lMax = record[2]
rBST = posOrder(rightNode, record)
rSize = record[0]
rMin = record[1]
rMax = record[2]
record[1] = min(rMin, lMin, value) # lmin, value, rmin -> min
record[2] = max(lMax, rMax, value) # lmax, value, rmax -> max
if leftNode == lBST and rightNode == rBST and lMax < value < rMin:
record[0] = lSize + rSize + 1
return pHead
record[0] = max(lSize, rSize)
return lBST if lSize > rSize else rBST
def biggestSubNSTInTreeProcess(pHead):
if pHead is None:
return 0, None, 0, 0
leftTree = pHead.left
leftSubTressInfo = biggestSubNSTInTreeProcess(leftTree)
rightTree = pHead.right
rightSubTressInfo = biggestSubNSTInTreeProcess(rightTree)
includeItSelf = 0
if leftSubTressInfo[1] == leftTree and rightSubTressInfo[1] == rightTree and \
rightSubTressInfo[2] > pHead.value > leftSubTressInfo[2]:
includeItSelf = leftSubTressInfo[0] + 1 + rightSubTressInfo[0]
p1, p2 = leftSubTressInfo[0], rightSubTressInfo[0]
maxSize = max(p1, p2, includeItSelf)
maxpHead = leftSubTressInfo[1] if p1 > p2 else rightSubTressInfo[1]
if maxSize == includeItSelf:
maxpHead = pHead
return maxSize, maxpHead
# 节点A走到节点B的距离为：A走到B最短路径上的节点个数。求一颗二叉树上的最远距离
def MaxDistanceInTree(pHead):
"""节点A走到节点B的距离为：A走到B最短路径上的节点个数。求一颗二叉树上的最远距离"""
return MaxDistanceInTreeProcess(pHead)[0]
def MaxDistanceInTreeProcess(pHead):
if pHead is None:
return 0, 0
leftReturnType = MaxDistanceInTreeProcess(pHead.left)
rightReturnType = MaxDistanceInTreeProcess(pHead.right)
includeHeadDistance = leftReturnType[1] + 1 + rightReturnType[1]
p1, p2 = leftReturnType[0], rightReturnType[0]
resultDistance = max(p1, p2, includeHeadDistance)
hitself = max(leftReturnType[1], rightReturnType[1]) + 1
return resultDistance, hitself
class maxHappyNode(object):
def __init__(self, huo):
self.huo = huo
self.nexts = []
def getMaxHuo(pHead):
"""活跃度的计算"""
return max(getMaxHuoProcess(pHead)[0], getMaxHuoProcess(pHead)[1])
def getMaxHuoProcess(pHead):
lai_huo, bu_lai_huo = pHead.huo, 0
if pHead.nexts == []:
return pHead.huo, 0
for i in range(len(pHead.nexts)):
nextNode = pHead.nexts[i]
nextNodeReturn = getMaxHuoProcess(nextNode)
lai_huo += nextNodeReturn[1]
bu_lai_huo = max(nextNodeReturn[0], nextNodeReturn[1])
return lai_huo, bu_lai_huo
class LRUNode(object):
def __init__(self, value):
self.value = value
self.last = None
self.next = None
class NodeDoubleLinkedList(object):
def __init__(self):
self.head = None
self.tail = None
def addNode(self, newNode):
if newNode is None:
return None
if self.head is None:
self.head = newNode
self.tail = newNode
else:
self.tail.next = newNode
newNode.last = self.tail
self.tail = newNode
def moveNodeToTail(self, pHead):
if self.tail == pHead:
return
if self.head == pHead:
self.head = pHead.next
self.head.last = None
else:
pHead.last.next = pHead.next
pHead.next.last = pHead.last
pHead.last = self.tail
pHead.next = None
self.tail.next = pHead
self.tail = pHead
def removeHead(self):
if self.head is None:
return None
res = self.head
if self.head == self.tail:
self.head = None
self.tail = None
else:
self.head = res.next
res.next = None
self.head.last = None
return res
# 自定义一种缓存结构(LRU)，假设大小为K，能实现两个功能set()和get()
# set和get方法的时间复杂度为O(1)
# 某个key的set或get操作一旦发生，则认为这个key的记录成了最经常使用的
# 当缓存的大小超过K时，移除最不经常使用的记录
class MyCache(object):
def __init__(self, capacity):
if capacity < 1: # capacity指限定的内存大小
raise RuntimeError("should be more than 0.")
self.keyNodeMap = {}
self.nodeKeyMap = {}
self.nodeList = NodeDoubleLinkedList()
self.capacity = capacity
def get(self, K):
if K in self.keyNodeMap.keys():
res = self.keyNodeMap[K]
self.nodeList.moveNodeToTail(res)
return res.value
return None
def set(self, K, V):
if K in self.keyNodeMap.keys():
node = self.keyNodeMap[K]
node.value = V
self.nodeList.moveNodeToTail(node)
else:
newNode = LRUNode(V)
self.keyNodeMap.update({K: newNode})
self.nodeKeyMap.update({newNode: K})
self.nodeList.addNode(newNode)
if len(self.keyNodeMap) == self.capacity + 1:
self.removeMostUnusedCache()
def removeMostUnusedCache(self):
removeNode = self.nodeList.removeHead()
K = self.nodeKeyMap[removeNode]
del self.nodeKeyMap[removeNode]
del self.keyNodeMap[K]
class LFUNode(object):
def __init__(self, key, value, times):
self.key = key
self.value = value
self.times = times
self.up = None
self.down = None
class NodeList(object):
def __init__(self, pHead):
self.next = None
self.last = None
self.head = pHead
self.tail = pHead
def addNodeFromHead(self, newHead):
newHead.down = self.head
self.head = newHead
def isEmpty(self):
return self.head is None
def deleteNode(self, pHead):
"""删除任意节点pHead"""
if self.head == self.tail:
self.head = None
self.tail = None
elif pHead == self.head:
self.head = pHead.down
self.head.up = None
elif pHead == self.tail:
self.tail = pHead.up
self.tail.down = None
else:
pHead.up.down = pHead.down
pHead.down.up = pHead.up
pHead.up = None
pHead.down = None
class LFUCache(object):
def __init__(self, capacity):
self.capacity = capacity # 容量
self.size = 0 # 实际存储的个数
self.records = {} # key(Integer): node
self.heads = {} # node: NodeList
self.headlist = NodeList(None)
def set(self, key, value):
if key in self.records.keys():
pHead = self.records[key]
pHead.value = value
pHead.times += 1
curNodeList = self.heads[pHead]
self.move(pHead, curNodeList)
else:
if self.size == self.capacity:
pHead = self.headlist.tail
self.headlist.deleteNode(pHead)
self.modifyHeadList(self.headlist)
del self.records[pHead.key]
del self.heads[pHead]
self.size -= 1
pHead = LFUNode(key, value, 1)
if self.headlist is None:
self.headlist = NodeList(pHead)
elif self.headlist.head.times == pHead.times:
self.headlist.addNodeFromHead(pHead)
else:
newList = NodeList(pHead)
newList.next = self.headlist
self.headlist.last = newList
self.headlist = newList
self.records.update({key: pHead})
self.heads.update({pHead: self.headlist})
self.size += 1
def get(self, key):
if key not in self.records.keys():
return -1
pHead = self.records[key]
pHead.times += 1
curNodeList = self.heads[pHead]
self.move(pHead, curNodeList)
return pHead.value
# return whether delete this head
def modifyHeadList(self, nodeList):
if nodeList.isEmpty():
if self.headlist == nodeList:
self.headlist = nodeList.next
if self.headlist is not None:
self.headlist.last = None
else:
nodeList.last.next = nodeList.next
if nodeList.next is not None:
nodeList.next.last = nodeList.last
return True
return False
# 将一个节点从老链表拿出，送到新链表中，需要考虑：
# 老链表在删除之后，是否还有存在必要(老链表中只有一个节点)
# 老链表是否是头链表
# 新链表是否存在(老链表是否是尾链表)
# 新链表是否与老链表在次数是相连的(比如老链表中的times均是4，而与之相连的链表的times为6，此时需要新建一个times为5的链表)
def move(self, node, oldNodeList):
oldNodeList.deleteNode(node)
preList = oldNodeList.last if self.modifyHeadList(oldNodeList) else oldNodeList
nextList = oldNodeList.next
if nextList is None:
newList = NodeList(node)
if preList is not None:
preList.next = newList
newList.last = preList
if self.headlist is None:
self.headlist = newList
self.heads.update({node, newList})
else:
if nextList.head.times == node.times:
nextList.addNodeFromHead(node)
self.heads.update({node, nextList})
else:
newList = NodeList(node)
if preList is not None:
preList.next = newList
newList.last = preList
newList.next = nextList
nextList.last = newList
if self.headlist == nextList:
self.headlist = newList
self.heads.update({node, newList})