首页  思维导图  详情

leecode

2021-04-05 19:22:27   1  举报





AI智能生成

leecode各种算法和刷题经验总结

leecode;算法

作者其他创作

大纲/内容

动态规划

基本问题

多阶段最优化决策，每次决策依赖于当前状态，又引起状态的转移

基本思想

分治法

将待求解的问题分为若干个子问题，按顺序求解子阶段，但是与分治法不同的是每个子问题不独立

求解核心

记住已经求过的解，自底向上

核心概念

阶段

决策

限制条件

优化函数

状态

状态转移

适用情境

问题可以被递归地处理，但很多子问题答案会被重复利用

对每个子问题只计算一次，然后将计算结果保存到一个表格中，每次需要上一个子问题的解时只需要调用即可，用空间换时间

求解步骤

划分阶段

确定状态和状态变量

确定决策并写出状态转移方程

寻求边界条件

典型例子

背包问题

相当于计算一个矩阵，一列代表各个物品，另一个代表包的容量（从1到max）一个一个增加物品，每次判断一下，如果装不下该物品就沿用上一行的最大价值，如果装得下就调整价值，可能用到之前的子问题

d[i][j] = max(d[i-1][j],d[i-1][j-weight[i]]+c[i])

走台阶问题

逆序分析，因为结果固定（登上了n层楼梯）

边界：F(1)=1,F(2)=2

最优子结构：每个阶段的最优状态可以从之前某个阶段的某个或者某些状态直接得到

状态转移函数：F(n)=F(n-1)+F(n-2)（类似于斐波那契数列）

走台阶（每次2的幂次）

dp[i]表示登上台阶i的可能数

def ac(n):     target = [0 for i in range(n+1)]     target[0]=1     for i in range(n):         if i==0 or i==1:              target[i+1]=i+1         else:               j=0              tmp=0              while 2**j<=i+1:                   tmp+=target[i+1-2**j]                   j+=1              target[i+1]=tmp       return target[n]

外面套的双层遍历

初始化

target[0]=1

target = [0 for i in range(n+1)]

矿工挖矿问题

类似于背包问题，资源有限要求价值最大

逆序分析，结果固定（10个人挖第5座金矿能获得最多的黄金数量，最优方案逆推的话是分为挖第5个矿和不挖第五个矿讨论的）

假如有n个矿，拥有的工人数量w，黄金数量G[n]，需要的矿工数P[n]

边界条件：当n=1 w>p[0]，F(n,w）=G[0] 当n=1, w

状态转移方程： F(n,w)=F(n-1,w) (n>1,w<p[n-1])工人数不够　　="" f(n,w)="max(F(n-1,w),F(n-1,w-P[n-1])+G[n-1])" (n="">1,w>p[n-1]) </p[n-1])工人数不够>

F(n,w)=max(F(n-1,w),F(n-1,w-P[n-1])+G[n-1]) (n>1,w>p[n-1])

最大子序和问题

定义一个列表存储子问题最优解

I表示数组第i个位置的元素

D[i]表示从0到i闭区间内，所有包含第i个元素的连续子数组中，总和最大的值

D[i] = max(nums[i], nums[i]+d[i-1])

乘积最大子序列

首先要定义一个空数据（列表套列表）

因为乘积涉及到正负号问题，负号可能会使最小值和最大值互换，所以都要存起来

当符号是负的，就把max和min的值换位置

ma[i] = max(mi[i-1]*nums[i],nums[i]) mi[i] = min(ma[i-1]*nums[i],nums[i])

ma[i] = max(ma[i-1]*nums[i],nums[i]) mi[i] = min(mi[i-1]*nums[i],nums[i])

小偷问题

d[i]=max(d[i-1],d[i-2]+nums[i])

买卖股票最佳时间

动态规划，设置一个变量记录买入的最小金额

假如计划在第 i 天卖出股票，那么最大利润的差值一定是在[0, i-1] 之间选最低点买入；所以遍历数组，依次求每个卖出时机的的最大差值，再从中取最大值。

d[i] = max( d[i-1], num[i]-min)

还有可以买卖多次的会用到贪心算法

若可以连续交易

for i in range(1,len(prices)):     if prices[i]>prices[i-1]:         maxprice+=prices[i]-prices[i-1]

主要找波峰波谷位置 

从图形上看

花费最小力气爬楼梯

Dp[i] = min(dp[i-1]+cost[i],dp[i-2]+cost[i]))

回文子串

最长回文子串

用一个二位数组来记录从l到r的字符串是否为回文串

若s[l,r]是回文串，那么s[l+1,r-1]一定是回文串

状态转移

record[i][j] = (s[i]==s[j] and (j-i<=2 or record[i+1][j-1]))

如果子串S i j 是回文子串

双层嵌套循环外层用j, 内层循环要用（0，j+1）保证以j结尾的前面字符串都判断完成了

动态规划中额外数组的含义非常重要

初始化一个二位数组都为fa'l'se

非空条件判断

遍历方式

dp = [[False for _ in range(len(s))] for _ in range(len(s))]for j in range(len(s)):     for i in range(0,j+1):         dp[i][j] = (s[i]==s[j]) and (j-i<=2 or dp[i+1][j-1])

dp = [[True for _ in range(len(s))] for _ in range(len(s))] for j in range(len(s)):     for i in range(0,j):          dp[i][j] = (s[i]==s[j]) and dp[i+1][j-1]

for i in range(len(s)-1,-1,-1):     for j in range(i+1,len(s)):        dp[i][j] = (s[i]==s[j]) and dp[i+1][j-1]

初始化也是True

非动态规划解法

双指针

left right

都从某个i开始向两边移动，判断两个字符是否相同

完全平方数

dp[i]表示组成完全平方数i的最少个数

