BM1 反转链表
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @return ListNode类 # class Solution: def ReverseList(self , head: ListNode) -> ListNode: # write code here pre=None while(head): tmp=head.next head.next=pre pre=head head=tmp return pre
BM2 链表内指定区间反转
class Solution: def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode: # write code here dummy=ListNode(-1) dummy.next=head pre=dummy for i in range(m-1): pre=pre.next cur=pre.next for i in range(n-m): tmp=cur.next cur.next=tmp.next tmp.next=pre.next pre.next=tmp return dummy.next
BM3 链表中的节点每k个一组翻转
class Solution: def reverseKGroup(self , head: ListNode, k: int) -> ListNode: # write code here a=[] s=[] while(head): a.append(head.val) head=head.next if(len(a)==k): s.extend(a[::-1]) a=[] if len(a)<k: s.extend(a) dummy=ListNode(-1) pre=dummy for num in s: node=ListNode(num) pre.next=node pre=node return dummy.next
BM4 合并两个排序的链表
class Solution: def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode: # write code here dummy=ListNode(0) cur=dummy p1,p2=pHead1,pHead2 while p1 and p2: if p1.val<=p2.val: cur.next=p1 p1=p1.next else: cur.next=p2 p2=p2.next cur=cur.next cur.next=p1 if p1 else p2 return dummy.next
BM5 合并k个已排序的链表
class Solution: def merge(self,p1,p2): dummy=ListNode(-1) pre=dummy while p1 and p2: if p1.val<=p2.val: pre.next=p1 p1=p1.next else: pre.next=p2 p2=p2.next pre=pre.next pre.next=p1 if p1 else p2 return dummy.next def mergeKLists(self , lists: List[ListNode]) -> ListNode: # write code here if not lists: return None res=lists[0] for i in range(1,len(lists)): res=self.merge(res,lists[i]) return res
BM6 判断链表中是否有环
class Solution: def hasCycle(self , head: ListNode) -> bool: s=set() while(head): if head in s: return True else: s.add(head) head=head.next return False
BM7 链表中环的入口结点
class Solution: def EntryNodeOfLoop(self, pHead): # write code here slow,fast=pHead,pHead while fast and fast.next: slow=slow.next fast=fast.next.next if slow==fast: break if not fast or not fast.next: return None slow=pHead while(slow!=fast): slow=slow.next fast=fast.next return slow
BM8 链表中倒数最后k个结点
class Solution: def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode: # write code here fast,slow=pHead,pHead while k>0 and fast: k-=1 fast=fast.next if k>0: return while(fast): fast=fast.next slow=slow.next return slow
BM9 删除链表的倒数第n个节点
class Solution: def removeNthFromEnd(self , head: ListNode, n: int) -> ListNode: # write code here dummy=ListNode(-1) dummy.next=head pre=dummy cur=head for i in range(n): cur=cur.next while cur: cur=cur.next pre=pre.next pre.next=pre.next.next return dummy.next
BM10 两个链表的第一个公共结点
class Solution: def FindFirstCommonNode(self , pHead1 , pHead2 ): # write code here p1,p2=pHead1,pHead2 len1,len2=0,0 while p1: p1=p1.next len1+=1 while p2: p2=p2.next len2+=1 if len1<len2: pHead1,pHead2=pHead2,pHead1 len1,len2=len2,len1 p1,p2=pHead1,pHead2 for i in range(len1-len2): p1=p1.next while p1!=p2: p1=p1.next p2=p2.next return p1
BM11 链表相加(二)
class Solution: def addInList(self , head1: ListNode, head2: ListNode) -> ListNode: # write code here nums1,nums2=[],[] while head1: nums1.append(head1.val) head1=head1.next while head2: nums2.append(head2.val) head2=head2.next s,c=0,0 tmp=None while nums1 or nums2: if nums1 and nums2: s=nums1.pop()+nums2.pop()+c s1=s%10 c=s//10 node=ListNode(s1) node.next=tmp tmp=node elif nums1: s=nums1.pop()+c s1=s%10 c=s//10 node=ListNode(s1) node.next=tmp tmp=node else: s=nums2.pop()+c s1=s%10 c=s//10 node=ListNode(s1) node.next=tmp tmp=node if c: node=ListNode(c) node.next=tmp tmp=node return tmp
BM12 单链表的排序
class Solution: def sortInList(self , head: ListNode) -> ListNode: # write code here if not head or not head.next: return head slow,fast=head,head.next while fast and fast.next: slow=slow.next fast=fast.next.next mid=slow.next slow.next=None left=self.sortInList(head) right=self.sortInList(mid) dummy=cur=ListNode(-1) while left and right: if left.val<=right.val: cur.next=left left=left.next else: cur.next=right right=right.next cur=cur.next cur.next=left if left else right return dummy.next
BM13 判断一个链表是否为回文结构
class Solution: def isPail(self , head: ListNode) -> bool: # write code here s=[] while head: s.append(head.val) head=head.next return s==s[::-1]
BM14 链表的奇偶重排
class Solution: def oddEvenList(self , head: ListNode) -> ListNode: # write code here if not head or not head.next: return head evenhead=head.next odd,even=head,evenhead while even and even.next: odd.next=even.next odd=even.next even.next=odd.next even=odd.next odd.next=evenhead return head
BM15 删除有序链表中重复的元素-I
class Solution: def deleteDuplicates(self , head: ListNode) -> ListNode: # write code here cur=head if not head or not head.next: return head while cur.next: if(cur.val==cur.next.val): cur.next=cur.next.next else: cur=cur.next return head
BM16 删除有序链表中重复的元素-II
class Solution: def deleteDuplicates(self , head: ListNode) -> ListNode: # write code here dummy=pre=ListNode(-1) dummy.next=head cur=head while cur: while(cur.next and cur.val==cur.next.val): cur=cur.next if pre.next==cur: pre=cur else: pre.next=cur.next cur=cur.next return dummy.next
BM17 二分查找-I
class Solution: def search(self , nums: List[int], target: int) -> int: # write code here if not nums: return -1 l,r=0,len(nums) while(l<=r): mid=l+(r-l)//2 if nums[mid]==target: return mid elif nums[mid]<target: l=mid+1 else: r=mid-1 return -1
BM18 二维数组中的查找
class Solution: def Find(self , target: int, array: List[List[int]]) -> bool: # write code here def binary(target,nums): if not nums: return False l,r=0,len(nums)-1 while(l<=r): mid=l+(r-l)//2 if nums[mid]==target: return True elif nums[mid]<target: l=mid+1 else: r=mid-1 return False for nums in array: result=binary(target,nums) if result: return result return False
BM19 寻找峰值
class Solution: def findPeakElement(self , nums: List[int]) -> int: # write code here l,r=0,len(nums)-1 while(l<r): mid=(r+l)//2 if(nums[mid]<=nums[mid+1]): l=mid+1 else: r=mid return l
BM20 数组中的逆序对
class Solution: def rr(self,data): if len(data)<2: return 0 big,small=[],[] ans=0 pre=data[0] for num in data[1:]: if num>pre: big.append(num)#如果num>pre,不构成逆序对 else: small.append(num)#如果num<pre,则本身构成一个逆序对，与此同时big数组里的数肯定大于num，也构成逆序对 ans+=len(big)+1 return ans+self.rr(big)+self.rr(small) def InversePairs(self , nums: List[int]) -> int: # write code here return self.rr(nums)%1000000007
BM21 旋转数组的最小数字
class Solution: def minNumberInRotateArray(self , nums: List[int]) -> int: # write code here l,r=0,len(nums)-1 while(l<r): mid=(l+r)//2 if nums[mid]>nums[r]: l=mid+1 elif nums[mid]<nums[l]: r=mid else: r-=1 return nums[l]
BM22 比较版本号
class Solution: def compare(self , version1: str, version2: str) -> int: # write code here nums1=version1.split('.') nums2=version2.split('.') while nums1 and nums2: if(int(nums1[0])>int(nums2[0])): return 1 elif (int(nums1[0])<int(nums2[0])): return -1 else: nums1.pop(0) nums2.pop(0) if nums1: if int(''.join(nums1)): return -1 else: return 0 elif nums2: if int(''.join(nums2)): return 1 else: return 0 else: return 0
BM23 二叉树的前序遍历
class Solution: def preorderTraversal(self , root: TreeNode) -> List[int]: # write code here def preorder(list1,root): if not root: return list1.append(root.val) if(root.left): preorder(list1,root.left) if(root.right): preorder(list1,root.right) list1=list() preorder(list1,root) return list1
BM24 二叉树的中序遍历
class Solution: def inorder(self,l,root): if not root: return if(root.left): self.inorder(l,root.left) l.append(root.val) if(root.right): self.inorder(l,root.right) def inorderTraversal(self , root: TreeNode) -> List[int]: # write code here l=list() self.inorder(l,root) return l
BM25 二叉树的后序遍历
class Solution: def postorder(self,l,root): if(not root): return self.postorder(l,root.left) self.postorder(l,root.right) l.append(root.val) def postorderTraversal(self , root: TreeNode) -> List[int]: # write code here l=list() self.postorder(l,root) return l
BM26 二叉树的层序遍历
class Solution: def levelOrder(self , root: TreeNode) -> List[List[int]]: # write code here res=[] if not root: return res q=[] q.append(root) while q: path=[] for i in range(len(q)): root=q.pop(0) path.append(root.val) if root.left: q.append(root.left) if root.right: q.append(root.right) res.append(path) return res
BM27 按之字形顺序打印二叉树
class Solution: def Print(self , pRoot: TreeNode) -> List[List[int]]: # write code here if not pRoot: return [] q=[pRoot] res=[] flag=True while q: path=[] for i in range(len(q)): root=q.pop(0) path.append(root.val) if root.left: q.append(root.left) if root.right: q.append(root.right) if flag: res.append(path) else: res.append(path[::-1]) flag=not flag return res
BM28 二叉树的最大深度
class Solution: def maxDepth(self , root: TreeNode) -> int: # write code here if not root: return 0 return max(self.maxDepth(root.left),self.maxDepth(root.right))+1
BM29 二叉树中和为某一值的路径(一)
class Solution: def hasPathSum(self , root: TreeNode, sum: int) -> bool: # write code here if not root: return False if not root.left and not root.right: if root.val==sum: return True return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)
BM30 二叉搜索树与双向链表
class Solution: def Convert(self , pRootOfTree ): # write code here if not pRootOfTree: return None arr=[] def midtraverse(root): if not root: return midtraverse(root.left) arr.append(root) midtraverse(root.right) midtraverse(pRootOfTree) for i in range(len(arr[:-1])): arr[i].right=arr[i+1] arr[i+1].left=arr[i] return arr[0]
BM31 对称的二叉树
class Solution: def isSymmetrical(self , pRoot: TreeNode) -> bool: # write code here if not pRoot: return True def isSym(p1,p2): if not p1 and not p2: return True elif not p1 or not p2: return False elif p1.val!=p2.val: return False else: return isSym(p1.left,p2.right) and isSym(p1.right,p2.left) return isSym(pRoot.left,pRoot.right)
BM32 合并二叉树
class Solution: def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode: # write code here if not t1: return t2 if not t2: return t1 head=TreeNode(t1.val+t2.val) head.left=self.mergeTrees(t1.left,t2.left) head.right=self.mergeTrees(t1.right,t2.right) return head
BM33 二叉树的镜像
class Solution: def Mirror(self , pRoot: TreeNode) -> TreeNode: # write code here if not pRoot: return None tmp=pRoot.left pRoot.left=self.Mirror(pRoot.right) pRoot.right=self.Mirror(tmp) return pRoot
BM34 判断是不是二叉搜索树
class Solution: def isValidBST(self , root: TreeNode) -> bool: # write code here if not root: return True def recur(root,lower,up): if not root: return True if lower<root.val<up: return recur(root.left,lower,root.val) and recur(root.right,root.val,up) else: return False return recur(root,float('-inf'),float('+inf'))
BM35 判断是不是完全二叉树
class Solution: def isCompleteTree(self , root: TreeNode) -> bool: # write code here q=[root] flag=True while q: for i in range(len(q)): root=q.pop(0) if not root: flag=False else: if not flag: return False q.append(root.left) q.append(root.right) return True
BM36 判断是不是平衡二叉树
class Solution: def IsBalanced_Solution(self , pRoot: TreeNode) -> bool: # write code here def depth(root): if not root: return 0 return max(depth(root.left),depth(root.right))+1 if not pRoot: return True return abs(depth(pRoot.left)-depth(pRoot.right))<=1 and self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
BM37 二叉搜索树的最近公共祖先
class Solution: def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int: # 该子树没找到，返回-1 if not root: return -1 # 该节点是其中某一个节点 if root.val == o1 or root.val == o2: return root.val # 左子树寻找公共祖先 left = self.lowestCommonAncestor(root.left, o1, o2) # 右子树寻找公共祖先 right = self.lowestCommonAncestor(root.right, o1, o2) # 左子树为没找到，则在右子树中 if left == -1: return right # 右子树没找到，则在左子树中 if right == -1: return left # 否则是当前节点 return root.val
BM38 在二叉树中找到两个节点的最近公共祖先
class Solution: def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int: # write code here if not root: return -1 if root.val==o1 or root.val==o2: return root.val left=self.lowestCommonAncestor(root.left,o1,o2) right=self.lowestCommonAncestor(root.right,o1,o2) if left==-1: return right elif right==-1: return left else: return root.val
BM39 序列化二叉树
class Solution: def Serialize(self, root): def serial(root): if not root: self.s.append('#') return self.s.append(root.val) serial(root.left) serial(root.right) self.s=[] serial(root) return self.s def Deserialize(self, s): # write code here s=iter(s) t=next(s) if t=='#': return root=TreeNode(t) root.left=self.Deserialize(s) root.right=self.Deserialize(s) return root
BM40 重建二叉树
class Solution: def reConstructBinaryTree(self , preOrder: List[int], vinOrder: List[int]) -> TreeNode: # write code here if not preOrder: return None root=TreeNode(preOrder[0]) r=vinOrder.index(preOrder[0]) root.left=self.reConstructBinaryTree(preOrder[1:r+1],vinOrder[:r]) root.right=self.reConstructBinaryTree(preOrder[r+1:],vinOrder[r+1:]) return root
BM41 输出二叉树的右视图
class Solution: def construct(self , preOrder, inOrder): if not preOrder: return None root=TreeNode(preOrder[0]) mid=inOrder.index(preOrder[0]) root.left=self.construct(preOrder[1:mid+1],inOrder[:mid]) root.right=self.construct(preOrder[mid+1:],inOrder[mid+1:]) return root def solve(self , preOrder: List[int], inOrder: List[int]) -> List[int]: # write code here root=self.construct(preOrder,inOrder) if not root: return [] l=[] q=[root] while q: size=len(q) for i in range(size): node=q.pop(0) if i==size-1: l.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) return l
BM42 用两个栈实现队列
# -*- coding:utf-8 -*- class Solution: def __init__(self): self.stack1 = [] self.stack2 = [] def push(self, node): # write code here self.stack1.append(node) def pop(self): # return xx if not self.stack2: while(self.stack1): self.stack2.append(self.stack1.pop()) return self.stack2.pop()
BM43 包含min函数的栈
# -*- coding:utf-8 -*- class Solution: A=[] B=[] def push(self, node): # write code here self.A.append(node) if not self.B or node<=self.B[-1]: self.B.append(node) def pop(self): # write code here val=self.A.pop() if(self.B[-1]==val): self.B.pop() return val def top(self): # write code here return self.A[-1] def min(self): # write code here return self.B[-1]
BM44 有效括号序列
class Solution: def isValid(self , s: str) -> bool: # write code here A=[] for c in s: if(c=='(' or c=='{' or c=='['): A.append(c) elif(c==')'): if(not A or A.pop()!='('): return False elif(c==']'): if(not A or A.pop()!='['): return False elif(c=='}'): if(not A or A.pop()!='{'): return False else: return False return not A
BM45 滑动窗口的最大值
class Solution: def maxInWindows(self , num: List[int], size: int) -> List[int]: # 维持一个单调递减队列 if not size: return [] res=[] queue=[] for i in range(len(num)): if queue and i-queue[0]+1>size: queue.pop(0) while queue and num[queue[-1]]<num[i]: queue.pop() queue.append(i) if i-size+1>=0: res.append(num[queue[0]]) return res
BM46 最小的K个数
class Solution: def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]: # write code here input.sort() return input[:k]
BM47 寻找第K大
class Solution: def findKth(self , a: List[int], n: int, K: int) -> int: # write code here def quicksort(a,l,r): if l>r: return -1 pivot=a[l] low,up=l,r while(l<r): while l<r and a[r]<=pivot: r-=1 while l<r and a[l]>=pivot: l+=1 a[l],a[r]=a[r],a[l] a[l],a[low]=a[low],a[l] if l==K-1: return a[l] elif l<K-1: return quicksort(a,l+1,up) else: return quicksort(a,low,l-1) return quicksort(a,0,n-1)
BM48 数据流中的中位数
# -*- coding:utf-8 -*- class Solution: val = [] def Insert(self, num): # write code here if len(self.val) == 0: self.val.append(num) else: i = 0 #遍历找到插入点 while i < len(self.val): if num <= self.val[i]: break i = i + 1 #插入相应位置 self.val.insert(i, num) def GetMedian(self): # write code here n = len(self.val) if n % 2 == 1: return self.val[n // 2] else: return (self.val[n // 2] + self.val[n // 2 - 1]) / 2.0
BM49 表达式求值
class Solution: def solve(self , s: str) -> int: # write code here return eval(s)
BM50 两数之和
class Solution: def twoSum(self , numbers: List[int], target: int) -> List[int]: # write code here dic=dict() for i,num in enumerate(numbers): if target-num in dic: return [dic[target-num]+1,i+1] dic[num]=i
BM51 数组中出现次数超过一半的数字
from collections import Counter class Solution: def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int: # write code here dic=Counter(numbers) l=len(numbers) for num in numbers: if dic[num]>l/2: return num
BM52 数组中只出现一次的两个数字
from collections import Counter class Solution: def FindNumsAppearOnce(self , nums: List[int]) -> List[int]: # write code here dic=Counter(nums) res=[] for num in dic: if dic[num]==1: res.append(num) return sorted(res)
BM53 缺失的第一个正整数
class Solution: def minNumberDisappeared(self , nums: List[int]) -> int: # write code here A=set() for num in nums: A.add(num) i=1 while True: if i not in A: return i i+=1
BM54 三数之和
class Solution: def threeSum(self , num: List[int]) -> List[List[int]]: # write code here res=[] num.sort() n=len(num) i=0 while i<n-2: j=i+1 k=n-1 while j<k: s=num[i]+num[j]+num[k] if s<0: j+=1 elif s>0: k-=1 else: res.append([num[i],num[j],num[k]]) j+=1 k-=1 i+=1 res=[list(i) for i in set(tuple(i) for i in res)] return sorted(res)
BM55 没有重复项数字的全排列
class Solution: def permute(self , num: List[int]) -> List[List[int]]: # write code here def dfs(num,path,res): if not num: res.append(path) return for i in range(len(num)): dfs(num[:i]+num[i+1:],path+[num[i]],res) path,res=[],[] dfs(num,path,res) return sorted(res)
BM56 有重复项数字的全排列
class Solution: def permuteUnique(self , num: List[int]) -> List[List[int]]: # write code here def dfs(num,path,res): if not num: res.append(path) return for i in range(len(num)): dfs(num[:i]+num[i+1:],path+[num[i]],res) res,path=[],[] dfs(num,path,res) res=[list(i) for i in set(tuple(i) for i in res)] return sorted(res)
BM57 岛屿数量
class Solution: def solve(self , grid: List[List[str]]) -> int: # write code here def dfs(grid,i,j): if not 0<=i<len(grid) or not 0<=j<len(grid[0]) or grid[i][j]=='0': return grid[i][j]='0' dfs(grid,i-1,j) dfs(grid,i,j-1) dfs(grid,i+1,j) dfs(grid,i,j+1) m,n=len(grid),len(grid[0]) count=0 for i in range(m): for j in range(n): if grid[i][j]=='1': count+=1 dfs(grid,i,j) return count
BM58 字符串的排列
class Solution: def Permutation(self , str: str) -> List[str]: # write code here def dfs(num,path,res): if not num: res.append(''.join(path)) return for i in range(len(num)): dfs(num[0:i]+num[i+1:],path+[num[i]],res) l=list(str) path,res=[],[] dfs(l,path,res) return sorted(set(res))
BM59 N皇后问题
class Solution: def Nqueen(self , n: int) -> int: # write code here def dfs(cols,d1,d2): r=len(cols) if r==n: res.append(cols) return for i in range(n): if i not in cols and r-i not in d1 and r+i not in d2: dfs(cols+[i],d1+[r-i],d2+[r+i]) cols,d1,d2=[],[],[] res=[] dfs(cols,d1,d2) return len(res)
BM60 括号生成
class Solution: def generateParenthesis(self , n: int) -> List[str]: # write code here def dfs(l,r,path,res): #先考虑异常情况 if l>r or l<0 or r<0: return if l==0 and r==0: res.append(path) return dfs(l-1,r,path+'(',res) dfs(l,r-1,path+')',res) path,res='',[] dfs(n,n,path,res) return res
BM61 矩阵最长递增路径
class Solution: def solve(self , matrix: List[List[int]]) -> int: # write code here m,n=len(matrix),len(matrix[0]) mem=[[0]*n for i in range(m)] res=0 def dfs(i,j): if mem[i][j]!=0: return mem[i][j] mem[i][j]=1 for newx,newy in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]: if 0<=newx<m and 0<=newy<n and matrix[newx][newy]>matrix[i][j]: mem[i][j]=max(mem[i][j],dfs(newx,newy)+1) return mem[i][j] for i in range(m): for j in range(n): dfs(i,j) res=max(res,mem[i][j]) return res
BM62 斐波那契数列
class Solution: def Fibonacci(self , n: int) -> int: # write code here dp=[0]*n dp[0],dp[1]=1,1 for i in range(2,n): dp[i]=dp[i-1]+dp[i-2] return dp[n-1]
BM63 跳台阶
class Solution: def jumpFloor(self , number: int) -> int: # write code here n=number dp=[0]*(n+1) dp[0]=1 dp[1]=1 for i in range(2,n+1): dp[i]=dp[i-1]+dp[i-2] return dp[n]
BM64 最小花费爬楼梯
class Solution: def minCostClimbingStairs(self , cost: List[int]) -> int: # write code here n=len(cost) if(n==0): return 0 elif n==1: return cost[0] else: dp=[0]*(n+1) for i in range(2,n+1): dp[i]=min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]) return dp[n]
BM65 最长公共子序列(二)
class Solution: def LCS(self , s1: str, s2: str) -> str: # write code here if not s1 or not s2: return "-1" len1,len2=len(s1),len(s2) dp=[[0 for i in range(len2+1)]for j in range(len1+1)] for i in range(1,len1+1): for j in range(1,len2+1): if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]+1 else: dp[i][j]=max(dp[i-1][j],dp[i][j-1]) i,j=len1,len2 s=[] while(dp[i][j]!=0): if(dp[i][j]==dp[i-1][j]): i-=1 elif(dp[i][j]==dp[i][j-1]): j-=1 elif(dp[i][j]>dp[i-1][j-1]): i-=1 j-=1 s.append(s1[i]).join(s)[::-1] if not res: return "-1" else: return res
BM66 最长公共子串
class Solution: def LCS(self , str1: str, str2: str) -> str: # write code here maxlen=0 for i in range(len(str1)): if (str1[i-maxlen:i+1] in str2): res=str1[i-maxlen:i+1] maxlen+=1 return res
BM67 不同路径的数目(一)
class Solution: def uniquePaths(self , m: int, n: int) -> int: # write code here dp=[[0]*n for i in range(m)] for i in range(m): for j in range(n): if i==0 or j==0: dp[i][j]=1 else: dp[i][j]=dp[i-1][j]+dp[i][j-1] return dp[m-1][n-1]
BM68 矩阵的最小路径和
class Solution: def minPathSum(self , matrix: List[List[int]]) -> int: # write code here m,n=len(matrix),len(matrix[0]) dp=[[0]*n for i in range(m)] dp[0][0]=matrix[0][0] for i in range(1,m): dp[i][0]=dp[i-1][0]+matrix[i][0] for j in range(n): dp[0][j]=dp[0][j-1]+matrix[0][j] for i in range(1,m): for j in range(1,n): dp[i][j]=matrix[i][j]+min(dp[i-1][j],dp[i][j-1]) return dp[m-1][n-1]
BM69 把数字翻译成字符串
class Solution: def solve(self , nums: str) -> int: # write code here n=len(nums) if n==1: if '1'<=nums[0]<='9': return 1 else: return 0 dp=[1]*(n+1) for i in range(2,n+1): if nums[i-2:i]=='10' or nums[i-2:i]=='20': dp[i]=dp[i-2] elif '11'<=nums[i-2:i]<='19' or '21'<=nums[i-2:i]<='26': dp[i]=dp[i-1]+dp[i-2] elif nums[i-1]=='0': return 0 else: dp[i]=dp[i-1] return dp[n]
BM70 兑换零钱(一)
class Solution: def minMoney(self , arr: List[int], aim: int) -> int: # write code here dp=[float('+inf')]*(aim+1) dp[0]=0 if not arr: return -1 for i in range(1,aim+1): for j in range(len(arr)): if arr[j]<=i: dp[i]=min(dp[i],dp[i-arr[j]]+1) return dp[aim] if dp[aim]!=float('+inf') else -1
BM71 最长上升子序列(一)
class Solution: def LIS(self , arr: List[int]) -> int: # write code here n=len(arr) if not n: return 0 dp=[1]*n for i in range(n): for j in range(i): if arr[j]<arr[i]: dp[i]=max(dp[i],dp[j]+1) return max(dp)
BM72 连续子数组的最大和
class Solution: def FindGreatestSumOfSubArray(self , array: List[int]) -> int: # write code here if not array: return 0 n=len(array) s,res=float('-inf'),float('-inf') for i in range(n): s=max(s+array[i],array[i]) res=max(res,s) return res
BM73 最长回文子串
class Solution: def getLongestPalindrome(self , A: str) -> int: # write code here def judge(A,l,r): if l>r: return while l>=0 and r<(len(A)) and A[l]==A[r]: l-=1 r+=1 return r-l-1 res=1 for i in range(len(A)-1): len1=judge(A,i,i) len2=judge(A,i,i+1) res=max(res,max(len1,len2)) return res
BM74 数字字符串转化成IP地址
class Solution: def restoreIpAddresses(self , s: str) -> List[str]: # write code here res=[] n=len(s) i=1 while(i<4 and i<n-2): j=i+1 while(j<i+4 and j<n-1): k=j+1 while(k<j+4 and k<n): if(n-k>3): k+=1 continue a=s[:i] b=s[i:j] c=s[j:k] d=s[k:] if(int(a)>255 or int(b)>255 or int(c)>255 or int(d)>255): k+=1 continue if((len(a)>1 and int(a[0])==0) or (len(b)>1 and int(b[0])==0) or (len(c)>1 and int(c[0])==0) or (len(d)>1 and int(d[0])==0) ): k+=1 continue res.append(a+'.'+b+'.'+c+'.'+d) k+=1 j+=1 i+=1 return res
BM75 编辑距离(一)
class Solution: def editDistance(self , str1: str, str2: str) -> int: # write code here m,n=len(str1),len(str2) dp=[[0]*(n+1) for i in range(m+1)] for i in range(1,m+1): dp[i][0]=dp[i-1][0]+1 for j in range(1,n+1): dp[0][j]=dp[0][j-1]+1 for i in range(1,m+1): for j in range(1,n+1): if(str1[i-1]==str2[j-1]): dp[i][j]=dp[i-1][j-1] else: dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1 return dp[m][n]
BM76 正则表达式匹配
class Solution: def match(self , str: str, pattern: str) -> bool: # write code here l=len(pattern) if(l==0): return not str elif(l==1): if(len(str)==l and pattern[0] in {str[0],'.'}): return True else: return False else: firstmatch=str and pattern[0] in {str[0],'.'} if(pattern[1]=='*'): return self.match(str,pattern[2:]) or firstmatch and self.match(str[1:],pattern) else: return firstmatch and self.match(str[1:],pattern[1:])
BM77 最长的括号子串
class Solution: def longestValidParentheses(self , s: str) -> int: # write code here st=[] start=-1 res=0 for i in range(len(s)): if s[i]=='(': st.append(i) else: if not st: start=i else: st.pop() if st: res=max(res,i-st[-1]) else: res=max(res,i-start) return res
BM78 打家劫舍(一)
class Solution: def rob(self , nums: List[int]) -> int: # write code here n=len(nums) if n==1: return nums[0] dp=[0]*n dp[0]=nums[0] dp[1]=max(nums[0],nums[1]) for i in range(2,n): dp[i]=max(dp[i-2]+nums[i],dp[i-1]) return dp[n-1]
BM79 打家劫舍(二)
class Solution: def caculate(self,nums): n=len(nums) dp=[0]*n if n==1: return nums[0] dp[0]=nums[0] dp[1]=max(nums[0],nums[1]) for i in range(2,n): dp[i]=max(dp[i-2]+nums[i],dp[i-1]) return dp[n-1] def rob(self , nums: List[int]) -> int: # write code here l1=self.caculate(nums[:-1]) l2=self.caculate(nums[1:]) return max(l1,l2)
BM80 买卖股票的最好时机(一)
class Solution: def maxProfit(self , prices: List[int]) -> int: # write code here n=len(prices) dp=[[0]*2 for i in range(n)] dp[0][0]=0 dp[0][1]=-prices[0] for i in range(1,n): dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]) dp[i][1]=max(dp[i-1][1],-prices[i]) return dp[n-1][0]
BM81 买卖股票的最好时机(二)
class Solution: def maxProfit(self , prices: List[int]) -> int: # write code here n=len(prices) dp=[[0]*2 for i in range(n)] dp[0][0]=0 dp[0][1]=-prices[0] for i in range(1,n): dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]) dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]) return dp[n-1][0]
BM82 买卖股票的最好时机(三)
import sys class Solution: def maxProfit(self , prices: List[int]) -> int: # write code here n=len(prices) dp=[[-sys.maxsize-1]*5 for i in range(n)] dp[0][0]=0 dp[0][1]=-prices[0] for i in range(1,n): dp[i][0]=dp[i-1][0] dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]) dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i]) dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i]) dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i]) return max(dp[n-1][2],max(0,dp[n-1][4]))
BM83 字符串变形
class Solution: def trans(self , s: str, n: int) -> str: lst = s.split(' ') #就算遇到多空格，用一个空格分割是没问题的，下面再用一个空格拼接;但如果用s.split(''),空格最后都变成单空格了 lst.reverse() #在原来的地址上修改，不能写lst = lst.reverse().join(lst) return s.swapcase() #直接大小写交换
BM84 最长公共前缀
class Solution: def longestCommonPrefix(self , strs: List[str]) -> str: if not strs: return '' for i in range(len(strs[0])): for s in strs[1:]: if i >= len(s) or s[i] != strs[0][i]: return strs[0][:i] return strs[0]
BM85 验证IP地址
class Solution: def solve(self , IP ): # write code here if '.' in IP: for ip in IP.split('.'): if ip.isdigit() is False or ip == '' or ip[0] == '0' or (not 0 <= int(ip) <= 255): return 'Neither' return 'IPv4' if ':' in IP: for ip in IP.split(':'): if ip == '' or (len(ip) > 1 and len(ip) == ip.count('0')) or not all(c in '0123456789abcdefABCDEF' for c in ip): return 'Neither' return 'IPv6'
BM86 大数加法
class Solution: def solve(self , s: str, t: str) -> str: s = [int(c) for c in s] t = [int(c) for c in t] res = [] digi = 1 carry = 0 while s or t: if s and t: SUM = s.pop() + t.pop() + carry carry = SUM // 10 s1 = SUM % 10 res.insert(0, str(s1)) elif s: SUM = s.pop() + carry carry = SUM // 10 s1 = SUM % 10 res.insert(0, str(s1)) else: SUM = t.pop() + carry carry = SUM // 10 s1 = SUM % 10 res.insert(0, str(s1)) if carry != 0: res.insert(0, str(carry)) return ''.join(res)
BM87 合并两个有序的数组
class Solution: def merge(self , A, m, B, n): # write code here i=m-1 j=n-1 k=m+n-1 while(i>=0 and j>=0): if(A[i]>B[j]): A[k]=A[i] k-=1 i-=1 else: A[k]=B[j] k-=1 j-=1 if(i<0): while(j>=0): A[k]=B[j] k-=1 j-=1
BM88 判断是否为回文字符串
class Solution: def judge(self , str: str) -> bool: # write code here l,r=0,len(str)-1 while(l<r): if(str[l]==str[r]): l+=1 r-=1 continue else: return False return True
BM89 合并区间
class Solution: def merge(self , intervals: List[Interval]) -> List[Interval]: # write code here res=[] n=len(intervals) if(n==0): return res intervals.sort(key=(lambda x:x.start)) res.append(intervals[0]) for i in range(1,n): if(res[-1].end>=intervals[i].start): res[-1].end=max(res[-1].end,intervals[i].end) else: res.append(intervals[i]) return res
BM90 最小覆盖子串
class Solution: def check(self,hash): for k,v in hash.items(): if v<0: return False return True def minWindow(self , S: str, T: str) -> str: # write code here res=len(S)+1 hash=dict() for c in T: if c in hash: hash[c]-=1 else: hash[c]=-1 l,r=0,0 cnt=len(S)+1 left,right=-1,-1 while(r<len(S)): c=S[r] if c in hash: hash[c]+=1 while(self.check(hash)): if(cnt>r-l+1): cnt=r-l+1 left=l right=r t=S[l] if t in hash: hash[S[l]]-=1 l+=1 r+=1 if left==-1: return "" return S[left:right+1]
BM91 反转字符串
class Solution: def solve(self , str: str) -> str: # write code here return str[::-1]
BM92 最长无重复子数组
class Solution: def maxLength(self , arr: List[int]) -> int: # write code here l,r=0,0 hash=dict() res=0 while(r<len(arr)): if arr[r] in hash: hash[arr[r]]+=1 else: hash[arr[r]]=1 while(hash[arr[r]]>1): hash[arr[l]]-=1 l+=1 res=max(res,r-l+1) r+=1 return res
BM93 盛水最多的容器
class Solution: def maxArea(self , height: List[int]) -> int: # write code here n=len(height) if(n<2): return 0 l,r=0,n-1 res=0 while(l<r): temp=min(height[l],height[r])*(r-l) res=max(res,temp) if(height[l]<height[r]): l+=1 else: r-=1 return res
BM94 接雨水问题
class Solution: def maxWater(self , arr: List[int]) -> int: # write code here n=len(arr) if(n<=2): return 0 l,r=0,n-1 maxl,maxr=-1,-1 res=0 while(l<r): maxl=max(maxl,arr[l]) maxr=max(maxr,arr[r]) if(maxl<maxr): res+=maxl-arr[l] l+=1 else: res+=maxr-arr[r] r-=1 return res
BM95 分糖果问题
class Solution: def candy(self , arr: List[int]) -> int: # write code here n=len(arr) sweet=[1]*len(arr) for i in range(1,n): if(arr[i]>arr[i-1]): sweet[i]=sweet[i-1]+1 for i in range(n-2,-1,-1): if(arr[i]>arr[i+1] and sweet[i]<=sweet[i+1]): sweet[i]=sweet[i+1]+1 return sum(sweet)
BM96 主持人调度（二）
class Solution: def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int: # write code here start,end=list(),list() for i in range(len(startEnd)): start.append(startEnd[i][0]) end.append(startEnd[i][1]) start.sort() end.sort() i,j,res=0,0,0 for i in range(len(start)): if(start[i]>=end[j]): j+=1 else: res+=1 return res
BM97 旋转数组
class Solution: def solve(self , n: int, m: int, a: List[int]) -> List[int]: # write code here return a[-(m%n):]+a[:(-m%n)]
BM98 螺旋矩阵
class Solution: def spiralOrder(self , matrix: List[List[int]]) -> List[int]: # write code here res=list() while(matrix): res+=matrix.pop(0) matrix = list(zip(*matrix))[::-1] return res
BM99 顺时针旋转矩阵
class Solution: def rotateMatrix(self , mat: List[List[int]], n: int) -> List[List[int]]: # write code here for i in range(n): for j in range(i): mat[i][j],mat[j][i]=mat[j][i],mat[i][j] for i in range(n): mat[i].reverse() return mat
BM100 设计LRU缓存结构
class ListNode: def __init__(self, val): self.val = val self.next = None self.pre = None class Solution: def __init__(self, capacity: int): # write code here self.cap = capacity self.hash = dict() self.head = None self.tail = None def get(self, key: int) -> int: # write code here if key in self.hash: if self.hash[key].pre!=None: self.freshListNode(self.hash[key]) return self.hash[key].val[0] else: return -1 def set(self, key: int, value: int) -> None: # write code here value = [value, key] if key in self.hash: self.hash[key].val = value if self.hash[key].pre!=None: self.freshListNode(self.hash[key]) return if self.cap > 0: ele = ListNode(value) self.hash[key] = ele self.addOneNode(ele) self.cap-=1 else: del self.hash[self.tail.val[1]] self.hash[key] = self.tail self.tail.val = value if self.tail.pre != None: self.freshListNode(self.tail) def freshListNode(self, ele): ele.pre.next = ele.next if self.tail == ele: self.tail = ele.pre else: ele.next.pre = ele.pre ele.pre = None self.head.pre = ele ele.next = self.head self.head = ele def addOneNode(self, ele): if self.head == None: self.head = ele self.tail = ele else: ele.pre = None ele.next = self.head self.head.pre = ele self.head = ele # Your Solution object will be instantiated and called as such: # solution = Solution(capacity) # output = solution.get(key) # solution.set(key,value)
