01链表

BM1 反转链表 1

头插法：将cur的后一个不断放到前面

class Solution:def ReverseList(self , head: ListNode)-> ListNode:dummy = ListNode(0)dummy.next = headcur = head #cur始终指向原始的第一个节点while cur and cur.next: #下一个还有就将其放到前面tmp = cur.nextcur.next = tmp.next #当tmp是最后一个节点时,cur.next指向tmp.next即空tmp.next = dummy.nextdummy.next = tmpreturn dummy.next

BM2 链表内指定区间内反转 1

class Solution:def reverseBetween(self , head: ListNode,m: int, n: int) -> ListNode:dummy = ListNode(0)dummy.next = headpre = dummyfor _ in range(m-1):pre = pre.nextcur = pre.nextfor _ in range(n-m):#不断地改变cur的下一个，将cur的下一个放到pre的前面#cur和pre都是不变的tmp = cur.next #要改变cur的指向，先保存一下cur的下一个cur.next = tmp.nexttmp.next = pre.next #要改变pre的指向，先保存pre的下一个(用tmp来保存正好正确连接)pre.next = tmpreturn dummy.next 

BM3 链表中的节点每k个一组翻转

尾插法，区别于前面头插

class Solution:def reverseKGroup(self, head:Optional[ListNode], k: int) -> Optional[ListNode]:dummy = ListNode(0)dummy.next = headpre = tail = dummywhile True:count = kwhile count and tail: #将tail指向当前组的尾部count -= 1tail = tail.nextif not tail:breakhead = pre.next # head是当前组的第一个，反转后就是最后一个while pre.next != tail:tmp = pre.nextpre.next = tmp.nexttmp.next = tail.nexttail.next = curpre = headtail = headreturn dummy.next

BM4 合并两个排序的链表

class Solution:def Merge(self , pHead1: ListNode, pHead2:ListNode) -> ListNode:# write code heredummy = ListNode(0)cur = dummyp1 = pHead1p2 = pHead2while p1 and p2:if p1.val < p2.val:cur.next = p1p1 = p1.nextcur = cur.nextelse:cur.next = p2p2 = p2.nextcur = cur.nextcur.next = p1 if p1 else p2return dummy.next

BM5 合并k个已排序的链表

方法一：维持一个res，与各个链表两两归并

class Solution:def mergeKLists(self , lists:List[ListNode]) -> ListNode:# write code hereif not lists: return def mergeTwoLists(head1, head2):dummy = ListNode(0)cur = dummyp1 = head1p2 = head2while p1 and p2:if p1.val <= p2.val:cur.next = p1p1 = p1.nextelse:cur.next = p2p2 = p2.nextcur = cur.nextcur.next = p1 if p1 else p2return dummy.nextres = lists[0]for head in lists[1:]:res = mergeTwoLists(res, head)return res

BM6 判断链表中是否有环

方法二：快慢指针，在环上，每次移动一次就，快指针和慢指针的距离会减一，最终总会追及

class Solution:def hasCycle(self , head: ListNode) ->bool:fast = slow = headwhile fast and fast.next: #因为每次移动两步，所以要考虑fast.next才不会漏掉条件fast = fast.next.nextslow = slow.nextif fast == slow:return Truereturn False

BM7 链表中环的入口节点

方法一：双指针

设入口节点前有a个节点，环中有b个节点

class Solution:def EntryNodeOfLoop(self, pHead):fast = slow = pHeadwhile fast and fast.next:fast = fast.next.nextslow = slow.next#第一次相交时fast走步数是slow的两倍 f = 2s，f = s + nb 有s = nb ，再走a步就到入口节点了if fast == slow:breakif not fast or not fast.next:returnfast = pHeadwhile fast != slow:fast = fast.nextslow = slow.nextreturn fast

BM8 链表中倒数最后K个节点

方法一：双指针

class Solution:def FindKthToTail(self , pHead: ListNode,k: int) -> ListNode:# write code herefast = pHeadwhile k > 0 and fast:fast = fast.nextk -= 1if k > 0: #如果链表长度小于kreturnwhile fast:fast = fast.nextpHead = pHead.nextreturn pHead

BM9 删除链表的倒数第n个节点

方法一：双指针

class Solution:def removeNthFromEnd(self , head: ListNode,n: int) -> ListNode:# write code heredummy = ListNode(0)dummy.next = headslow = dummyfast = headfor _ in range(n):fast = fast.nextwhile fast:fast = fast.nextslow = slow.nextslow.next = slow.next.nextreturn dummy.next

BM10 两个链表的第一个公共节点

class Solution:def FindFirstCommonNode(self , pHead1 ,pHead2 ):p1 = pHead1p2 = pHead2while p1 != p2: #找到第一个相等的节点则返回p1 = p1.next if p1 else pHead2p2 = p2.next if p2 else pHead1return p1

BM11 链表相加（二）

结果返回一个链表

class Solution:def addInList(self , head1: ListNode,head2: ListNode) -> ListNode:# write code herenums1 = []nums2 = []while head1:nums1.append(head1.val)head1 = head1.nextwhile head2:nums2.append(head2.val)head2 = head2.nextc = 0tmp = Nonewhile nums1 or nums2:if nums1 and nums2:s = nums1.pop() + nums2.pop() +c #用栈就相当于倒序了s1 = s % 10c = s // 10node = ListNode(s1)node.next = tmptmp = nodeelif nums1:s = nums1.pop() + cs1 = s % 10c = s // 10node = ListNode(s1)node.next = tmptmp = nodeelse:s = nums2.pop() + cs1 = s % 10c = s // 10node = ListNode(s1)node.next = tmptmp = nodeif c:node = ListNode(c)node.next = tmptmp = nodereturn tmp

BM12 单链表的排序

归并排序

先用快慢指针找到中点

class Solution:def sortInList(self , head: ListNode) ->ListNode:if not head or not head.next: returnhead #空节点或者节点为一，什么都不用做，返回slow, fast = head, head.nextwhile fast and fast.next:slow = slow.nextfast = fast.next.nextmid = slow.nextslow.next = Noneleft = self.sortInList(head)right = self.sortInList(mid)dummy = cur = ListNode(0)while left and right:if left.val <= right.val:cur.next = leftleft = left.nextelse:cur.next = rightright = right.nextcur = cur.nextcur.next = left if left else rightreturn dummy.next

BM13 判断一个链表是否为回文结构

class Solution:def isPail(self , head: ListNode) ->bool:# write code herecur = headstack = []while cur:stack.append(cur.val)cur = cur.nextreturn stack == stack[::-1]

BM14 链表的奇偶重排

奇数节点和偶数节点分别放在一起，重排后输出

方法二：

同样用两个节点记录奇偶，但交替进行，更简洁

class Solution:def oddEvenList(self , head: ListNode)-> ListNode:if not head: returnevenhead = head.nextodd, even = head, evenheadwhile even and even.next:odd.next = even.nextodd = odd.nexteven.next = odd.nexteven = even.nextodd.next = evenheadreturn head

BM15 删除有序链表中重复的元素-I

方法二：如果下一个与当前相等，则下一个变为下一个的下一个

class Solution:def deleteDuplicates(self , head: ListNode)-> ListNode:if not head: return cur = headwhile cur.next:if cur.val == cur.next.val: #相等则连到下一个，直到不等cur.next = cur.next.nextelse:cur = cur.nextreturn head

BM16 删除有序链表中重复的元素-II

删除所有出现的元素，第一个不保留

方法一：用到dummy技巧

并且是标记最后一个重复的元素，最后再链接

class Solution:def deleteDuplicates(self , head: ListNode)-> ListNode:if not head: returndummy = pre = ListNode(0)dummy.next = headcur = headwhile cur:while cur.next and cur.val ==cur.next.val:cur = cur.next  #结束循环后cur是最后一个重复的元素if pre.next == cur: #没有重复，cur无移动pre = curelse:pre.next = cur.next #跳过重复的元素，相当于删除,pre位置不变cur = cur.nextreturn dummy.next

