def getValueFromStr(str1):
"""给定字符串，字符串表示一个公式，可能有整数、加减乘除符号和左右括号，返回公式计算结果"""
return valueProcess(str1, 0)[0]
# 返回两个值：计算结果，计算到的位置
def valueProcess(str1, index):
pre = 0
que = []
while index < len(str1) and str1[index] != ')':
if '0' <= str1[index] <= '9':
pre = pre * 10 + int(str1[index])
index += 1
elif str1[index] != "(": # str1[index] 此时是 +-*/
addNum(que, pre)
que.append(str1[index])
index += 1
pre = 0
else: # str1[index] 此时为 '('
bra = valueProcess(str1, index + 1)
pre = bra[0]
index = bra[1] + 1
addNum(que, pre)
return getResult(que), index
def addNum(que, num):
if que != []:
topStr = que.pop()
if topStr in '+-':
que.append(topStr)
else:
cur = int(que.pop())
num = cur * num if topStr == '*' else cur // num
que.append(str(num))
def getResult(que):
res = 0
addFlag = True
while que != []:
cur = que.pop(0)
if cur == '+':
addFlag = True
elif cur == '-':
addFlag = False
else:
res += int(cur) if addFlag else -int(cur)
return res
class SkipListNode(object):
"""跳表节点"""
def __init__(self, value):
self.value = value
# 列表中存储的是节点，nextNodes[1]指的是这一层所指向的下一个节点是什么
self.nextNodes = []
class SkipList(object):
def __init__(self):
self.size = 0 # 加入了多少个key
self.maxLevel = 0 # 所有数据随机出的最大层
self.head = SkipListNode(None) # 巨小，整个结构最前面的链，层数与所有数据随机出的最大层一样
self.head.nextNodes.append(None)
self.PROBABILITY = 0.5
def add(self, newValue):
if not self.contains(newValue):
self.size += 1
level = 0
while random.random() < self.PROBABILITY:
level += 1
while level > self.maxLevel:
self.head.nextNodes.insert(0, None)
self.maxLevel += 1
newNode = SkipListNode(newValue)
current = self.head
while level >= 0:
current = self.findNext(newValue, current, level)
newNode.nextNodes.insert(0, current.nextNodes[level])
current.nextNodes[level] = newNode
level -= 1
def findNext(self, e, current, level):
nextNode = current.nextNodes[level]
while nextNode is not None:
value = nextNode.value
if self.lessThan(e, value):
break
current = nextNode
nextNode = current.nextNodes[level]
return current
def contains(self, value):
node = self.findNode(value)
return node is not None and node.value is not None and node.value == value
def findNode(self, e):
return self.find(e, self.head, self.maxLevel)
def lessThan(self, a, b):
return a < b
def find(self, e, current, level):
while level >= 0:
current = self.findNext(e, current, level)
level -= 1
return current
def delete(self, deleteValue):
if self.contains(deleteValue):
deleteNode = self.findNode(deleteValue)
self.size -= 1
level = self.maxLevel
current = self.head
while level >= 0:
current = self.findNext(deleteNode.value, current, level)
if deleteNode.nextNodes.size > level:
current.nextNodes[level] = deleteNode.nextNodes[level]
level -= 1
def getMaxEor1(alist):
maxNum, eor = 0, 0
dp = [0] * len(alist)
for i in range(len(alist)):
eor ^= alist[i]
maxNum = max(maxNum, eor)
for start in range(1, i + 1):
curEor = eor ^ dp[start - 1] # eor(alist[start:i]) = eor(alist[:i]) ^ eor(alist[:start-1])
maxNum = max(maxNum, curEor)
dp[i] = eor
return maxNum
class NumTrieNode(object):
def __init__(self):
self.nexts = [None] * 2
class NumTrie(object):
def __init__(self):
self.head = NumTrieNode()
def add(self, num):
curNode = self.head
for move in range(31, -1, -1):
path = (num >> move) & 1 # 从高位依次取数
curNode.nexts[path] = NumTrieNode() if curNode.nexts[path] is None else curNode.nexts[path]
curNode = curNode.nexts[path]
# 为了求以i为结尾最大的异或和，假设从start开始到i结束的异或和是最大的。
# 由公式eor(alist[start:i]) = eor(alist[:i]) ^ eor(alist[:start-1]),但由于k无法得知，
# 而eor(alist[:i])是从头开始异或，是已知的，因此可以按照已知的eor(alist[:i])推测当eor(alist[:start-1])是什么时，
# 可以使eor(alist[start:i])成为最大的。而eor(alist[start:i])最好的结果是符号位是0，其他位均为1。
# 即使最高位被迫只能为1(因为eor(alist[:start-1])全都是以1开始的)时，其他位也最好能为1，此时是最大的(负数是以补码的形式存在的)
def maxXor(self, num):
curNode = self.head
res = 0
for move in range(31, -1, -1):
path = (num >> move) & 1 # 从高位一次取数
# 为了使数最大，最高位符号位最好的结果是0(正数)，其他位最好的结果是1。
best = path if move == 31 else path ^ 1 # 期待要选的路
# 如果有理想的数字通道，当然按照理想的走，但如果实际并没有，只能按实际来，下一位在试，这样是最大的
best = best if curNode.nexts[best] is not None else best ^ 1 # 实际选择的路
res |= (path ^ best) << move # 设置答案的每一位
curNode = curNode.nexts[best]
return res
def maxXorSubArray(alist):
if alist == [] or len(alist) == 0:
return 0
maxNum, eor = 0, 0
numTrie = NumTrie()
numTrie.add(0)
for i in range(len(alist)):
eor ^= alist[i]
maxNum = max(maxNum, numTrie.maxXor(eor))
numTrie.add(eor)
return maxNum
# 换钱的方法数，给定数组arr，arr中所有值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，
# 再给定一个整数aim代表要找的钱数，求换钱有多少种方法
def coins(alist, aim):
if alist == [] or len(alist) == 0 or aim < 0:
return 0
# return coinsProcess(alist, 0, aim)
return coinsProcess_map(alist, 0, aim)
def coinsProcess(alist, index, aim):
"""
:param alist: 给定的正数数组
:param index: 可以任意自由使用index及其以后所有的钱
:param aim: 目标钱数
:return: 方法数
"""
res = 0
if index == len(alist):
res = 1 if aim == 0 else 0
else:
i = 0
while i * alist[index] <= aim:
res += coinsProcess(alist, index + 1, aim - i * alist[index])
i += 1
return res
# 无后效性：如果到达这个状态，和这个状态以后要完成的工作无影响。
# 比如[200, 100, 50, 10],目标金额1000，假设index=2，此时目标金额为600，使用index以后的金钱实现目标金额600的方法数和
# 如何达到index=2，aim=600的这种状态无关，即通过alist数组前2个数实现400这个过程和通过alist数组后2个数实现600这两个过程
# 互不影响、无关联。
# 一张200，两张100，后面需要完成600的目标，和两张200，没有100，后面完成600的目标。两个方法中，通过后两个实现600的目标方法数是一定的。
# 可以将其放在一个字典中，极大的节省了暴力递归时间
def coinsProcess_map(alist, index, aim):
""" 记忆化搜索
:param alist: 给定的正数数组
:param index: 可以任意自由使用index及其以后所有的钱
:param aim: 目标钱数
:return: 方法数
"""
mapDict = {} # key: "index_aim" value: 返回值
res = 0
if index == len(alist):
res = 1 if aim == 0 else 0
else:
i = 0
while i * alist[index] <= aim:
nextAim = aim - i * alist[index]
keyStr = str(index + 1) + '_' + str(nextAim)
if keyStr in mapDict.keys():
res += mapDict[keyStr]
else:
res += coinsProcess_map(alist, index + 1, aim - i * alist[index])
i += 1
mapDict.update({str(index) + "_" + str(aim): res})
return res
# 完全由暴力递归改为动态规划
def coins2(alist, aim):
if alist == [] or len(alist) == 0 or aim < 0:
return 0
dp = np.zeros((len(alist) + 1, aim + 1))
for i in range(1, aim + 1):
dp[len(alist)][i] = 0 # 由终止条件确定。已经到了数组末尾，而aim>0，已经没有整数可用，仍想配成一定金额，所以方法数为0
dp[len(alist)][0] = 1 # 由终止条件确定。当数组的数已经用完，此时目标数同时为0，返回方法数为1
for i in range(len(alist) - 1, -1, -1):
for j in range(0, aim + 1):
k = 0
while j - k * alist[i] >= 0:
dp[i][j] += dp[i + 1][j - k * alist[i]]
k += 1
return dp[0][aim]
# 对初始版的动态规划优化一丢丢
def coins3(alist, aim):
if alist == [] or len(alist) == 0 or aim < 0:
return 0
dp = np.zeros((len(alist) + 1, aim + 1))
for i in range(aim + 1):
dp[len(alist)][i] = 0
dp[len(alist)][0] = 1
for i in range(len(alist) - 1, -1, -1):
for j in range(0, aim + 1):
dp[i][j] = dp[i + 1][j]
# dp[i][j] = dp[i + 1][j] + dp[i + 1][j - alist[i]] + dp[i + 1][j - 2 * alist[i]] + ...
# dp[i][j - alist[i]] = dp[i + 1][j - alist[i]] + dp[i + 1][j - 2 * alist[i]] + ...
# 因此 dp[i][j] = dp[i + 1][j] + dp[i][j - alist[i]]
dp[i][j] += dp[i][j - alist[i]] if j - alist[i] >= 0 else 0
return dp[0][aim]
def coins4(alist, aim):
if alist == [] or len(alist) == 0 or aim < 0:
return 0
dp = np.zeros((len(alist), aim + 1))
for i in range(len(alist)):
dp[i][0] = 1
j = 1
# 不需要终止行，在第一行，只需要是5的倍数的aim，都可以实现，方法数仅是1(因为只用了一种金额的)
while alist[0] * j <= aim:
dp[0][alist[0] * j] = 1
j += 1
for i in range(1, len(alist)):
for j in range(1, aim + 1):
dp[i][j] = dp[i - 1][j]
dp[i][j] += dp[i][j - alist[i]] if j - alist[i] >= 0 else 0
return dp[len(alist) - 1][aim]
# 排成一条线的纸牌博弈问题
def winCard1(alist):
if alist == [] or len(alist) == 0:
return 0
return max(f(alist, 0, len(alist) - 1), s(alist, 0, len(alist) - 1))
# alist[i:j]这个排列的纸牌被绝顶聪明的人先拿，最终能获得什么分数
def f(alist, i, j):
"""alist[i:j]这个排列的纸牌被绝顶聪明的人先拿，最终能获得什么分数"""
if i == j: # 如果仅剩一张，当然会被先拿的人拿走
return alist[i]
# 先拿的人拿的是alist[i],或者是alist[j],此时后拿的人因为同样是绝顶聪明的人，所以调用s()函数
return max(alist[i] + s(alist, i + 1, j), alist[j] + s(alist, i, j - 1))
def s(alist, i, j):
"""alist[i:j]这个排列的纸牌被绝顶聪明的人后拿，最终能获得什么分数"""
if i == j: # 如果仅剩一张，肯定会被先拿的人拿走，后拿的人什么也拿不到
return 0
# 由于对手先拿，由于对方也是绝顶聪明的人，肯定会将最差的情况留给玩家。在对方拿完之后，此时玩家成了先拿的人
return min(f(alist, i + 1, j), f(alist, i, j - 1))
def winCard2(alist):
"""由暴力递归改成动态规划"""
if alist == [] or len(alist) == 0:
return 0
dpF = np.zeros((len(alist), len(alist)))
dpS = np.zeros((len(alist), len(alist)))
for j in range(len(alist)):
dpF[j][j] = alist[j]
for i in range(j - 1, -1, -1):
dpF[i][j] = max(alist[i] + dpS[i + 1][j], alist[j] + dpS[i][j - 1])
dpS[i][j] = min(dpF[i + 1][j], dpF[i][j - 1])
return max(dpF[0][len(alist) - 1], dpS[0][len(alist) - 1])
# 机器人处于位置M(1<=M<=N)时,既可以向左走，也可以向右走(M=1时，只能向右，M=N时，只能向左)。经过P步后，走到位置K，一共有多少种方法
def ways(N, curPosition, restSteps, K):
"""
:param N: 一共有1~N的位置
:param curPosition:
:param restSteps: 剩余走的步数
:param K: 最终停留的位置
:return: 一共有多少种走法
"""
if N < 2 or curPosition < 1 or curPosition > N or restSteps < 0 or K < 1 or K > N:
return 0
if restSteps == 0:
return 1 if curPosition == K else 0
if curPosition == 1:
res = ways(N, curPosition + 1, restSteps - 1, K)
elif curPosition == N:
res = ways(N, curPosition - 1, restSteps - 1, K)
else:
res = ways(N, curPosition + 1, restSteps - 1, K) + ways(N, curPosition - 1, restSteps - 1, K)
return res
def ways2(N, curPosition, restSteps, K):
if N < 2 or restSteps < 0 or K < 1 or K > N:
return 0
dp = np.zeros((restSteps + 1, N))
dp[0][K - 1] = 1
for i in range(1, restSteps + 1):
for j in range(0, N):
dp[i][j] = dp[i - 1][j - 1] if j - 1 >= 0 else 0
dp[i][j] += dp[i - 1][j + 1] if j + 1 < N else 0
return dp[restSteps][curPosition - 1]
def getMaxLength(alist, aim):
if alist == [] or len(alist) == 0 or aim <= 0:
return 0
leftPoint, rightPoint, maxLen = 0, 0, 0
sum = alist[0]
while rightPoint < len(alist):
if sum < aim:
rightPoint += 1
if rightPoint == len(alist):
break
sum += alist[rightPoint]
elif sum == aim:
maxLen = max(maxLen, rightPoint - leftPoint + 1)
sum -= alist[leftPoint]
leftPoint += 1
else:
sum -= alist[leftPoint]
leftPoint += 1
return maxLen
def getMinSteps(eggNum, floorNum):
"""
扔鸡蛋问题
:param eggNum:
:param floorNum:
:return:
"""
if eggNum < 1 or floorNum < 1:
return 0
dp = np.zeros((eggNum + 1, floorNum + 1))
for i in range(1, eggNum + 1):
for j in range(1, floorNum + 1):
dp[i][j] = j
for i in range(2, eggNum + 1):
for j in range(1, floorNum + 1):
for k in range(1, j):
dp[i][j] = min(dp[i][j], 1 + max(dp[i - 1][k - 1], dp[i][j - k]))
return dp
# 从0位置开始向右扩，假如扩到位置T时，仍满足累加和<sum。但加上minSumList[T+1]时，>sum。此时不是从1位置重新开始，
# 而是在原有的基础上减去alist[1]，看此时能否将minSumList[T+1]加上，因为我们求的是最长子数组的长度。这样做保证了右边界始终向右，
# 左边界也一直向右移动，做到了O(N).
def maxLengthAwesom(alist, aim):
if alist == []:
return 0
if len(alist) == 1:
return alist[0]
# minSumList[i]: i开头的所有子数组的最小累加和
# minSumIndexList[i]: 取得最小累加和的右边界
minSumList, minSumIndexList = [], []
minSumList.append(alist[-1])
minSumIndexList.append(len(alist) - 1)
for i in range(len(alist) - 2, -1, -1):
if minSumList[0] < 0:
minSumList.insert(0, alist[i] + minSumList[0])
minSumIndexList.insert(0, minSumIndexList[0])
else:
minSumList.insert(0, alist[i])
minSumIndexList.insert(0, i)
end, sumNum, res = 0, 0, 0
for i in range(len(alist)):
while end < len(alist) and sumNum + minSumList[end] <= aim:
sumNum += minSumList[end]
end = minSumIndexList[end] + 1
sumNum -= alist[i] if end > i else 0
res = max(res, end - i)
end = max(end, i + 1)
return res
# 当仅剩最后一个时，修改其编号为1，因此，由公式推导它对应的在最一开始的编号。
# 旧编号(链表长度长度为i)和新编号(链表长度为i-1)对应的公式：旧 = (新 - 1 + S) % i + 1(S:被杀编号)
# 编号 = (报数 - 1) % i + 1
# 被杀编号：S = (m - 1) % i + 1
# --> 旧 = (新 + m - 1) % i + 1
# 当仅剩最后一个时，修改其编号为1，因此，由公式推导它对应的在最一开始的编号。
def getLive(Len, m):
"""
:param Len: 总人数
:param m: 报到m就杀人
:return: 最后一个人
"""
if Len == 1:
return 1
return (getLive(Len - 1, m) + m - 1) % Len + 1
# 环形单链表的约瑟夫问题，链表长度N，时间复杂度O(N)
def josephusKill2(pHead, m):
if pHead is None or pHead.next == pHead or m < 1:
return pHead
cur = pHead.next
tmp = 1 # 链表长度
while cur != pHead:
tmp += 1
cur = cur.next
tmp = getLive(tmp, m) # 由最后一个生存者编号为1，根据公式回推在初始链表中的编号
tmp -= 1
while tmp != 0:
pHead = pHead.next
tmp -= 1
pHead.next = pHead
return pHead
def isMatch(str1, str2):
"""带有‘.’和‘*’的字符串匹配问题"""
if str1 == "" or str2 == "":
return False
strList1, strList2 = [], []
for i in str1:
strList1.append(i)
for i in str2:
strList2.append(i)
# return processMatchStr(strList1, strList2, 0, 0) if isValidStr(str1, str2) else False
return processMatchStr(strList1, strList2, 0, 0) and isValidStr(str1, str2)
def isValidStr(str1, str2):
"""检查两个字符串的有效性，str1字符串不能有.和*，str2字符串首字符不能是*，不能连着两个字符都是*"""
for i in str1:
if i in '.*':
return False
if str2[0] == '*':
return False
for i in range(len(str2) - 1):
if str2[i] == '*' and str2[i + 1] == '*':
return False
return True
def processMatchStr(strList1, strList2, start1, start2):
if start2 == len(strList2):
return start1 == len(strList1)
if start2 + 1 == len(strList2) or strList2[start2 + 1] != '*':
"""start2后面接的不是'*'(或者start2已经指向了最后一个字符，或是start2后面的字符不是'*')
在这种情况下，必须是三种情况都满足才会满足True。
start1并没有越界
此时两个字符串对应位置的字符相等，或是str2字符串对应的位置为'.'可以匹配任意的字符
在start1,start2位置之后的字符串都能匹配上"""
return start1 != len(strList1) and (strList1[start1] == strList2[start2] or strList2[start2] == '.') \
and processMatchStr(strList1, strList2, start1 + 1, start2 + 1)
"""此时，start2+1位置是'*',分为两种情况讨论
如果start1位置的字符和start2位置的字符不匹配，则start2+1位置的'*'起的作用是0个之前的字符，然后由start2+2位置的字符继续与start1位置的字符继续考虑匹配问题
假设此时从start1位置开始的str1是：a...,从start2位置开始的str2是b*...，
如果start1位置的字符和start2位置的字符匹配，则需要考虑start2+1位置的'*'所起的作用，是当做1倍、2倍、3倍...之前的字符进行匹配"""
while start1 != len(strList1) and (strList1[start1] == strList2[start2] or strList2[start2] == '.'):
"""假设此时从start1位置开始的str1是：aaab...,从start2位置开始的str2是a*...
首先考虑'*'只当做0倍，也就是str1从start1开始匹配，str2从start2+2开始匹配，如果不匹配
则考虑'*'当做1倍考虑，也就是str1从start1+1开始匹配，str2从start2+2开始匹配，如果不匹配
则考虑'*'当做2倍考虑，也就是str2从start1+1开始匹配，str2从start2+2开始匹配，如果不匹配
...
直到匹配或者某一个越界为止
"""
if processMatchStr(strList1, strList2, start1, start2 + 2):
return True
start1 += 1
return processMatchStr(strList1, strList2, start1, start2 + 2)
# dp(横轴：exp(范围[0, len(exp)]), 纵轴: str(范围[0, len(str)])))
# 由原题意可知，dp[i][j]与dp[i + 1][j + 1]、dp[i][j + 2]、dp[i++][j + 2]有关，因此,需要知道dp表中最后两列和最后一排的数，才能推出整张表
# 最后一列的意义：j=len(exp)，已经没有字符可用了，此时str仍有待匹配项，所以全部为False(除了i=len(str),j=len(exp)，此时匹配项和待匹配项整好全部耗尽，此位置为True)
# 倒数第二列的意义：此时exp仅剩最后一个字符，而待匹配项还有好多，全部为False。只有str[len(str)-1]==exp[len(exp)-1],或者exp[len(exp)-1]='.'时该位置为True，其他位置全为False
# 最后一排的意义：此时待匹配项str已经没有字符需要被匹配，而匹配项还有好多。只有匹配项满足'a*a*a*...'，这样才会为True，否则是False
# 当推出普遍位置后，发现basicase不够，需要还原到原题意，把欠缺的位置补上
def isMatchDPMatrix(str1, str2):
if str1 == "" or str2 == "":
return False
strList1, strList2 = [], []
for i in str1:
strList1.append(i)
for i in str2:
strList2.append(i)
if not isValidStr(str1, str2):
return False
dpMatrix = initDPMap(strList1, strList2)
for i in range(len(strList1) - 1, -1, -1):
for j in range(len(strList2) - 2, -1, -1):
if strList2[j + 1] != '*':
dpMatrix[i][j] = (strList1[i] == strList2[j] or strList2[j] == '.') and dpMatrix[i + 1][j + 1]
else:
si = i
while si != len(strList1) and (strList1[si] == strList2[j] or strList2[j] == '.'):
if dpMatrix[si][j + 2]:
dpMatrix[i][j] = 1
break
si += 1
if dpMatrix[i][j] != 1:
dpMatrix[i][j] = dpMatrix[si][j + 2]
return dpMatrix[0][0]
def initDPMap(strList1, strList2):
strLen1, strLen2 = len(strList1), len(strList2)
dpMatrix = np.zeros((strLen1 + 1, strLen2 + 1))
dpMatrix[strLen1][strLen2] = 1
for j in range(strLen2 - 2, -1, -2):
# 最后一排要满足'a*a*a*...'这种情况，才会为True，否则为False
if strList2[j] != '*' and strList2[j + 1] == '*':
dpMatrix[strLen1][j] = 1
else:
break
if strLen1 > 0 and strLen2 > 0:
if strList2[strLen2 - 1] == '.' or strList1[strLen1 - 1] == strList2[strLen1 - 1]:
# 此时str1还剩最后一个待匹配项，str2也仅剩最后一个匹配项。
dpMatrix[strLen1 - 1][strLen2 - 1] = 1
return dpMatrix