维持两个栈：stack1负责插入，stack2负责删除   当进队列时，直接插入stack1;   当出队列时， 若stack2为空，则将stack1的元素依次弹出到stack2 若stack2不为空，则弹出stack2栈顶元素   # -*- coding:utf-8 -*- class Solution: def __init__(self): self.stack1 = [] # 负责插入 self.stack2 = [] # 负责删除 def push(self, node): self.stack1.append(node) def pop(self): # stack2为空时，将s...

逆波兰表达式计算  维持一个栈，存储操作数 遇到操作数则入栈 遇到运算符，则从弹出两个操作数进行计算，并将结果再存入栈中  注：这道题的除非运算，必须取整（四舍五入），即用int（b/a），而不能用b//a,双斜杠都是向下取整。 # # @param tokens string字符串一维数组 # @return int整型 # class Solution: def evalRPN(self , tokens: List[str]) -> int: stack = [] # 存储操作数 for i in tokens: if i in "+-*/": a = stack.pop() b ...

# # 返回表达式的值 # @param s string字符串 待计算的表达式 # @return int整型 # class Solution: def solve(self , s: str) -> int: # 对符号和数字进行分离 arr = [] for i in s: if len(arr) >= 1 and arr[-1][0] in "0123456789" and '0' <= i <= '9': temp = arr.pop() arr.append(temp+i) else: arr.append(i) # 维持两个栈，一个保存符号，一个保存数字...

# 输入 I = input().split()[1:] R = map(str,sorted(map(int,set(input().split()[1:])))) # 匹配满足条件的I res = [] for i in R: # 临时存储结果，为了后面在最前面加入数量 tempI = [] for j in range(len(I)): if i in I[j]: tempI.append(j) tempI.append(I[j]) # 加入数量 if tempI: res.append(i) res.append(int(len(tempI)/2)) for j in tempI: r...

# 输入 n = int(input()) # 找到小于n的所有素数 lst = [True for i in range(n)] prime = [] for i in range(n): if i < 2: lst[i] = False else: if lst[i]: prime.append(i) temp = i*i while temp < n: lst[temp] = False temp += i # 从可能的素数中，找到两个素数的和为n，且距离最小的 res = [] for i in prime: target = n - i if target in prim...

# 匈牙利算法 def match(i): for j in range(M): # 有边且未访问 if matrix[i][j] == 1 and not visit[j]: visit[j] = True # 如果暂无匹配，或者原来匹配的元素可以找到新的匹配 if matched[j] == -1 or match(matched[j]): matched[j] = i return True return False while True: try: # 输入 n = int(input()) lst = list(map(int,input().split())) except: br...

while True: try: A,B = map(int,input().split()) val = 1 for i in range(2,min(A,B)+1): while A%i == 0 and B%i ==0: val = val*i A = A//i B = B//i print(val*A*B) except: break

队列 # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # @param root TreeNode类 # @return int整型一维数组 # class Solution: def PrintFromTopToBottom(self , root: TreeNode) -> List[int]: if not root: return queue,res = [root],[] while len(queue) > 0: # 弹出...

集合 # 输入 n = int(input()) weight = list(map(int,input().split())) weightNum = list(map(int,input().split())) # 整合 arr = [] for i in range(n): for j in range(weightNum[i]): arr.append(weight[i]) # 所有组合情况 res = {0} for i in arr: for j in list(res): # 集合去重 res.add(i+j) print(len(res))

滑动窗口+哈希 # # @param S string字符串 # @param T string字符串 # @return string字符串 # class Solution: def minWindow(self , S: str, T: str) -> str: # 维护两个哈希表，hashT表示需要的字符，hash1表示记录窗口内满足条件的字符 hashT = {} for i in list(T): if i not in hashT: hashT[i] = 1 else: hashT[i] += 1 # 一次遍历找“可行解” res = '' for i in range(l...

中心扩展算法 遍历字符串，分别以每个字符为中心，往两边扩展，寻找最长回文子串 中心可能有两种情况：  以单独一个字符为中心进行扩展，针对如‘aba’的字符串 以两个字符为中心，针对如‘abba’的字符串  # 输入字符串 string = input() maxLength = 0 # 分别以每个字符为中心，向外扩展 for i in range(len(string)): # 以一个字符为中心的情况，如'bab' step = 0 while 0 <= i-step and i+step < len(string): if string[i+step] == string[i-s...

回溯 # # @param S int整型一维数组 # @return int整型二维数组 # class Solution: def subsets(self , S: List[int]) -> List[List[int]]: # res收集所有子集，track记录访问过的元素 res,track = [],[] def backTrack(S,start,track): res.append(track[:]) if len(track) == len(S): return for i in range(start,len(S)): track.append(S[i]) back...

回溯  参考：https://mp.weixin.qq.com/s/nMUHqvwzG2LmWA9jMIHwQQ   def check(string,track): # 触发结束条件 if len(track) == len(string): res.append(''.join(track)) return for i in range(len(string)): # 排除不合法的选择 if string[i] in track: continue # 做选择 track.append(string[i]) check(string, track) # 取消选择 track.pop() #...

栈 借助栈结构，遍历字符串：  遇到左括号，则入栈 遇到右括号，跳出栈顶元素，与右括号进行比较，判断是否匹配。若匹配，则继续；若不匹配，则不合法。  此外，要特别注意两种情况： A.开始就遇到右括号，直接判断不合法； B.结束时，栈内还存在左括号，也不合法； # # @param s string字符串 # @return bool布尔型 # class Solution: def isValid(self , s: str) -> bool: stack = [] for i in range(len(s)): # 遇到左括号加入 if s[i] in ['(','[','{']: s...