02 二分查找

BM17 二分查找-I

实现无重复数字的升序数组的二分查找

class Solution:def search(self , nums: List[int], target:int) -> int:# write code hereif not nums: return -1i, j = 0, len(nums) - 1while i <= j:mid = i + ((j - i) >> 1) # 二进制位全部右移1位，相当于除以2if nums[mid] == target:return midelif nums[mid] < target:i = mid + 1else:j = mid - 1return -1

BM18 二维数组中的查找

在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，

每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

class Solution:def Find(self , target: int, array:List[List[int]]) -> bool:# 优先判断特殊if len(array) == 0: return Falsen = len(array)if len(array[0]) == 0:return Falsem = len(array[0])i = n-1j = 0# 从最左下角的元素开始往左或往上while i >=0 and j < m: # 元素较大，往上走if array[i][j] > target: i -= 1# 元素较小，往右走elif array[i][j] < target: j += 1else:return Truereturn False

BM19寻找峰值

峰值就是中间数值大于左右两侧的元素值，类似于数学中的极值。

class Solution:def findPeakElement(self , nums: List[int])-> int:left = 0right = len(nums) - 1# 二分法while left < right: mid = left+ ((right - left)>> 1) # 二进制位全部右移1位，相当于除以2# 右边是往下，不一定有波峰if nums[mid] > nums[mid+1]: right = mid# 右边是往上，一定能找到波峰else: left = mid + 1# 其中一个波峰return right 

BM20数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。

class Solution:def InversePairs(self, data):# write code hereif not data:return Nonedef inversePairsCore(array, counts):# nonlocal countsif len(array) == 1:return array, countsmid = len(array) // 2left, counts =inversePairsCore(array[:mid], counts)right, counts =inversePairsCore(array[mid:], counts)p1 = 0p2 = 0result = []while p1 < len(left) and p2 <len(right):if left[p1] > right[p2]:counts += len(left) - p1result.append(right[p2])p2 += 1else:result.append(left[p1])p1 += 1result += left[p1:] + right[p2:]return result, counts_, counts = inversePairsCore(data, 0)return counts%1000000007

BM21 旋转数组的最小数字

class Solution:def minNumberInRotateArray(self ,rotateArray: List[int]) -> int:# write code hereleft, right = 0, len(rotateArray) - 1while left <= right:  mid = left+ ((right - left)>> 1) # 二进制位全部右移1位，相当于除以2if rotateArray[mid] >rotateArray[right]: left = mid + 1elif rotateArray[mid] <rotateArray[left]: right= mid #注意不是mid -1else: right-= 1return rotateArray[left]

BM22比较版本号

某项目发布项目版本时会有版本号，比如1.02.11，2.14.4等等，现在给你2个版本号version1和version2，请你比较他们的大小。

class Solution:def compare(self , version1: str, version2: str) -> int:# write code herenums1 = [int(i) for i in version1.split('.')]nums2 = [int(i) for i in version2.split('.')]while len(nums1) < len(nums2):nums1.append(0)while len(nums2) < len(nums1):nums2.append(0)for i, j in zip(nums1, nums2):if i > j:return 1elif i < j:return -1return 0

BM23二叉树的前序遍历-

def preorder(self, list: List[int], root: TreeNode):# 遇到空节点则返回if root == None:returnlist.append(root.val) # 先遍历根节点self.preorder(list, root.left) # 再取左子树self.preorder(list, root.right) # 最后取右子树def preorderTraversal(self , root: TreeNode) -> List[int]:# 添加遍历结果的数组list = []# 递归前序遍历self.preorder(list, root)return list

BM24二叉树的中序遍历-

