解法1：hash记录，如果重复直接退出，时间O(n),空间O(n) 解法2：鸽笼原理：判断i==(nums[i]=m)，相等判断下一个数字，不相等则判断nums[i]==nums[m],出现重复，不相等调整nums[i]。时间O(n),空间O(1) 解法3：排序查找相同。时间O(nlogn),空间O(1)
hashmap = {} for i in nums: if i in hashmap: return i hashmap[i]=1 for i in range(len(nums)): while nums[i] != i: if nums[nums[i]] == nums[i]: return nums[i] nums[nums[i]] , nums[i] = nums[i] , nums[nums[i]]解法：站在右上角看,这个矩阵其实就像是一个Binary Search Tree。从右上角开始p，等于p返回，小于p在左边，大于p在下方。时间O(n*m),空间O(1)
if len(matrix)==0 or len(matrix[0])==0: return False row,col = 0,len(matrix[0])-1 while row<len(matrix) and col>=0: if matrix[row][col]>target: col-=1 elif matrix[row][col]<target: row+=1 else: return True return False解法1：从后面开始，遇到空格替换，减少空间使用，可以先扩充空格*2个空间。时间O(len(s),空间O(len(s)) 解法2：从前面开始，遇到空格替换。时间O(len(s)),空间O(len(s))
res = "" for i in range(len(s)-1,-1,-1): if s[i]!=' ': res = s[i]+res else: res = ' '+res return res return s.replace(" "," ")解法：遍历链表，将每个值加入res，结果反转或是使用insert,使用栈先进后出的特性，全部读完后反向输出。时间空间O(n)
res = [] while head: res.append(head.val) head = head.next return res[::-1]解法：根据先序划分左右子树，然后递归调用，时间空间O(n)
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: if not inorder: return None root_val = preorder.pop(0) index_root = inorder.index(root_val) root = TreeNode(root_val) root.left = self.buildTree(preorder,inorder[:index_root]) root.right = self.buildTree(preorder,inorder[index_root+1:]) return root解法：入栈保存在stack_in,出栈保存在stack_out,删除时将stack_in反向保存在out里。 时间空间O(n)
def __init__(self): # 入栈和出栈分别维护 self.stack_in=[] self.stack_out=[] def appendTail(self, value: int) -> None: self.stack_in.append(value) def deleteHead(self) -> int: if self.stack_out==[]: if self.stack_in==[]: return -1 else: while self.stack_in: self.stack_out.append(self.stack_in.pop()) return self.stack_out.pop()解法：dp[i + 1] = dp[i] + dp[i - 1] dp[n]，即斐波那契数列的第 n 个数字。 时间O(n) 空间O(1)
#Python 由于语言特性可以省去 sumsum 辅助变量和大数越界处理 a, b = 0, 1 for _ in range(n): a, b = b, a+b return a % 1000000007解法：dp[i ] = dp[i-2] + dp[i - 1] 。 时间O(n) 空间O(1)
def numWays(self, n: int) -> int: a,b=1,1 for _ in range(n): temp = (a+b)00000007 a,b=b,temp return a解法：二分判断可能无序的情况（右边），如果顺序，最小点在m处r=m;如果乱序，最小点在[m+1,r]l=m+1;相等的时候，不确定状况，从右边下来保守。时间O(logn)空间O(1)
l, r =0,len(numbers)-1 while l<r: m = (l+r)//2 if numbers[m]<numbers[r]: r=m elif numbers[m]>numbers[r]: l=m+1 else: r-=1 return numbers[l]解法：DFS+递归，每次判断当前字母的合法性（索引越界，是否为当前查找值），使用递归判断下一个字母，直到长度为k=len(word)。时间O(3kmn)每次递归深度为k,每次3个（不走前路），因此每次时间为O(3k),可查找元素为m*n,空间O(k)
def dfs(i,j,k): # 行、列越界，不相等 if not 0<=i<row or not 0<=j<col or board[i][j]!=word[k]: return False if k==len(word)-1: return True tmp, board[i][j] = board[i][j], '/' # 在调用邻居时，保证当前不可访问 res = dfs(i-1,j,k+1) or dfs(i+1,j,k+1) or dfs(i,j-1,k+1) or dfs(i,j+1,k+1) board[i][j] = tmp return res row,col = len(board),len(board[0]) for i in range(row): for j in range(col): if dfs(i,j,0): return True return False即使是k=0，也能走一步（0，0）.首先将（0，0）保存，每一步只能向下或向右走，只需判断当前数位和是否合法。时空O(mn)
def digitsum(n): n = 0 while(v): n+=v v = v//10 return n def movingCount(self, m: int, n: int, k: int) -> int: vis = set([(0, 0)]) for i in range(m): for j in range(n): if ((i - 1, j) in vis or (i, j - 1) in vis) and digitsum(i) + digitsum(j) <= k: vis.add((i, j)) return len(vis)尽可能的剪出3和2，3的优先级最高.将绳子 .以相等的长度等分为多段 ，得到的乘积最大n=3a+b,b=0是，res=3a;b=1时，res=3a-1x2x2;b=2时，res=3ax2
if n<=3: return n-1 s = 1 while n>4: s*=3 n-=3 return s*n区别是大整数溢出，需要取余：快速幂求余
a,b,x,p,rem=n//3-1,n%3,3,1000000007,1 while a>0: # (x^a-1^) % p # 奇数 if a%2: rem = (rem*x)%p x = x**2%p a = a//2 if b==0: return (rem*3)%p elif b==1: return (rem*4)%p else: return (rem*6)%p1&1=1 1&0=0,时间O(log2n),空间O(1)
res = 0 while n: res += n&1 n>>=1 return res1&1=1 1&0=0,时间O(log2n),空间O(1)
def myPow(self, x: float, n: int) -> float: if x==0: return 0 if n<0: x,n=1/x,-n rem = 1 while n>0: if n%2:rem *= x x *=x n//=2 return rem使用哑节点
def deleteNode(self, head: ListNode, val: int) -> ListNode: dummy = ListNode(float('inf')) dummy.next = head pre,p = dummy,dummy.next while p: if p.val == val: pre.next = p.next break pre,p = p,p.next return dummy.next当前在（i，j）主要考虑的是✳号：分为两种可能，匹配前面字符0次，转移（i,j+2）;匹配一次，转移s[i]=p[j] and（i+1，j）
def isMatch(self, s: str, p: str) -> bool: memo = {} def dp(i,j): # 记在备忘录 if (i,j) in memo: return memo[(i,j)] # j超出pattern时，若i此时也超出s，则成功，否则失败 if j==len(p): return i==len(s) # j没有超出，i没有超出，现在匹配第一个是否成功(第一个有两种可能，‘.’或是‘s[i]’) first_match = i<len(s) and p[j] in [s[i],'.'] # 判断‘*’的存在 if j<=len(p)-2 and p[j+1]=='*': # 匹配0次（pj走两步，si不走） 或 匹配当前字符s[i]一次(si走一步,p不走) ans = dp(i,j+2) or (first_match and dp(i+1,j)) else: # 没有‘*’，直接判断第一个字符 ans = first_match and dp(i+1,j+1) memo[(i,j)]=ans return ans return dp(0,0)状态机states[i] ，其中 i 为所处状态， states[i]使用哈希表存储可转移至的状态
def isNumber(self, s: str) -> bool: # states[i] ，其中 i 为所处状态， states[i]使用哈希表存储可转移至的状态 # A[.[B]][e/EC] # 从开始可能的状态 ' ':继续作为开始, 's'：e之前的符号, 'd'：数字, '.'：小数点 # e之前的符号s:可转移状态有'd' '.' # A是小数点之前的整数：可转移状态有'd', '.' , 'e', ' ' # B是小数点之后的数字：可转移状态有'd', 'e', ' ' # 开始之后直接是小数点：可转移状态有'd' # e 可转移状态有's', 'd' # e之后的符号：可转移状态有'd' # C是e之后的数字：可转移状态有'd', , ' ' # 结束空格，只能一直空格到末尾：转移状态' ' states = [ { ' ': 0, 's': 1, 'd': 2, '.': 4 }, # 0. start with 'blank' 空格开始 { 'd': 2, '.': 4 } , # 1. 'sign' before 'e' 出现在e之前的符号 { 'd': 2, '.': 3, 'e': 5, ' ': 8 }, # 2. 'digit' before 'dot' 出现在小数点之前的数字 { 'd': 3, 'e': 5, ' ': 8 }, # 3. 'digit' after 'dot' 出现在小数点之后的数字 { 'd': 3 }, # 4. 'digit' after 'dot' (‘blank’ before 'dot') 空格后直接就是小数点，小数点之后的数字 { 's': 6, 'd': 7 }, # 5. 'e' 出现e { 'd': 7 }, # 6. 'sign' after 'e' e之后的符号 { 'd': 7, ' ': 8 }, # 7. 'digit' after 'e' e之后的数字 { ' ': 8 } # 8. end with 'blank' 结束空格符 ] p = 0 # start with state 0 for c in s: # c是下一个转移状态 if '0' <= c <= '9': t = 'd' # digit elif c in "+-": t = 's' # sign elif c in ".eE ": t = c # dot, e, blank else: t = '?' # unknown # t不在哈希表 states[p]中，说明无法转移至下一状态，因此直接返回 False if t not in states[p]: return False p = states[p][t] return p in (2,3,7,8)左右两个指针,如果左为奇，则左指针前移；如果右为偶，则右指针后移;如果左指向数组元素为偶，右指向数组元素为奇，互相交换位置
def exchange(self, nums: List[int]) -> List[int]: i,j =0, len(nums)-1 while i<j: # 找偶数 if nums[i]&1==1: i+=1 # 找奇数 elif nums[j]&1==0 and i<j: j-=1 else: nums[i],nums[j] = nums[j],nums[i] i+=1 j-=1 return nums双指针：指针p走k步；然后两个指针p,q一起走，p走到头时，q走了lenth-k步，即倒数第k个
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode: p,q=head,head while k: p = p.next k-=1 while p: p, q = p.next, q.next return q新建尾结点q=None，从头遍历链表，每次将头结点指向尾结点，并将头结点指向下一个节点，尾结点更新为当前节点
def reverseList(self, head: ListNode) -> ListNode: q = None while head: temp = head.next head.next = q q = head head = temp return q def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: dummy = ListNode(0) L = dummy while l1 and l2: if l1.val<=l2.val: L.next = l1 l1=l1.next else: L.next = l2 l2=l2.next L = L.next if l1: L.next = l1 if l2: L.next = l2 return dummy.next哑节点 时空O(M+N)
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: dummy = ListNode(0) L = dummy while l1 and l2: if l1.val<=l2.val: L.next = l1 l1=l1.next else: L.next = l2 l2=l2.next L = L.next if l1: L.next = l1 if l2: L.next = l2 return dummy.next递归匹配，使用原函数找到第一个匹配点B的根节点；递归函数匹配B的左右子树 时间O(MN)：先序遍历A树时间O(M)，每次调用递归函数O(N)。空间O(M)，空间栈占用的A的节点
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool: def Recur(A,B): # 当节点 B 为空：说明树 B 已匹配完成 if not B:return True # 当节点A为空，B不为空或是A!=B，匹配错误， if not A or A.val!=B.val:return False # 匹配左右子树 return Recur(A.left,B.left) and Recur(A.right,B.right) # 特例是第一次传参的A,B为空时错误.找到第一个匹配点后会调用 return bool( A and B) and (Recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B))使用队列，将每一层由左至右记录下来，并将每个节点的左右置换,时间O(n),空间O(最大行)
def mirrorTree(self, root: TreeNode) -> TreeNode: if not root:return root queue = collections.deque([root]) while queue: lenth = len(queue) for i in range(lenth): node = queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) node.left, node.right = node.right, node.left return root递归调用，每次判断左左-右右，左右-右左 时间O(N)，最多调用N/2个节点；空间O(N)，最差的链表状态占用空间O(N)
def isSymmetric(self, root: TreeNode) -> bool: return self.check(root,root) def check(self,p,q): if not p and not q:return True elif p and q and p.val==q.val: return self.check(p.left,q.right) and self.check(p.right,q.left) else: return False按照顺时针打印，左->右（上）->下（右）->左（下）->上，判断是否到达边界 时间O(MN) 空间O(1)
def spiralOrder(self, matrix: List[List[int]]) -> List[int]: if not matrix: return [] left,right,up,down,res,i = 0,len(matrix[0])-1,0,len(matrix)-1,[],0 while True: # left to right 上边界 up 加 1 up>down for i in range(left,right+1): res.append(matrix[up][i]) up+=1 if up>down: break # up to down 右边界 right减 1 right<left for i in range(up,down+1): res.append(matrix[i][right]) right-=1 if left>right: break # right to left 下边界 down减 1 up>down for i in range(right,left-1,-1): res.append(matrix[down][i]) down-=1 if up>down: break # down to up 左边界 left加 1 right<left for i in range(down,up-1,-1): res.append(matrix[i][left]) left+=1 if left>right: break return res使用min_stack存储当前最小值 时间O(1)，空间O(N)
class MinStack: import math def __init__(self): """ initialize your data structure here. """ self.stack = [] self.min_stack = [math.inf] def push(self, x: int) -> None: self.stack.append(x) self.min_stack.append(min(x,self.min_stack[-1])) def pop(self) -> None: if len(self.stack)==0: return None self.stack.pop() self.min_stack.pop() def top(self) -> int: return self.stack[-1] def min(self) -> int: return self.min_stack[-1]使用一个栈模拟入栈出栈操作，如果栈顶是出栈元素，出栈并且出栈元素向后移动，否则入栈 时空O(N)
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool: stack = [] i=0 for num in pushed: stack.append(num) while stack and stack[-1]==popped[i]: stack.pop() i+=1 return not stack层次遍历 时间O(N) 空间O(N)
def levelOrder(self, root: TreeNode) -> List[int]: if not root:return [] queue = collections.deque([root]) res = [] while queue: node = queue.popleft() res.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return res层次遍历+记录行数 时间O(N) 空间O(N)
def levelOrder(self, root: TreeNode) -> List[List[int]]: if not root:return [] h=0 queue = collections.deque([root]) res = [] while queue: layer = [] lenth = len(queue) for i in range(lenth): node = queue.popleft() layer.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) # 奇数层，逆序 if h&1: res.append(layer[::-1]) else: res.append(layer) h+=1 return res二叉搜索树:左<中<右，左子树始终小于root和右子树。整个树是float(‘inf’)的左子树，现将右子树以及根入栈，遇到左子树时，出栈并更新当前root。若左子树存在比root大的数，直接False 时空O(N)
def verifyPostorder(self, postorder: List[int]) -> bool: root,stack=float('inf'),[] for i in range(len(postorder)-1,-1,-1): if postorder[i]>root:return False while stack and stack[-1]>postorder[i]: root = stack.pop() stack.append(postorder[i]) return True中序遍历，每次判断当前节点是否为叶子结点以及sum==0,成功记录路径；遍历其左右节点。遍历完成当前节点，路径删除 时空O(N)
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]: res,path = [],[] def dfs(node,s): if not node:return path.append(node.val) s -= node.val if s==0 and node.left==None and node.right==None: res.append(list(path)) dfs(node.left,s) dfs(node.right,s) path.pop() dfs(root,sum) return res每个节点复制之后放在当前节点之后，复制random，最后拆分链表 时间O(N) 空间O(1)
def copyRandomList(self, head: 'Node') -> 'Node': if not head: return head cur = head while cur: new_node = Node(cur.val,None,None) new_node.next = cur.next cur.next=new_node cur = new_node.next cur = head while cur: cur.next.random = cur.random.next if cur.random else None cur = cur.next.next old, new = head, head.next new_head = head.next while old: old.next = old.next.next new.next = new.next.next if new.next else None old, new = old.next, new.next return new_headLeft:prev right:next 中序遍历最后是尾结点，记录头结点head以及前节点prev，更改头结点与尾结点的l,r，对节点node处理prev.right=node;node.left=prev 。解法1：使用递归。解法2：使用堆栈 时间O(N) 空间O(N)
def treeToDoublyList(self, root: 'Node') -> 'Node': def dfs(node): if not node:return dfs(node.left) if self.pre==None: # 头结点 self.head = node else: node.left = self.pre self.pre.right = node self.pre = node dfs(node.right) if not root:return self.pre = None dfs(root) self.head.left = self.pre self.pre.right = self.head return self.head def treeToDoublyList(self, root: 'Node') -> 'Node': if not root:return stack = [] pre=None while stack or root: if root: stack.append(root) root = root.left else: node = stack.pop() if pre==None: head = node else: pre.right = node node.left = pre pre = node root = node.right head.left=pre pre.right=head return head层次遍历：正向反向 时间O(N) 空间O(N)
def serialize(self, root): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ if not root: return "[]" res=[] queue = collections.deque([root]) while queue: node = queue.popleft() if node: res.append(str(node.val)) queue.append(node.left) queue.append(node.right) else: res.append('null') return "["+','.join(res)+"]" def deserialize(self, data): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ if data=="[]":return None vals = data[1:-1].split(',') i=1 root = TreeNode(vals[0]) queue = collections.deque([root]) while queue: node = queue.popleft() if vals[i]!='null': node.left = TreeNode(vals[i]) queue.append(node.left) i+=1 if vals[i]!='null': node.right = TreeNode(vals[i]) queue.append(node.right) i+=1 return root全排列,固定第x位，固定x+1位，一直到最后一位存储c.第x位[x,n-1],第x+1范围是[x+1,n-1] 时间O(N！) 空间O(N2)
def permutation(self, s: str) -> List[str]: c, n, res = list(s), len(s), [] def dfs(x): if x==n-1: res.append("".join(c)) dic = set() for i in range(x,n): if c[i] in dic:continue dic.add(c[i]) c[i], c[x] = c[x], c[i] dfs(x+1) c[i], c[x] = c[x], c[i] dfs(0) return res解法1：需要的数字出现次数多于一半 那么排序后必定在中间 时间O(NlogN) 空间O(1)
def majorityElement(self, nums: List[int]) -> int: nums.sort() return nums[len(nums)//2]解法2：摩尔投票，由于众数出现的次数超过数组长度的一半；若记 众数 的票数为 +1+1 ，非众数 的票数为 -1−1 ，则一定有所有数字的 票数和 > 0>0 时间O(N) 空间O(1)
def majorityElement(self, nums: List[int]) -> int: votes=0 for num in nums: if votes==0: x = num votes += 1 if num==x else -1 count=0 for num in nums: if num==x: count+=1 return x if count>len(nums)//2 else 0解法：快速选择，类似于快速排序的分治法 时间O(N)，最坏会退化到O(n^2) 空间O(N)
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]: # 快速选择 n = len(arr) if n==0 or k>n: return if k==0: return [] def quickselect(l,r): pivot = arr[l] low = l+1 high = r while True: while low<=high and arr[low]<=pivot: low+=1 while high>=low and arr[high]>=pivot: high-=1 if low>high: break arr[low], arr[high] = arr[high], arr[low] arr[l], arr[high]=arr[high], arr[l] return high l, r = 0, len(arr)-1 while l<=r: m = quickselect(l,r) if m==k: break elif m<k: l = m+1 else: r = m-1 return arr[:k]解法：插入数字的排序，使用A是小顶堆，保存较大的那一半，如果是奇数，多保存一个元素，B是大顶堆，保存较小的那一半。向A中插入元素，先在B里比较，然后较小一半的最大值放在A堆 插入时间O(logN) ，访问时间O(1)空间O(N)
class MedianFinder: def __init__(self): """ initialize your data structure here. """ self.A = [] self.B = [] def addNum(self, num: int) -> None: if len(self.A)==len(self.B): heappush(self.B,-num) heappush(self.A,-heappop(self.B)) else: heappush(self.A,num) heappush(self.B,-heappop(self.A)) def findMedian(self) -> float: return self.A[0] if len(self.A)!=len(self.B) else (self.A[0]-self.B[0])/2.0解法：对于第i个数字要么自成一派，要么和前面的子数组和合并 dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]); 插入时间O(N)空间O(1)
def maxSubArray(self, nums: List[int]) -> int: res= nums[0] for i in range(1,len(nums)): if nums[i-1]>0: nums[i] += nums[i-1] res = max(res,nums[i]) return res解法：字符串的拼接规则，若x+y>y+x:则x>y; 插入时间O(NlogN)空间O(N)
def minNumber(self, nums: List[int]) -> str: def sort_rule(x,y): a, b = x+y, y+x if a>b: return 1 elif b>a: return -1 else: return 0 strs = [str(num) for num in nums] strs.sort(key = functools.cmp_to_key(sort_rule)) return "".join(strs)解法：翻译方法增加点在于10-25之间两种状态，dp[i]:0-i之间的翻译方法。如果num_l[i-1], num_l[i]处于10-25，那当前的翻译方式由dp[i-1]和dp[i-2]得到。举例：122 指向最后一个2时，dp[2] = dp1+dp0 时间O(logN)时间复杂度是字符串的长度 空间O(logN)
def translateNum(self, num: int) -> int: num_l = list(map(int,str(num))) if len(num_l)<=1: return len(num_l) def helper(a: int, b:int) -> bool: x = a*10+b return x>=10 and x<=25 # dp dp = [0 for _ in num_l] # base case dp[0] = 1 dp[1] = 2 if helper(num_l[0],num_l[1]) else 1 for i in range(2,len(num_l)): if helper(num_l[i-1], num_l[i]): dp[i] = dp[i-1] + dp[i-2] else: dp[i] = dp[i-1] return dp[-1]解法1：翻译方法增加点在于10-25之间两种状态，dp[i]:0-i之间的翻译方法。如果num_l[i-1], num_l[i]处于10-25，那当前的翻译方式由dp[i-1]和dp[i-2]得到。举例：122 指向最后一个2时，dp[2] = dp1+dp0 解法2：每次判断最后两位，如果最后两位处于10-25则有两个选择num/10+num/100进行递归；如果不是那只有一种选择num/10 时间O(N) 时间复杂度是字符串的长度 空间O(N)
def translateNum(self, num: int) -> int: num_l = list(map(int,str(num))) if len(num_l)<=1: return len(num_l) def helper(a: int, b:int) -> bool: x = a*10+b return x>=10 and x<=25 # dp dp = [0 for _ in num_l] # base case dp[0] = 1 dp[1] = 2 if helper(num_l[0],num_l[1]) else 1 for i in range(2,len(num_l)): if helper(num_l[i-1], num_l[i]): dp[i] = dp[i-1] + dp[i-2] else: dp[i] = dp[i-1] return dp[-1] public int translateNum(int num) { if (num<=9) {return 1;} //获取输入数字的余数，然后递归的计算翻译方法 int ba = num0; //如果小于等于9或者大于等于26的时候，余数不能按照2位数字组合，比如56，只能拆分为5和6；反例25，可以拆分为2和5，也可以作为25一个整体进行翻译。 if (ba<=9||ba>=26) {return translateNum(num/10);} // ba=[10, 25]时，既可以当做一个字母，也可以当做两个字母 else {return translateNum(num/10)+translateNum(num/100);} } }** 解法：dp[i][j]=max(dp[i -1][j], dp[i][j - 1]) + grid[i - 1][j - 1],注意边界判断或是空间换时间减少边界判断 ** 时间O(MN) 空间O(MN)
def maxValue(self, grid: List[List[int]]) -> int: row, col = len(grid),len(grid[0]) dp = [[0 for j in range(col+1)] for i in range(row+1)] for i in range(1,row+1): for j in range(1,col+1): dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1]; return dp[row][col]解法：滑动窗口 时间O(N) 空间O(N)
def lengthOfLongestSubstring(self, s: str) -> int: if len(s)<=1: return len(s) windows = {} left, right, valid= 0, 0, 0 lenth = 0 while right<len(s): c = s[right] right+=1 windows[c] = windows.get(c, 0) + 1 # 判断左侧窗口是否要收缩:出现重复字符,left+1 while windows[c]>1: d = s[left] left+=1 # 进行窗口内数据的一系列更新 windows[d] -= 1 lenth = max(lenth,right-left) return lenth解法：任意一个丑数都是由小于它的某一个丑数*2，3或者5得到的,所有丑数的排列，必定就是3个数组的合并结果然后去重得到的 时间O(N) 空间O(N)
def nthUglyNumber(self, n: int) -> int: dp, a,b,c=[1]*n,0,0,0 for i in range(1,n): n2,n3,n5 = dp[a]*2,dp[b]*3,dp[c]*5 dp[i] = min(n2,n3,n5) if dp[i]==n2:a+=1 if dp[i]==n3:b+=1 if dp[i]==n5:c+=1 return dp[n-1]解法：Python 3.6 后，默认字典就是有序的，因此无需使用 OrderedDict() 时间O(N) 空间O(N)
def firstUniqChar(self, s: str) -> str: dic = {} for c in s: dic[c] = not c in dic for c in s: if dic[c]: return c return ' '解法：如果左边部分的数组第l个元素大于右边第r个元素，那么左边数组将有(n1-l)个都大于右边第r个元素 时间O(NlogN) 空间O(N)
def merge(self,arr1,arr2) -> List[int]: l,r=0,0 n1,n2=len(arr1),len(arr2) res = [] while l<n1 and r<n2: if arr1[l]>arr2[r]: self.ans+=(n1-l) res.append(arr2[r]) r+=1 else: res.append(arr1[l]) l+=1 return res+arr1[l:]+arr2[r:] def merge_sort(self,arr: List[int]) -> List[int]: n = len(arr) if n<=1: return arr left = self.merge_sort(arr[:n//2]) right = self.merge_sort(arr[n//2:]) return self.merge(left,right) def reversePairs(self, nums: List[int]) -> int: self.ans = 0 self.merge_sort(nums) return self.ans剑指 Offer 52. 两个链表的第一个公共节点 简单 解法：两个链表长度分别为L1+C、L2+C， C为公共部分的长度. 第一个人走了L1+C步后，回到第二个人起点走L2步；第2个人走了L2+C步后，回到第一个人起点走L1步。 当两个人走的步数都为L1+L2+C时就两个家伙就相爱了 时间O(L1+l2+c)空间O(1)
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: p, q = headA, headB while p!=q: p = headB if p==None else p.next q = headA if q==None else q.next return p剑指 Offer 56 - I. 数组中数字出现的次数 中等 解法：首先获取所有数字的xor,不相同的两个数字的最低位保存在diff，与diff一致类型保存在b，不同的保存在a 时间空间O(1)
def singleNumbers(self, nums: List[int]) -> List[int]: res = 0 for num in nums: res ^= num diff = res&(-res) a, b = 0, 0 for num in nums: # 与差距最低位不一致 if num&diff: a ^= num # 与差距最低位一致 else: b ^= num return [a,b]