def numSquares(self, n: int) -> int:     dp=[i for i in range(n+1)]     dp[0]=0     for i in range(2,n//2+1):         for j in range(i*i,n+1):            dp[j]=min(dp[j],dp[j-i*i]+1) return dp[n]

外层循环遍历所有可能选项，内侧循环修改不同的目标平方数

最长上升子序列

01矩阵

从四个方向找最小值

并查集

概念

树形的数据结构，用于处理一些不相交的集合的合并和查询问题

基本思路

为每个集合选定一个固定的元素成为代表，表示整个集合，Find(x)返回x所属集合的代表，Union使用两个集合的代表作为参数

步骤

建立新集合，集合代表唯一，为元素本身

返回x所在集合的节点---优化：查找路径上的每个节点都直接直接向根节点

将包含x,y的动态集合合并为一个新的集合----让较小秩的集合指向较大秩的集合

HMM

含义

有一个隐藏的马尔可夫过程和一个与这个隐马尔科夫过程概率相关的可以直接观察到的状态集合；用来描述一个含有隐含未知参数的马尔可夫过程

马尔科夫链其实是指隐含状态链

可见状态之间没有转换概率，但是隐含状态和可见状态之间会有一个输出概率

与HMM模型相关的算法

已知色子有几种（隐含状态数量），每种是什么（转移概率），根据掷色子结果（可见状态链），求每次掷出来的都是哪种骰子（隐含状态链）

Viterbi Algo，维特比算法

预测问题

已知模型和观测序列，求最可能的状态序列

还是知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率），根据掷骰子掷出的结果（可见状态链），我想知道掷出这个结果的概率

Forword Algorithm，向前算法，或者 Backward Algorithm，向后算法

概率计算问题

已知模型和观测序列，求出现的概率

知道骰子有几种（隐含状态数量），不知道每种骰子是什么（转换概率），观测到很多次掷骰子的结果（可见状态链），我想反推出每种骰子是什么（转换概率）

Baum-Welch Algo，鲍姆-韦尔奇算法

学习问题

已知观测序列，求模型参数

二分查找

效率较高的查找方法

必须先排序再查找

对数时间复杂度

o(logn)

非空的判断

有三个主要变量，循环外初始化，循环内变化

left

right=len-1

while循环

条件

left != right

重新计算middle

middle= int((left+right)/2)

每次循环都要重新计算

循环体内判断num[middle]和target的大小

三种模板

while条件有等号的一定不能在赋值left，right时等于mid-1

(left <= right)/(left < right)/(left + 1 < right)

一般思路

预处理 —— 如果集合未排序，则进行排序。 二分查找 —— 使用循环或递归在每次比较后将查找空间划分为两半。 后处理 —— 在剩余空间中确定可行的候选者。

查找浮点数

def find_num(array,x):     if not array:         return None     r = len(array)-1     l = 0     while l<r-1: mid="(l+r)//2" if="" array[mid]=""> < r-1:         if array[mid]>x: r = mid         else: l = mid+1     if abs(array[l]-x) > abs(array[r]-x):         return array[r]     else:         return array[l] if __name__=='__main___':     array = [1.0,2.0,3.0,5.0]     x = 2.56 target = find_num(array, x) print(target)</r-1:>

实现开根号

两数之和 II - 输入有序数组

判断和与目标值大小，移动指针

寻找旋转排序数组中的最小值

有两种情况，可以判断

先判断有无断点，再比较mid和0移动指针

寻找旋转排序数组中的最小值 II

有重复数字

mid和right的比较并移动指针

寻找比目标字母大的最小字母

right=mid

类似于第一个错误版本

搜索旋转排序数组

找到旋转的下标

在选中的数组区域中再次使用二分查找

回溯法

含义

走不通就退回再走的技术

类似于枚举的深度优先搜索

选优搜索法

Brute-Force蛮力搜索穷举的改进

基本思想

从一条路往前走，能进则进，不能进则退回来换一条路再走

从根节点出发深度搜索，探索到某一节点时要判断该节点是否包含问题的解，不包含逐层向祖先节点回溯

回溯法求问题的所有解要回溯到根

重点

递归函数

递归算法的出口

放在递归函数的第一行

千万不能放在for或者while循环中

递归函数的参数

这个参数是随着每次的递归操作而发生改变的

不要破坏当前值

才能如果当前操作行不通，回溯到上一步

结果一定要有一个全局参数来保存，只用来保存每次递归成功时的结果

final_queens = []

递归函数的处理

如果当前递归过程的处理参数符合要求，则执行相关赋值或其他操作，然后转入下一次递归，如果下一次递归不能找到出口，就把之前相关赋值或其他操作重置为初始状态

check(int k,int j)

能使得递归进行的约束条件

递归函数就是自己调用自己的函数

经典例题

有限制条件的

八皇后

主函数

记录可行的方式，定义一个空列表

res = []

if n==0: return res

记录不可行的位置

用set

不可行列

col=set()

不可行主对角线

master=set()

行列值相加固定

不可行负对角线

slave=set()

行列值相减固定

存储queen在的列

stack=[]

调用递归函数

self.__backtracking(nums, 0, n, col, master, slave, stack, res)

返回结果

递归函数

出口 

if row == n:     board = self.__convert2board(stack, n)     res.append(board)     return

def __convert2board(self, stack, n): return ["." * stack[i] + "Q" + "." * (n - stack[i] - 1) for i in range(n)]

参数

列数、当前所在行、皇后个数、列状态、主对角线状态、负对角线状态、皇后摆放位置、结果

递归要用的上一次的状态+递归轮数（会变）

循环体

if i not in col and row + i not in master and row - i not in slave:     stack.append(nums[i])     col.add(i)     master.add(row + i)     slave.add(row - i)     self.__backtracking(nums, row + 1, n, col, master, slave, stack, res)     slave.remove(row - i)     master.remove(row + i)     col.remove(i)     stack.pop()

逐行，逐列搜索

若都不满足条件则回溯

子主题

条件判断函数

if i not in col and row + i not in master and row - i not in slave:

合理的括号组合

主函数

记录可行组合

res = [] if n == 0: return res

res = [] # if n==0: # return res # position = [] # self.back(0,n,position,res)

调用递归函数

self.back(1,n,res,"(")

注意传入参数设置，一定要这样

返回结果

return res

递归函数

出口

if len(cur)==2*n: res.append(cur)

if cur == 2*n: # res.append(self.convert(position))

def convert(self,position): # pat = '' # for i in position: # if i == 0: # pat = pat+'(' # else: # pat = pat+')'

循环体

if left<n:   self.back(left+1,n,res,cur+"(")

if len(cur)<2*left:    self.back(left,n,res,cur+")")

右括号等于左括号

for i in [0,1]: # position.append(i) # if position.count(0)<=n and position.count(1)<=n and position[:cur+1].count(0)>=position[:cur+1].count(1): #     self.back(cur+1,n,position,res) # position.pop()

可以看到递归函数中的参数设置和算法效率有重要关系

递归条件

特殊

有两个

只记左括号

数独

背包问题

无限制条件的

手机键盘上字母的组合

主函数

记录可行组合

res = [] if len(digits)==0: return res

定义需要记录状态用的列表

无

调用递归函数

self.back('',digits,res)

返回结果

return res

递归函数

出口

_map= {'2':"abc",'3':"def",'4':"ghi",'5':"jkl",'6':"mno",'7':'pqrs','8':"tuv",'9':"wxyz"} if len(next_digit)==0:     res.append(combine)

深度优先搜索

参数

递归要用的字符串、下一个数字、记录结果的列表

循环体

for s in _map[next_digit[0]]: self.back(combine+s,next_digit[1:],res)

类型

找出所有可能的组合数

找出所有子集

递归和分治函数

在函数内部可以调用自己

包括出口条件判断和递归体的处理

不是所有递归里面都必须写成循环体的形式，不要被8皇后问题蒙蔽了

道理上讲，所有的递归都可以写成循环的形式，但是递归的逻辑更加清晰

分治用递归实现

如果原问题可以分解成若干个与原问题结构相同但规模较小的子问题时，往往可以用递归的方法解决

能用循环的不要用递归

回溯也可以用递归实现

动态规划是递归的升级版本

例子

汉诺塔问题

n = 1 时，直接把盘子从 A 移到 C； n > 1 时， 先把上面 n - 1 个盘子从 A 移到 B（子问题，递归）； 再将最大的盘子从 A 移到 C； 再将 B 上 n - 1 个盘子从 B 移到 C（子问题，递归）

def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:     n= len(A)     self.move(n,A,B,C) def move(self,n,A,B,C):     if n == 1:         C.append(A[-1])         A.pop()         return     else:         self.move(n-1,A,C,B)         C.append(A[-1])         A.pop()         self.move(n-1,B,A,C)

Sliding Window

原理

通过使用特定大小的子列表，在遍历完整列表的同时进行特定的操作，以达到降低嵌套深度

一般通过双指针实现

确定何时移动慢指针，移动到什么位置是关键

快指针要记得每次循环都要+1

排序算法

冒泡排序

概念

冒泡排序就占有优势：它可以在发现列表已排好时立刻结束

在找到最终位置前需要不断交换

代码

获取列表长度

n = len(alist)

双层循环

外层循环

排第几个位置

for i in range(n-1, 0, -1):

设置变量代表是否交换

exchange = False

内层循环

两两逐个比较

循环条件

for j in range(0, i):

交换位置

if alist[j] > alist[j+1]: alist[j], alist[j+1] = alist[j+1], alist[j] exchange = True

确定排序过程中有没有交换

if not exchange: break

没有交换代表已排好顺序

选择排序

概念

提高了冒泡排序的性能

快速排序

概念

分治算法

每次选择一个元素并且将整个数组以那个元素分为两部分

每部分分别进行快排

在原数组上直接进行操作

选择元素

随机选择

选择第一个元素

选择最后一个元素

核心

分区

传入一个数组和一个选定的元素，把所有小于那个元素的其他元素放在左边，大于的放在右边

复杂度

最好

nlogn

最坏

o(n^2）

稳定性

不稳定

代码

主函数（递归函数）__quickSort(alist, l, r)

出口

数组只有一个数时返回（左指针=右指针）

if l >= r: return

分区

p = partition(alist, l, r)

调用本递归函数（两部分都快排）

__quickSort(alist, l, p-1) __quickSort(alist, p+1, r)

参数

alist l r

双指针

交换位置

循环判断条件一般以指针<=len()-1

for j in range(i, 0, -1): 效率低

分区partition(alist, l, r)

1. 选择传入数组中的第一个数

v = alist[l]

2. 设置两个变量

记录比指定值小的数的位置

j = l

遍历数组

i = l + 1

3. 循环比较

while i <= r:     if alist[i] <= v:        alist[j+1],alist[i] = alist[i],alist[j+1]         j += 1 #记录比v小的位置     i += 1 #遍历数组

4. 调整指定值的位置

alist[l], alist[j] = alist[j], alist[l]

5. 返回下标j

alist[l...r]中寻找j,使得alist[l...j] <= alist[l], alist[j+1...r] >alist[l]

归并排序

概念

分治原理

归并排序中间劈一刀，数组分两半，两边排好序，最后把左右两个合并。就是先局部有序，再整体有序。

在原数组上操作

把两个排序好了的列表结合在一起组合成一个单以的有序新列表

核心

合并函数

合并有序数列alist[start....mid] 和 alist[mid+1...end]，使之成为有序数列

在原数组操作

需要临时复制alist[start:end+1]

稳定性

稳定

代码

主函数(递归函数）__mergeSort(alist, start, mid)

出口

if start >= end: return

取mid 

mid = (start + end) // 2

调用本递归函数（两部分都做归并排序）

__mergeSort(alist, start, mid) __mergeSort(alist, mid + 1, end)

传入参数

alist

start

end

事件复杂度

o(nlogn)

合并函数merge(alist, start, mid, end)

参数设置

复制传入的一段list

blist=alist[start:end+1]

左侧指针

l=start

右侧指针

k=mid+1

alist中相应位置

pos=start

循环遍历alist中相应位置

条件

while pos<=end:

判断情况

if l>mid:  alist[pos]=blist[k-start] k+=1

elif (k > end):  alist[pos] = blist[l-start] l += 1

elif blist[l-start]<=blist[k-start]:   alist[pos]=blist[l-start] l+=1

else: alist[pos] = blist[k-start]  k += 1

alist中位置移动

pos+=1

插入排序

概念

总是保持一个位置考前的已排好的子表，然后每一个新的数据项被“插入”到前面的子表中，排好的子表增加一项

在归并排序或者快速排序中，当列表元素少于15个，一般会采用插入排序

稳定性

稳定

代码insertionSort(alist)

外层循环

for i in range(1,len(alist))

待比较的值

currentvalue=alist[i]

遍历所有已排好的项

position=i

要插入currentvalue的位置

while alist[position-1]>currentvalue and position>0:     alist[position]=alist[position-1]     position=position-1 alist[position]=currentvalue

return alist

bitedance专题

字符串

无重复字符的最长子串

滑动窗口算法

一个字典记录出现过的字符

一个头指针0

一个当前指针0

最大长度max初始化为0

编写一个函数查找字符串数组中的最长公共前缀

嵌套循环

选一个最短的开始作为外层循环

分别判断每个字符串中的前缀是否相同

字符串的排列是否是另一个目标字符串的子集

滑动窗口

字符串相乘

不许转成数字

进位问题需要记录下来

可以转为用一个数字每位✖另一个数字（需要记录进位）

保存 num2 第i位数字与 num1 相乘的结果

位数越高需要末尾加0

简化路径

用到栈的思想

主要的思路还是跟提取字符串中的单词差不多，用到了栈的思想。首先对path进行处理，提取出有用的词，主要就是用’/‘分割字符串，连续的’/'忽略，然后对提取出的词进行处理，如果是.则不做处理，如果是..则出栈一个字符，最后将剩下的词处理成字符串返回就行了

复原IP地址

回溯法

findIp(s, f + i, idx + 1, ip + to_string(num) + ".", res)

s字符串 f记录已经分配好的总长度  idx记录段数（递归出口条件） res记录最终结果

递归出口和递归体

递归体中也有一个循环，每次切1，2，3种可能

数组与排序

三数之和

先排序再使用对撞指针

最大岛屿面积

递归+深度优先搜索

深度搜索每一个值为1的点，然后找到面积最大的一个，记得要把每一个已经搜索过的点置零，避免重复搜索以减少计算量

递归里面判断下标限制和是否为1，符合条件就返回num，不符合返回0

搜索旋转数组

二分搜索法的关键在于获得了中间数后，判断下面要搜索左半段还是右半段

nums[mid] < nums[0]

target 和nums[0]

最长且连续的的递增序列

设置一个max保存长度，一个头指针和一个当前指针遍历

o(n)复杂度

数组中第k大元素

最大堆排序

维护一个元素个数为k的最大堆, 将所有数字放入到最大堆中, 全部放完之后, 最大堆中最小的那个元素就是第k个最大的元素

任意一种O(nlogn)算法对数组进行降序排序, 取下标为k - 1的数组元素即可

快速排序思想, 使用三路快排, 每次都将数组分割成三部分, 每次只需要在其中一部分继续寻找, 时间复杂度O(logn)

最长连续序列的长度

使用一个辅助变量，记录序列长度

螺旋矩阵

先确定环数max(m,n)/2

再双层嵌套遍历

有up,down,left,right四个变量初始为0,m-1,1,n-1 然后作为遍历的限制条件控制方向

第k个排列

找规律

以1开头的有(n-1)!个，和k比较

1，2开头的有（n-2)!个

朋友圈

查并集

设置一个额外的字典记录每个人所属类别，每次先查找该类别所有人，再把她们的类别改成一样的

合并重叠区间

将所有区间的开始值和结束值都排好序，这样在合并区间的时候会更简单一些，这也是区间问题常用的套路

是否存在一个区间的结束值大于一个区间开始值

先按区间开始值排序

然后用一个RES记录最终结果，用最后一个区间的end与下一个的start和end比较

o(nlogn)

链表与树

合并两个有序链表

需要四个指针

最后返回+从头遍历加载+两个链表遍历

设计一个链表

设计节点结构和链表结构

反转链表

维护三个变量指针

法2：一种解决方案是按原始顺序迭代结点，并将它们逐个移动到列表的头部

两链表相加

维护carry进位变量

re = ListNode(0) r = re carry = 0

while(l1 or l2)

排序链表

借助列表排序再创建

空间复杂度o(n)

归并排序

sortlist(head)

get_mid(head)

用快慢指针

每次慢指针走一步快指针走两步

移除链表元素

哨兵节点

伪头节点

当要删除的一个或多个节点位于链表的头部时，事情会变得复杂。

prev cur双指针

使用cur遍历 

旋转链表

思想同下一个题，以k的距离同时走两个指针

注意k旋转步数大于size的情况，要取余数

删除链表的倒数第N个节点

一次遍历+两个指针

以n的距离走

环形链表找到环尾连接的节点

先判断有无环

快慢指针速度2倍走看是否相遇

有环则将一个节点放在开始位置，一个放在快慢指针相遇位置，一样速度的走，知道再次相遇

需要四个指针

俄罗斯套娃

排序+动态规划

算法面试

字符串

验证回文串

字符串的内置函数(预处理）+双指针

单词拆分

宽度优先搜索

一个表示位置的数组+一个队列

当end==len(s)返回true

时间复杂度：O(n^2)  。求出 dp 数组需要两重循环。 空间复杂度：O(n)。dp 数组的长度是 n+1

动态规划

双层循环

df=[0]*(len(s)+1) df[0]=True for i in range(len(s)+1):     for j in range(i):         if df[j] and s[j:i] in wordDict:             df[i]=True     break return df[len(s)]

额外数组

数据结构 Trie（前缀树）及其最常见的操作

有效的字母异位词

使用哈希表

一个用来增加计数，一个用来减少计数，看最后是否为0

o(n) o(1)

可以先用计数器表计算 ss，然后用 tt 减少计数器表中的每个字母的计数器。如果在任何时候计数器低于零，我们知道 tt 包含一个不在 ss 中的额外字母，并立即返回 FALSE。

分别排序两个数组在比较

时间复杂度o(nlogn) 空间复杂度取决于排序算法

反转字符串

双指针

字符串中的第一个唯一字符

额外字典+两次遍历

数组

求众数

用一个字典维护次数

存在重复元素

用一个字典维护次数

或者直接比较len(list(set(alist)))

两个数组的交集 II

用一个字典维护次数

遍历另一个数组用来比较

o(n+m) o(m)

排序+双指针（三指针）

o(mlogm+nlogn) o(1)

递增的三元子序列

找到比small和mid都大的数即存在

除自身以外数组的乘积

不能用除法

左右数组的乘积

o(n) o(1)

堆栈与队列

最小栈

两个列表

在push和pop时注意检查是否是最小的那个数

“以空间换时间”，使用辅助栈是常见的做法

出栈时，最小值出栈才同步；入栈时，最小值入栈才同步。

注意栈是否为空的判断

数组中的第K个最大元素

heapq.nlargest(k, nums)[-1]

小顶堆

基于我们建好的小根堆，可以将需要筛选的元素依次与堆顶元素进行比较，若比堆顶大，则置换堆顶，然后对堆进行调整，我们可以得到序列中前N条最大的记录

排序取第k个

数据流中的第K大元素

heapq.heappushpop(self.heap,val)

堆

heapq.heapify(heapq.nlargest(k，list))

有序矩阵中第K小的元素

heapq.nsmallest(k,lis)

得到一个递增序列

排序与检索

在排序数组中查找元素的第一个和最后一个位置

def extreme_insertion_index(self, nums, target, left):      lo = 0      hi = len(nums)      while lo < hi:          mid = (lo + hi) // 2          if nums[mid] > target or (left and target == nums[mid]):                 hi = mid          else:                 lo = mid+1      return lo def searchRange(self, nums, target):      left_idx = self.extreme_insertion_index(nums, target, True)      if left_idx == len(nums) or nums[left_idx] != target:            return [-1, -1]      return [left_idx, self.extreme_insertion_index(nums, target, False)-1]

引入参数left 如果 left 为 true ，那么我们递归查询左区间，否则递归右区间

寻找峰值

二分法

创新判断条件为比较i与i+1位置

寻找重复数

先排序再遍历比较i i+1

最大数

自定义排序+初始化

寻找比目标字母大的最小字母

二分查找+先判断字符数组里面的字符是否都小于target

循环条件留l<r-1

搜索二维矩阵

可以把二维矩阵看作一个长度为m*n的有序数组，在整个数组上进行二分查找

需要注意的是row,col下标的转换dp[mid//col][mid%col]

<h4 data-cypress="QuestionTitle" class="css-10c1h40-Title eugt34i1" style="box-sizing: border-box; color: rgb(38, 38, 38); font-weight: 500; padding: 0px; line-height: 16px; font-family: -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, "Helvetica Neue", Arial, "Noto Sans", sans-serif, "Apple Color Emoji", "Segoe UI Emoji", "Segoe UI Symbol", "Noto Color Emoji"; font-size: 14px;"><a href="https://leetcode-cn.com/problems/search-insert-position/" style="box-sizing: border-box; color: rgba(var(--grey-8-rgb),1); background-color: transparent; outline: none; transition: color 0.3s ease 0s; touch-action: manipulation; overflow: hidden; text-overflow: ellipsis; white-space: pre;">搜索插入位置</a></h4>

标准二分法

def searchInsert(self, nums: List[int], target: int) -> int:     left = 0     right = len(nums)-1     while left<=right:         mid = (left+right)//2         if nums[mid]>=target:             right = mid-1         else:              left = mid+1 return left

动态规划

至少有K个重复字符的最长子串

递归法

用出现次数最少的字符分割字符串，递归调用，当该字符出现次数多于k返回len

最长连续序列

遍历列表，如果这个数的小一个数在列表里面，转下一个

遍历一次，如果满足该数是最小数才继续看下一个数在不在列表里

用一个变量保存maxlen

数组和字符串

说起数组就要想到：双指针/额外数组记录 (考虑需不需要排序）

寻找数组中心索引

一般相加为定值的条件的要记得转换成减法的等式判断条件

至少是其他数字两倍的最大数：if all( max>x*2 for x in nums if x!=m)

加1

通过int和str之间的转换求解 .join()

for i in range(len(digits)-1,-1,-1) 倒序遍历列表一定要记住这个range里面的规则！！！！然后注意空列表和类似[9]的情况，当遍历到列表第一个值 一定要判断一下还有没有进位（dividee/modee)

最长公共前缀 o(kn) 正常遍历

反转字符串 [::-1] 列表字典字符串的基本方法一定要掌握！！！！！

数组和字符串的双指针技巧！！！

从两端向中间迭代数组。 一个指针从始端开始，而另一个指针从末端开始。这种技巧经常在排序数组中使用

同时有一个慢指针和一个快指针。 解决这类问题的关键是确定两个指针的移动策略。有时可能需要在使用双指针技巧之前对数组进行排序，也可能需要运用贪心想法来决定你的运动策略

给定一个数组和一个值，原地删除该值的所有实例并返回新的长度

相当于使用了两个指针，一个用于原始数组的迭代，另一个总是指向新数组的最后一个位置 使用两个指针，一个快指针 i 和一个慢指针 k ，i 每次移动一步，而 k 只在添加新的被需要的值时才移动一步

给定一个二进制数组，计算其中最大连续1的个数

双指针，滑动窗口

长度最小子数组

滑动窗口，借助total额外变量

旋转数组

原本数组里下标为 i 的我们把它放到 (i+k)\%数组长度的位置

三次反转即可得到答案

反转分割点k%len

因为如果旋转的单位是长度的整数倍相当于没有旋转

我自己没有想到k可以比len大

旋转矩阵

使用额外数组

n=len(matrix) m=[[0]*n for i in range(n)] for i in range(n):     for j in range(n):         m[j][n-1-i] = matrix[i][j] matrix[:]=m return

不使用额外数组，寻找下标之间的规律

n=len(matrix) for i in range(n//2):     for j in range(n):         matrix[i][j],matrix[n-1-i][j]= matrix[n-1-i][j],matrix[i][j] for i in range(n):      for j in range(i+1,n):          matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j] return

先翻转再按照对角线翻转

删除排序数组中的重复项

双指针

一个记录所有不重复的值

另一个遍历数组

寻找不重复的数

难点在于指针移动策略的设计

不要为了用双指针而用，要灵活

排序数组其实只要比较相邻两个数就好了啊

一个用来遍历所有，另一个用i-1表示就好啦

倒序遍历列表，两个相邻的数相同就pop

问题关键是正向遍历的话列表长度随时在变不好写

i=1 count = 1 while i<len(nums):     if nums[i] == nums[i-1]:         count+=1     if count>2:          nums.pop(i)          i-=1    else:          count=1     i+=1

移动0

先找到第一个为0 的位置设置为left

注意没有0的情况

遍历数组，遇到不是0 的数就和left交换

杨辉三角

每次都在列表位置0插入一个0

二维数组查找

int column = lie -1; int row =0; while(row<hang &&column>=0){ int value = array[row][column]; if(target>value){ row++; }else if(value>target){ column--; }else{ found = true; break; }

从左下方开始小了往右走，大了往上走

哈希表和哈希映射

设计键

字母异位词分组

以排序数组为key

分组使用哈希表时要确定好key是什么

以计数数组为value

二叉树

搜索与排序

二叉树的最大深度

如何计算深度，每次都返回左右子树中比较大的深度

if not root:     return 0 lheight=self.maxDepth(root.left) rheight=self.maxDepth(root.right) return max(lheight,rheight)+1

二叉树最大路径和

深度优先遍历，分别计算左右增益，计算不再向上的增益，比较得到最大和

def maxPathSum(self, root: TreeNode) -> int:     max_sum = [float('-inf')]     self.max_gain(root,max_sum)     return max_sum[0] def max_gain(self,node,max_sum):     if not node:         return 0     left_gain=max(self.max_gain(node.left,max_sum),0)     right_gain=max(self.max_gain(node.right,max_sum),0)     price_newpath=node.val+left_gain+right_gain     max_sum[0]=max(max_sum[0],price_newpath)     return node.val+max(left_gain,right_gain)

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

深度优先遍历+回溯算法

每次判断是否为该值，每轮左右节点判断完就pop

def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:      res=[]      ans=[]      self.recr(root,res,ans,sum)      return ans def recr(self,root,res,ans,total):     if root:         total-=root.val         res.append(root.val)         if total==0 and not root.left and not root.right:             ans.append(res.copy())         self.recr(root.left,res,ans,total)         self.recr(root.right,res,ans,total)         res.pop()

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

递归方法

退出条件是root值介于两个待找点之间

class Solution:     def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':         if not root:             return root         if root.val>p.val and root.val>q.val:             return self.lowestCommonAncestor(root.left,p,q)         elif root.val<p.val and root.val<q.val:             return self.lowestCommonAncestor(root.right,p,q)         else:             return root

非递归方法

while root

class Solution:     def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':         if not root:             return root     while root:         if root.val<p.val and root.val<q.val:             root=root.right         elif root.val>p.val and root.val>q.val:             root=root.left         else:             return root

二叉树的最近公共祖先

在左右子树上搜索两个值

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':     if not root or root==p or root==q:         return root     left=self.lowestCommonAncestor(root.left,p,q)     right=self.lowestCommonAncestor(root.right,p,q)     if not left:         return right     elif not right:         return left     else:         return root

二叉树的直径

深度优先搜索，结合最大深度寻找，每次迭代都比较l+r与原来max值大小

def diameterOfBinaryTree(self, root: TreeNode) -> int:     maxlen=[0]     self.height(root,maxlen)     return maxlen[0] def height(self,root,maxlen):     if not root:         return 0     lheight=self.height(root.left,maxlen)     rheight=self.height(root.right,maxlen)     maxlen[0]=max(maxlen[0],lheight+rheight)     return max(lheight,rheight)+1

二叉树的右视图

广度优先

层次遍历，每次把该层最右节点加入结果集合中

while循环，每次获取当前queue的大小并遍历当前层所有节点，加入最右节点在结果集合中

深度优先

按照根节点-右节点-左节点顺序遍历，并且记录该层深度，只有大于深度的节点能加入结果中

def rightSideView(self, root: TreeNode) -> List[int]: res=[] stack=[(root,0)] depth=-1 while stack:     p=stack.pop()     if p[0]:        if p[1]>depth:            res.append(p[0].val)            depth+=1        stack.append((p[0].left,p[1]+1))        stack.append((p[0].right,p[1]+1)) return res

求二叉树的左叶子节点的和

递归

def sumOfLeftLeaves(self, root: TreeNode) -> int:     if not root:         return 0     res = [0]     self.recr(root,res,0)     return res[0] def recr(self,root,res,direct):     if not root.left and not root.right:         if direct:             res[0]+=root.val         return     if root.left:         self.recr(root.left,res,1)     if root.right:         self.recr(root.right,res,0)     return

非递归

如果是左叶子节点则加上去；如果是左节点进列表；如果是右子节点结束；如果是右节点加进去

def sumOfLeftLeaves(self, root: TreeNode) -> int:     if not root:         return 0     isLeafNode = lambda node: not node.left and not node.right     q = collections.deque([root])     ans = 0     while q:         node = q.popleft()         if node.left:             if isLeafNode(node.left):                  ans += node.left.val             else:                 q.append(node.left)        if node.right:            if not isLeafNode(node.right):                 q.append(node.right)      return ans

每日一题

最接近的三数之和

首先进行数组排序，时间复杂度 O(nlogn) 在数组 nums 中，进行遍历，每遍历一个值利用其下标i，形成一个固定值 nums[i]，再使用前指针指向 start = i + 1 处，后指针指向 end = nums.length - 1 处，也就是结尾处 根据 sum = nums[i] + nums[start] + nums[end] 的结果，判断 sum 与目标 target 的距离，如果更近则更新结果 ans

三数之和

要注意是否需要寻找不重复的数组，要的话得额外维护一个字典记录已经遍历过的数

寻找两个有序数组的中位数

中位数;将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素

认为前i-1个数为左部分，剩下右部分

j=(n+m+1)//2-i

保证左右部分数量相同

或者左边比右边多一个数

判断条件是左侧的数永远小于右侧的

注意i=0/m的特殊情况处理

如果长度和为偶数，m//2 m//2+1两个位置平均

如果长度和为奇数，m//2位置数

m=len

迭代的时候，m//2取到的都是左侧的数

O(log(m + n))时间复杂度

盛最多水的容器

o(n)解法

双指针法，哪边短就移动哪边

双指针搜索寻找最优值

mx=0 left=0 right=len(height)-1 while left<right:     mx=max(mx,min(height[left],height[right])*(right-left))     if height[left]<height[right]:         left+=1     else:         right-=1

腐烂的橘子

多源广度优先搜索

每次增加的是三元数组，除了坐标外需要有一个记录圈数的值

m=len(grid) n=len(grid[0]) queue=[] d=0 dim=[(-1,0),(1,0),(0,1),(0,-1)] for row in range(m):     for col in range(n):         if grid[row][col]==2:             queue.append((row,col,d)) while queue:     q = queue.pop(0)     for di in dim:         x=q[0]+di[0]         y=q[1]+di[1]         d=q[2]     if x>=0 and y>=0 and x<m and y<n and grid[x][y]==1:          queue.append((x,y,d+1))          grid[x][y]=2 for s in grid:      if 1 in s:         return -1 return d

所谓广度优先搜索，就是从起点出发，每次都尝试访问同一层的节点，如果同一层都访问完了，再访问下一层，最后广度优先搜索找到的路径就是从起点开始的最短合法路径。

观察到对于所有的腐烂橘子，其实它们在广度优先搜索上是等价于同一层的节点的。所以一开始可以把他们都加到队列中

螺旋矩阵

用一个seen数组记录所有被访问过的元素

用一个下标数组表示坐标变化，转换条件是指针超过正常范围或者已经访问过该元素，下标数组取值用（di+1)%4确定

遍历每一个矩阵中的数

不断用新的下标替代之前的

分糖果 II

编程与等差数列结合的一道题

2的幂次

使用位运算，o(n) 

我们通过 x & (-x) 保留了最右边的 1，并将其他位设置为 0 若 x 为 2 的幂，则它的二进制表示中只包含一个 1，则有 x & (-x) = x。 若 x 不是 2 的幂，则在二进制表示中存在其他 1，因此 x & (-x) != x。 因此判断是否为 2 的幂的关键是：判断 x & (-x) == x

不断除2看最后是否为1

while条件是 n%2

都要先判断0

回文数

回文的想法

两个指针遍历判断

倒转

倒转一半

倒转数字

可以倒转一半的数字，停止条件是倒转数字比不倒转部分大或者相等

当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。

注意所有被10能整除的数字都不是回文数字

if x<0 or (x%10==0 and x!=0): return False revernum=0 while revernum<x: revernum=revernum*10+x%10 x=x//10 return x==revernum or x==revernum//10

整数反转

while xcopy:     res = res*10 + xcopy % 10     xcopy=xcopy//10

和为s的连续正数序列

双指针

注意sum 和append的顺序

将数组分成和相等的三个部分

o(n)

需要想一想切分规则

def canThreePartsEqualSum(self, A: List[int]) -> bool:     s=sum(A)     if s%3:         return False     s1=0     for i in range(len(A)):         s1+=A[i]         if s1==s/3:             for j in range(i+1,len(A)-1):                  s1+=A[j]                  if s1==s*2/3:                      return True              return False      return False

字符串的最大公因子

最大公约数的概念

时间复杂度：O（（len1+len2）o（ gcd（leni，len2）），其中o（n）表示n的约数个数，gcd（a，b）表示a和b的最大公约数。我们需要线性的时间来两两比较拼接后的字符串和被比较的串是否相等 空间复杂度：O（lem+lem），每次枚举比较的过程中需要创建长度为lem和lem2的临时字符串变量，所以需 要额外O（em1+lem2）的空间

要求的字符串长度必然是两个输入字符串长度的公约数，而且是最大公因数

也是就取余数为0

再判断由该字符串拼接的和原来两个字符串是否相同

def gcdOfStrings(self, str1: str, str2: str) -> str:     length = min(len(str1),len(str2))     while length>0:         if len(str1)%length==0 and len(str2)%length==0:             if str1[:length]*(len(str1)//length)==str1 and str1[:length]*(len(str2)//length)==str2:                  return str2[:length]                            length-=1 return ""

小技巧就是因为求最大所以从后往前试探约数

多数元素

trick:排序以后中间位置的数就是众数，因为如果一个数个数大于len//2，那么排序之后肯定会在中间位置上

nums.sort() return nums[len(nums)//2]

维护hash表

子集

O(N×2 N)

res=[[]] for n in nums:     res+=[[n]+re for re in res]

求所有子集

矩阵重叠

判断投影是否交叉

使数组唯一的最小增量

def minIncrementForUnique(self, A: List[int]) -> int: if len(A)<=1:     return 0 A.sort() count=0 for i in range(1,len(A)):     if A[i]<=A[i-1]:         count+=A[i-1]+1-A[i]         A[i]=A[i-1]+1 return count

暴力法通不过

面试题62. 圆圈中最后剩下的数字

约瑟夫环

ans=0 for i in range(2,n+1):     ans=(ans+m)%i return ans

数学问题

总结一下反推的过程，就是 (当前index + m) % 上一轮剩余数字的个数

水壶问题

贝德定理

def canMeasureWater(self, x: int, y: int, z: int) -> bool: if x+y<z: return False if x==0 or y==0: return z==0 or x+y==z return z%math.gcd(x,y)==0

ax+by=z 有解当且仅当z是x和y的最大公约数的倍数

单词压缩编码问题

其实是找到所有不是其他单词后缀的单词

可以通过维护一个后缀树（用字典）

words = list(set(words)) #remove duplicates Trie = lambda: collections.defaultdict(Trie) trie = Trie() nodes = [reduce(dict.__getitem__, word[::-1], trie) for word in words] return sum(len(word) + 1 for i, word in enumerate(words) if len(nodes[i]) == 0)

打印括号组合

def generateParenthesis(self, n: int) -> List[str]:     res=[]     self.recr(0,0,n,res,'')     return res def recr(self,l,r,n,res,temp):     if l==n and r==n:         res.append(temp)         return     if l<n:         self.recr(l+1,r,n,res,temp+'(')     if r<n and l>r:         self.recr(l,r+1,n,res,temp+")")

接雨水

可以一个柱子一个柱子的考虑，每个柱子上能容下的水量是min(maxleft,maxright)-height[i]

可以用两个数组保存leftmax和rightmax

我的思路好清奇，先确定一个凹形结构，再确定能容水量，会嵌套很多循环

盛最多水的容器

不要啥都想到动态规划，多动动脑子

def maxArea(self, height: List[int]) -> int:     left=0     right=len(height)-1     mx=0     while left<right:         mx=max(mx,min(height[left],height[right])*(right-left))         if height[left]<height[right]:             left+=1         else:             right-=1     return mx

双指针left right  缩小距离就要增加柱子高度

丑数

难点在于查找第n个丑数不一定只查找了n次，要是一个一个找的话

可以用三个指针分别寻找*2/*3/*5的大于当前最大值的最小值，再将对应指标+1

dp=[0]*n dp[0]=1 da=0 db=0 dc=0 for i in range(1,n):     dp[i]=min(2*dp[da],3*dp[db],5*dp[dc])     if dp[i]==2*dp[da]: da+=1     if dp[i]==3*dp[db]: db+=1     if dp[i]==5*dp[dc]: dc+=1 return dp[n-1]

这样可以保证事件复杂度o(n)

dp[i]=min(2*dp[da],3*dp[db],5*dp[dc])

分析递推公式！！！

螺旋打印

根据边界打印，即将元素按顺序添加至列表 res 尾部； 边界向内收缩 11 （代表已被打印）； 判断是否打印完毕（边界是否相遇），若打印完毕则跳出。

if not matrix:     return [] u,d,l,r=0,len(matrix)-1,0,len(matrix[0])-1 res=[] while True:     for j in range(l,r+1):         res.append(matrix[u][j])     u+=1     if u>d:break     for i in range(u,d+1):         res.append(matrix[i][r])     r-=1     if l>r:break     for j in range(r,l-1,-1):         res.append(matrix[d][j])     d-=1     if u>d:break     for i in range(d,u-1,-1):         res.append(matrix[i][l])     l+=1     if l>r:break return res

四个边界条件的分析很精妙

每次边界向内收缩并且判断上下和左右边界是否相遇

栈的压入弹出序列

模拟栈的压入弹出过程： 使用一个栈，开始为空 持续压入pushed数组元素到栈中，直到栈顶元素和popped首元素相同，开始弹出，若弹出后还是匹配，继续弹出 最后判断栈是否为空，空则true，否则false

面试题44. 数字序列中某一位的数字

先判断n处于哪一个位数里面，再判断处于哪一个数字里面

def findNthDigit(self, n: int) -> int: if n<10:     return n nn=9 digit=1 while n-nn*digit>0:     n-=nn*digit     digit+=1     nn*=10 idx=n%digit if idx==0:     a=str(n//digit+10**(digit-1)-1)     return int(a[-1]) a=str(n//digit+10**(digit-1)) return int(a[idx-1])

最少移动次数使数组元素相等 II

绝对值和的最小值

两数相加

本题的主要难点在于链表中数位的顺序与我们做加法的顺序是相反的，为了逆序处理所有数位，我们可以使用栈：把所有数字压入栈中，再依次取出相加。计算过程中需要注意进位的情况。

carry=carry+a+b//10 cur=carry+a+b%10 先判断a b是否为0

逆序构建链表

ans=None  node.next=ans ans=node

用carry参与计算，注意最后要加一个carry的判断

class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) {     ListNode head = null;     ListNode tail = null;     int carry = 0;     int num;     while(l1!=null || l2!=null){         int n1 = l1 != null?l1.val:0;         int n2 = l2 != null?l2.val:0;         num = n1+n2+carry;         if(head==null){             head = tail = new ListNode(num%10);         }else{             tail.next = new ListNode(num%10);             tail = tail.next;         }         carry = num/10;         if(l1!=null){              l1 = l1.next;         }         if(l2!=null){             l2 = l2.next;         }     }     if(carry>0){         tail.next = new ListNode(carry);     }     return head; } }

python可以使用字符串处理

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:     str1 = ''     str2 = ''     while l1:         str1+=str(l1.val)         l1 = l1.next      while l2:         str2+=str(l2.val)         l2 = l2.next      res = str(int(str1[::-1]) + int(str2[::-1]))      head = ListNode(0)      move = head      for i in res[::-1]:          head.next = ListNode(int(i))          head = head.next     return move.next

URL化

S.split()默认去掉空格

'%20'.join(S[:length].split(' '))

S[:length].replace(' ', '%20')

贪心算法

跳跃游戏

维护一个最远到达距离，只要小于这个距离就是可以到达

def canJump(self, nums: List[int]) -> bool: right=0 for i in range(len(nums)):     if i<=right:         right=max(right,i+nums[i]) if right>=len(nums)-1:     return True else:     return False

要从全局考虑，不要太执着于细节，有几个0啥的

跳跃游戏2

如果我们「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。

def jump(self, nums: List[int]) -> int:     n = len(nums)     maxPos, end, step = 0, 0, 0     for i in range(n - 1):         if maxPos >= i:             maxPos = max(maxPos, i + nums[i])         if i == end:             end = maxPos             step += 1      return step

在具体的实现中，我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1

用动态规划超出时间限制了

合并数组

我们用数组 merged 存储最终的答案。 首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间： 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾； 否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。

def merge(self, intervals: List[List[int]]) -> List[List[int]]: if not intervals:     return intervals intervals = sorted(intervals,key=lambda x:x[0]) merged=[intervals[0]] for i in range(1,len(intervals)):     if intervals[i][0]>merged[-1][-1]:         merged.append(intervals[i])     else:         merged[-1][-1]=max(merged[-1][-1],intervals[i][-1]) return merged

斐波那契

def fib(self, N: int) -> int: if N in [0,1]:     return N a = 0 b = 1 for i in range(N-1):     a,b = b,a+b return b

统计重复个数

寻找循环节

好难啊，用hash表记录

N*3网格涂色

动态规划+排列组合

def numOfWays(self, n: int) -> int:     mod = 10**9 + 7     fi0, fi1 = 6, 6     for i in range(2, n + 1):         fi0, fi1 = (2 * fi0 + 2 * fi1) % mod, (2 * fi0 + 3 * fi1) % mod     return (fi0 + fi1) % mod

我们可以把它们分成两类： ABC 类：三个颜色互不相同，一共有 66 种：012, 021, 102, 120, 201, 210； ABA 类：左右两侧的颜色相同，也有 66 种：010, 020, 101, 121, 202, 212。 这样我们就可以把 12 种 type 浓缩成了 2 种，尝试写出这两类之间的递推式。我们用 f[i][0] 表示 ABC 类，f[i][1] 表示 ABA 类。在计算时，我们可以将任意一种满足要求的涂色方法带入第 i - 1 行，并检查第 i 行的方案数

有k个奇数的连续子数组个数

前缀和+差分

def numberOfSubarrays(self, nums: List[int], k: int) -> int: cnt={0:1} odd=0 ans=0 for i in range(len(nums)):     odd+=nums[i]%2     if odd>=k:         ans+=cnt.get(odd-k,0)     cnt[odd]=cnt.get(odd,0)+1 return ans

用一个字典记录每一个前缀和出现的次数，每次遍历都记录答案

[j..i] 这个子数组里的奇数个数恰好为 kk」这个条件我们可以转化为 pre[j−1]==pre[i]−k

pre[i]=pre[i−1]+(nums[i]&1)

数学方法只记录奇数位置，但是边界处理要注意

n = len(nums) odd= [-1] ans = 0 for i in range(n):     if nums[i] % 2 == 1:         odd.append(i) odd.append(n) print(odd) for i in range(1, len(odd) - k):     ans += (odd[i] - odd[i - 1]) * (odd[i + k] - odd[i + k - 1]) return ans

归并排序扩展-数组的逆序对

数组的逆序对刻画数组混乱程度

那么求逆序对和归并排序又有什么关系呢？关键就在于「归并」当中「并」的过程。

在每次合并的时候计算逆序的个数

def reversePairs(self, nums: List[int]) -> int:     left=0     right=len(nums)-1     res=[0]     self.merge_sort(left,right,nums,res)     return res[0] def merge_sort(self,left,right,nums,res):     if left>=right:         return     mid=(left+right)//2     self.merge_sort(left,mid,nums,res)     self.merge_sort(mid+1,right,nums,res)     if nums[mid]>nums[mid+1]:         self._merge(left,mid,right,nums,res) def _merge(self,left,mid,right,nums,res):     blist=nums[left:right+1]     cur=left     l=0     r=mid+1-left     while l<=mid-left or r<=right-left:         if l>mid-left:             nums[cur]=blist[r]             r+=1         elif r>right-left:             nums[cur]=blist[l]             l+=1         elif blist[l]<=blist[r]:             nums[cur]=blist[l]             l+=1         else:             nums[cur]=blist[r]             res[0]=res[0]+mid-left-l+1             r+=1     cur+=1

情侣牵手

异或操作选择第i个人的情侣

会保证偶数编号的情侣得到比其小1的奇数编号，奇数编号得到比其大一的编号

row[i+1]==row[i]^1

res=0 for i in range(0,len(row),2):     if row[i+1]==row[i]^1:        continue     res+=1     for j in range(i+2,len(row)):         if row[j]==row[i]^1:             row[i+1],row[j]=row[j],row[i+1]             break

贪心算法：依次比较i,i+2，i+4位置，并找到其情侣位置交换

合并k个排序链表

先合并一个大数组在整体快排

两两合并

新21点概率论和动态规划反序求解

def new21Game(self, N: int, K: int, W: int) -> float:     dp=[None]*(K+W)     s=0     for i in range(K,K+W): # 填蓝色的格子         dp[i] = 1 if i<=N else 0         s+=dp[i]     for i in range(K-1,-1,-1): # 填橘黄色格子         dp[i]=s/W         s=s-dp[i+W]+dp[i]     return dp[0]

7月加油

靠归并排序求逆序数也太难了吧

归并排序

逆序的动态规划找好初始值

def calculateMinimumHP(self, dungeon: List[List[int]]) -> int: if not dungeon:     return 1 row = len(dungeon) col = len(dungeon[0]) dp = [[float('inf')]*(col+1) for i in range(row+1)] dp[row][col-1] = 1 dp[row-1][col] = 1 for i in range(row-1,-1,-1):     for j in range(col-1,-1,-1):         dp[i][j]=max(min(dp[i+1][j],dp[i][j+1])-dungeon[i][j],1) return dp[0][0]

找到奇数个个数的元素

set求和-原数组求和

异或

快乐数

缩减到1 或者陷入小于243的循环

可以借助判断链表是否有环的方法

用一个1-7的随机数生成器生成1-10的随机数

rand48 =（rand7-1)*7+rand7-1

rand48<39//10+1

找出数组中的重复数字

使用一个dict记录出现过的item

2021.3

技巧性位运算

比特位计数

按位与运算（\&）的一个性质是：对于任意整数 xx，令 x=x&(x−1)，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」

def countBits(self, num: int) -> List[int]:     def count(i):         ones=0         while i>0:               i &= (i-1)               ones+=1         return ones      ans = [count(i) for i in range(num+1)]      return ans

数组中不重复的两个数

异或操作

ret=0 a=0 b=0 for n in nums:     ret^=n h=1 while(h & ret ==0):     h<<=1 for n in nums:     if n&h==0:         a^=n     else:         b^=n return [a,b]

相同数字异或结果一定为0

判断字符是否唯一

位运算

def isUnique(self, astr: str) -> bool: mark = 0 for char in astr:     move_bit = ord(char) - ord('a')     if (mark & (1 << move_bit)) != 0:         return False     else:         mark |= (1 << move_bit) return True

1<<2 把1这个二进制表示左移2位

1>>2把1右移2位

正数的补码是本身，负数的补码是除符号位其他取反加1

与。或。非操作

栈

java用栈实现队列

双栈实现队列

deque双端队列接口，最常用的实现类是linkedlist

deque可以实现java中栈和队列

代码

class MyQueue { Deque<Integer> inStack; Deque<Integer> outStack; public MyQueue() {     inStack = new LinkedList<Integer>();     outStack = new LinkedList<Integer>(); } public void push(int x) {     inStack.addFirst(x); } public int pop() {    if (outStack.isEmpty()){       in2out(); } return outStack.removeFirst(); } private void in2out(){     while(!inStack.isEmpty()){          outStack.push(inStack.removeFirst()); } } public int peek() {     if(outStack.isEmpty()){         in2out(); } return outStack.peek(); } public boolean empty() {     return inStack.isEmpty() && outStack.isEmpty(); } }

下一个更大元素 II

单调栈

右边第一个比它大的数，维护单调递减的栈，从头到尾遍历

求右边第一个比他小的数，维护单调递增的栈，从头到尾遍历

求左边第一个比它大的数，维护单调递减栈，从尾到头遍历

循环数组

可以把前n-1补到后面，或者采用遍历2n-1次然后对下标取余数

代码

class Solution { public int[] nextGreaterElements(int[] nums) {     int n = nums.length;     int[] ans = new int[n];     Arrays.fill(ans,-1);     Deque<Integer> stk = new LinkedList<Integer>();     for(int i=0;i<2*n-1;i++){         while(!stk.isEmpty() && nums[stk.peek()] < nums[i%n]){              ans[stk.pop()]=nums[i%n];         }     stk.push(i%n);     }     return ans; } }

class Solution: def nextGreaterElements(self, nums: List[int]) -> List[int]:     n = len(nums)     ret = [-1] * n     stk = list()     for i in range(n * 2 - 1):         while stk and nums[stk[-1]] < nums[i % n]:              ret[stk.pop()] = nums[i % n]         stk.append(i % n) return ret

删除字符串中的重复相邻字符

python用栈（list）,java用StringBuffer

code

class Solution { public String removeDuplicates(String S) {     StringBuffer stk = new StringBuffer();     int top=-1;     for(int i = 0;i < S.length();i++){         if(top>=0 && S.charAt(i)==stk.charAt(top)){             stk.deleteCharAt(top);             top--;         }else{             stk.append(S.charAt(i));             top++;          }     }     return stk.toString(); } }

class Solution: def removeDuplicates(self, S: str) -> str:     stack = []     n = len(S)     i = 0     while i < n:        if stack and S[i] == stack[-1]:            stack.pop()        else:            stack.append(S[i])            i+=1        res = ''.join(stack)     return res

逆波兰表达式

遇到运算符就把栈顶两个元素出栈，执行运算，得到的结果再入栈的原则来进行处理

class Solution: def evalRPN(self, tokens: List[str]) -> int:     stack = []     f1 = lambda a,b : a+b     f2 = lambda a,b : a-b     f3 = lambda a,b : a * b     f4 = lambda a,b : int(a / b) ##取整不能用 a//b     op = {'+':f1, '-':f2, '*':f3,'/':f4}     for i in tokens:         if i in op:            b = stack.pop()            a = stack.pop()            stack.append(op[i](a,b))         else:            stack.append(int(i))     return stack[0]

基本计算器

使用栈记录每次当前数字的正负号，括号内部的符号也受到括号前符号的影响

ops-stack-ret-num-i-n

只有加减和括号

入栈的只有符号（+-1），每次结果都计算好了的不用存在栈里面

栈内存储integer类型

注意要初始化push一个1

代码

class Solution { public int calculate(String s) {     int ret = 0;     int sign = 1;     int i = 0;     int n = s.length();     Deque<Integer> ops = new LinkedList<Integer>();     ops.push(1);     while(i<n){         if(s.charAt(i)==' '){            i++;         }else if(s.charAt(i)=='+'){            sign = ops.peek();            i++;         }else if(s.charAt(i)=='-'){            sign = -ops.peek();            i++;         }else if(s.charAt(i)=='('){            ops.push(sign);             i++;         }else if(s.charAt(i)==')'){             ops.pop();             i++;         }else{             long num = 0;             while(i<n && Character.isDigit(s.charAt(i))){                 num = num*10 + s.charAt(i)-'0';                 i++;              }            ret+=num*sign;         }      }      return ret; } }

基本计算器2

只有加减乘除

入栈：数字，没有符号

只使用栈，不能遇到*/就pop，因为涉及两个操作数

技巧：另设一个ops，每次当前是符号，就用上一次的符号乘数字结果入栈

代码

class Solution { public int calculate(String s) {     char ops = '+';     int num = 0;     Deque<Integer> stk = new LinkedList<Integer>();     for(int i=0;i<s.length();i++){         if(Character.isDigit(s.charAt(i))){             num = num * 10 + s.charAt(i) - '0';         }         if(!Character.isDigit(s.charAt(i)) && s.charAt(i)!=' ' || i==s.length()-1){             switch(ops){                 case '+':                     stk.push(num);                     break;                 case '-':                     stk.push(-num);                     break;                 case '*':                      stk.push(stk.pop()*num);                      break;                 default:                      stk.push(stk.pop()/num);             }             num = 0;             ops = s.charAt(i);        }     }      int ret = 0;      while(!stk.isEmpty()){          ret += stk.pop();      }      return ret; } }

class Solution: def calculate(self, s: str) -> int:     ops='+'     stack = []     num = 0     for i,c in enumerate(s):         if c.isnumeric():              num = num*10 + int(c)         if c in '+-*/' or i==len(s)-1:             if ops=="+":                   stack.append(num)             if ops=="-":                   stack.append(-num)             if ops=="*":                    stack.append(stack.pop()*num)             if ops=="/":                    stack.append(stack.pop()/num)         num = 0         ops = c return sum(stack)

队列的最大值

比实现最小栈更难一些

因为队列和维护最大值的栈出队顺序是相反的

所以最好也用一个队列去维护最大值

在一个数之前入队的数中，比它小的数出队对最大值没有影响

import queue class MaxQueue: def __init__(self): self.queue=[] self.deque=queue.deque() def max_value(self) -> int: if self.deque: return self.deque[0] else: return -1 def push_back(self, value: int) -> None: while self.deque and self.deque[-1]<value:     self.deque.pop() self.deque.append(value) self.queue.append(value) def pop_front(self) -> int: if self.queue: pop = self.queue.pop(0) if pop==self.deque[0]: self.deque.popleft() return pop else return -1

只需要保证辅助队列中的顺序是递减的

深度优先或者广度优先搜索

二维动态规划

二维区域和检索 - 矩阵不可变

记录每一个位置的前缀和，一维或者二维

注意加减关系别搞错

代码

class NumMatrix {     int[][] sums;     public NumMatrix(int[][] matrix) {         int m = matrix.length;         if(m>0){             int n = matrix[0].length;             sums = new int[m+1][n+1];             for(int i=0;i<m;i++){                 for(int j=0;j<n;j++){                     sums[i+1][j+1] = sums[i][j+1]+sums[i+1][j]-sums[i][j]+matrix[i][j];                 }             }         }     }     public int sumRegion(int row1, int col1, int row2, int col2) {         return sums[row2+1][col2+1] - sums[row2+1][col1]-sums[row1][col2+1]+sums[row1][col1];     } }

class NumMatrix: def __init__(self, matrix: List[List[int]]):    m,n = len(matrix),len(matrix[0]) if matrix else 0    self.sums = [[0]*(n+1) for _ in range(m+1)]    for i in range(m):        for j in range(n):            self.sums[i+1][j+1] = self.sums[i][j+1] + self.sums[i+1][j] - self.sums[i][j] + matrix[i][j] def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:      return self.sums[row2+1][col2+1]-self.sums[row2+1][col1]-self.sums[row1][col2+1]+self.sums[row1][col1]

01矩阵

多源广度优先搜索

超级零

「最短路」的读者应该知道，我们所说的「超级零」实际上就是一个「超级源点」。在最短路问题中，如果我们要求多个源点出发的最短路时，一般我们都会建立一个「超级源点」连向所有的源点，用「超级源点」到终点的最短路等价多个源点到终点的最短路。

queue=collections.deque() ans=[[0]*col for i in range(row)] dim=[(1,0),(-1,0),(0,1),(0,-1)] seen=set() for i in range(row):     for j in range(col):         if matrix[i][j]==0:             queue.append((i,j,0))             seen.add((i,j)) while queue:     p=queue.popleft()     for d in dim:         x=d[0]+p[0]         y=d[1]+p[1]         r=p[2]+1     if x>=0 and x<row and y>=0 and y<col and ((x,y) not in seen):         ans[x][y]=r         seen.add((x,y))         queue.append((x,y,r)) return ans

一开始我们就将所有的 0 加入队列，它们的初始距离为 0。这样以来，在广度优先搜索的过程中，我们每遇到一个 1，就得到了它到「超级零」的距离减去一，也就是这个 1 到最近的 0 的距离

动态规划

关键怎么设置状态转移

初始值一定要inf

设置初始值0

对于矩阵中的任意一个 1 以及一个 0，我们如何从这个 1 到达 0 并且距离最短呢？根据上面的做法，我们可以从 1 开始，先在水平方向移动，只要与 0 在同一列。随后再在竖直方向上移动，直到到达 0 的位置。这样以来，从一个固定的 1 走到任意一个 0，在距离最短的前提下可能有四种方法，故有4个状态转移函数

我想到了这种方法，但是不知道怎么处理上下左右四个位置，就想要用两个dp存取最小，但是边界难处理，这道题直接用一个数组，每次比较上下左右和自己，很巧妙的动态规划

def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]: row=len(matrix) col=len(matrix[0]) dp=[[float('inf')]*col for i in range(row)] for i in range(row):     for j in range(col):        if matrix[i][j]==0:             dp[i][j]=0 for i in range(row):     for j in range(col):         if i-1>=0:             dp[i][j]=min(dp[i][j],dp[i-1][j]+1)         if j-1>=0:             dp[i][j]=min(dp[i][j],dp[i][j-1]+1) for i in range(row-1,-1,-1):     for j in range(col-1,-1,-1):         if i+1<row:            dp[i][j]=min(dp[i][j],dp[i+1][j]+1)         if j+1<col:             dp[i][j]=min(dp[i][j],dp[i][j+1]+1) return dp

机器人的运动范围

广度优先搜索，只考虑向右和向下方向，需要一个额外的数组保存该方格是否已经被遍历过的信息

递推：用set保存满足条件的格子，每次只需要判断左侧和上方的格子是否已经在集合中

def digitsum(self,n):     ans=0     while n:         ans=ans+n%10         n//=10     return ans def movingCount(self, m: int, n: int, k: int) -> int:     vim=set([(0,0)])     for i in range(m):         for j in range(n):             if ((i-1,j) in vim or (i,j-1) in vim) and self.digitsum(i)+self.digitsum(j)<=k:             vim.add((i,j))     return len(vim)

数据结构设计

设计哈希集合

链地址法 设哈希表的大小为base，则可以设计一个简单的哈希函数：hash(x)=xmodbase。 我们开辟一个大小为 base 的数组，数组的每个位置是一个链表。当计算出哈希值之后，就插入到对应位置的链表当中。 由于我们使用整数除法作为哈希函数，为了尽可能避免冲突，应当将base 取为一个质数。在这里，我们取base=769。

数组+链表实现，每次都要判断有无重复，iterator的使用

class MyHashSet {     private static final int BASE=769;     private LinkedList[] data;     public MyHashSet() {         data = new LinkedList[BASE];         for(int i=0;i<BASE;i++){              data[i] = new LinkedList<Integer>();         }     }     public void add(int key) {         int h = hash(key);         Iterator<Integer> it = data[h].iterator();         while(it.hasNext()){             Integer ele = it.next();             if(ele==key){                  return;             }         }         data[h].offerLast(key);     }     public void remove(int key) {         int h = hash(key);         Iterator<Integer> it = data[h].iterator();         while(it.hasNext()){             Integer ele = it.next();             if(ele==key){                  data[h].remove(ele);                  return;             }          }     }     public boolean contains(int key) {          int h = hash(key);          Iterator<Integer> it = data[h].iterator();          while(it.hasNext()){               Integer ele = it.next();               if(ele==key){                    return true;               }           }           return false;     }     private static int hash(int key){         return key%BASE;     } }

设计哈希映射

「设计哈希映射」与「设计哈希集合」解法接近，唯一的区别在于我们存储的不是 key 本身，而是 (key,value) 对。除此之外，代码基本是类似的

类内设计一个内部类

代码

class MyHashMap {     private class Pair {     private int key;     private int value;     public Pair(int key, int value) {         this.key = key;         this.value = value;     }     public int getKey() { return key; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } } private static final int BASE = 769; private LinkedList[] data; /** Initialize your data structure here. */ public MyHashMap() { data = new LinkedList[BASE]; for (int i = 0; i < BASE; ++i) { data[i] = new LinkedList<Pair>(); } } /** value will always be non-negative. */ public void put(int key, int value) { int h = hash(key); Iterator<Pair> iterator = data[h].iterator(); while (iterator.hasNext()) { Pair pair = iterator.next(); if (pair.getKey() == key) { pair.setValue(value); return; } } data[h].offerLast(new Pair(key, value)); } /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */ public int get(int key) { int h = hash(key); Iterator<Pair> iterator = data[h].iterator(); while (iterator.hasNext()) { Pair pair = iterator.next(); if (pair.getKey() == key) { return pair.value; } } return -1; } /** Removes the mapping of the specified value key if this map contains a mapping for the key */ public void remove(int key) { int h = hash(key); Iterator<Pair> iterator = data[h].iterator(); while (iterator.hasNext()) { Pair pair = iterator.next(); if (pair.key == key) { data[h].remove(pair); return; } } } private static int hash(int key) { return key % BASE; } } 作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/design-hashmap/solution/she-ji-ha-xi-ying-she-by-leetcode-soluti-klu9/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。题

子主题

设计停车系统

为每种车维护一个计数器，初始值为车位的数目。此后，每来一辆车，就将对应类型的计数器减 1。当计数器为 0 时，说明车位已满

模拟

class ParkingSystem {     int big,medium,small;     public ParkingSystem(int big, int medium, int small) {          this.big = big;          this.medium = medium;          this.small = small;     }     public boolean addCar(int carType) {          if(carType==1){             if(this.big>0){                 this.big--;                 return true;             }          } else if(carType==2){              if(this.medium>0){                  this.medium--;                  return true;              }          }else if(carType==3){               if(this.small>0){                   this.small--;                   return true;               }         }         return false;     } }

也可以使用python的字典数据结构来实现

螺旋矩阵二

打印1到n2，按照顺时针打印

class Solution {     public int[][] generateMatrix(int n) {         int[][] matrix = new int[n][n];         int up = 0;         int down = n-1;         int left = 0;         int right = n-1;         int num = 1;     while(true){         for(int i=left;i<=right;i++){             matrix[up][i] = num;             num++;         }         up++;         if(up>down){             return matrix;         }         for(int i=up;i<=down;i++){             matrix[i][right] = num;             num++;         }         right--;         if(left>right){             return matrix;          }          for(int i=right;i>=left;i--){              matrix[down][i] = num;              num++;          }          down--;          if(up>down){              return matrix;          }          for(int i=down;i>=up;i--){              matrix[i][left] = num;              num++;          }          left++;          if(left>right){              return matrix;          }      } } }

三个易错点

矩阵下标

循环范围

判断条件

回溯法小专题

回溯法

一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试

组合总和

递归回溯法

求出所有和为 target 的组合，并且每个数只能使用一次，因此我们可以使用递归 + 回溯的方法来解决这个问题： 我们用 dfs(pos,rest) 表示递归的函数，其中 pos 表示我们当前递归到了数组 candidates 中的第 pos 个数，而 rest 表示我们还需要选择和为rest 的数放入列表作为一个组合；      对于当前的第 pos 个数，我们有两种方法：选或者不选。如果我们选了这个数，那么我们调用dfs(pos+1,rest−candidates[pos]) 进行递归，注意这里必须满足 rest≥candidates[pos]。如果我们不选这个数，那么我们调用dfs(pos+1,rest) 进行递归；      在某次递归开始前，如果rest 的值为 0，说明我们找到了一个和为 target 的组合，将其放入答案中。每次调用递归函数前，如果我们选了那个数，就需要将其放入列表的末尾，该列表中存储了我们选的所有数。在回溯时，如果我们选了那个数，就要将其从列表的末尾删除。 上述算法就是一个标准的递归 + 回溯算法，适用于集合没有重复数字的数组

代码

class Solution:     def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:         combine = []         idx = 0         res = []         self.dfs(candidates,target,combine,idx,res)         return res     def dfs(self,candidates,target,combine,idx,res):         if target<=0 or idx>=len(candidates):             if target==0:                 res.append(combine)                 return         self.dfs(candidates,target-candidates[idx],combine+[candidates[idx]],idx,res)         self.dfs(candidates,target,combine,idx+1,res)         return

组合总和二

有重复的数字，每个数字用一次

转换为不重复数组，用一个字典记录

代码

class Solution:     def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:          res=[]          temp=[]          start=0          freq = sorted(collections.Counter(candidates).items())          self.back(start,freq,target,res,temp)          return res     def back(self,start,freq,target,res,temp):          if start>=len(freq) or target<=0:              if target==0:                  res.append(temp.copy())                  return          self.back(start+1,freq,target,res,temp)          most = min(target//freq[start][0],freq[start][1])          for i in range(1,most+1):              temp.append(freq[start][0])              self.back(start+1,freq,target-i*freq[start][0],res,temp)          for i in range(most):               temp.pop()

组合总和三

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

回溯退出条件

class Solution: def combinationSum3(self, k: int, n: int) -> List[List[int]]:     alist=[i for i in range(1,10)]     res=[]     temp=[]     idx=0     self.back(alist,k,n,idx,res,temp)     return res def back(self,alist,k,target,idx,res,temp):     if idx>=len(alist) or len(temp)>=k:         if len(temp)==k and target==0 and sorted(temp) not in res:             res.append(sorted(temp))         return     temp.append(alist[idx])     self.back(alist,k,target-alist[idx],idx+1,res,temp)     temp.pop()     self.back(alist,k,target,idx+1,res,temp)

分割回文串

回溯法

确定好回溯函数需要的参数

每次都要判断分割出来的是不是一个回文串

用【：：-1】

退出条件

if index == len(s): res.append(temp.copy()) return

代码

def partition(self, s: str) -> List[List[str]]:     res=[]     index=0     temp=[]     self.back(s,res,temp,index)      return res def back(self,s,res,temp,index):     if index==len(s):         res.append(temp.copy())         return     for j in range(index,len(s)):         s1 = s[index:j+1]         if s1[::-1]==s1:             temp.append(s1)             self.back(s,res,temp,j+1)             temp.pop()

def partition(self, s: str) -> List[List[str]]:     dp = [[True for _ in range(len(s))] for _ in range(len(s))]     for j in range(len(s)):         for i in range(0,j):               dp[i][j] = (s[i]==s[j]) and dp[i+1][j-1]     res = []     ans = []     def dfs(i):          if i == len(s):             res.append(ans[:])             return          for j in range(i,len(s)):              if dp[i][j]:                 ans.append(s[i:j+1])                 dfs(j+1)                 ans.pop()     dfs(0)     return res

动态规划+回溯

用一个二维数组记录从i到j位置是否是回文串

每次都保证i前面的是回文串并且加入临时数组，然后更新j+1的位置为新的i，继续搜索

一般这种需要搜索每一种情况的都要用到index来作为退出条件，意思是搜索位置

比二重循环灵活

java代码

class Solution {     boolean[][] f;     List<List<String>> ret = new ArrayList<List<String>>();     List<String> ans = new ArrayList<String>();     int n;     public List<List<String>> partition(String s) {         n = s.length();         f = new boolean[n][n];         for (int i = 0; i < n; ++i) {             Arrays.fill(f[i], true);         }         for (int i = n - 1; i >= 0; --i) {             for (int j = i + 1; j < n; ++j) {                   f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i + 1][j - 1];              }         }        dfs(s, 0);        return ret;    }     public void dfs(String s, int i) {         if (i == n) {             ret.add(new ArrayList<String>(ans));             return;          }        for (int j = i; j < n; ++j) {             if (f[i][j]) {                   ans.add(s.substring(i, j + 1));                   dfs(s, j + 1);                   ans.remove(ans.size() - 1);             }         }      } }

需要判断每一种遍历结果是否符合条件就用回溯剪枝，无法直接用循环得到，因为不确定是几重循环

全排列

有重复或者没有重复元素

回溯法

def permuteUnique(self, nums: List[int]) -> List[List[int]]:      if not nums:         return []      temp=[]      res=[]      n=len(nums)      label=[]      self.recr(nums,temp,res,n,label)      return res def recr(self,nums,temp,res,n,label):     if len(temp)==n:         if temp not in res:            res.append(temp)         return     for i in range(len(nums)):         if i not in label:             self.recr(nums,temp+[nums[i]],res,n,label+[i])

<span style="color: rgb(38, 38, 38); font-family: -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, "Helvetica Neue", Arial, "Noto Sans", sans-serif, "Apple Color Emoji", "Segoe UI Emoji", "Segoe UI Symbol", "Noto Color Emoji";">给定一个可包含重复数字的序列 <code style="box-sizing: border-box; background: rgba(var(--grey-9-rgb),0.04); color: rgba(var(--grey-7-rgb),1); padding: 2px 4px; border-radius: 3px;">nums</code><span style="color: rgb(38, 38, 38); font-family: -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, "Helvetica Neue", Arial, "Noto Sans", sans-serif, "Apple Color Emoji", "Segoe UI Emoji", "Segoe UI Symbol", "Noto Color Emoji";"> ，<span style="box-sizing: border-box; font-weight: bolder; color: rgb(38, 38, 38); font-family: -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, "Helvetica Neue", Arial, "Noto Sans", sans-serif, "Apple Color Emoji", "Segoe UI Emoji", "Segoe UI Symbol", "Noto Color Emoji";">按任意顺序<span style="color: rgb(38, 38, 38); font-family: -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, "Helvetica Neue", Arial, "Noto Sans", sans-serif, "Apple Color Emoji", "Segoe UI Emoji", "Segoe UI Symbol", "Noto Color Emoji";"> 返回所有不重复的全排列。

这个问题可以看作有 n个排列成一行的空格，我们需要从左往右依此填入题目给定的 n个数，每个数只能使用一次。那么很直接的可以想到一种穷举的算法，即从左往右每一个位置都依此尝试填入一个数，看能不能填完这 n 个空格，在程序中我们可以用「回溯法」来模拟这个过程。 我们定义递归函数 backtrack(first, output) 表示从左往右填到第 first 个位置，当前排列为 output。那么整个递归函数分为两个情况： 如果 first==n，说明我们已经填完了 n 个位置（注意下标从 0 开始），找到了一个可行的解，我们将 output 放入答案数组中，递归结束。 如果 first<n，我们要考虑这第first 个位置我们要填哪个数。根据题目要求我们肯定不能填已经填过的数，因此很容易想到的一个处理手段是我们定义一个标记数组vis[] 来标记已经填过的数，那么在填第first 个数的时候我们遍历题目给定的 n 个数，如果这个数没有被标记过，我们就尝试填入，并将其标记，继续尝试填下一个位置，即调用函数 backtrack(first + 1, output)。回溯的时候要撤销这一个位置填的数以及标记，并继续尝试其他没被标记过的数。

无重复字符串排列组合

思路：假设你有abc的所有排列。你怎么用它来得到abcd的所有排列？

def permutation(self, S: str) -> List[str]:     if len(S)<=1:         return [S]     tmp=[S[0]]     res=[tmp]     for i in range(1,len(S)):         n = len(res)         for j in range(n):             base = res.pop(0)             tmp = base.copy()             for k in range(len(tmp)+1):                  tmp.insert(k,S[i])                  res.append(tmp)                  tmp =base.copy()      ans=[]     for r in res:        ans.append(''.join(r)) return ans

你可以通过计算abc的所有排列，然后在每个可能的位置插入d，从而创建abcd的所有排列。

要生成abcd的所有排列组合，请选择每个字符（a、b、c、d）作为首字符。排列剩余的字符并追加首字符。如何排列剩余的字符？使用遵循相同逻辑的递归过程

动态规划背包小专题

组合总和 Ⅳ

求有顺序的排列数量

完全背包，可重复使用元素

外层遍历target，内层遍历元素

def combinationSum4(self, nums: List[int], target: int) -> int:     dp = [0]*(target+1)     dp[0]=1     for i in range(1,target+1):          for n in nums:               if i-n>=0:               dp[i]+=dp[i-n]     return dp[-1]

零钱兑换

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

外层遍历元素，内层遍历target

完全背包无顺序

def change(self, amount: int, coins: List[int]) -> int:     dp = [0]*(amount+1)     dp[0] = 1     for c in coins:         for j in range(c,amount+1):              dp[j] += dp[j-c]      return dp[-1]

动态规划

策略为： 从基本情况没有开始，一一添加。 对于每个添加的***，我们从金额 0 到 amount 递归的计算组合数量。 算法： 以基本情况没有***开始组合数量。dp[0] = 1，然后其余等于 0。 遍历所有***面值： 对于每个***，我们将从金额 0 遍历到 amount： 对于每个 x，计算组合数：dp[x] += dp[x - coin]。 返回 dp[amount]

零钱兑换

dp[x] = min(dp[x], dp[x - coin] + 1)

dp[x]表示构成金额x的硬币最少数量

分割回文串

不同的子序列

困难

栈和队列

最大队列

数据取出和输入的端不一样

def push_back(self, value: int) -> None:         while self.stack and self.stack[-1]<value:              self.stack.pop()        self.stack.append(value)    self.queue.append(value)

最小栈

数据取出和输入端一样

if not self.stack:     self.minlist.append(x) else:     if x<=self.minlist[-1]:        self.minlist.append(x) self.stack.append(x)

队列与广度优先搜索

def get_answer(): row,col = list(map(int,input().strip().split())) mat = [list(input()) for r in range(row)] s,t = [(i,j) for i,r in enumerate(mat) for j,v in enumerate(r) if v=='S' or v=='E'] seen = set([s]) queue = [s] while queue:     nq = []     for x,y in queue:         for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:             nx,ny = x+dx,y+dy             if (nx,ny) == t:                 print('YES')                 return            if 0<=nx<row and 0<=ny<col and mat[nx][ny]=='.' and (nx,ny) not in seen:                 nq.append((nx,ny))                 seen.add((nx,ny)) queue = nq print('NO') f()

王子救公主

指定起点和终点

栈与深度优先搜索

逆波兰表达式

矩阵中的路径

def hasPath(self, matrix, string): for i in range(len(matrix)):     for j in range(len(matrix[i])):          if self.dfs(matrix, string, 0, i, j):              return True return False def dfs(self, matrix, string, u, x, y):     memo = matrix[x][y]     if matrix[x][y] != string[u]:        return False # 出口     if u == len(string) - 1:         return True      dx = [-1, 0, 1, 0]     dy = [0, 1, 0, -1]     matrix[x][y] = '*'     for i in range(4):         a = x + dx[i]         b = y + dy[i]     if a >= 0 and a < len(matrix) and b >= 0 and b < len(matrix[a]):         if self.dfs(matrix, string, u + 1, a, b):              return True     matrix[x][y] = memo     return False

字符串解码

每次 [ 入栈另一个元组，保留之前的字符和倍数

def decodeString(self, s: str) -> str:     stack=[]     res=''     multi=0     for i in s:         if i>='0' and i <='9':             multi=multi*10+int(i)         elif i=="[":             stack.append((multi,res))             res, multi = "", 0         elif i=="]":              kv=stack.pop()              res=kv[1]+kv[0]*res           else:              res+=i     return res

股票最大收益

def maxDiff(self, nums): if len(nums) == 0: return 0 minv = nums[0] res = 0 for i in range(len(nums)): minv = min(minv, nums[i]) maxv = nums[i] - minv res = max(res, maxv) return res

算法

前缀和

差分

双指针

桶排序

队列

栈

bfs/dfs

拓扑排序

欧拉路

Tarjan求连通分量

KMP

字典树

o(logn）

排序

二分

并查集

快速幂

最大公因数

o(nlogn)

ST表

线段树

堆

树状数组

二叉搜索树

归并/快速排序

最短路

最小生成树

凸包

o(nm)

背包问题

n个物品m大小

匈牙利匹配

哈希

o(2^n)

搜索

状态压缩

牛客网

获取输入输出

单行输入

input_str = raw_input("") input_str=map(int,input_str.split())

le = input().strip() res = input().strip().split()

多行输入

m=int(input().strip()) list1=[] for i in range(m): list1.append(int(input().strip()))

sys.stdin.readline().strip()

切两刀获得最大奖金

两个指针，注意应该取最大奖金

le=int(input().strip()) res=list(map(int,input().strip().split())) if le<=1:     print(0) left=-1 right=le leftsum=0 rightsum=0 while left<right:     if leftsum<rightsum:         left+=1         leftsum+=res[left]     elif leftsum>rightsum:         right-=1         rightsum+=res[right]     else:         ans=leftsum         left, right = left + 1, right - 1         leftsum += res[left]         rightsum += res[right]  print(ans)

注意输入输出

最大乘积

每次循环都判断两种情况

max*second*third

把第二大给第3大，第1大给第2大，第一大赋给新的值

打印蛇形矩阵

和之前的螺旋矩阵一样的

除了设置四个边界

可以设置偏移量d=(d+1)%4

外加一个判断是否已经存入数据的矩阵

凑1-m所有面值的硬币最少需要多少

分别确定每个面值需要多少