字符串和数字
05. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
示例 1： 输入：s = “We are happy.” 输出：”We%20are%20happy.”
class Solution:"""没有技巧，全是感情"""def replaceSpace(self, s: str) -> str:res=''for c in s:if c!=' ':res+=celse:res+='%20'return res
20. 表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
数值（按顺序）可以分成以下几个部分：
- 若干空格
- 一个 小数 或者 整数
- （可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数
- 若干空格
小数（按顺序）可以分成以下几个部分：
- （可选）一个符号字符（’+’ 或 ‘-‘）
- 下述格式之一：
- 至少一位数字，后面跟着一个点 ‘.’
- 至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
- 一个点 ‘.’ ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：
- （可选）一个符号字符（’+’ 或 ‘-‘）
- 至少一位数字
部分数值列举如下：
[“+100”, “5e2”, “-123”, “3.1416”, “-1E-16”, “0123”]
部分非数值列举如下：
[“12e”, “1a3.14”, “1.2.3”, “+-5”, “12e+5.4”]
class Solution:def isNumber(self, s: str) -> bool:states = [{ ' ': 0, 's': 1, 'd': 2, '.': 4 }, # 0. start with 'blank'{ 'd': 2, '.': 4 } , # 1. 'sign' before 'e'{ 'd': 2, '.': 3, 'e': 5, ' ': 8 }, # 2. 'digit' before 'dot'{ 'd': 3, 'e': 5, ' ': 8 }, # 3. 'digit' after 'dot'{ 'd': 3 }, # 4. 'digit' after 'dot' (‘blank’ before 'dot'){ 's': 6, 'd': 7 }, # 5. 'e'{ 'd': 7 }, # 6. 'sign' after 'e'{ 'd': 7, ' ': 8 }, # 7. 'digit' after 'e'{ ' ': 8 } # 8. end with 'blank']p = 0 # start with state 0for c in s:if '0' <= c <= '9': t = 'd' # digitelif c in "+-": t = 's' # signelif c in "eE": t = 'e' # e or Eelif c in ". ": t = c # dot, blankelse: t = '?' # unknownif t not in states[p]: return Falsep = states[p][t]return p in (2, 3, 7, 8)
58. II左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。
输入: s = “abcdefg”, k = 2 输出: “cdefgab”
class Solution:def reverseLeftWords(self, s: str, n: int) -> str:res = ""for i in range(n, n + len(s)):res += s[i % len(s)]return res
67. 把字符串转换成整数
64. 求1+2+…n
求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
class Solution:def sumNums(self, n: int) -> int:# python 中and成立会返回第二个的结果，or成立会返回第一个结果return n and n+self.sumNums(n-1)
65. 不用加减乘除符号实现加法
class Solution {public:# 加法可以分解为 进位部分和非进位部分，分别相加即可int add(int a, int b) {if(b==0)return a;return add(a^b,(unsigned)(a&b)<<1);}};
67. 把字符串转换成整数
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
class Solution:# 使用strip() 去掉多余空格def strToInt(self, str: str) -> int:ss=str.strip()if not ss: return 0res,i,sign=0,1,1int_max,int_min,bndry=2**31-1,-2**31,2**31//10if ss[0]=='-':sign=-1elif ss[0]!='+': i=0 # 若无符号位从第0位开始for c in ss[i:]:if not '0'<=c<='9': breakif res>bndry or res==bndry and c>'7':return int_max if sign==1 else int_minres=res*10+ord(c)-ord('0')return res*signclass Solution:# 不使用strip，将空间复杂度降低到O(1)def strToInt(self, str: str) -> int:res,i,sign,length=0,0,1,len(str)int_max,int_min,bndry=2**31-1,-2**31,2**31//10if not str: return 0while str[i]==' ':i+=1if i==length:return 0if str[i]=='-':sign=-1if str[i] in '+-': i+=1for c in str[i:]:if not '0'<=c<='9': breakif res>bndry or res==bndry and c>'7':return int_max if sign==1 else int_minres=res*10+ord(c)-ord('0')return res*sign
61. 扑克牌中的顺子
从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
class Solution:# 顺子的条件： 1. 非0卡牌不重复，2. 最大值-最小值<5def isStraight(self, nums: List[int]) -> bool:repeat=set()ma,mi=0,14for v in nums:if v==0: continuema=max(ma,v)mi=min(mi,v)if v in repeat:return Falserepeat.add(v)return ma-mi<5
29. 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
class Solution:def spiralOrder(self, matrix: List[List[int]]) -> List[int]:if not matrix: return []l,r,t,b,res=0,len(matrix[0])-1,0,len(matrix)-1,[]while True:for i in range(l,r+1):res.append(matrix[t][i]) # left to rightt+=1if t>b: breakfor i in range(t,b+1):res.append(matrix[i][r]) # top to bottomr-=1if r<l: breakfor i in range(r,l-1,-1):res.append(matrix[b][i]) # right to leftb-=1if t>b: breakfor i in range(b,t-1,-1):res.append(matrix[i][l]) # bottom to topl+=1if r<l: breakreturn res
44. 数字序列中某一位数字
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1， 第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
根据上述规律，可将求解分为三步：
- 确定n所在数字的位数，记为digit
- 确定n所在数字，即为num
确定n是num的哪个数位，返回结果
class Solution:def findNthDigit(self, n: int) -> int:digit,start,count=1,1,9while n>count: # 1. 获取数字的位数n-=countstart*=10 # 起始数递推digit+=1 # 位数递推count=9*start*digit # 总位数递推num=start+(n-1)//digit # 2. 获取对应的num，# 注意这里用n-1是为了兼顾整除和非整除两种情况return int(str(num)[(n-1)%digit]) # # 3. 获取对应的数字
43.1~n整数中1出现的次数
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。class Solution:def countDigitOne(self, n: int) -> int:# digit 为当前位个位digit,res=1,0high,cur,low=n//10,n%10,0# 当high和cur同时为0时，说明已经越过了最高位，退出循环while high!=0 or cur!=0:# cur==0时该位出现1的次数由高位决定# cur==1时该位出现1的次数由高位和低位决定# cur==2,3..9时该位出现1的次数由高位决定if cur==0: res+=high*digitelif cur==1: res+=high*digit+low+1else:res+=(high+1)*digit# 向高位递推low+=cur*digit # cur加入low，组成下轮lowcur=high%10 # 下轮cur时本轮high的最低位high//=10 # high最低位删除，得到下轮highdigit*=10 # 位因子X10return res
栈和队列
09. 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
class CQueue:def __init__(self):# 一个用于添加，一个用于删除# 每次删除时，将A中元素全部倒入B中再对B进行删除self.A=[]self.B=[]def appendTail(self, value: int) -> None:self.A.append(value) # 元素都添加到第一个栈中def deleteHead(self) -> int:if len(self.B)==0:while len(self.A)!=0:self.B.append(self.A.pop())if len(self.B)==0:return -1return self.B.pop()
30. 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
class MinStack:def __init__(self):"""initialize your data structure here."""self.A=[]self.B=[]def push(self, x: int) -> None:self.A.append(x)# A中链表的最小值始终要对应B的栈顶# 若B中为空，或者B栈顶元素比当前元素大，说明当前元素就是最小值if not self.B or self.B[-1]>=x:self.B.append(x)def pop(self) -> None:if self.A.pop()==self.B[-1]:self.B.pop()def top(self) -> int:return self.A[-1]def min(self) -> int:return self.B[-1]
31. 栈的压入，弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
class Solution:def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:# 模拟入栈出栈顺序，如果栈顶元素和出栈元素相同则一直出栈deq=collections.deque()i=0for v in pushed:deq.append(v)while deq and deq[-1]==popped[i]:deq.pop()i+=1return not deq
41. 数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。from heapq import *class MedianFinder:def __init__(self):"""initialize your data structure here."""self.A=[] # 小顶堆，保存较大的一半self.B=[] # 大顶堆，保存较小的一半# [ B ] [ A ]def addNum(self, num: int) -> None:if len(self.A)==len(self.B): # 个数为偶数heappush(self.B,-num)heappush(self.A,-heappop(self.B))else: # 个数为奇数，肯定是A多出额外一个，并且位于顶部heappush(self.A,num)heappush(self.B,-heappop(self.A))def findMedian(self) -> float:return self.A[0] if len(self.A)!=len(self.B) else (self.A[0]-self.B[0])/2
59. I 滑动窗口最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:if not nums: return []n = len(nums)# 注意 Python 默认的优先队列是小顶堆q = [(-nums[i], i) for i in range(k)] # 将前k个元素构建大顶堆heapq.heapify(q)ans = [-q[0][0]]for i in range(k, n):heapq.heappush(q, (-nums[i], i))while q[0][1] <= i - k: # 堆顶最大值元素的索引已经出界了，则将其弹出heapq.heappop(q)ans.append(-q[0][0]) # 目前堆顶的元素为当前窗口最大值return ans
59.II 队列最大值
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
输入: [“MaxQueue”,”push_back”,”push_back”,”max_value”,”pop_front”,”max_value”] [[],[1],[2],[],[],[]] 输出: [null,null,null,2,1,2]
输入: [“MaxQueue”,”pop_front”,”max_value”] [[],[],[]] 输出: [null,-1,-1]
import queueclass MaxQueue:def __init__(self):self.queue = queue.Queue() # [front,...tail]self.deque = queue.deque() # [maxv....]def max_value(self) -> int:return self.deque[0] if self.deque else -1def push_back(self, value: int) -> None:self.queue.put(value)while self.deque and self.deque[-1] < value:self.deque.pop() # 双端队列只保存对结果有影响的值self.deque.append(value) # 作为最大值def pop_front(self) -> int:if self.queue.empty(): return -1val = self.queue.get()if val == self.deque[0]:self.deque.popleft()return val
链表
24. 反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
class Solution:"""1. 迭代2. 递归"""def reverseList(self, head: ListNode) -> ListNode:pre,cur=None,headwhile cur:nxt=cur.nextcur.next=prepre=curcur=nxtreturn predef reverseList(self, head: ListNode) -> ListNode:# 越过尾节点时终止递归，回溯时修改各节点next指向def recur(cur,pre):if not cur: return prerev=recur(cur.next,cur) # 反转后头节点cur.next=prereturn revreturn recur(head,None)
06. 从头到尾打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
class Solution:"""1. 递归2. 辅助栈"""def reversePrint(self, head: ListNode) -> List[int]:if not head:return []rev=self.reversePrint(head.next)rev.append(head.val)return revdef reversePrint(self, head: ListNode) -> List[int]:stk=[]while head:stk.append(head.val)head=head.nextreturn stk[::-1]
52. 两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
# 哈希表法：记录第一个指针遍历的节点，然后从另一端遍历，遇到的第一个重复节点即为公共节点class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:if not headA or not headB:return Nonedic=set()p1,p2=headA,headBwhile p1:dic.add(p1)p1=p1.nextwhile p2:if p2 in dic: return p2p2=p2.nextreturn None## 双指针法class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:# 双指针法，当两者指针有一个为空时肯定步相交if not headA or not headB:return Nonep1,p2=headA,headB# 当p1和p2相遇时 两者都为空或者为相同节点while p1!=p2:p1=p1.next if p1 else headBp2=p2.next if p2 else headAreturn p1
35. 复杂链表的复制
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
输入：head = [] 输出：[] 解释：给定的链表为空（空指针），因此返回 null。
class Solution:def copyRandomList(self, head: 'Node') -> 'Node':if not head: return None# 1 将新节点放在原节点后面cur=headwhile cur:nodeNew=Node(cur.val)nodeNew.next=cur.nextcur.next=nodeNewcur=nodeNew.next# 2 构建新的random指向cur=headwhile cur:if cur.random:cur.next.random=cur.random.nextcur=cur.next.next# 3 拆分节点cur=headheadNew=cur.nextwhile cur:nodeNew=cur.nextcur.next=nodeNew.nextnodeNew.next=nodeNew.next.next if nodeNew.next else Nonecur=cur.nextreturn headNew
19. 删除链表倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
class Solution:"""1. 双指针，快指针先走k步，然后同时走"""def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:dummy=ListNode(0)dummy.next=headslow,fast=dummy,dummyfor i in range(n):fast=fast.nextwhile fast.next:slow=slow.nextfast=fast.nextslow.next=slow.next.nextreturn dummy.next
动态规划
10.I 斐波那契数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
class Solution:"""1. 直接遍历，使用两个变量记录 O(n)2. 矩阵快速乘法 O(logn)"""def fib(self, n: int) -> int:a,b=0,1for i in range(n):a,b=b,a+breturn a%1000000007
思路2：我们可以构建一个递推关系
因此有
只要能够快速计算矩阵M的n次幂，就可以得到F(n)的值，直接求Mn复杂度为O(n),可以定义矩阵快速幂乘法来加速计算。
class Solution:def fib(self, n: int) -> int:mod=10**9+7if n<2: return n# 定义二维矩阵乘法def multiply(a,b):c=[[0,0],[0,0]]for i in range(2):for j in range(2):c[i][j]=(a[i][0]*b[0][j]+a[i][1]*b[j][1])%modreturn c# 矩阵快速幂运算def matrix_pow(a,n):ret=[[1,0],[0,1]]while n>0:if n&1: # 最低有效位是1，需要多乘一次ret=multiply(ret,a)# 不断进行平方n>>=1a=multiply(a,a)return retres=matrix_pow([[1,1],[1,0]],n-1)return res[0][0]
10.II 青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
class Solution:"""1. 斐波那契变体，动态规划遍历"""def numWays(self, n: int) -> int:mod=10**9+7f1,f2,f3=1,1,2 # 0,1,2阶if n==0: return 1if 0<n<=2: return nfor i in range(3,n+1): # 遍历3-nf1=f2f2=f3f3=(f1+f2)%modreturn f3# 简洁版def numWays(self, n: int) -> int:a,b=1,1 # 对应0，1阶for i in range(n):a,b=b,a+breturn a%1000000007
46. 把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
class Solution:def translateNum(self, num: int) -> int:# 动态规划递推，将数字转换为字符串 时间O(n)，空间O(n)# dp[i]= dp[i-1]+dp[i-2] if 10xi-1+xi~[10,25] else dp[i-1]s=str(num)b,a=1,1for i in range(2,len(s)+1):tmp=s[i-2:i]c=b+a if '10'<=tmp<='25' else ab=aa=creturn aclass Solution:def translateNum(self, num: int) -> int:# 动态规划递推，数字求余法 时间O(n)，空间O(1)# dp[i]= dp[i-1]+dp[i-2] if 10xi-1+xi~[10,25] else dp[i-1]b,a=1,1y=num%10while num!=0:num//=10x=num%10tmp=10*x+yc=a+b if 10<=tmp<=25 else aa,b=c,ay=xreturn a
47. 礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
class Solution:
def maxValue(self, grid: List[List[int]]) -> int:
# 对于从左上到右下的动态规划，需要对第一行和第一列进行初始化
m, n = len(grid), len(grid[0])
for j in range(1, n): # 初始化第一行
grid[0][j] += grid[0][j - 1]
for i in range(1, m): # 初始化第一列
grid[i][0] += grid[i - 1][0]
for i in range(1, m):
for j in range(1, n):
grid[i][j] += max(grid[i][j - 1], grid[i - 1][j])
return grid[-1][-1]
48. 最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
输入: “abcabcbb” 输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# dp[j] 表示以s[j]结尾的最长不重复串的长度，设左边最近重复字符位置为s[i]
# i<0 时 s[j]左边无相同字符，此时 dp[j]=dp[j-1]+1
# dp[j-1]<j-i 说明 s[i] 在dp[j-1]范围之外 故 dp[j]=dp[j-1]+1
# 若dp[j-1]>=j-i 则dp[j]=j-i
ans,cur=0,0
dic=dict()
for j,v in enumerate(s):
i=dic.get(v,-1)
dic[v]=j # cur能不能加1 取决于i的位置有没有向前移动
cur=cur+1 if cur< j-i else j-i # dp[j - 1] -> dp[j]
ans=max(ans,cur) # max(dp[j - 1], dp[j])
return ans
62. 圆圈中最后剩下的数字
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
# “约瑟夫环” 问题
# dp[i]=(dp[i−1]+m)%i
# 最后一个数所在的下标一定为0，可以递推得到上一轮所在的下标
# 最后一轮剩下一个人，那么上一轮剩下2个人，故从2开始递推
x=0
for i in range(2,n+1):
x=(x+m)%i
return x
63. 股票的最大利润
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
class Solution:
def maxProfit(self, prices: List[int]) -> int:
ans,minP=0,inf
for v in prices:
minP=min(v,minP)
ans=max(ans,v-minP)
return ans
66. 构建乘积数组
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
思路：打表，将结果分为上三角和下三角分别计算
| B[0] | 1 | A[1] | A[2] | A[3] |
|---|---|---|---|---|
| B[1] | A[0] | 1 | A[2] | A[3] |
| B[2] | A[0] | A[1] | 1 | A[3] |
| B[3] | A[0] | A[1] | A[2] | 1 |
class Solution:
def constructArr(self, a: List[int]) -> List[int]:
b=[1]*len(a)
# 先求下三角乘积
for i in range(1,len(a)):
b[i]=b[i-1]*a[i-1]
# 再求上三角乘积
tmp=1
for i in range(len(a)-2,-1,-1):
tmp*=a[i+1] # 上三角
b[i]*=tmp # 合并
return b
60. n个骰子的点数
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
class Solution:
def dicesProbability(self, n: int) -> List[float]:
# n个筛子点数范围[n,6n],总数为5n+1
# 已知n-1个色子的解f(n-1),新增一枚色子，n个色子点数和x的概率为f(n,x)
# f(n,x)= sum(i=1:6){ f(n-1,x-i) * 1/6 }
dp=[1/6 for _ in range(6)]
for i in range(2,n+1):
tmp=[0.0]*(5*i+1)
for j in range(len(dp)):
for k in range(6):
tmp[j+k]+=dp[j]/6
dp=tmp
return dp
查找算法
03. 数组中重复的数字
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3
class Solution:
"""
思路1. 建立哈希进行遍历，返回第一个重复的，时间O(n),空间O(n),
思路2. 考虑所有数据都在0~n-1这个条件，即索引和值应该是一一对应的，现在值出现了重复，
因此可以考虑通过交换，使得元素和索引一一对应(nums[i]=i),最后不匹配的即为重复值
"""
def findRepeatNumber(self, nums: List[int]) -> int:
i=0
while i<len(nums):
if nums[i]==i: # 位置正确，不需要动
i+=1
continue
if nums[nums[i]]==nums[i]:# nums[i]处和索引i处元素值都为nums[i],重复
return nums[i]
# 否则交换索引i和nums[i]的值
nums[nums[i]],nums[i]=nums[i],nums[nums[i]]
# 这里不能交换顺序，因为首先将右边两个保存为元组，然后按左右顺序赋值，会先将nums[i]修改
return -1
04. 二维数组的查找
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
class Solution:
"""
有序数组，从左下角遍历即可，小于target右移，大于target上移
"""
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
if not matrix:return False
m,n=len(matrix),len(matrix[0])
i,j=0,n-1
while i<m and j>=0:
if matrix[i][j]==target:
return True
elif matrix[i][j]<target:
i+=1
else:
j-=1
return False
11. 旋转数组中的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
示例1
输入：numbers = [3,4,5,1,2] 输出：1
示例2
输入：numbers = [2,2,2,0,1] 输出：0
class Solution:
def minArray(self, numbers: [int]) -> int:
i, j = 0, len(numbers) - 1
while i < j:
m = (i + j) // 2
if numbers[m] > numbers[j]: i = m + 1
elif numbers[m] < numbers[j]: j = m
# nums[m]=nums[j]时无法判断x在[i,m]还是[m+1,j]
# 执行j-=1 缩小范围
else: j -= 1
return numbers[i]
50. 第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
输入：s = “abaccdeff” 输出：’b’
输入：s = “” 输出：’ ‘
class Solution:
'''
1. 使用有序哈希表，存储每个字符的重复状态
然后遍历，返回第一个满足条件的字符
'''
def firstUniqChar(self, s: str) -> str:
dic = collections.OrderedDict()
for c in s:
dic[c] = not c in dic
for k, v in dic.items():
if v: return k
return ' '
53.I 在排序数组中查找数字I
统计一个数字在排序数组中出现的次数
class Solution:
"""
1. 利用有序的条件，使用二分寻找左右边界
"""
def search(self, nums: List[int], target: int) -> int:
l,r=0,len(nums)-1
# 定位右边界，
while l<=r:
mid=(l+r)//2
if nums[mid]<=target:
l=mid+1
else:
r=mid-1
right=l #当退出时l=r+1，并且nums[l]在target之外，nums[r]<=target
l=0
while l<=r:
mid=(l+r)//2
if nums[mid]>=target: # 退出时 l=r+1，此时r在外，而l在内因此左边界为r
r=mid-1
else:
l=mid+1
left=r
return right-left-1
53.II 0~n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
输入: [0,1,3] 输出: 2
class Solution:
'''
1. 直接二分查找
'''
def missingNumber(self, nums: List[int]) -> int:
l,r=0,len(nums)-1
while l<=r:
mid=(r+l)//2
if nums[mid]==mid:
l=mid+1
else:
r=mid-1
return l
53. 在排序数组中查找数字I
统计一个数字在排序数组中出现的次数。
输入: nums = [5,7,7,8,8,10], target = 8 输出: 2
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums: return 0
i,j=0,len(nums)-1
# 寻找右边界
while i<=j:# 跳出时i=j+1，而最后一定是i=mid+1,故跳出循环时，j为target最后一个位置
mid=(j+i)>>1
if nums[mid]<=target: i=mid+1
else:j=mid-1
# 在更新有边界之前，需要判断是否存在target，若不存在直接返回
if j>=0 and nums[j]!=target: return 0
right=i # 右边界
i,j=0,len(nums)-1
# 寻找左边界
while i<=j: # 跳出循环时，j=mid-1，j为边界外的第一个元素，i为第一个target
mid=(i+j)>>1
if nums[mid]>=target: j=mid-1
else: i=mid+1
left=j # 左边界
return right-left-1
57. 和为s的两个数字
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
输入：nums = [2,7,11,15], target = 9 输出：[2,7] 或者 [7,2]
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
i,j=0,len(nums)-1
while i<j:
ss=nums[i]+nums[j]
if ss>target: j-=1
elif ss<target: i+=1
else: return [nums[i],nums[j]]
return []
57. II 和为s的连续正数序列
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
class Solution:
def findContinuousSequence(self, target: int) -> List[List[int]]:
i,j,s,res=1,2,3,[]
while i<j:
if s==target:
res.append(list(range(i,j+1)))
if s>=target: # s>=target，缩小范围，移动左指针
s-=i
i+=1
else: # s<target 移动右指针，缩小范围
j+=1
s+=j
return res
58. 反转单词顺序I
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。
class Solution:
def reverseWords(self, s: str) -> str:
ss=s.split()
return ' '.join(ss[::-1])
位运算
15. 二进制中1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）
class Solution:
def hammingWeight(self, n: int) -> int:
count=0
while n:
n=n&(n-1) # 每执行一次都会消除最低位的1
count+=1
return count
56.I 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
# 思路：分组异或
# 1. 先对数组整体异或得到x^y的值
# 2. 然后寻找结果中为1的位，表示x与y不同的位的位置
# 3. 然后对数组中每个元素根据该位进行异或运算。
res=0
for v in nums: # 得到所有元素的异或值
res^=v
div=1
while div&res==0:# 寻找异或结果中为1的位
div<<=1
a,b=0,0
for v in nums:
if div&v: a^=v
else: b^=v
return [a,b]
56.II 数组中数字出现的次数II
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
# 方法一： 统计所有数字中二进制位的个数，
# 然后计算结果，将每个次数都对3取余
class Solution {
public:
int singleNumber(vector<int>& nums) {
vector<int> count(32);
for(int v:nums){
for(int i=0;i<count.size();i++){
count[i]+=v&1;
v>>=1;
}
}
int res=0;
for(int i=31;i>=0;i--){
res<<=1;
res|=count[i]%3;
}
return res;
}
};
# 方法二： 有限状态机
class Solution {
public:
int singleNumber(vector<int>& nums) {
int one=0,two=0;
for(int v:nums){
one=one^v & ~two;
two=two^v & ~one;
}
return one;
}
};
65. 不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
a, b 均可能是负数或 0 结果不会溢出 32 位整数
class Solution {
# 将非进位和进位和相加得到结果
public:
int add(int a, int b) {
if(a==0 || b==0) return a==0?b:a;
return add(a^b,(uint)(a&b)<<1);
}
};
搜索与回溯算法
12. 矩阵中的路径
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。
输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED” 输出：true
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def dfs(i,j,k):
if i<0 or j<0 or i>=len(board) or j>=len(board[0]) or board[i][j]!=word[k]:
return False
if k==len(word)-1: return True
board[i][j]=""
res=dfs(i+1,j,k+1) or dfs(i-1,j,k+1) or dfs(i,j-1,k+1) or dfs(i,j+1,k+1)
# 注意这里需要回退
board[i][j]=word[k]
return res
for i in range(len(board)):
for j in range(len(board[0])):
if dfs(i,j,0):return True
return False
13. 机器人的运动范围
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
class Solution:
# 思路1：BFS搜索
def movingCount(self, m: int, n: int, k: int) -> int:
que=collections.deque()
que.append((0,0))
s=set()
while que:
(x,y)=que.popleft()
if (x,y) not in s and 0<=x<m and 0<=y<n and self.getK(x)+self.getK(y)<=k:
s.add((x,y))
for i,j in [(x+1,y),(x,y+1)]: # 朝右或者下移动
que.append((i,j))
return len(s)
def getK(self,m):
ans=0
while m:
ans+=m%10
m//=10
return ans
38. 字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
输入：s = “abc” 输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]
class Solution:
def permutation(self, s: str) -> List[str]:
c,res=list(s),[]
def dfs(x):
nonlocal res,c
if x==len(c)-1:
res.append(''.join(c)) # 添加排列方案
return
dic=set() # 去重集合
for i in range(x,len(c)):
if c[i] in dic: continue
dic.add(c[i])
c[x],c[i]=c[i],c[x] # 将c[i]固定在x位
dfs(x+1) # 递归
c[x],c[i]=c[i],c[x] # 恢复交换
dfs(0)
return res
分治算法
16. 数值的整数次方
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
class Solution:
"""
1. 分治，递归
2. 快速幂
需要考虑n为负数时的处理
"""
def myPow(self, x: float, n: int) -> float:
if n==0:return 1
if n<0:return self.myPow(1/x,-n)
# 末尾为1 需要单独乘一次，否则直接平方
if n%2:return x*self.myPow(x,n-1)
return self.myPow(x*x,n//2)
def myPow(self, x: float, n: int) -> float:
if n<0:
x=1/x
n=-n
res=1.0
while n>0:
if n&1:
res*=x
n>>=1
x*=x
return res
07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]
class Solution:
"""
1. 利用根节点在前序和中序中的不同位置来定位左子树和右子树
"""
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
# 前序： [root, [left_tree], [right_tree]]
# 中序： [[left_tree], root, [right_tree]]
def build(pre_left,pre_right,in_left,in_right)->TreeNode:
if pre_left>pre_right:
return None
pre_root=pre_left # 先序遍历第一个节点就是根节点
in_root=index[preorder[pre_root]] # 从中序遍历中找到根节点索引
left_sub_size=in_root-in_left # 左子树节点个数
root=TreeNode(preorder[pre_root]) # 开始构建根节点
# 构造左子树
root.left=build(pre_left+1,pre_left+left_sub_size,in_left,in_root-1)
# 构造右子树
root.right=build(pre_left+left_sub_size+1,pre_right,in_root+1,in_right)
return root
n=len(preorder)
# 构造哈希映射，快速定位根节点
index={elem:i for i,elem in enumerate(inorder)}
return build(0,n-1,0,n-1)
双指针
39. 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
class Solution:
"""
1. 哈希表保存，然后找最大值
2. 数组排序，找中间
3. 摩尔投票法
"""
def majorityElement(self, nums: List[int]) -> int:
count=0
vote=0
for v in nums:
if count==0: # 计数为0时直接赋值
vote=v
# 遇到相等的count+1，否则减1
count+=1 if vote==v else -1
return vote
二叉树
26. 树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
if not A or not B: return False
return self.isSub(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)
def isSub(self,A,B): # 判断以A为根节点的子树是否包含B
if not B: return True
if not A or A.val!=B.val: return False
return self.isSub(A.left,B.left) and self.isSub(A.right,B.right)
27. 二叉树的镜像
请完成一个函数，输入一个二叉树，输出它的镜像
class Solution:
# 左右子节点递归互换
def mirrorTree(self, root: TreeNode) -> TreeNode:
if not root: return None
root.left,root.right=root.right,root.left
self.mirrorTree(root.left)
self.mirrorTree(root.right)
return root
28. 对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
class Solution:
# 创建一个递归函数，同时输入根节点，然后镜像判断
def isSymmetric(self, root: TreeNode) -> bool:
def recur(L,R):
if not L and not R: return True
if not L or not R or L.val!=R.val: return False
return recur(L.left,R.right) and recur(L.right,R.left)
return recur(root,root)
32. 从上到下打印二叉树
# 层序打印
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
que=collections.deque()
que.append(root)
res=[]
while que:
cur=[]
for i in range(len(que)):
node=que.popleft()
cur.append(node.val)
if node.left: que.append(node.left)
if node.right: que.append(node.right)
res.append(cur[:])
return res
# 之字形打印
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
que=collections.deque()
que.append(root)
res=[]
while que:
cur=[]
for i in range(len(que)):
node=que.popleft()
cur.append(node.val)
if node.left: que.append(node.left)
if node.right: que.append(node.right)
if len(res)&1==1:cur=cur[::-1]
res.append(cur[:])
return res
33. 二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
class Solution:
def verifyPostorder(self, postorder: [int]) -> bool:
# 后序倒序： 根，右，左，类似于线序遍历的根左右
# 对于该列表，若ri<ri+1,节点ri一定是某节点root的左子节点，
# 若ri>ri+1,节点ri一定是节点ri+1的右子节点
stack, root = [], float("+inf")
for i in range(len(postorder) - 1, -1, -1):
# 若ri>root 说明此后序遍历序列不满足二叉搜索树定义
if postorder[i] > root: return False
# 更新父节点root，当栈不为空且ri<stk.peek()时循环出栈，并将出栈节点赋给root
while(stack and postorder[i] < stack[-1]):
root = stack.pop()
stack.append(postorder[i]) # 将当前节点ri入栈
return True
68. 二叉搜索树最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or p==root or q==root:
return root
l=self.lowestCommonAncestor(root.left,p,q)
r=self.lowestCommonAncestor(root.right,p,q)
if not l: return r
if not r: return l
return root
55. II 平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
if not root: return True
return abs(self.height(root.left)-self.height(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)
def height(self,root):
if not root: return 0
return 1+max(self.height(root.left),self.height(root.right))
54. 二叉搜索树的第k大节点
给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
class Solution:
# 二叉搜索树中序遍历为升序, 左，根，右
def kthLargest(self, root: TreeNode, k: int) -> int:
cnt,ans=k,0
def dfs(root):
nonlocal cnt,ans
if not root or cnt==0:return
dfs(root.right)
# 右，根，左遍历为倒序，第k次即为结果
cnt-=1
if cnt==0:ans=root.val
dfs(root.left)
dfs(root)
return ans
36. 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
class Solution:
def treeToDoublyList(self, root: 'Node') -> 'Node':
if not root: return
pre,head=None,None # 需要记录前驱节点和头节点
def dfs(cur):
if not cur: return
nonlocal pre,head
# 中序遍历
dfs(cur.left) # 递归左子树
if pre:
pre.right=cur
cur.left=pre
else:
head=cur # 记录头节点
pre=cur # 保存前驱节点
dfs(cur.right)# 递归右子树
dfs(root)
head.left=pre # 修改头尾指向
pre.right=head
return head
37. 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
class Codec:
def serialize(self, root):
if not root: return '#,' # 空节点设为#，后面的分隔符必不可少
res=str(root.val)+','
res+=self.serialize(root.left)
res+=self.serialize(root.right)
return res
def deserialize(self, data):
data=iter(data.split(','))
def helper():
nonlocal data
val=next(data)
if val=='#': return
root=TreeNode(int(val))
root.left=helper()
root.right=helper()
return root
return helper()
34. 二叉树中和为某一值得路径
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是没有子节点的节点。
示例：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]]
class Solution:
def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
res,cur=[],[]
def dfs(root:TreeNode,target:int):
# terminator
if not root: return
# process
cur.append(root.val)
target-=root.val
if not root.left and not root.right and target==0:
res.append(cur[:])
# drill down
dfs(root.left,target)
dfs(root.right,target)
# revert
cur.pop()
dfs(root,target)
return res
排序
40. 最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
class Solution:
# 方法1：利用快速排序的特性，提前终止
def getLeastNumbers(self, nums: List[int], k: int) -> List[int]:
def quickSort(arr,low,high):
if low>=high:
return
l,r=low,high
mid=random.randint(l,r)
pivot=arr[mid]
arr[l],arr[mid]=arr[mid],arr[l]
while l<r:
while l<r and pivot<=arr[r]:
r-=1
arr[l]=arr[r]
while l<r and pivot>arr[l]:
l+=1
arr[r]=arr[l]
arr[l]=pivot
if k<l: quickSort(arr,low,l-1)
if k>l: quickSort(arr,l+1,high)
return
quickSort(nums,0,len(nums)-1)
return nums[:k]
# 方法二： 构造大顶堆( 维护较小值，将较大值弹出)
def getLeastNumbers(self, nums: List[int], k: int) -> List[int]:
if k==0: return []
hp=[-x for x in arr[:k]]
heapq.heapify(hp)
# 维护一个大顶堆，将前k个元素入堆，
# 当新来元素小于堆顶元素时，堆顶弹出，当前值入堆
for i in range(k,len(arr)):
if arr[i]<-hp[0]:
heapq.heappop(hp)
heapq.heappush(hp,-arr[i])
ans=[-x for x in hp]
return ans
51. 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
class Solution:
def reversePairs(self, nums: List[int]) -> int:
count=0
def merge(L,R):
nonlocal count
i,j=0,0
tmp=[]
while i<len(L) and j<len(R):
if L[i]<=R[j]:
tmp.append(L[i])
i+=1
else:
# 利用了归并排序的特性，在合并两个有序列表的时候，
# ！！！
count+=(len(L)-i)
tmp.append(R[j])
j+=1
tmp+=L[i:]
tmp+=R[j:]
return tmp
def mergeSort(nums:list):
if len(nums)<=1:
return nums
mid=len(nums)//2
left=mergeSort(nums[:mid])
right=mergeSort(nums[mid:])
return merge(left,right)
res=mergeSort(nums)
return count
若有收获，就点个赞吧
0 人点赞