class Solution {
public:   vector<int>inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if(root!=nullptr) st.push(root);while(!st.empty()){TreeNode* node=st.top();//node遍历前进的步骤//将所有遍历节点和处理节点（放入结果的节点元素）全部入栈，在处理节点之后放入一个空指针（标记法）if(node!=nullptr){st.pop();//清空栈，避免重复if(node->right)st.push(node->right);//入栈顺序：右根左【中序：左根右】st.push(node);st.push(nullptr);if(node->left)st.push(node->left);  }else{st.pop();//删除空节点node=st.top();st.pop();result.push_back(node->val);}}return result;}
};

BM25二叉树的后序遍历-

/* struct TreeNode {*        intval;*        structTreeNode *left;*        structTreeNode *right;*        TreeNode(intx) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:vector<int> ans;void postordervisited(TreeNode* root) {if(root == NULL)return;postordervisited(root -> left);postordervisited(root -> right);ans.push_back(root -> val);}vector<int>postorderTraversal(TreeNode* root) {postordervisited(root);return ans;}
};

BM26二叉树的层序遍历-

class Solution {
public:vector<vector<int> >levelOrder(TreeNode* root) {vector<vector<int>> ans;queue<TreeNode*> qu; qu.push(root);while(!qu.empty()){int len = qu.size(); //队列中的结点个数（也即当前层结点个数）vector<int> curlayer; for(int i=0; i<len; i++){ //处理当前层节点TreeNode* tmp = qu.front();curlayer.push_back(tmp->val);if(tmp->left != NULL)qu.push(tmp->left);if(tmp->right != NULL)qu.push(tmp->right);qu.pop();  //每处理完一个节点就将其出队}ans.push_back(curlayer);}return ans;}
};

BM27 按之字形顺序打印二叉树

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};
*/
class Solution {
public:vector<vector<int> > Print(TreeNode* root) {vector<vector<int> >ans;// 层数int index = 1;if(root == NULL)return ans;// 存放相邻两层节点queue<TreeNode* >tree;tree.push(root);while(!tree.empty()) {// 存储一层的节点vector<int>temp;int len = tree.size();if(index % 2 != 0) {for(int i = 0;i < len;i++) {TreeNode* treenode =tree.front();tree.pop();temp.push_back(treenode-> val);// 下一层入队if(treenode -> left !=NULL)tree.push(treenode-> left);if(treenode -> right !=NULL)tree.push(treenode-> right);}}else {stack<TreeNode* >tree1;for(int i = 0;i < len;i++) {tree1.push(tree.front());TreeNode* treenode =tree.front();tree.pop();// 下一层入队if(treenode -> left!= NULL)tree.push(treenode-> left);if(treenode -> right !=NULL)tree.push(treenode-> right);}while(!tree1.empty()) {TreeNode* treenode =tree1.top();tree1.pop();temp.push_back(treenode-> val);}}index++;ans.push_back(temp);}return ans;}   
};

BM28 求二叉树的最大深度

class Solution {
public:int maxDepth(TreeNode* root) {int ans = 0;dfs(root, 0, ans);return ans;}void dfs(TreeNode* root, int depth, int& maxdepth){if(root == NULL) return;depth++;if(depth > maxdepth) maxdepth = depth;if(root->left)dfs(root->left, depth, maxdepth);if(root->right)dfs(root->right, depth, maxdepth);}
};

03 二叉树

BM29 二叉树中和为某一值的路径

class Solution:def hasPathSum(self , root: TreeNode, sum:int) -> bool:# write code heredef dfs(root, sum):if not root:return Falseif not root.left and notroot.right:if root.val == sum:return Truereturn dfs(root.left, sum -root.val) or dfs(root.right, sum - root.val)return dfs(root, sum)

BM30 二叉搜索树与双向链表

class Solution:def Convert(self , pRootOfTree ):# write code heredef dfs(cur):if not cur:returndfs(cur.left)if self.pre:self.pre.right = curcur.left = self.preself.pre = curelse:self.head = cur #记录头结点self.pre = cur #初始化predfs(cur.right)if not pRootOfTree:returnself.pre = Nonedfs(pRootOfTree)return self.head

BM31对称的二叉树

class Solution:def isSymmetrical(self , pRoot: TreeNode)-> bool:# write code heredef dfs(A, B):if not A and not B:return Trueelif not A or not B:return Falseelif A.val != B.val:return Falseelse:return dfs(A.left, B.right) anddfs(A.right, B.left)if not pRoot:return Truereturn dfs(pRoot.left, pRoot.right)

BM32 合并二叉树

class Solution:def isSymmetrical(self , pRoot: TreeNode)-> bool:# write code heredef dfs(A, B):if not A and not B:return Trueelif not A or not B:return Falseelif A.val != B.val:return Falseelse:return dfs(A.left, B.right) anddfs(A.right, B.left)if not pRoot:return Truereturn dfs(pRoot.left, pRoot.right)

BM33 二叉树的镜像

class Solution:def Mirror(self , pRoot: TreeNode) ->TreeNode:# write code hereif not pRoot:returntmp = pRoot.leftpRoot.left = self.Mirror(pRoot.right)pRoot.right = self.Mirror(tmp)return pRoot

BM34 判断是不是搜索二叉树

方法二：中序遍历，递归

中序遍历的的结果应该是递增的，即当前节点的值应该大于前一个节点，否则返回False

class Solution:def isValidBST(self, root: TreeNode) ->bool:self.pre = float('-inf')def recur(root):if not root: return Truel = recur(root.left)  #中序遍历，会一直进入到左子树的尽头，才会进行下面的访问操作if root.val <= self.pre:return Falseself.pre = root.valr = recur(root.right)return l and rreturn recur(root)

BM35 判断是不是完全二叉树

方法一： 层序遍历，空节点也加入队列，如果出现了空节点，右边还有节点就不是完全二叉树

class Solution:def isCompleteTree(self , root: TreeNode)-> bool:# write code hereif not root:return Truequeue = [root]flag = Falsewhile queue:for _ in range(len(queue)):node = queue.pop(0)if not node:flag = Trueelse: #当前节点不为空if flag: #如果出现了一个空节点，右边还有节点，说明不是完全二叉树return Falsequeue.append(node.left) #空子节点也加入队列queue.append(node.right)return True #遍历完返回True

BM36 判断是不是平衡二叉树

写法一：类似LC100 相同的树、BM31对称的树

class Solution:def IsBalanced_Solution(self , pRoot:TreeNode) -> bool:if not pRoot:return Trueleft = self.depth(pRoot.left)right = self.depth(pRoot.right)if abs(left - right) > 1:return Falsereturnself.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)def depth(self, root):if not root:return 0left = self.depth(root.left)right = self.depth(root.right)return max(left, right) + 1

LC100 相同的树

class Solution:def isSameTree(self, p: TreeNode, q:TreeNode) -> bool:if not p and not q: #到空了还没有False的就返回Truereturn Trueelif not p or not q: #在不是两个都为空的条件下，那么至少有一个不为空。如果有一个为空则就是一个为空另一个不为空，那么一定不相同return Falseelif p.val != q.val:return Falseelse:return self.isSameTree(p.left,q.left) and self.isSameTree(p.right, q.right)

BM37 二叉搜索树的最近公共祖先

如果某节点是p、q的最近公共祖先，那么p、q肯定在该节点的两边

如果p、q同在某节点左侧或右侧，则该节点还不是最近的公共祖先

#方法二：递归

class Solution:def lowestCommonAncestor(self , root:TreeNode, p: int, q: int) -> int:if (p <= root.val and q >=root.val) or (p >= root.val and q <= root.val):return root.valelif p <= root.val and q <=root.val:returnself.lowestCommonAncestor(root.left, p, q)else:returnself.lowestCommonAncestor(root.right, p, q)

BM38 在二叉树中找到两个节点的最近公共祖先

方法一：递归

class Solution:def lowestCommonAncestor(self , root:TreeNode, o1: int, o2: int) -> int:# write code hereif not root:return #或标记为 -1if root.val == o1 or root.val == o2:return root.valleft =self.lowestCommonAncestor(root.left, o1, o2) #在左子树中寻找公共祖先right =self.lowestCommonAncestor(root.right, o1, o2) #在右子树中寻找公共祖先if not left:return right #左子树中没找到，则在右子树中if not right:return left #右子树中没找到吗，则在左子树中return root.val #否则是当前节点（两边都找到）

BM39 序列化二叉树

class Solution:index = 0s = ''def SerializeFunc(self, root):# write code hereif not root:self.s += '#'returnself.s += str(root.val) + '!'self.SerializeFunc(root.left)self.SerializeFunc(root.right)def Serialize(self, root):if not root:return '#'self.SerializeFunc(root)return self.sdef Deserialize(self, s):#write code hereif s == '#':returnif self.index >= len(s) ors[self.index] == '#':self.index += 1return Noneval = 0 while s[self.index] != '!' andself.index != len(s):val = val * 10 + int(s[self.index])self.index += 1root = TreeNode(val)if self.index == len(s):return rootelse:self.index += 1root.left = self.Deserialize(s)root.right = self.Deserialize(s)return root

BM40 重建二叉树

根据前序遍历和中序遍历结果重建二叉树

class Solution:def reConstructBinaryTree(self , pre:List[int], vin: List[int]) -> TreeNode:# write code here#left, right是子树的边界def recur(root, left, right): ##注意这里的root是当前子树的根在pre中的索引if left > right:return node = TreeNode(pre[root])i = dic[pre[root]] #根在vin中的索引node.left = recur(root+1, left,i-1)node.right = recur(root+i-left+1, i+1,right)return nodedic = {}for i, v in enumerate(vin):dic[v] = ireturn recur(0, 0, len(vin)-1)

BM41 输出二叉树的右视图

方法一：建树+BFS

class Solution:def solve(self , xianxu: List[int],zhongxu: List[int]) -> List[int]:# write code heredef recur(root, left, right):if left > right:returnnode = TreeNode(xianxu[root])i = dic[xianxu[root]] #在中序遍历中的索引node.left = recur(root+1, left,i-1)node.right = recur(root+i-left+1,i+1, right)return nodedic = {}for i in range(len(zhongxu)):dic[zhongxu[i]] = iroot = recur(0, 0, len(zhongxu)-1)#层序遍历res = []queue = [root]while queue:n = len(queue)for i in range(n):node = queue.pop(0)if i == n-1:res.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)return res

04 堆、栈、队列

BM42 用两个栈实现队列

class Solution:def __init__(self):self.stack1 = []self.stack2 = []def push(self, node):# write code hereself.stack1.append(node)def pop(self):# return xxif not self.stack2:while self.stack1:self.stack2.append(self.stack1.pop())if self.stack2:return self.stack2.pop()

BM43 包含min函数的栈

class Solution:A = []B = []def push(self, node):# write code hereself.A.append(node)if not self.B or node <= self.B[-1]:self.B.append(node)def pop(self):# write code hereval = self.A.pop()if self.B[-1] == val:self.B.pop()return valdef top(self):# write code herereturn self.A[-1]def min(self):# write code herereturn self.B[-1]

BM44 有效括号序列

给出一个仅包含字符’(‘,’)‘,’{‘,’}‘,’[‘和’]',的字符串，判断给出的字符串是否是合法的括号序列

class Solution:def isValid(self , s: str) -> bool:# write code here#([]{})stack = []for c in s:if c == '(' or c == '[' or c =='{':stack.append(c)elif not stack: #必须有左括号才能遇到右括号return Falseelif c == ')':if stack.pop() != '(':return Falseelif c == ']':if stack.pop() != '[':return Falseelse:if stack.pop() != '{':return Falsereturn not stack

BM45 滑动窗口的最大值

方法一：维持一个单调递减的双向队列

class Solution:def maxInWindows(self , num: List[int],size: int) -> List[int]:from collections import dequeres = []dq = deque()for i in range(size):while dq and num[dq[-1]] <num[i]:dq.pop()  #比当前小的都不会是后面的最大值，pop掉dq.append(i)for i in range(size, len(num)):res.append(num[dq[0]])if dq and dq[0] < i - size + 1:#弹出窗口移走后的值dq.popleft()while dq and num[dq[-1]] <num[i]:dq.pop()dq.append(i)res.append(num[dq[0]])return res

BM46 最小的K个数

class Solution {
public:vector<int>GetLeastNumbers_Solution(vector<int> input, int k) {vector<int> res;if(k>input.size()){return res;}priority_queue<int> que;for(auto it:input){que.push(it);if(que.size()>k){que.pop();}}while(que.size()){int it=que.top();que.pop();res.push_back(it);}return res;}
};

BM47 寻找第K大值

快排写法一：

class Solution:        def quick_sort(arr, l, r):if l >= r:returni, j = l, rwhile i < j:while i < j and arr[j] <=arr[l]: j -= 1while i < j and arr[i] >=arr[l]: i += 1arr[i], arr[j] = arr[j], arr[i]arr[i], arr[l] = arr[l], arr[j]quick_sort(arr, l, i-1)quick_sort(arr, i+1, r)quick_sort(a, 0, n-1)

BM48 数据流中的中位数

方法二：

插入排序

class Solution:A = []def Insert(self, num):self.A.append(num)for i in range(len(self.A)-1, 0, -1):if self.A[i] < self.A[i-1]:self.A[i], self.A[i-1] =self.A[i-1], self.A[i]else:breakdef GetMedian(self):n = len(self.A)if n % 2:return self.A[n//2]else:return (self.A[(n-1)//2] +self.A[n//2]) / 2

BM49 表达式求值

方法一：栈+递归

class Solution:def solve(self , s: str) -> int:# write code heres.strip()stack = []res = 0num = 0sign = '+'index = 0while index < len(s):if s[index] == '(':lens = 1 #当前还有几个左括号end = index + 1while lens > 0:if s[end] == '(':lens += 1if s[end] == ')':lens -= 1end += 1num = self.solve(s[index + 1:end - 1])index = end - 1continueif '0' <= s[index] <='9':num = num * 10 + int(s[index])if not '0' <= s[index] <= '9'or index == len(s) - 1:if sign == '+':stack.append(num)elif sign == '-':stack.append(-1 * num)elif sign == '*':stack.append(stack.pop() *num)num = 0sign = s[index]index += 1while stack:res += stack.pop()return res

05 哈希

BM50 两数之和

注意这里数组下标从1开始算

class Solution:def twoSum(self , numbers: List[int],target: int) -> List[int]:# write code heredic = {}for i, num in enumerate(numbers):if target - num in dic:return [dic[target-num]+1, i+1]dic[num] = i   #关键是遍历一次就将其记录下来，避免重复遍历return

BM51数组中出现次数超过一半的数字

方法一：摩尔投票

不同的两两抵消

class Solution:def MoreThanHalfNum_Solution(self ,numbers: List[int]) -> int:# write code herecount = 0for num in numbers:if count == 0:x = numcount += 1else:if num == x:count += 1else:count -= 1return x

BM52 数组中只出现一次的两个数字

最优的应该是异或位运算发方法

方法一：哈希统计

class Solution:def FindNumsAppearOnce(self , array:List[int]) -> List[int]:# write code heredic = {}res = []for num in array:if num in dic:dic[num] += 1else:dic[num] = 1for k, v in dic.items():if v == 1:res.append(k)res.sort()return res

BM53 缺失的第一个正整数

方法一：哈希

class Solution:def minNumberDisappeared(self , nums:List[int]) -> int:# write code hereA = set()for num in nums:A.add(num)i = 1while 1:if i not in A:return ibreaki += 1

BM54 三数之和

方法一：先排序，然后遍历做双指针

class Solution:def threeSum(self , num: List[int]) ->List[List[int]]:# write code herenum.sort()res = []for k in range(len(num) - 2):if num[k] > 0:breakif k > 0 and num[k] == num[k-1]:continuei, j = k + 1, len(num) - 1while i < j:s = num[k] + num[i] + num[j]if s < 0:i += 1while i < j and num[i]== num[i-1]: i += 1elif s > 0:j -= 1while i < j and num[j]== num[j+1]: j -= 1else:res.append([num[k], num[i],num[j]])i += 1j -= 1while i < j and num[i] ==num[i-1]: i += 1while i < j and num[j]== num[j+1]: j -= 1 #注意这里是num[j+1]return res

06 递归，回溯

BM55 没有重复数字的全排列

LC46 题解

方法一：回溯

选一个，后接剩下没选过的的数字的全排列

达到深度则返回（当前填充到最后一个）

写法二：选过的则去掉，写法一是选过的则标记

class Solution:def permute(self, nums: List[int]) ->List[List[int]]:def dfs(nums, path, res):if not nums:res.append(path)returnfor i in range(len(nums)):dfs(nums[:i] + nums[i+1:],path+[nums[i]], res)path, res =[], []dfs(nums, path, res)return res

BM56 有重复数字的全排列

class Solution:def permuteUnique(self , num: List[int])-> List[List[int]]:# write code heredef dfs(num, size, index, path, used,res): #index表示当前要选择的位置if index == size:res.append(path[:])return for i in range(size):#i和i-1相等的情况下， 只有i-1是用过在才递归，这样保证只出现一次1,1,2if not used[i] and (i == 0  or num[i] != num[i-1] or used[i-1]): used[i] = Truepath.append(num[i])dfs(num, size, index + 1,path, used, res)used[i] = Falsepath.pop()num.sort()used = [False for _ in range(len(num))]res, path = [], []dfs(num, len(num), 0, path, used, res)return res

LC78 子集

class Solution:def subsets(self, nums: List[int]) ->List[List[int]]:def dfs(nums, start, path, res):res.append(path[:])for i in range(start, len(nums)):path.append(nums[i])dfs (nums, i+1, path, res)path.pop()res, path = [], []dfs(nums, 0, path, res)return res

LC39 组合总和

class Solution:def combinationSum(self, candidates:List[int], target: int) -> List[List[int]]:def dfs(nums, start, size, path, res,target):if target < 0:returnif target == 0:res.append(path[:])return for i in range(start, size):path.append(nums[i])target -= nums[i]dfs(nums, i, size, path, res,target) #注意这里仍然是从i开始，可以重复选取# dfs(nums, i, size, path, res,target - nums[i]) #如果在这里计算target，传进去的是计算出来的一个新值，有新的地址，返回当前target不变target += nums[i]path.pop()path, res = [], []dfs(candidates, 0, len(candidates),path, res, target)return res

BM57岛屿数量

方法一：回溯

遍历行和列进行，如果当前为岛屿1，则进入dfs

在dfs中将其置为0，并且dfs其上下上左右

dfs终止的条件是当前位置为0或者超出边界

class Solution:def solve(self , grid: List[List[str]])-> int:# write code heredef dfs(grid, i, j):nr, nc = len(grid), len(grid[0])if not 0 <= i < nr ornot  0 <= j < nc or grid[i][j] =='0': #终止条件return grid [i][j] = '0' #标记为0避免重复访问dfs(grid, i - 1, j) dfs(grid, i + 1, j)dfs(grid, i, j - 1)dfs(grid, i, j + 1)nr, nc = len(grid), len(grid[0])count = 0for i in range(nr):for j in range(nc):if grid[i][j] == '1':count += 1dfs(grid, i, j)return count

BM58 字符串的排列

有重复的需要先排序

class Solution:def Permutation(self , str: str) ->List[str]:# write code heredef dfs(s, size, index, path, used,res):if index == size:res.append(path)returnfor i in range(size):if not used[i] and (i == 0 ors[i] != s[i-1] or used[i-1]):used[i] = Truepath += s[i]dfs(s, size, index+1, path,used, res)path = path[:-1]used[i] = Falsestr = sorted(str) #注意str没有str.sortused = [False for _ in range(len(str))]res, path = [], ''dfs(str, len(str), 0, path, used, res)return res

BM59 N皇后问题

方法一：回溯

用dfs遍历行

对于每一行，遍历每一列，并看当前列是不是可以放Q的位置

放满n行结果+1

class Solution:def Nqueen(self , n: int) -> int:# write code heredef dfs(r, res):if r == n:res += 1return resfor i in range(n):if i in columns or r - i indiagonals1 or r + i in diagonals2:continuecolumns.add(i)diagonals1.add(r - i)diagonals2.add(r + i)res = dfs(r + 1, res)columns.remove(i)diagonals1.remove(r - i)diagonals2.remove(r + i)return rescolumns = set()diagonals1 = set()diagonals2 = set()res = 0return dfs(0, res)

注意：

Python参数传递采用的肯定是“传对象引用”的方式。实际上，这种方式相当于传值和传址的一种综合。如果函数收到的是一个可变对象(比如字典或者列表)的引用，就能修改对象的原始值——相当于传址。如果函数收到的是一个不可变对象(比如数字、字符或者元组)的引用，就不能直接修改原始对象——相当于传值。所以以下代码返回的结果是0

class Solution:def Nqueen(self , n: int) -> int:# write code heredef dfs(r, res):if r == n:res += 1for i in range(n):if i in columns or r - i indiagonals1 or r + i in diagonals2:continuecolumns.add(i)diagonals1.add(r - i)diagonals2.add(r + i)dfs(r + 1, res)columns.remove(i)diagonals1.remove(r - i)diagonals2.remove(r + i)columns = set()diagonals1 = set()diagonals2 = set()res = 0dfs(0, res)return res

返回可行棋盘版本：

class Solution:def solveNQueens(self, n: int) ->List[List[str]]:def generateBoard():board = list()for i in range(n):row[queens[i]] = "Q"#row是一维向量，表示当前行的情况，i表示当前是第几行，queens[i]表示第几列；即当前第i行的第几列是Qboard.append("".join(row))row[queens[i]] = "."return boarddef backtrack(row: int):if row == n:board = generateBoard()solutions.append(board)else:for i in range(n): #遍历所有的列if i in columns or row - iin diagonal1 or row + i in diagonal2:continuequeens[row] = i #第row行的第i列; 使用一个数组记录每行放置的皇后的列下标，依次在每一行放置一个皇后columns.add(i)diagonal1.add(row - i) #同是左上-右下对角线的话，行坐标与列坐标之差相等diagonal2.add(row + i) #同是做下-右上对角线，行坐标与列坐标之和相等backtrack(row + 1) #遍历行columns.remove(i)diagonal1.remove(row - i)diagonal2.remove(row + i)solutions = list()queens = [-1] * ncolumns = set()diagonal1 = set()diagonal2 = set()row = ["."] * nbacktrack(0)return solutions

BM60 括号生成

方法一：回溯

相比于全排列，只是没有了从所给nums中选择的过程，而是直接添加 ‘(’ 或 ‘)’

全排列 indexlen(nums) 时添加结果，这里 s2*n 时添加结果

class Solution:def generateParenthesis(self, n: int) ->List[str]:def dfs(s, left, right):if len(s) == 2 * n:res.append(''.join(s))returnif left < n:s.append('(')dfs(s, left + 1, right)s.pop()if right < left: #如果写right < n, 就包括了left <= right的情况， 这是不该加右括号的s.append(')')dfs(s, left,  right + 1)s.pop()res = []s = []dfs(s, 0, 0)return res

BM61 最长增长路径

方法一：深度优先搜索+保存中间结果

记忆化搜索

class Solution:defsolve(self , matrix: List[List[int]]) -> int:if not matrix: return m, n = len(matrix), len(matrix[0])memo = [[0] * n for _ in range(m)]def dfs(x, y):if memo[x][y] != 0: returnmemo[x][y] #避免重复计算；相当与动态规划用dp保存子问题的解memo[x][y] += 1for new_x, new_y in [(x - 1, y), (x+ 1, y), (x, y - 1), (x, y + 1 )]:if 0 <= new_x < m and 0<= new_y < n and matrix[x][y] < matrix[new_x][new_y]:memo[x][y] =max(memo[x][y], dfs(new_x, new_y) + 1) #每能遍历一个，长度就加一return memo[x][y] #一定是遍历到最后超出边界或者没有增长路径才返回，每个格子结果唯一res = 0for i in range(m):for j in range(n):res = max(res, dfs(i, j))return res

07 动态规划

BM62 斐波那契数列

写法一：

class Solution:def Fibonacci(self , n: int) -> int:a, b = 1, 1if n == 1 or n ==2:return 1for i in range(n-2):tmp = aa = bb += tmpreturn b

BM63 跳台阶

class Solution:def jumpFloor(self , number: int) ->int:#1, 2, #dp[i] = dp[i-1] + dp[i-2]]a, b = 1, 2for _ in range(number):tmp = aa = bb += tmpreturn a

BM64最小花费爬楼梯

方法一：

用dp保存跳到第i个阶梯的费用，i可以从i-2开始跳，跳两个台阶，也可以从i-1开始跳，跳一个台阶

转移方程：dp[i] = min(cost[i-2] + dp[i-2], cost[i-1] +dp[i-1])

关键是递推过程，而不是模拟具体怎么跳

class Solution:def minCostClimbingStairs(self , cost:List[int]) -> int:n = len(cost)dp = [0] * (n + 1)for i in range(2, n + 1): #题目的跳到顶部是越过n-1到ndp[i] = min(cost[i-2] + dp[i-2],cost[i-1] + dp[i-1])return dp[n]

BM65 最长公共子序（二）

涉及两个字符串，一般是动态规划一般是二维的

class Solution:def LCS(self , s1: str, s2: str) -> str:# write code herem, 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]+ 1else:dp[i][j] = max(dp[i -1][j], dp[i][j - 1]) #此s1[i-1]不一定等于s2[j], s1[i-1]不一定等于s2[j]i, j = m, ns = []while dp[i][j] != 0:if dp[i][j] == dp[i - 1][j]:i -= 1elif dp[i][j] == dp[i][j - 1]:j -= 1elif dp[i][j] > dp[i-1][j - 1]:#说明s1[i - 1] == s2[j - 1]i -= 1j -= 1s.append(s1[i])if not s:return '-1'else:return ''.join(s[::-1])

BM66 最长公共子串

方法一：枚举

暴力法是遍历str1中的每个起点，并遍历每个长度，看是在str2中。复杂度太大

改进方法是维持一个最大长度，看i往前max_len+1个字符在不在str2中，在则更新

class Solution:def LCS(self , str1: str, str2: str) ->str:if len(str1) > len(str2):str1, str2 = str2, str1max_len = 0for i in range(len(str1)):if str1[i - max_len : i + 1] instr2: #第i个字符及往前max_len+1个字符在str2中才更新最长字符res = str1[i - max_len : i + 1]max_len += 1return res

BM67 不同路径的数目（一）

方法一：动态规划

class Solution:def uniquePaths(self , m: int, n: int)-> int:# write code heredp = [[1] * n] + [[1] + [0] * (n - 1)for _ in range(m - 1)]for i in range(1, m):for j in range(1, n):dp[i][j] = dp[i][j - 1] + dp[i- 1][j]return dp[m - 1][n - 1]

BM68 矩阵的最小路径和

方法一：动态规划

class Solution:def minPathSum(self , matrix:List[List[int]]) -> int:m, n = len(matrix), len(matrix[0])for i in range(m):for j in range(n):if i == 0 and j == 0:matrix[i][j] = matrix[i][j]continueif i == 0:matrix[i][j] += matrix[i][j- 1]elif j == 0:matrix[i][j] += matrix[i-1][j]else:matrix[i][j] +=min(matrix[i-1][j], matrix[i][j -1])return matrix[m -1][n -1]

BM69 把数字翻译成字符串

有一种将字母编码成数字的方式：‘a’->1, ‘b->2’, … , ‘z->26’。

我们把一个字符串编码成一串数字，再考虑逆向编译成字符串。

由于没有分隔符，数字编码成字母可能有多种编译结果，例如 11 既可以看做是两个 ‘a’ 也可以看做是一个‘k’。但 10 只可能是 ‘j’，因为 0 不能编译成任何结果。

方法一：动态规划

class Solution:def solve(self , nums: str) -> int:# 当前位单独翻译dp[i] = dp[i-1], 与前一位一起翻译 dp[i] = dp[i - 2]n = len(nums)dp = [0] * (n + 1)dp[0] = 1dp[1] = 1for i in range(2, n +1):if nums[i - 1] == '0' and nums[i -2] != '1' and nums[i - 2] != '2':return 0elif '11' <= nums[i - 2 : i]<= '19' or '21' <= nums[i - 2 : i] <= '26':dp[i] = dp[i - 2] + dp[i - 1]elif nums[i - 2 : i] == '10' ornums[i - 2 : i] == '20':dp[i] = dp[i - 2]else:dp[i] = dp[i - 1]return dp[n]

LC 剑指offer 46. 把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a”，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

写法一：初始化一个第一个状态，i表示当前字符的下标加一

class Solution:def translateNum(self, num: int) -> int:s = str(num)n = len(s)dp = [0] * (n + 1)dp[0] = 1dp[1] = 1for i in range(2, n + 1):if '10' <= s[i - 2 : i] <='25':dp[i] = dp[i - 2] + dp[i - 1]else:dp[i] = dp[i - 1]return dp[n]

BM70 兑换零钱（一）

方法一：动态规划

dp[i]根据dp[0]~dp[i-1]得到

class Solution:def minMoney(self , arr: List[int], aim:int) -> int:dp = [float('+inf')] * (aim + 1)dp[0] = 0for i in range(1, aim + 1): #遍历1~aim元for j in range(len(arr)):if arr[j] <= i:#在遍历硬币的时候，i还是i，并没有减少，只是不断查看dp[i - arr[j]]看哪个dp[0]~dp[i-1]中的dp最小，并维护最小值dp[i] = min(dp[i], dp[i -arr[j]] + 1)return dp[aim] if dp[aim] !=float('+inf') else -1

BM71 最长上升子序列（一）

方法一：动态规划

要找到最长的递增子序列长度，每当我们找到一个位置，它是继续递增的子序列还是不是，它选择前面哪一处接着才能达到最长的递增子序列

dp[i] 表示以arr[i]结尾的最长子序列长度

class Solution:def LIS(self , arr: List[int]) -> int:if not arr:return 0n = len(arr)dp = [1] * nfor i in range(n):for j in range(i):if arr[j] < arr[i]:dp[i] = max(dp[i], dp[j] +1) #已知dp[0] ~ dp[i - 1]return max(dp) #这里不是dp[n - 1], dp[i]的值代表以arr[i]结尾的最长子序列长度,不是前i个数字的最长子序列，最长子序列不一定以arr[i]结尾

BM72 连续子数组的最大和

方法一：动态规划

#dp[i] 代表以元素 array[i] 为结尾的连续子数组最大和。

#dp[i] = max(dp[i -1] + array(i) , array[i] )

class Solution:def FindGreatestSumOfSubArray(self , array:List[int]) -> int:# write code hereif len(array) == 1:return array[0]s = array[0]res = float('-inf')for num in array[1:]:s = max(s + num, num)res = max(res, s)return res

BM73 最长回文子串

class Solution:def getLongestPalindrome(self , A: str)-> int:n = len(A)dp = [[False] * n for _ in range(n)]#dp[i][j]表示i到j的子串是否为回文串for i in range(n):dp[i][i] = Truemax_len = 1 #需要记录最大长度       for L in range(2, n + 1): #状态转移的时候，是从较短的字符向较长的字符转移，所以循环的时候先枚举长度for i in range(n):j = i + L -1if j > n -1:breakif A[i] != A[j]:dp[i][j] = Falseelse:if L <= 3:dp[i][j] = Trueelse:dp[i][j] = dp[i + 1][j- 1]if dp[i][j] and L > max_len:max_len = Lreturn max_len

BM74 数字字符串转化成ip地址

与子集、组合总和问题一样，需要定义一个起点，然后遍历；这里需要通过长度和数值大小进行约束剪枝

class Solution:def restoreIpAddresses(self, s: str) ->List[str]:seg_count = 4res = []segments = [0] * seg_countdef dfs(segId, segStart):if segId == 4:if segStart == len(s):ip = '.'.join([str(seg) forseg in segments])res.append(ip)returnif segStart == len(s):returnif s[segStart] == '0':segments[segId] = 0dfs(segId + 1, segStart + 1)addr = 0for segEnd in range(segStart,len(s)):addr = addr * 10 + (ord(s[segEnd]) -ord('0'))if 0 < addr <= 255:segments[segId] = addr  #这里不涉及pop，因为不是用栈来保存结果，这里新结果会覆盖旧结果dfs(segId + 1, segEnd + 1)else:returndfs(0, 0)return res

BM75 编辑距离（一）

class Solution:def editDistance(self , str1: str, str2:str) -> int:#dp[i][j]表示str1前i个字符与str2前j个字符的编辑距离m = len(str1)n = len(str2)dp = [[0] * (n + 1) for _ in range(m +1)]for i in range(m + 1):dp[i][0] = ifor j in range(n + 1):dp[0][j] = jfor i in range(1, m + 1):for j in range(1, n + 1):a = dp[i - 1][j] + 1 #在str1中插入一个字符到达dp[i][j]b = dp[i][j - 1] + 1 #在str2中插入一个字符到达dp[i][j]c = dp[i - 1][j - 1] #str[i] ==str[j]的情况下，不用操作，dp[i][j] =dp[i -1][j - 1]if str1[i - 1] != str2[j - 1]:c += 1dp[i][j] = min(a, b, c)return dp[m][n]

BM76 正则表达式匹配

class Solution:def match(self , str: str, pattern: str)-> bool:m = len(str)n = len(pattern)dp = [[False] * (n + 1) for _ inrange(m + 1)]dp[0][0] = Truedef match(i, j):if i == 0:return Falseif pattern[j - 1] == '.':return Truereturn str[i - 1] == pattern[j - 1]for i in range(m + 1):for j in range(1, n + 1):if pattern[j - 1] == '*':dp[i][j] |= dp[i][j - 2]#pattern *前面的字符取0次if match(i, j - 1): #str[i]与pattern[j - 1]匹配，*前面的字符可以取多次，相当于把str的最后一个字符一次次丢弃，并与pattern匹配dp[i][j] |= dp[i -1][j] #在s[i] == p[i - 1]时，将s[i]扔掉, 检查s的1~i-1是否与p的1~j匹配#虽然这里只看dp[i - 1][j] 但dp[i - 1][j] 也是由dp[i - 2][j]得来的else:if match(i, j):dp[i][j] |= dp[i - 1][j- 1]return dp[m][n]

BM77 最长的括号子串

class Solution:def longestValidParentheses(self, s: str)-> int:#dp[i] 表示以s[i]结尾的最长有效子串长度，注意不是前i个字符的最长有效子串长度n= len(s)if n == 0 or n == 1:return 0dp = [0] * nif s[0] == '(' and s[1] == ')':dp[1] = 2res = max(0, dp[1])for i in range(2, n):if s[i] == '(': #以'('结尾，必不是有效的子串dp[i] = 0elif s[i] == ')' and s[i - 1] =='(':dp[i] = dp[i - 2] + 2elif s[i] == ')' and s[i - 1] ==')':if i - dp[i - 1] - 1 >= 0and s[i - dp[i - 1] - 1] == '(':dp[i] = dp[i - 1] + 2 +dp[i - dp[i - 1] - 2] #最后一项是因为s[i - dp[i -1] -1]前可能是(...)这样的有效括号，通过s[i - dp[i - 1] - 1]连起来了res = max(res, dp[i])return res

BM78 打家劫舍

方法一：动态规划

dp[i] 表示到第i间房屋可以偷得的最大金额，dp[i] = max()

i 可以选择偷或者不偷, 偷的话dp[i] = dp[i -2] + nums[i] , 不偷的话dp[i] = dp[i -1]

偷窃第 k间房屋，那么就不能偷窃第 k-1 间房屋，偷窃总金额为前 k-2间房屋的最高总金额与第 kk 间房屋的金额之和。

不偷窃第 k 间房屋，偷窃总金额为前 k-1 间房屋的最高总金额。

写法一：

class Solution:def rob(self , nums: List[int]) -> int:n = len(nums)if n == 1:return nums[0]dp = [0] * ndp[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]

空间优化：用两个变量滚动保存dp[i - 2] 和dp[i - 1]。因为这里dp[i] [j]只与dp[i - 1] 和dp[i - 2]有关系

class Solution:def rob(self , nums: List[int]) -> int:n = len(nums)if n == 1:return nums[0]a = nums[0]b = max(nums[0], nums[1])for i in range(2, n):a, b = b, max(a + nums[i], b)return b

写法二：dp[i]表示第i个，比对应的下标要多1

 
class Solution:def rob(self , nums: List[int]) -> int:n = len(nums)dp = [0] * (n + 1)dp[1] = nums[0]for i in range(2, n + 1):dp[i] = max(dp[i - 2] + nums[i-1],dp[i - 1]) #分别对应选和不选当前nums.如果选，则只能和dp[i-2]相加#如果上一次选了当前nums,下一次选在num的时候只能和dp[i-2]相加，也不相邻return dp[n]

BM79 打家劫舍（二）

情况1：偷第一家的钱，不偷最后一家的钱。初始状态与状态转移不变，只是遍历的时候数组最后一位不去遍历。

情况2：偷最后一家的请，不偷第一家的钱。初始状态改变，第一家就不要了，然后遍历的时候也会遍历到数组最后一位。

class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)if n == 1:return nums[0]pre = nums[0]cur = max(pre, nums[1])if n == 2:return curfor i in range(2, n - 1):pre, cur = cur, max(pre + nums[i],cur)tmp = curpre = nums[1]cur = max(pre, nums[2])for i in range(3, n):pre, cur = cur, max(pre + nums[i],cur)return max(tmp, cur)

BM80 买卖股票的最好时机

dp[i]表示第i天的利润,

dp[i] = max(dp[i -1], prices[i] - cost)

维护一个cost表示第i天之前的最低价格

class Solution:def maxProfit(self , prices: List[int])-> int:n = len(prices)res = 0cost = prices[0]for i in range(1, n):res = max(res, prices[i] - cost)cost = min(cost, prices[i])return res

BM81 买卖股票的最好时机（二）

方法二：贪心

class Solution:def maxProfit(self , prices: List[int])-> int:res = 0for i in range(1, len(prices)):if prices[i] > prices[i - 1]:res += prices[i] - prices[i -1]return res

BM82 买卖股票的最好时机（三）

dp[i] [0] 表示到第i天为止没有买卖过的最大收益

dp[i] [1] 表示到第i天为止买了一次的最大收益

dp[i] [2] 表示到第i天为止买一次，卖一次的最大收益

dp[i] [3] 表示到第i天为止买两次，卖一次的最大收益

dp[i] [4] 表示到第i天为止买两次，卖两次的最大收益

class Solution:def maxProfit(self , prices: List[int])-> int:n = len(prices)dp = [[float('-inf')] * 5 for _ inrange(n)]dp[0][0] = 0 #第一天不持有dp[0][1] = -prices[0] #第一天持有for i in range(1, n):dp[i][0] = dp[i - 1][0] #实际上都是0dp[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]))

08 字符串

BM83 字符串变形

对于一个长度为 n 字符串，我们需要对它做一些变形。

首先这个字符串中包含着一些空格，就像"Hello World"一样，然后我们要做的是把这个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。

比如"Hello World"变形后就变成了"wORLD hELLO"。

方法一：str.split()函数

class Solution:def trans(self , s: str, n: int) -> str:lst = s.split(' ') #就算遇到多空格，用一个空格分割是没问题的，下面再用一个空格拼接;但如果用s.split(''),空格最后都变成单空格了lst.reverse() #在原来的地址上修改，不能写lst = lst.reverse()s = ' '.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: str) -> str:numsv4 = IP.split('.')numsv6 = IP.split(':')res = ''if len(numsv4) == 4:for num in numsv4:for c in num:if not '0' <= c <='9':res = 'Neither'breakif res == 'Neither':breakif not num or (num[0] == '0'and len(num) > 1) or int(num) > 255:res = 'Neither'breakif res != 'Neither':res = 'IPv4'if res == 'IPv4':return resres1 = ''if len(numsv6) == 8:for num in numsv6:if len(num) <= 0 or len(num)>= 5:res1 = 'Neither'breakfor c in num:if '0' <= c <= '8' or'a' <= c <= 'f' or 'A' <= c <= 'F':continueelse:res1 = 'Neither'breakif res1 != 'Neither':res1 = 'IPv6'return res1 if res1 == 'IPv6' else'Neither'

BM86 大数加法

写法二：res = [ ]，后面再join（res）

该写法并没有提高空间效率

写法一：时间70%，空间12%

写法二：时间1%，空间6%

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 = 1carry = 0while s or t:if s and t:SUM = s.pop() + t.pop() + carrycarry = SUM // 10s1 = SUM % 10res.insert(0, str(s1))elif s:SUM = s.pop() + carrycarry = SUM // 10s1 = SUM % 10res.insert(0, str(s1))else:SUM = t.pop() + carrycarry = SUM // 10s1 = SUM % 10res.insert(0, str(s1))if carry != 0:res.insert(0, str(carry))return ''.join(res)

09 双指针

BM87 合并两个有序的数组

class Solution:def merge(self , A, m, B, n):i = m - 1j = n - 1p = m + n - 1while i >= 0 and j >= 0:if A[i] > B[j]:A[p] = A[i]i -= 1else:A[p] = B[j]j -= 1p -= 1while j >= 0:A[p] = B[j]j -= 1p -= 1

BM88 判断是否为回文子串

class Solution:def judge(self , str: str) -> bool:# write code herei, j = 0, len(str) - 1while i < j:if str[i] != str[j]:return Falsei += 1j -= 1

BM89 合并区间

把两个区间合并，覆盖原来两个区间的范围。

# class Interval:
#     def __init__(self, a=0, b=0):
#         self.start = a
#         self.end = b
class Solution:def merge(self , intervals: List[Interval])-> List[Interval]:if not intervals:return []intervals.sort(key = lambda x: x.start)res = []pre = intervals[0]for cur in intervals[1:]:if pre.end < cur.start:res.append(pre)pre = curelif cur.start <= pre.end <cur.end:pre.end = cur.endres.append(pre)return res

BM90 最小覆盖字串

方法一：哈希 + 滑动窗口

哈希记录T中的每字符串还缺几个

i, j 分别指向滑动窗口的左右端点。

j 向右扩张，如果窗口满足包含T的条件，则i向右收缩，同时记录最短字串和对应的端点

class Solution:def minWindow(self , S: str, T: str) ->str:dic = {}for c in T:if c in dic:dic[c] -= 1 #表示还缺几个字符else:dic[c] = -1 def check(dic):for k, val in dic.items():if val < 0: #当还缺字符，则不满足return Falsereturn TrueL = len(S) + 1i = 0j = 0left = -1 #用来记录最短区间的左右端点，因为最后要返回字符串而不是最小长度right = -1while j < len(S):if S[j] in dic: #找到一个则加1dic[S[j]] += 1 while check(dic): #窗口的字符串满足要求if j - i + 1 < L:L = j - i + 1left = iright = jif S[i] in dic: #当前收缩的子符是否在T中dic[S[i]] -= 1 #如果在T中，则减1i += 1 #左边界收缩j += 1if left == -1: #找不到，return ''return S[left : right + 1]

BM91 反转字符串

class Solution:def solve(self , str: str) -> str:i = len(str) - 1res = []while i >= 0:res.append(str[i])i -= 1return ''.join(res)

BM92 最长无重复子数组

方法一：哈希，记录每个数字的最右边的位置

写法二：

class Solution:def lengthOfLongestSubstring(self, s: str)-> int:dic = {}res = tmp = 0for j in range(len(s)):i = dic.get(s[j],-1) #dic.get获取键s[j]的值，若不存在则返回第二参数-1dic[s[j]] = jtmp = tmp + 1 if j - i > tmpelse j - ires = max(tmp, res)return res

BM93 盛最多水的容器

关键是容积由最小的高度决定

class Solution:def maxArea(self , height: List[int]) ->int:n = len(height)if n < 2:return 0i, j = 0, n - 1res = min(height[i], height[j]) * (j -i)while i < j:if height[i] < height[j]:i += 1else:j -= 1res = max(res, min(height[i],height[j]) * (j - i))return res

BM94 接雨水问题

方法一：双指针

指针指向两边向中间靠，

且维护左右的最大边界的高度，当指针指向的高度比边界高度低时，对应的雨水单位就是边界减当前高度

class Solution:def maxWater(self , arr: List[int]) ->int:i, j = 0, len(arr) - 1maxL = 0maxR = 0res = 0while i < j:maxL = max(maxL, arr[i])maxR = max(maxR, arr[j])if arr[i] < arr[j]:res += maxL - arr[i]i += 1else:res += maxR - arr[j]j -= 1return res 

10 贪心算法

BM95 分糖果问题

方法一：两次遍历

从左到右，当前比左边大时，当前的糖果为左边加1

从右到左，当前比右边大，但糖果数比右边小时，当前的糖果为右边加1

class Solution:def candy(self , arr: List[int]) -> int:n = len(arr)nums = [1] * nfor i in range(1, n):if arr[i] > arr[i - 1]:nums[i] = nums[i - 1] + 1res = nums[n - 1]i = n - 2while i >= 0:if arr[i] > arr[i + 1] andnums[i] <= nums[i + 1]: #当左边比右边大，但分到的糖果小于或等于右边nums[i] = nums[i + 1] + 1res += nums[i]i -= 1return res

BM96 主持人调度（二）

方法一：排序＋遍历比较

class Solution:def minmumNumberOfHost(self , n: int,startEnd: List[List[int]]) -> int:start = []end = []for i in range(n):start.append(startEnd[i][0])end.append(startEnd[i][1])start.sort()end.sort()res = 0j = 0for i in range(n):if start[i] >= end[j]: #新开始的节目的开始时间大于上一轮快要结束的结束时间，主持人不变j += 1  #最快要结束的时间变为下一个else:res += 1 #增加主持，最快要结束的时间还是原来的j，不变return res

11模拟

BM97 旋转数组

方法一：切片

class Solution:def solve(self , n: int, m: int, a:List[int]) -> List[int]:m = m % nres = a[n - m :] + a[:n - m]return res

BM98 螺旋矩阵

class Solution:def spiralOrder(self , matrix:List[List[int]]) -> List[int]:if not matrix:return []l, r, u, d = 0, len(matrix[0]) - 1, 0,len(matrix) - 1res = []while l <= r and u <= d:  #等于的时候是要进入循环的，比如[[2, 3]]，u == d == 0. 一旦l > r 或者u > d就跳出for j in range(l, r + 1):res.append(matrix[u][j])u += 1if u > d: #但不满足时就要跳出，否者下面会重复打印。比如matrix= [[2, 3]]时，若不跳出，breakfor i in range(u, d + 1):res.append(matrix[i][r])r -= 1if l > r:breakfor j in range(r, l - 1, -1): #这里会重复打印res.append(matrix[d][j])d -= 1if u > d:breakfor i in range(d, u - 1, -1):res.append(matrix[i][l])l += 1if l > r:breakreturn res

BM99 顺时针旋转矩阵

方法一：利用辅助矩阵

设原矩阵的元素坐标为i, j，那么在结果中该元素的坐标为 j, n - i - 1

即原来在第几列，则在新数组中第几行。原来在第几行，则在新数组中的倒数第几列

class Solution:def rotateMatrix(self , mat:List[List[int]], n: int) -> List[List[int]]:mat_tmp = [[0] * n for _ in range(n)]for i in range(n):for j in range(n):mat_tmp[j][n - i - 1] =mat[i][j]return mat_tmp

BM100 设计LRU缓存

双向链表+哈希

class DlinkedNode:def __init__(self, key = 0, value = 0):self.key = keyself.value = valueself.next = Noneself.prev = Noneclass LRUCache:def__init__(self, capacity: int):self.cache = {}self.head = DlinkedNode()self.tail = DlinkedNode()self.head.next = self.tailself.tail.prev = self.headself.capacity = capacityself.size = 0def get(self, key: int) -> int: if not key in self.cache:return -1node = self.cache[key]self.removeNode(node)self.addToHead(node)return node.valuedef put(self, key: int, value: int) ->None:if key in self.cache:node = self.cache[key]self.removeNode(node)self.addToHead(node)node.value = valueelse:node = DlinkedNode(key, value)self.cache[key] = nodeself.addToHead(node)self.size += 1if self.size > self.capacity:removed = self.removeTail()self.cache.pop(removed.key)self.size -= 1def addToHead(self, node):node.next = self.head.nextnode.prev = self.headself.head.next = nodenode.next.prev = nodedef removeNode(self, node):node.prev.next = node.nextnode.next.prev = node.prevdef removeTail(self,):node = self.tail.prev# node.prev.next = self.tail# self.tail.prev = node.prevself.removeNode(node)return node

BM101 设计LFU 缓存

用两个哈希：

记录key和节点

记录频率和双向链表

# importcollections
class Node:def __init__(self, key, value):self.freq = 0self.key = keyself.value = valueself.pre = Noneself.next = Noneclass LFUCache:def __init__(self, capacity: int):self.capacity = capacityself.size = 0self.minFreq = 0self.freqMap =collections.defaultdict(self.create_linked_list) #使用某个键时，该键不存在，则生成该键，值为self.create_linked_list()self.keyMap = {} #保存的值是双向链表的头和尾，注意喂进去的函数参数没有括号def create_linked_list(self):head = Node(0, 0)tail = Node(0, 0)head.next = tailtail.pre = headreturn (head, tail) #元组类似于列表，区别是元组不能修改def insert(self, node1, node2): #将node2插入到node1后面node2.pre = node1node2.next = node1.nextnode1.next.pre = node2node1.next = node2def delete(self, node):if node.pre:node.pre.next = node.nextnode.next.pre = node.preif node.pre is self.freqMap[node.freq][0]and node.next is self.freqMap[node.freq][1]: #如果node是最后一个元素self.freqMap.pop(node.freq)return node.keydef increase(self, node): #插入到下一个频率对应的双链表node.freq += 1self.delete(node)self.insert(self.freqMap[node.freq][-1].pre, node) #插入到尾部，尾部是最新的if node.freq == 1:self.minFreq = 1elif self.minFreq == node.freq - 1: #如果当前处理的node是之前频率最小的，则查看node.freq - 1还有没有节点，如果没有则node.freq就是最小head, tail = self.freqMap[node.freq- 1]if head.next is tail:self.minFreq = node.freqdef get(self, key: int) -> int:if key in self.keyMap:self.increase(self.keyMap[key])return self.keyMap[key].valuereturn -1def put(self, key: int, value: int) ->None:if self.capacity == 0:returnif key in self.keyMap:node = self.keyMap[key]node.value = valueelse:node = Node(key, value)self.keyMap[key] = nodeself.size += 1if self.size > self.capacity:self.size -= 1deleted =self.delete(self.freqMap[self.minFreq][0].next) #删除频率最小的头部缓存self.keyMap.pop(deleted)self.increase(node)