BM1 反转链表
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
class Solution:
def ReverseList(self, head: ListNode) -> ListNode:
if not head: # 如果非空
return head
a, a.next, b = head, None, head.next # 初始化
while b:
b, a, a.next = b.next, b, a # 遍历
return aBM2 链表内指定区间反转
输入： {1,2,3,4,5},2,4
返回值： {1,4,3,2,5}
class Solution:
def reverseBetween(self, head, left, right):
#设置哨兵节点，对于链表相关的问题，我们通过设置哨兵节点
#可以省去边界条件的判断
dummynode = ListNode(-1)
#哨兵节点指向链表头
dummynode.next = head
pre = dummynode
#遍历，使得pre指向链表反转部分
#的第一个结点left
for _ in range(left - 1):
pre = pre.next
#cur指向链表反转部分的第一个节点
cur = pre.next
for _ in range(right - left):
next = cur.next
cur.next = next.next
next.next = pre.next
pre.next = next
return dummynode.nextBM3 链表中的节点每k个一组翻转
将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
输入：
{1,2,3,4,5},2
返回值：
{2,1,4,3,5}
class Solution:
def reverseKGroup(self , head: ListNode, k: int) -> ListNode:
Test=ListNode(-1) #定义哨兵节点，老套路了
Test.next=head
lend=Test.next
i=0
while lend:
i=i+1 #求链表总长度
lend=lend.next
print(i)
pre = Test
cur = pre.next
while head and i>=k: #分组进行判断，一组组进行反转
for j in range(k-1): #当前这组满足反转的
next = cur.next
cur.next = next.next
next.next = pre.next
pre.next = next
i = i-k #分组的思想，减去已经反转的个数，供下一次循环得到条件
pre = cur
cur = pre.next
return Test.nextBM4 合并两个排序的链表
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： 0 ≤n≤1000，-1000 ≤节点值≤1000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
输入：
{1,3,5},{2,4,6}
返回值：
{1,2,3,4,5,6}
class Solution:
def Merge(self, pHead1, pHead2):
# write code here
if not pHead1 or not pHead2:
return pHead1 or pHead2
if pHead1.val < pHead2.val:
pHead1.next = self.Merge(pHead1.next, pHead2)
return pHead1
else:
pHead2.next = self.Merge(pHead1, pHead2.next)
return pHead2BM5 合并k个已排序的链表
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
class Solution:
def mergeKLists(self , lists: List[ListNode]) -> ListNode:
import heapq
root=None
newlist=None
l=[(k.val,idx) for idx, k in enumerate(lists) if not k is None]
heapq.heapify(l)
while l:
vt=heapq.heappop(l)
if not newlist:
newlist=root=ListNode(vt[0])
else:
newlist.next=ListNode(vt[0])
newlist=newlist.next
if lists[vt[1]].next:
n=lists[vt[1]].next
lists[vt[1]]=lists[vt[1]].next
heapq.heappush(l,(n.val,vt[1]))
return rootBM6 判断链表中是否有环
class Solution:
def hasCycle(self , head ):
# write code here
if not head:
return False
# 双指针 快慢指针
slow = head
fast = head
while slow and fast:
slow = slow.next
if fast.next:
fast = fast.next.next
else:
return False
# 当双指针相遇 即表示指针有环
if slow == fast:
return True
return FalseBM7 链表中环的入口结点
class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
if not pHead:return
p_list=[]
while pHead: # 遍历节点，第一次重复出现的节点即为入口节点
if pHead not in p_list:
p_list.append(pHead)
pHead=pHead.next
else:
return pHead
return BM8 链表中倒数最后k个结点
class Solution:
def FindKthToTail(self , pHead , k ):
# write code here
if pHead == None:
return
#首先初始化两个指针，都指向头节点
p1,p2 = pHead,pHead
# p1 先走K步，如果p1 为None，则表示k小于n，返回None
for i in range(k):
if p1==None:
return None
p1 = p1.next
# p1 走完k步后，p1,p2同时走，当p1走到最后，p2为倒数第K个节点
while p1:
p1 = p1.next
p2 = p2.next
return p2BM9 删除链表的倒数第n个节点
class Solution:
def removeNthFromEnd(self , head: ListNode, n: int) -> ListNode:
# write code here
if not head:
return head
dummy = ListNode(-1)
dummy.next = head
pre, cur = dummy, dummy
for k in range(n):
cur = cur.next
while cur.next:
cur = cur.next
pre = pre.next
pre.next = pre.next.next
return dummy.nextBM10 两个链表的第一个公共结点
class Solution:
def FindFirstCommonNode(self , pHead1 , pHead2 ):
# write code here
node_list=[]
while pHead1 and pHead2:
if pHead1 in node_list:
return pHead1
else:
node_list.append(pHead1)
pHead1 = pHead1.next
if pHead2 in node_list:
return pHead2
else:
node_list.append(pHead2)
pHead2 = pHead2.next
res = pHead1 or pHead2
while res:
if res in node_list:
return res
else:
node_list.append(res)
res = res.next
return NoneBM11 链表相加(二)
class Solution:
def addInList(self , head1 , head2 ):
if not head1: return head2
if not head2: return head1
def reverse_link(root):
r=None
while root:
l=r
r=root
root=root.next
r.next=l
return r
ptr1=reverse_link(head1)
ptr2=reverse_link(head2)
i,ptr=0,ListNode(7) #初始进位,创建链表
sol=ptr
while ptr1 and ptr2:
tmp=ptr1.val+ptr2.val
sol.next=ListNode((tmp+i)%10) #当前值
sol=sol.next
i=(tmp+i)//10 #更新进位值
ptr1=ptr1.next
ptr2=ptr2.next
def remain_long(root,sol1,i): #判断剩余一个长位的情况
ptr=sol1
while root:
tmp=(root.val+i)
ptr.next=ListNode(tmp%10)
ptr=ptr.next
i=tmp//10
root=root.next
return sol1,i
if ptr1:
sol1,i=remain_long(ptr1,ListNode('TMP'), i)
sol.next=sol1.next
elif ptr2:
sol1,i=remain_long(ptr2,ListNode('TMP'), i)
sol.next=sol1.next
ptr=ptr.next
head=reverse_link(ptr)
if i>=1:
new_head=ListNode(i)
new_head.next=head
head=new_head
return headBM12 单链表的排序
描述:
给定一个节点数为n的无序单链表，对其按升序排序。
class Solution:
def sortInList(self , head: ListNode) -> ListNode:
# write code here
node_values=[]
while head:
node_values.append(head.val)
head = head.next
node_values.sort()
res = p = ListNode(0)
for value in node_values:
p.next = ListNode(value)
p = p.next
return res.nextBM13 判断一个链表是否为回文结构
class Solution:
def isPail(self , head: ListNode) -> bool:
# write code here
node_values = []
while head:
node_values.append(head.val)
head = head.next
n = len(node_values)
half = n//2
for i in range(half):
if node_values[i] != node_values[n-1-i]:
return False
return TrueBM14 链表的奇偶重排
描述:
给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
注意是节点的编号而非节点的数值。
class Solution:
def oddEvenList(self, head):
#如果链表为空，直接返回
if not head:
return head
#evenHead指向偶数链表的头节点
evenHead = head.next
#指向奇数链表和偶数链表的末尾节点
odd = head
even = evenHead
while even and even.next:
#奇数链表的末尾节点指向偶数节点的下一个节点
odd.next = even.next
#奇数链表末尾节点后移
odd = odd.next
#偶数链表的末尾节点指向奇数节点的下一个节点
even.next = odd.next
#偶数链表末尾节点后移
even = even.next
#偶数链表连接到奇数链表的末尾
odd.next = evenHead
return headBM15 删除有序链表中重复的元素-I
描述
删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
class Solution:
def deleteDuplicates(self , head: ListNode) -> ListNode:
# write code here
if not head:
return None
res = p = ListNode(head.val-1)
while head:
if head.val == p.val:
head = head.next
else:
p.next = ListNode(head.val)
p = p.next
head = head.next
return res.next
BM16 删除有序链表中重复的元素-II
给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
class Solution:
def deleteDuplicates(self, head):
#如果链表为空，直接返回
if not head:
return head
#创建一个哨兵节点
dummy = ListNode(0)
dummy.next=head
#开始时，将cur指向哨兵节点
cur = dummy
while cur.next and cur.next.next:
#如果cur.next.val和cur.next.next.val相同，删除重复元素
if cur.next.val == cur.next.next.val:
data = cur.next.val
while cur.next and cur.next.val == data:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.next
BM17 二分查找-I
请实现无重复数字的升序数组的二分查找
给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1
class Solution:
def search(self , nums: List[int], target: int) -> int:
# write code here
if not nums:
return -1
low = 0
high = len(nums)-1
while low <= high:
mid = (low+high)//2
if nums[mid] == target:
return mid
elif nums[mid] > target:
high = mid - 1
else:
low = mid + 1
return -1
BM18 二维数组中的查找
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
for alist in array:
if target in alist:return True
return FalseBM19 寻找峰值
给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
2.假设 nums[-1] = nums[n] = -\infty−∞
3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
4.你可以使用O(logN)的时间复杂度实现此问题吗？
class Solution:
def findPeakElement(self , nums: List[int]) -> int:
# write code here
for i in range(1,len(nums)-1):
if nums[i]>nums[i-1] and nums[i]>nums[i+1]:
return i
if max(nums)==nums[-1]:
return len(nums) -1
elif max(nums) == nums[0]:
return 0BM20 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
class Solution:
def InversePairs(self , data: List[int]) -> int:
# write code here
def mergesort(data):
n = len(data)
if n<=1:
return data,0
l,r = 0,0
mid = n//2
left,leftinverse = mergesort(data[:mid])
right,rightinverse = mergesort(data[mid:])
res = []#record ordered list
countinverse = leftinverse+rightinverse
while l < len(left) and r < len(right):
if left[l]<=right[r]:
res.append(left[l])
l += 1
else:
countinverse += len(left)-l
res.append(right[r])
r+=1
res += left[l:]
res += right[r:]
return res,countinverse
orderlist,count = mergesort(data)
return count%1000000007BM21 旋转数组的最小数字
有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值
class Solution:
def minNumberInRotateArray(self, rotateArray):
n=len(rotateArray)
if n==0:
return 0
if n==1:
return rotateArray[0]
minval = rotateArray[0]
for i in range(n):
if rotateArray[i] < minval:
return rotateArray[i]
else:
return minvalBM22 比较版本号
class Solution:
def compare(self , version1: str, version2: str) -> int:
# write code here
v1_list = version1.split(".")
v2_list = version2.split(".")
diff = len(v1_list) - len(v2_list)
if diff>0:
v2_list.extend(['0' for x in range(diff)])
if diff<0:
v1_list.extend(['0' for x in range(-diff)])
for index,item in enumerate(v1_list):
v1_item = item
v2_item = v2_list[index]
if len(str(v1_item))>1 and str(v1_item).startswith("0"):
v1_item.lstrip("0")
v1_item = int(v1_item)
else:
v1_item = int(v1_item)
if len(str(v2_item))>1 and str(v2_item).startswith("0"):
v2_item.lstrip("0")
v2_item = int(v2_item)
else:
v2_item = int(v2_item)
if v1_item > v2_item:
return 1
if v1_item < v2_item:
return -1
else:
return 0BM23 二叉树的前序遍历
class Solution:
def preorderTraversal(self , root: TreeNode) -> List[int]:
# write code here
if not root:
return []
return [root.val]+self.preorderTraversal(root.left)+self.preorderTraversal(root.right)BM24 二叉树的中序遍历
import sys
sys.setrecursionlimit(100000)
class Solution:
def inorderTraversal(self , root: TreeNode) -> List[int]:
# write code here
if not root:
return []
return self.inorderTraversal(root.left)+[root.val]+self.inorderTraversal(root.right)BM25 二叉树的后序遍历
import sys
sys.setrecursionlimit(1000000)
class Solution:
def postorderTraversal(self , root: TreeNode) -> List[int]:
# write code here
if not root:
return []
return self.postorderTraversal(root.left)+self.postorderTraversal(root.right)+[root.val]BM26 求二叉树的层序遍历
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res = []
node_list = [root]
res.append([root.val])
while node_list:
level_node = []
for node in node_list:
if node.left:level_node.append(node.left)
if node.right:level_node.append(node.right)
node_list = level_node
if level_node:
res.append([x.val for x in level_node])
return resBM27 按之字形顺序打印二叉树
class Solution:
def Print(self, pRoot):
# write code here
if not pRoot:return []
tmp_list = [pRoot]
res=[[pRoot.val]]
left_to_right=False
while tmp_list:
tmp=[]
for node in tmp_list:
if node.left:
tmp.append(node.left)
if node.right:
tmp.append(node.right)
tmp_list=tmp
ret = [x.val for x in tmp]
if ret:
if left_to_right:
res.append(ret)
else:
res.append(ret[::-1])
left_to_right=not left_to_right
return resBM28 二叉树的最大深度
class Solution:
def maxDepth(self , root ):
# write code here
if root == None:
return 0
else:
return max(self.maxDepth(root.left),self.maxDepth(root.right)) + 1BM29 二叉树中和为某一值的路径(一)
给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
- 该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
- 叶子节点是指没有子节点的节点
- 路径只能从父节点到子节点，不能从子节点到父节点
- 总节点数目为n
class Solution:
def hasPathSum(self , root: TreeNode, sum: int) -> bool:
# 遇到节点为None，退出
if root==None:
return False
# 遇到叶子节点，并且累计和符合条件，退出
if root.left==None and root.right==None and 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
"""
思路：
1.中序遍历（关键），将节点放到列表中维护
2.遍历列表，添加指针指向
3.返回首节点
"""
res = self.inorderTraversal(pRootOfTree)
res_len=len(res)
if res_len <= 1:return pRootOfTree
# 首尾节点特殊处理
res[0].left=None
res[0].right=res[1]
res[-1].left=res[-2]
res[-1].right=None
# 遍历列表，将节点指针关系上来，注意去掉首节点，尾节点
for i in range(1,res_len-1):
res[i].left=res[i-1]
res[i].right=res[i+1]
return res[0]
def inorderTraversal(self,root):
"中序遍历二叉树"
if not root:return []
return self.inorderTraversal(root.left) + [root] + self.inorderTraversal(root.right)
BM31 对称的二叉树
给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
class Solution:
def isSymmetrical(self, pRoot):
# write code here
if not pRoot:return True
cRoot = pRoot # 设定两个指针，一个遍历左子树，一个遍历右子树
# 左右子树均存在
if pRoot.left and pRoot.right:
if pRoot.left.val != pRoot.right.val: return False
return self.symmetrical(cRoot.left, pRoot.right)
# 左右子树均不存在，True
if not pRoot.left and not pRoot.right:
return True
# 左右子树，一个存在，一个不存在，False
return False
def symmetrical(self, left_Root, right_Root):
"""递归，比较两个指针的孩子们对称"""
if not left_Root and not right_Root: return True
# 左指针左孩子值==右指针右孩子值，左指针右孩子值==右指针左孩子值，则对称
if left_Root.left and right_Root.right:
if left_Root.left.val != right_Root.right.val: return False
if left_Root.left and not right_Root.right: return False
if not left_Root.left and right_Root.right: return False
if left_Root.right and right_Root.left:
if left_Root.right.val != right_Root.left.val: return False
if left_Root.right and not right_Root.left: return False
if not left_Root.right and right_Root.left: return False
# 递归
return self.symmetrical(left_Root.left, right_Root.right) and self.symmetrical(left_Root.right, right_Root.left)BM32 合并二叉树
已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替
class Solution:
def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
# write code here
if t1 == None:
return t2
elif t2 == None:
return t1
else:
t1.val += t2.val
t1.left = self.mergeTrees(t1.left,t2.left)
t1.right = self.mergeTrees(t1.right, t2.right)
return t1BM33 二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
class Solution:
def Mirror(self , pRoot ):
# write code here
#当不存在二叉树的时候
if not pRoot:
return None
#先分别找到源二叉树的左子树和右子树
left = self.Mirror(pRoot.left)
right = self.Mirror(pRoot.right)
#然后开始翻转二叉树后，再让左子树 == 右子树,右子树 == 左子树即得到镜像二叉树
pRoot.left = right
pRoot.right = left
return pRootBM34 判断是不是二叉搜索树
给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。
二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点
class Solution:
def isValidBST(self , root: TreeNode) -> bool:
# write code here
return self.valid_bst(root, TreeNode(float("-inf")), TreeNode(float("inf")))
def valid_bst(self, root: TreeNode, left: TreeNode, right: TreeNode) -> bool:
if not root:
return True
if root.val < left.val or root.val > right.val:
return False
return self.valid_bst(root.left, left, root) and self.valid_bst(root.right, root, right)
BM35 判断是不是完全二叉树
给定一个二叉树，确定他是否是一个完全二叉树。
完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）
class Solution:
def isCompleteTree(self , root: TreeNode) -> bool:
# write code here
import queue
q = queue.Queue()
reachNull = False
q.put(root)
while not q.empty():
cur = q.get()
if not cur:
reachNull = True # 发现空节点
continue
else:
if reachNull: # 发现空节点之后存在非空节点
return False
q.put(cur.left) # 继续遍历左右节点
q.put(cur.right)
return TrueBM36 判断是不是平衡二叉树
输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
class Solution:
def IsBalanced_Solution(self, pRoot):
# write code here
""" 思路:每个节点，它的左子树深度与右子树深度，相减绝对值大于1，不是平衡树
关键是，递归，获取树的深度
"""
if not pRoot:return True
flag=True
# 遍历所有节点
root_list=[pRoot]
while root_list:
tmp_list=[]
for root in root_list:
if abs(self.dept_tree(root.left) - self.dept_tree(root.right))>1:return False
if root.left:tmp_list.append(root.left)
if root.right:tmp_list.append(root.right)
root_list=tmp_list
return True
def dept_tree(self,pRoot):
""" 获取树的深度
思路：如果节点不为空，深度+1。如果节点为空，该节点退出递归，深度+0.
"""
if not pRoot:return 0
return max(self.dept_tree(pRoot.left),self.dept_tree(pRoot.right))+1BM37 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
- 对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.
- 二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
class Solution: def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int: if (p-root.val) *(q-root.val)<=0: return root.val elif p<root.val and q<root.val: return self.lowestCommonAncestor(root.left, p, q) elif p>root.val and q>root.val: return self.lowestCommonAncestor(root.right, p, q)
BM38 在二叉树中找到两个节点的最近公共祖先
给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
class Solution:
def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
# write code here
def dfs(root, o1, o2):
if not root:
return None
# 如果不是同一层的，那么在根上第一个出现的就是公共祖先
if root.val == o1 or root.val == o2:
return root
left = dfs(root.left, o1, o2)
right = dfs(root.right, o1, o2)
# 如果在同一层出现的，那么必然left和right都有，那么久返回root（该层的根）就行了
if not left:
return right
if not right:
return left
return root
return dfs(root, o1, o2).valBM39 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）
二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
class Solution:
def __init__(self):
self.split_s=[]
def Serialize(self, root):
# write code here
if not root:
return "#,"
return str(root.val)+","+self.Serialize(root.left)+self.Serialize(root.right)
def Deserialize(self, s):
if s==None:
return None
if s=="#":
return None
self.split_s=s.split(',')
return self.construct()
def construct(self):
if self.split_s[0]=="#":
self.split_s=self.split_s[1:]
return None
node=TreeNode(int(self.split_s[0]))
node.left=None
node.right=None
self.split_s=self.split_s[1:]
node.left=self.construct()
node.right=self.construct()
return node
# write code hereBM40 重建二叉树
给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
lon = len(pre)
if lon == 0:
return None
elif lon == 1:
return TreeNode(pre[0])
else:
# 每次前序遍历列表的第一个值为根节点
root = TreeNode(pre[0])
# 在中序遍历中，找到根节点的值。左侧的为左子树的元素，右侧的为右子树的元素
# 通过根节点在中序遍历列表中的位置，知道下一次递归的前序列表
# 左树
# pre[1:tin.index(pre[0])+1] 前序遍历
# tin = tin[:tin.index(pre[0])] 中序遍历
root.left=self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tin[:tin.index(pre[0])])
# 右树
# pre[tin.index(pre[0])+1:] 前序遍历
# tin[tin.index(pre[0])+1:] 中序遍历
root.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],tin[tin.index(pre[0])+1:])
return root BM41 输出二叉树的右视图
请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图
class Solution:
def solve(self , xianxu , zhongxu ):
# write code here
result = []
def dfs(p, i, level):
if not p:
return
if level >= len(result):
result.append(p[0])
else:
result[level] = p[0]
tmp = i.index(p[0])
dfs(p[1:tmp+1], i[0:tmp] , level+1)
dfs(p[tmp+1:], i[tmp+1:], level+1)
dfs(xianxu, zhongxu, 0)
return resultBM42 用两个栈实现队列
用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。
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 self.stack2:
return self.stack2.pop()
else:
for i in range(len(self.stack1)):
self.stack2.append(self.stack1.pop())
return self.stack2.pop()BM43 包含min函数的栈
class Solution:
def __init__(self):
self.queue = []
def push(self, node):
# write code here
return self.queue.append(node)
def pop(self):
# write code here
if self.queue:return self.queue.pop()
def top(self):
# write code here
if self.queue:return self.queue[-1]
def min(self):
# write code here
if self.queue:
return min(self.queue)
BM44 有效括号序列
给出一个仅包含字符’(‘,’)’,’{‘,’}’,’[‘和’]’,的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，”()”和”()[]{}”都是合法的括号序列，但”(]”和”([)]”不合法。
class Solution:
def isValid(self , s ):
# write code here
d = {'}': '{', ']': '[', ')': '('}
stack = []
for char in s:
if char in '{[(':
stack.append(char)
if char in '}])':
if not stack:
return False
else:
if d[char] == stack[-1]:
stack.pop()
else:
return False
return not stackBM45 滑动窗口的最大值
class Solution:
def maxInWindows(self, num, size):
# write code here
if size > len(num) or size<1:return []
if size==1:return num
ret=[]
for i in range(len(num)-size+1):
ret.append(max(num[i:i+size]))
return ret
BM46 最小的K个数
给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
def quick_sort(arr, l, r):
if l>=r: return
i, j = l, r
while i < j:
while i < j and tinput[j] >= tinput[l]: j-=1
while i < j and tinput[i] <= tinput[l]: i+=1
tinput[i], tinput[j] = tinput[j], tinput[i]
tinput[i], tinput[l] = tinput[l], tinput[i]
quick_sort(tinput, l, i-1)
quick_sort(tinput, i+1, r)
quick_sort(tinput, 0, len(tinput)-1)
return tinput[:k]BM47 寻找第K大
有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
class Solution:
def findKth(self, a, n, K):
# write code here
#先来个快速排序
resArr = self.quickSort(a)
#最后直接返回结果
return resArr[n-K]
def quickSort(self, arr):
if len(arr)>=2:
mid=arr[len(arr)//2]
left = []
right = []
arr.remove(mid)
for num in arr:
if num>mid:
right.append(num)
else:
left.append(num)
return self.quickSort(left)+[mid]+self.quickSort(right)
else:
return arrBM48 数据流中的中位数
class Solution:
res=[] #用res来存数组
def Insert(self, num):
# write code here
self.res.append(num)
def GetMedian(self):
# write code here
s=len(self.res)
self.res.sort()
if s & 1: #判断奇数
return self.res[s//2]
else:
return (self.res[(s//2)-1]+self.res[s//2])/2.0 #左+右除以2.0BM49 表达式求值
请写一个整数计算器，支持加减乘三种运算和括号。
class Solution:
def solve(self , s ):
# write code here
return eval(s)BM50 两数之和
给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）
class Solution:
def twoSum(self , numbers: List[int], target: int) -> List[int]:
# write code here
value2index = {} # 保存见过的数值和index
for i,num in enumerate(numbers):
if (target-num) in value2index:
return [value2index[target-num]+1, i+1]
value2index[num] = iBM51 数组中出现次数超过一半的数字
给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
import itertools
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
if not numbers:return 0
half_len = len(numbers)/2
numbers.sort()
for key,data in itertools.groupby(numbers):
if len([x for x in data])>half_len:return key
else:
return 0BM52 数组中只出现一次的两个数字
一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
class Solution:
def FindNumsAppearOnce(self , array ):
array = sorted(array)
re = []
for i in array:
if array.count(i) == 1:
re.append(i)
return reBM53 缺失的第一个正整数
给定一个无重复元素的整数数组nums，请你找出其中没有出现的最小的正整数
class Solution:
def minNumberDisappeared(self , nums: List[int]) -> int:
# write code here
nums.sort()
if 1 not in nums:
return 1
i = nums.index(1) # 查找1在哪个地方，因为是正整数，后面直接从1开始
s = 1
for v in nums[i:]:
if v == s: # 遍历里面的内容，依次判断缺失，要是依次加一不等里面的值
s = s + 1 # 就返回值
else:
break
return sBM54 三数之和
给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。
class Solution:
def threeSum(self , num ):
# write code here
length = len(num)
if length <3:
return []
res = [] #返回结果
num.sort() #对数组进行排序
# 三元组的所有情况有三种：两正一负，两负一正，一负一正一零
positive = [i for i in num if i >0]
negative = [i for i in num if i <0]
zeros = [i for i in num if i ==0]
#如果只有正数或负数
if (len(positive) == 0 or len(negative)==0) and len(zeros)<3 :
return []
#两负一正的情况
if len(negative)>1:
for i in range(len(negative)-1):
for j in range(i+1,len(negative)):
if -(negative[i] + negative[j]) in positive:
res.append([negative[i],negative[j],-(negative[i] + negative[j])])
#一负一正的情况
if 0 in num and len(negative)>=1 and len(positive)>=1:
tem = [i for i in positive if -i in negative]
for i in tem:
res.append([-i,0,i])
#三个零的情况：
if len(zeros)>=3:
res.append([0,0,0])
# 两正一负的情况
if len(positive)>1:
for i in range(len(positive)-1):
for j in range(i+1,len(positive)):
if -(positive[i] + positive[j]) in negative:
res.append([-(positive[i] + positive[j]),positive[i],positive[j]])
#去重
new_res = []
for i in res:
if i not in new_res:
new_res.append(i)
new_res.sort(key = lambda x:x[0])
return new_resBM55 没有重复项数字的全排列
给出一组数字，返回该组数字的所有排列
例如：
[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
class Solution:
def permute(self , num: List[int]) -> List[List[int]]:
# write code here
res = []
path = []
n = len(num)
def backTracking(array, n):
if len(path) == n:
res.append(path[:])
return
for idx, digit in enumerate(array):
path.append(digit)
del array[idx]
backTracking(array, n)
array.insert(idx, digit)
path.pop()
backTracking(num, n)
return resBM56 有重复项数字的全排列
给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。
BM57 岛屿数量
给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。
例如：
输入
[
[1,1,0,0,0],
[0,1,0,1,1],
[0,0,0,1,1],
[0,0,0,0,0],
[0,0,1,1,1]
]
对应的输出为3
class Solution:
def solve(self , grid ):
record=[[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
cnt=0
def dfs(grid,record,m,n):
if m>=0 and m<len(grid) and n>=0 and n<len(grid[0]):
if grid[m][n]=="1" and record[m][n]==0:
record[m][n]=1
dfs(grid,record, m+1, n)
dfs(grid,record, m-1, n)
dfs(grid,record, m, n+1)
dfs(grid,record, m, n-1)
else:
return
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]=="1" and record[i][j]==0:
cnt+=1
dfs(grid, record, i, j)
return cntBM58 字符串的排列
输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。
class Solution:
def Permutation(self, ss):
# write code here
length = len(ss)
if length <= 1:
return ss
lists = []
for i in range(length):
first_str = ss[i]
# 这里的ss[:i]+ss[i+1:] 刚好把ss[i]扣出来
for temp_sub_list in self.Permutation(ss[:i]+ss[i+1:]):
temp = first_str + temp_sub_list
if temp not in lists:
lists.append(temp)
return listsBM59 N皇后问题
N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后，
要求：任何两个皇后不同行，不同列也不在同一条斜线上，
求给一个整数 n ，返回 n 皇后的摆法数。
class Solution:
def Nqueen(self , n: int) -> int:
# write code here
matrix = [["." for _ in range(n)] for _ in range(n)]
res = 0
def check(r, c, matrix):
for i in range(r):
if matrix[i][c] == "Q":
return False
i, j = r, c
while i > 0 and j > 0:
if matrix[i - 1][j - 1] == "Q":
return False
i -= 1
j -= 1
i, j = r, c
while i > 0 and j < n - 1:
if matrix[i - 1][j + 1] == "Q":
return False
i -= 1
j += 1
return True
def dfs(r):
nonlocal res, matrix
if r == n:
res += 1
return
for i in range(n):
if check(r, i, matrix):
matrix[r][i] = "Q"
dfs(r + 1)
matrix[r][i] = "."
dfs(0)
return resBM60 括号生成
class Solution:
def generateParenthesis(self , n ):
# write code here
res = []#保存对象
cur_str = ''#储存括号
def dfs(cur_str, left, right): #左括号或者右括号还可以使用的个数
if left == 0 and right == 0:
res.append(cur_str)
return
if right < left: #生成括号的过程中，右括号使用的个数是不能多于左括号使用的个数的 return if left > 0:
dfs(cur_str + ')', left - 1, right)
if right > 0:
dfs(cur_str + '(', left, right - 1)
dfs(cur_str, n, n)
return resBM61 矩阵最长递增路径
给定一个 n 行 m 列矩阵 matrix ，矩阵内所有数均为非负整数。 你需要在矩阵中找到一条最长路径，使这条路径上的元素是递增的。并输出这条最长路径的长度。
这个路径必须满足以下条件：
- 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外。
- 你不能走重复的单元格。即每个格子最多只能走一次。
class Solution:
def solve(self , matrix: List[List[int]]) -> int:
# write code here
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
mem = [[0 for _ in range(n)] for _ in range(m)]
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
def dfs(x, y):
nonlocal mem
if mem[x][y] != 0:
return mem[x][y]
else:
res = 1
for i, j in dirs:
xi, yi = x + i, y + j
if 0 <= xi < m and 0 <= yi < n and matrix[xi][yi] > matrix[x][y]:
res = max(res, dfs(xi, yi) + 1)
mem[x][y] = res
return mem[x][y]
res = 0
for i in range(m):
for j in range(n):
res = max(res, dfs(i, j))
return resBM62 斐波那契数列
大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
class Solution:
def Fibonacci(self, n: int) -> int:
# write code here
if n==1 or n==2:
return 1
s1 = 1
s2 = 1
for i in range(3,n+1):
s = s1+s2
s1 = s2
s2 = s
return sBM63 跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
class Solution:
def jumpFloor(self, number):
# write code here
# n=1 [1]
# n=2 [1,1] [2]
# n=3 [1,1,1][2,1][1,2]
# n=4 [1,1,1,1] [2,1,1] [1,2,1] [1,1,2] [2,2]
# n=5 [1,1,1,1,1] [2,1,1,1] [1,2,1,1] [1,1,2,1] [1,1,1,2] [2,2,1] [2,1,2] [1,2,2]
a = 1
b = 2
if number==1:return 1
if number ==2:return 2
for _ in range(2,number):
a,b = b,a+b
return b
BM64 最小花费爬楼梯
给定一个整数数组 cost \cost ，其中 cost[i]\cost[i] 是从楼梯第i \i 个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费
class Solution:
def minCostClimbingStairs(self , cost: List[int]) -> int:
# write code here
if len(cost) == 1: return cost[0]
n = len(cost)
dp = [cost[0], cost[1]]
for i in range(2, n):
dp.append(min(dp[i - 1], dp[i - 2]) + cost[i])
return min(dp[-1], dp[-2])BM65 最长公共子序列(二)
给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回”-1”。目前给出的数据，仅仅会存在一个最长的公共子序列
class Solution:
def LCS(self , s1 , s2 ):
# write code here
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
ans = ''
i, j = m, n
while i >= 1 and j >= 1:
if s1[i-1] == s2[j-1]:
ans += s1[i-1]
i -= 1
j -= 1
elif dp[i][j-1] > dp[i-1][j]:
j -= 1
else: i -= 1
if not ans: return -1
return ans[::-1]BM66 最长公共子串
给定两个字符串str1和str2,输出两个字符串的最长公共子串
题目保证str1和str2的最长公共子串存在且唯一。
class Solution:
def LCS(self , str1: str, str2: str) -> str:
res=""
left=0
for i in range(len(str1)+1):
if str1[i-left:i] in str2:
res=str1[i-left:i]
left+=1
return resBM67 不同路径的数目(一)
一个机器人在m×n大小的地图的左上角（起点）。
机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？
import math
class Solution:
def uniquePaths(self , m , n ):
x = m+n-2
#注意，python除法用的是 //
res = math.factorial(x) // (math.factorial(m-1)*math.factorial(n-1))
return resBM68 矩阵的最小路径和
给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。
class Solution:
def minPathSum(self , matrix ):
# write code here
m = len(matrix)
n = len(matrix[0])
for i in range(1, n):
matrix[0][i] += matrix[0][i-1]
for i in range(1, m):
matrix[i][0] += matrix[i-1][0]
for i in range(1, m):
for j in range(1, n):
matrix[i][j] += min(matrix[i][j-1], matrix[i-1][j])
print(matrix)
return matrix[-1][-1]BM69 把数字翻译成字符串
有一种将字母编码成数字的方式：’a’->1, ‘b->2’, … , ‘z->26’。
现在给一串数字，返回有多少种可能的译码结果
class Solution:
def solve(self , nums ):
# write code here
cur = 0 if nums[-1] == '0' else 1
prev = 1
pprev = 0
for i in range(len(nums)-2, -1, -1):
pprev = prev
prev = cur
if nums[i] == '0':
cur = 0
else:
cur = prev
if 0 < int(nums[i: i+2]) <= 26:
cur += pprev
return curBM70 兑换零钱(一)
给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
如果无解，请返回-1.
class Solution:
def minMoney(self , arr: List[int], aim: int) -> int:
# write code here
aim_list = [aim+1]*(aim+1)
aim_list[0] = 0
for i in range(1,aim+1,1):
for j in arr:
if j <= i:
aim_list[i] = min(aim_list[i],aim_list[i-j]+1)
if aim_list[aim] == (aim + 1):
return -1
else:
return aim_list[aim]BM71 最长上升子序列(一)
class Solution:
def LIS(self , arr: List[int]) -> int:
# write code here
if not arr:
return 0
dp = [1 for _ in range(len(arr))]
for i in range(len(arr)):
for j in range(i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)BM72 连续子数组的最大和
输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。
class Solution:
def FindGreatestSumOfSubArray(self, array):
# write code here
dp = [i for i in array]
for i in range(1,len(array)):
dp[i] = max(dp[i-1]+array[i],array[i])
return max(dp)
BM73 最长回文子串
对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。
class Solution:
def getLongestPalindrome(self , A: str, n: int) -> int:
# write code here
dp = [1]*n
if n ==1:
return 1
for i in range(1,n-1):
if A[i-1] == A[i+1]:
left_point ,right_point = i-1 , i+1
elif A[i] == A[i-1]:
left_point ,right_point = i-1 , i
elif A[i+1] == A[i]:
left_point ,right_point = i , i+1
else:
continue
while left_point>=0 and right_point<n and A[left_point]==A[right_point]:
left_point -= 1
right_point += 1
dp[i] = right_point - left_point - 1
return max(dp)BM74 数字字符串转化成IP地址
现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。
例如：
给出的字符串为”25525522135”,
返回[“255.255.22.135”, “255.255.221.35”]. (顺序没有关系)
class Solution:
def restoreIpAddresses(self , s ):
# write code here
if len(s) < 4 or len(s) > 12: return []
res, tmp = [], []
def backtrack(idx):
if len(tmp) == 4 and idx == len(s):
res.append('.'.join(tmp))
for i in range(1, 4):
if idx+i > len(s): continue
sub = s[idx:idx+i]
if len(sub) > 1 and sub[0] == '0': continue
if int(sub) > 255: continue
tmp.append(sub)
backtrack(idx+i)
tmp.pop()
backtrack(0)
return resBM75 编辑距离(一)
给定两个字符串 str1 和 str2 ，请你算出将 str1 转为 str2 的最少操作数。
你可以对字符串进行3种操作：
- 插入一个字符
- 删除一个字符
- 修改一个字符。
输入： "nowcoder","new" 返回值： 6 说明： "nowcoder"=>"newcoder"(将'o'替换为'e')，修改操作1次 "nowcoder"=>"new"(删除"coder")，删除操作5次
class Solution:
def editDistance(self , str1: str, str2: str) -> int:
# write code here
dp = [[0 for _ in range(len(str2) + 1)] for _ in range(len(str1) + 1)]
for i in range(1, len(str1) + 1):
dp[i][0] = dp[i - 1][0] + 1
for i in range(1, len(str2) + 1):
dp[0][i] = dp[0][i - 1] + 1
for i in range(1, len(str1) + 1):
for j in range(1, len(str2) + 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], dp[i][j - 1], dp[i - 1][j - 1]) + 1
return dp[-1][-1]BM76 正则表达式匹配
请实现一个函数用来匹配包括’.’和’‘的正则表达式。
1.模式中的字符’.’表示任意一个字符
2.模式中的字符’‘表示它前面的字符可以出现任意次（包含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配
class Solution:
def match(self , str , pattern ):
if not pattern: #1.特殊情况，不存在匹配模式，那么就没有匹配字符串
return not str
#2. 递归的终止条件f(1) = 1：在这里就是 首位即匹配。
first_match = str and pattern[0] in {str[0], '.'}
#如果模式长度 >= 2,并且 模式索引[1] == '*'情况，也要分两种：
if len(pattern) >= 2 and pattern[1] == '*':
#第一种就是模式长度>2的情况下：字符串完全匹配从模式索引2之后的位置
return (self.match(str, pattern[2:]) or
#或者模式长度 =2的情况下：字符串从索引1位置开始，完全匹配模式
first_match and self.match(str[1:], pattern))
else:
#否则，模式长度>=2,而模式索引从1开始是 点字符或 *字符在其他位置，
return first_match and self.match(str[1:], pattern[1:])BM77 最长的括号子串
给出一个长度为 n 的，仅包含字符 ‘(‘ 和 ‘)’ 的字符串，计算最长的格式正确的括号子串的长度。
例1: 对于字符串 “(()” 来说，最长的格式正确的子串是 “()” ，长度为 2 .
例2：对于字符串 “)()())” , 来说, 最长的格式正确的子串是 “()()” ，长度为 4 .
class Solution:
def longestValidParentheses(self , s: str) -> int:
dp=[0]*len(s)
maxans=0
for i in range(1,len(s)):
if s[i]==')':
if s[i-1]=='(':
if i>=2:
dp[i]=dp[i-2]+2
else:
dp[i]=2
else:
# then this is type of '...))'
if (i-dp[i-1])>0 and s[i-dp[i-1]-1]=='(':
if i-dp[i-1] >=2:
dp[i] = dp[i-1]+dp[i-dp[i-1]-2] +2
else:
dp[i] = dp[i-1]+2
maxans=max(maxans,dp[i])
return maxansBM78 打家劫舍(一)
你是一个经验丰富的小偷，准备偷沿街的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家；如果偷了第二家，那么就不能偷第一家和第三家。
给定一个整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。
class Solution:
def rob(self , nums: List[int]) -> int:
# write code here
dp = [0 for _ in range(len(nums) + 2)]
for i in range(len(nums) - 1, -1, -1):
dp[i] = max(dp[i + 2] + nums[i], dp[i + 1])
return dp[0]
BM79 打家劫舍(二)
你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。
给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。
class Solution:
def rob(self , nums: List[int]) -> int:
# write code here
if len(nums) == 1:
return nums[0]
return max(self.sub_rob(nums[:-1]), self.sub_rob(nums[1:]))
def sub_rob(self, nums: List[int]) -> int:
dp = [0 for _ in range(len(nums) + 2)]
for i in range(len(nums) - 1, -1, -1):
dp[i] = max(dp[i + 2] + nums[i], dp[i + 1])
return dp[0]
BM80 买卖股票的最好时机(一)
假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
- 你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
- 如果不能获取到任何利润，请返回0
- 假设买入卖出均无手续费
class Solution:
def maxProfit(self , prices ):
# write code here
min_=float("inf")
max_=0
for i in range(len(prices)):
min_=min(min_,prices[i])
max_=max(max_,prices[i]-min_)
return max_BM81 买卖股票的最好时机(二)
假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
- 你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票
- 如果不能获取收益，请返回0
- 假设买入卖出均无手续费
BM95 分糖果问题
一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：
- 每个孩子不管得分多少，起码分到一个糖果。
- 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)
给定一个数组 arrarr 代表得分数组，请返回最少需要多少糖果。
class Solution:
def candy(self , arr: List[int]) -> int:
# write code here
if len(arr) == 1:
return 1
data = [0 for _ in range(len(arr))]
l, r = [0 for _ in range(len(arr))], [0 for _ in range(len(arr))]
l[0], r[-1] = 1, 1
for i in range(1, len(arr)):
if arr[i] > arr[i - 1]:
l[i] = l[i - 1] + 1
else:
l[i] = 1
for i in range(len(arr) - 2, -1, -1):
if arr[i] > arr[i + 1]:
r[i] = r[i + 1] + 1
else:
r[i] = 1
for i in range(len(arr)):
data[i] = max(l[i], r[i])
return sum(data)BM96 主持人调度
有 n 个活动即将举办，每个活动都有开始时间与活动的结束时间，第 i 个活动的开始时间是 starti ,第 i 个活动的结束时间是 endi ,举办某个活动就需要为该活动准备一个活动主持人。
一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，一个主持人参与了第 i 个活动，那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动，最少需要多少名主持人。
import heapq
class PriorityQueue:
def __init__(self):
self.data = []
def push(self, d):
heapq.heappush(self.data, d)
def pop(self):
heapq.heappop(self.data)
def peek(self):
return self.data[0]
def empty(self):
return not self.data
def size(self):
return len(self.data)
class Solution:
def minmumNumberOfHost(self , n , startEnd ):
# write code here
startEnd.sort()
pq = PriorityQueue()
for i in range(n):
if not pq.empty() and pq.peek() <= startEnd[i][0]:
pq.pop()
pq.push(startEnd[i][1])
return pq.size()BM97 旋转数组
一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M（ M >=0）个位置，即将A中的数据由（A0 A1 ……AN-1 ）变换为（AN-M …… AN-1 A0 A1 ……AN-M-1 ）（最后 M 个数循环移至最前面的 M 个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？
class Solution:
def solve(self , n: int, m: int, a: List[int]) -> List[int]:
if m == 0 or m == n:
return a
else:
for i in range(m%n):
value = a.pop()
a.insert(0, value)
return aBM98 螺旋矩阵
给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。
class Solution:
def spiralOrder(self , matrix ):
res = []
while matrix:
res += matrix[0]
matrix = list(zip(*matrix[1:]))[::-1]
return resBM99 顺时针旋转矩阵
有一个NxN整数矩阵，请编写一个算法，将矩阵顺时针旋转90度。
给定一个NxN的矩阵，和矩阵的阶数N,请返回旋转后的NxN矩阵。
class Solution:
def rotateMatrix(self , mat: List[List[int]], n: int) -> List[List[int]]:
# write code here
final = []
res = list(reversed(mat))
for i in range(n):
temp = []
for k in range(n):
temp.append(res[k][i])
final.append(temp)
return final BM100 设计LRU缓存结构
class Solution:
def LRU(self , operators , k ):
A,a=dict(),[]
def set(key,value):
if len(a)<k:
A[key]=value
a.append(key)
else:
del A[a.pop(0)]
A[key]=value
a.append(key)
def get(key):
if key in A.keys():
a.remove(key)
a.append(key)
return A[key]
else: return -1
sol=[]
for i in operators:
if i[0]==1: set(i[1],i[2])
else:
sol.append(get(i[1]))
return solBM101 设计LFU缓存结构
class Cache:
def __init__(self, k):
self.cap = k
self.data = dict()
def getFirstKey(self):
k = sorted(self.data.items(), key=lambda x:[x[1][1], x[1][2]])[0][0]
return k
def isFull(self):
return len(self.data) == self.cap
def setKey(self, key, val, tp):
if not self.isFull():
if key not in self.data:
self.data[key] = [val, 1, tp]
else:
self.data[key][0] = val
self.data[key][1] += 1
self.data[key][2] = tp
elif self.isFull() and key in self.data:
self.data[key][0] = val
self.data[key][1] += 1
self.data[key][2] = tp
else:
self.data.pop(self.getFirstKey())
self.data[key] = [val, 1, tp]
def getKey(self, key, tp):
if key in self.data:
self.data[key][1] += 1
self.data[key][2] = tp
return -1 if key not in self.data else self.data[key][0]
class Solution:
def LFU(self , op: List[List[int]], k: int) -> List[int]:
# write code here
res = []
cache = Cache(k)
for i in range(len(op)):
if op[i][0] == 1:
cache.setKey(op[i][1], op[i][2], i)
elif op[i][0] == 2:
res.append(cache.getKey(op[i][1],i))
return res转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。
