class getCommonNode(object):
"""返回两个单链表的第一个相交点"""
def FindFirstCommonNode(self, pHead1, pHead2):
loop1 = self.getLoopNode(pHead1)
loop2 = self.getLoopNode(pHead2)
if loop1 is None and loop2 is None:
return self.noLoop(pHead1, pHead2)
if loop1 is not None and loop2 is not None:
return self.bothLoop(pHead1, pHead2, loop1, loop2)
return None
def getLoopNode(self, pHead):
if pHead is None or pHead.next is None or pHead.next.next is None:
return pHead
slow = pHead.next
fast = pHead.next.next
while slow != fast:
if fast.next is None or fast.next.next is None:
return None
fast = fast.next.next
slow = slow.next
fast = pHead
while slow != fast:
slow = slow.next
fast =fast.next
return slow
def noLoop(self, pHead1, pHead2):
"""两个无环链表的第一个相交公共点"""
if pHead1 is None or pHead2 is None:
return None
cur1 = pHead1
cur2 = pHead2
moreLen = 0
while cur1.next is not None:
moreLen += 1
cur1 = cur1.next
while cur2.next is not None:
moreLen -= 1
cur2 = cur2.next
if cur1 != cur2:
return None
cur1 = pHead1 if moreLen > 0 else pHead2
cur2 = pHead2 if cur1 == pHead1 else pHead1
moreLen = abs(moreLen)
while moreLen != 0:
moreLen -= 1
cur1 = cur1.next
while cur1 != cur2:
cur1 = cur1.next
cur2 = cur2.next
return cur1
def bothLoop(self, pHead1, pHead2, loop1, loop2):
if loop1 == loop2:
"入环结点相同，退化到两个无环单链表相交问题"
cur1 = pHead1
cur2 = pHead2
moreLen = 0
while cur1 != loop1:
moreLen += 1
cur1 = cur1.next
while cur2.next != loop2:
moreLen -= 1
cur2 = cur2.next
if cur1 != cur2:
return None
cur1 = pHead1 if moreLen > 0 else pHead2
cur2 = pHead2 if cur1 == pHead1 else pHead1
moreLen = abs(moreLen)
while moreLen != 0:
moreLen -= 1
cur1 = cur1.next
while cur1 != cur2:
cur1 = cur1.next
cur2 = cur2.next
return cur1
else:
"两个有环单链表相交问题，且是不同的入环点"
cur1 = loop1.next
while cur1 != loop1:
if cur1 == loop2:
return loop1
cur1 = cur1.next
return None
def preOrderRecur(pHead):
"""先序遍历(递归版本)"""
if pHead is None:
return pHead
print(pHead.value + " ")
preOrderRecur(pHead.left)
preOrderRecur(pHead.right)
def preOrderUnRecur(pHead):
"""先序遍历(非递归版本)"""
if pHead is None:
return pHead
tempList = []
tempList.append(pHead)
while tempList != []:
curnode = tempList.pop()
print(curnode.value + " ")
if curnode.right is not None:
tempList.append(curnode.right)
if curnode.left is not None:
tempList.append(curnode.left)
def serialByPre(pHead):
"""先序遍历序列化"""
if pHead is None:
return "#!"
resultStr = pHead.value + "!"
resultStr += serialByPre(pHead.left)
resultStr += serialByPre(pHead.right)
return resultStr
def reconByPreString(preStr):
"""先序遍历反序列化"""
valueList = preStr.split("!")
tempList = []
for i in range(len(valueList)):
tempList.index(0, valueList[i])
return reconPreOrder(tempList)
def reconPreOrder(tempList):
valueStr = tempList.pop()
if valueStr == "#":
return None
node = treeNode(valueStr)
node.left = reconPreOrder(tempList)
node.right = reconPreOrder(tempList)
return node
def inOrderRecur(pHead):
"""中序遍历(递归版本)"""
if pHead is None:
return pHead
inOrderRecur(pHead.left)
print(pHead.value + " ")
inOrderRecur(pHead.right)
def inOrderUnRecur(pHead):
"""中序遍历(非递归版本)"""
if pHead is None:
return pHead
tempList = []
while tempList != [] or pHead is not None:
if pHead is not None:
tempList.append(pHead)
pHead = pHead.left
else:
pHead = tempList.pop()
print(pHead.value + " ")
pHead = pHead.right
def posOrderRecur(pHead):
"""后序遍历(递归版本)"""
if pHead is None:
return pHead
inOrderRecur(pHead.left)
inOrderRecur(pHead.right)
print(pHead.value + " ")
def posOrderUnRecur(pHead):
"""后序遍历(非递归版本)"""
if pHead is None:
return pHead
tempList1, tempList2 = [], []
tempList1.append(pHead)
while tempList1 != []:
pHead = tempList1.pop()
tempList2.append(pHead)
if pHead.left is not None:
tempList1.append(pHead.left)
if pHead.right is not None:
tempList1.append(pHead.right)
while tempList2 != []:
print(tempList2.pop() + " ")
# 如果一个节点有右子树，则这个节点的后继节点就是这个节点右子树的最左的节点
# 如果一个节点没有右子树，则寻找这个节点作为哪个节点左子树的最后一个节点(中序遍历：左、中、右)
# 通过这个节点向上寻找，直到满足这个节点作为该节点的左子树的最后一个节点，也就是表明这个树的左子树已经遍历完，该打印父节点了。
class withParentNode(object):
def __init__(self, value):
self.value = value
self.right, self.left, self.parent = None, None, None
def getSuccessorNode(node):
"""通过节点中增加的父节点指针，找后继节点"""
if node is None:
return None
if node.right is not None:
return getLeftMost(node.right)
else:
# 这个节点没有右子树
parentNode = node.parent
while parentNode is not None and parentNode.left != node:
node = parentNode
parentNode = node.parent
return parentNode
def getLeftMost(node):
"""找右子树中最左的节点"""
if node is None:
return None
while node.left is not None:
node = node.left
return node
def SerialByLevel(pHead):
"""按层序列化"""
if pHead is None:
return '#！'
res = str(pHead.value) + '！'
queueList = []
queueList.append(pHead)
while queueList != []:
pHead = queueList.pop()
if pHead.left is not None:
res += str(pHead.left.value) + '！'
queueList.append(pHead.left)
else:
res += '#'
if pHead.right is not None:
res += str(pHead.right.value) + '！'
queueList.append(pHead.right)
else:
res += '#'
return res
def reconByLevelString(levelStr):
"""按层遍历反序列化"""
levelList = []
for i in levelStr:
if i != '！':
levelList.append(i)
index = 0
pHead = generateNodeByString(levelList[index])
index += 1
queueList = []
if pHead is not None:
queueList.append(pHead)
while queueList != []:
curNode = queueList.pop()
curNode.left = generateNodeByString(levelList[index])
index += 1
curNode.right = generateNodeByString(levelList[index])
index += 1
if curNode.left is not None:
queueList.append(curNode.left)
if curNode.right is not None:
queueList.append(curNode.right)
return curNode
def generateNodeByString(str1):
if str1 == '#':
return None
return treeNode(int(str1))
def isBalanceTree(pHead):
"""判断一棵树是否是平衡二叉树(任一节点的左子树和右子树高度差小于2)
使用递归，函数返回两个值，一个是这个树的高度，一个是这个树是否是平衡二叉树"""
return isBalanceTreeProcess(pHead)[0]
def isBalanceTreeProcess(pHead):
if pHead is None:
return True, 0
leftDataIsB, leftDataHigh = isBalanceTreeProcess(pHead.left)
if not leftDataIsB:
# 左子树不平衡，则没有继续的必要，直接返回False
return False, 0
rightDataIsB, rightDataHigh = isBalanceTreeProcess(pHead.right)
if not rightDataIsB:
# 右子树不平衡，则没有继续的必要，直接返回False
return False, 0
# 运行到此时仍没有返回，证明该节点左子树和右子树都是平衡二叉树
if abs(leftDataHigh - rightDataHigh) > 1:
return False, 0
return True, max(leftDataHigh, rightDataHigh) + 1
def isBST(pHead):
"""判断一棵树是否是搜索二叉树"""
if pHead is None:
return True
res = True
pre = treeNode(None)
cur1 = pHead
while cur1 is not None:
cur2 = cur1.left
if cur2 is not None:
while cur2.right is not None and cur2.right != cur1:
cur2 = cur2.right
if cur2.right is None:
cur2.right = cur1
cur1 = cur1.left
continue
else:
cur2.right = None
if pre is not None and pre.value > cur1.value:
res = False
pre = cur1
cur1 = cur1.right
return res
def isCBT(pHead):
"""判断一棵树是否是完全二叉树"""
if pHead is None:
return True
queueList = []
leafNode = False
queueList.append(pHead)
while queueList != []:
pHead = queueList.pop()
leftNode = pHead.left
rightNode = pHead.right
if (leafNode and (leftNode is not None or rightNode is not None)) or (leftNode is None and rightNode is not None):
# 两种情况下返回False
# 1. 一个节点有右子树，没有左子树，则不是完全二叉树
# 2. 当有一个节点只有左子树，没有右子树时，leftNode=True，同一层次往后节点则只能是叶节点，否则不是完全二叉树
return False
if leftNode is not None:
queueList.insert(0, leftNode)
if rightNode is not None:
queueList.insert(0, rightNode)
else:
# 当一个节点只有左子树没有右子树时，标记位变为True，同一层次后面的节点和下面所有的节点必须都是叶节点
leftNode = True
return True
def getTreeNodeNum(pHead):
"""求一颗完全二叉树的节点数，时间复杂度小于O(N)"""
if pHead is None:
return 0
return getTreeNodeNumProcess(pHead, 1, mostLeftLevel(pHead, 1))
def getTreeNodeNumProcess(pHead, level, high):
# level:pHead节点在第几层
# high：这棵树的深度(固定值)
# 返回的是以pHead为根节点的子树一共有多少个节点
if level == high:
# pHead节点到了最后一层，即是叶节点。则以pHead为头的子树就1个节点
return 1
if mostLeftLevel(pHead.right, level + 1) == high:
# 该节点右子树的最左节点如果到了最后一层，则表明该节点的左子树是满二叉树，则左子树节点数可以通过公式算出，右子树是完全二叉树
return (1 << (high - level)) + getTreeNodeNumProcess(pHead.right, level + 1, high)
else:
# 如果该节点右子树的最左节点没到最后一层，则表明该节点的右子树是少一层的满二叉树，右子树节点数可以通过公式算出，左子树是完全二叉树
return (1 << (high - level - 1)) + getTreeNodeNumProcess(pHead.left, level + 1, high)
def mostLeftLevel(pHead, level):
while pHead is not None:
level += 1
pHead = pHead.left
return level - 1
def countIslands(matrix):
"""矩阵中有多少个岛"""
if matrix is None or matrix[0] is None:
return 0
res = 0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 1:
res += 1
infect(matrix, i, j, len(matrix), len(matrix[0]))
return res
def infect(matrix, i, j, N, M):
if i < 0 or i >= N or j < 0 or j > M or matrix[i][j] != 1:
return
matrix[i][j] = 2
infect(matrix, i + 1, j, N, M)
infect(matrix, i - 1, j, N, M)
infect(matrix, i, j + 1, N, M)
infect(matrix, i, j - 1, N, M)
class TrieTree(object):
"""前缀树节点"""
def __init__(self):
self.path = 0 # 有多少个字符串经过这个节点
self.end = 0 # 有多少个字符串以这个节点结尾
self.nexts = [None] * 26 # 这个结点往下一共有26(限定)个方向
class Trie(object):
"""前缀树"""
def __init__(self):
self.rootNode = TrieTree() # 头结点
def insert(self, strWord):
if strWord is None:
return
strList = list(strWord)
node = self.rootNode
for i in range(len(strList)):
index = ord(strList[i]) - ord('a')
if node.nexts[index] is None:
node.nexts[index] = TrieTree()
node = node.nexts[index]
node.path += 1
node.end += 1
def search(self, strWord):
# 查找strWord出现过几次
if strWord is None:
return 0
strList = list(strWord)
node = self.rootNode
for i in range(len(strList)):
index = ord(strList[i]) - ord('a')
if node.nexts[index] is None:
return 0
node = node.nexts[index]
return node.end
def delete(self, strWord):
if self.search(strWord) != 0:
strList = list(strWord)
node = self.rootNode
for i in range(len(strList)):
index = ord(strList[i]) - ord('a')
node.nexts[index].path -= 1
if node.nexts[index].path == 0:
node.nexts[index] = None
return
node = node.nexts[index]
node.end -= 1
def prefixNumber(self, pre):
"""查某个字符串的前缀数量是多少"""
if pre is None:
return 0
preList = list(pre)
node = self.rootNode
for i in range(len(preList)):
index = ord(preList[i]) - ord('a')
if node.nexts[index] is None:
return 0
node = node.nexts[index]
return node.path
def strCompare(str1, str2):
if str1 + str2 < str2 + str1:
return -1
elif str1 + str2 > str2 + str1:
return 1
else:
return 0
def lowestString(strsList):
if strsList is None or len(strsList) == 0:
return ""
strsList = sorted(strsList, key=functools.cmp_to_key(strCompare))
res = ""
for i in range(len(strsList)):
res += strsList[i]
return res
# 原题求解，是将数组调整为小根堆，将最小的两个数相加放回到原数组中，直至数组中仅剩一个数为止
def lessMoney(alist):
pQ = []
for i in range(len(alist)):
pQ.append(alist[i])
pQ = sorted(pQ, reverse=True)
sum, cur = 0, 0
while len(pQ) > 1:
cur = pQ.pop() + pQ.pop()
sum += cur
pQ.append(alist[i])
pQ = sorted(pQ, reverse=True)
return sum
class moreProfits(object):
def __init__(self, profit, cost):
self.profit = profit
self.cost = cost
def minCostComparator(node1, node2):
# 花费(小根堆)比较器
return node1.cost - node2.cost
def maxProfitComparator(node1, node2):
# 利润(大根堆)比较器
return node2.profit - node1.profit
# 首先将项目按照成本大小压入小根堆(成本)中，然后依次将目前能做的项目(成本小于启动资金)压入利润大根堆(利润)中,每做一个项目，启动
# 资金相应变化，相应从成本堆中进行弹出，直到做完k个项目，或者成本堆中无项目可谈，而利润堆中无项目可做为止
def findMaximizedCapital(k, w, profitsList, capitalList):
# 通过两个根堆(一个大根堆(利润),一个小根堆(花费))实现安排项目的使用顺序
# 仅能做k个项目，初始资金为w
nodes = [None] * len(profitsList)
for i in range(len(profitsList)):
nodes[i] = moreProfits(profitsList[i], capitalList[i])
minCostList, maxProfitList = [], []
for i in range(len(nodes)):
minCostList.append(nodes[i])
minCostList = sorted(minCostList, key=functools.cmp_to_key(minCostComparator))
for i in range(k):
while minCostList != [] and minCostList[-1].cost <= w:
maxProfitList.append(minCostList.pop())
maxProfitList = sorted(maxProfitList, key=functools.cmp_to_key(maxProfitComparator))
if maxProfitList == []:
return w
w += maxProfitList.pop().profit
return w
class meetingNode(object):
def __init__(self, start, end):
self.start = start
self.end = end
def meetingCompare(o1, o2):
return o1.end - o2.end
def bestArrangement(programs, startTime):
programs = sorted(programs, key=functools.cmp_to_key(meetingCompare))
result = 0
for i in range(len(programs)):
if startTime <= programs[i].start:
result += 1
startTime = programs[i].end
return result