leecode
2021-04-05 19:22:27 1 举报AI智能生成
leecode各种算法和刷题经验总结
作者其他创作
大纲/内容
leecode
动态规划
基本问题
多阶段最优化决策，每次决策依赖于当前状态，又引起状态的转移
基本思想
分治法
将待求解的问题分为若干个子问题，按顺序求解子阶段，但是与分治法不同的是每个子问题不独立
求解核心
记住已经求过的解，自底向上
核心概念
阶段
决策
限制条件
优化函数
状态
状态转移
适用情境
问题可以被递归地处理，但很多子问题答案会被重复利用
对每个子问题只计算一次，然后将计算结果保存到一个表格中，每次需要上一个子问题的解时只需要调用即可，用空间换时间
求解步骤
划分阶段
确定状态和状态变量
确定决策并写出状态转移方程
寻求边界条件
典型例子
背包问题
相当于计算一个矩阵，一列代表各个物品，另一个代表包的容量（从1到max）一个一个增加物品，每次判断一下，如果装不下该物品就沿用上一行的最大价值，如果装得下就调整价值，可能用到之前的子问题
走台阶问题
逆序分析，因为结果固定（登上了n层楼梯）
最优子结构：每个阶段的最优状态可以从之前某个阶段的某个或者某些状态直接得到
状态转移函数：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]
最大子序和问题
定义一个列表存储子问题最优解
I表示数组第i个位置的元素
D[i]表示从0到i闭区间内，所有包含第i个元素的连续子数组中，总和最大的值
乘积最大子序列
首先要定义一个空数据（列表套列表）
因为乘积涉及到正负号问题，负号可能会使最小值和最大值互换，所以都要存起来
当符号是负的，就把max和min的值换位置
小偷问题
买卖股票最佳时间
动态规划，设置一个变量记录买入的最小金额
还有可以买卖多次的会用到贪心算法
若可以连续交易
主要找波峰波谷位置
从图形上看
花费最小力气爬楼梯
回文子串
最长回文子串
用一个二位数组来记录从l到r的字符串是否为回文串
record[i][j] = (s[i]==s[j] and (j-i<=2 or record[i+1][j-1]))
如果子串S i j 是回文子串
动态规划中额外数组的含义非常重要
初始化一个二位数组 都为fa'l'se
非空条件判断
遍历方式
初始化也是True
非动态规划解法
双指针
left right
都从某个i开始向两边移动，判断两个字符是否相同
完全平方数
dp[i]表示组成完全平方数i的最少个数
外层循环遍历所有可能选项，内侧循环修改不同的目标平方数
最长上升子序列
01矩阵
从四个方向找最小值
并查集
概念
\t树形的数据结构，用于处理一些不相交的集合的合并和查询问题
基本思路
为每个集合选定一个固定的元素成为代表，表示整个集合，Find(x)返回x所属集合的代表，Union使用两个集合的代表作为参数
步骤
建立新集合，集合代表唯一，为元素本身
返回x所在集合的节点---优化：查找路径上的每个节点都直接直接向根节点
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)
一般思路
预处理 —— 如果集合未排序，则进行排序。二分查找 —— 使用循环或递归在每次比较后将查找空间划分为两半。后处理 —— 在剩余空间中确定可行的候选者。
查找浮点数
实现开根号
两数之和 II - 输入有序数组
判断和与目标值大小，移动指针
寻找旋转排序数组中的最小值
有两种情况，可以判断
先判断有无断点，再比较mid和0移动指针
寻找旋转排序数组中的最小值 II
有重复数字
mid和right的比较并移动指针
寻找比目标字母大的最小字母
right=mid
类似于第一个错误版本
搜索旋转排序数组
找到旋转的下标
在选中的数组区域中再次使用二分查找
回溯法
走不通就退回再走的技术
类似于枚举的深度优先搜索
选优搜索法
Brute-Force蛮力搜索穷举的改进
从一条路往前走，能进则进，不能进则退回来换一条路再走
从根节点出发深度搜索，探索到某一节点时要判断该节点是否包含问题的解，不包含逐层向祖先节点回溯
回溯法求问题的所有解要回溯到根
重点
递归函数
递归算法的出口
放在递归函数的第一行
千万不能放在for或者while循环中
递归函数的参数
这个参数是随着每次的递归操作而发生改变的
不要破坏当前值
才能如果当前操作行不通，回溯到上一步
结果一定要有一个全局参数来保存，只用来保存每次递归成功时的结果
final_queens = []
递归函数的处理
如果当前递归过程的处理参数符合要求，则执行相关赋值或其他操作，然后转入下一次递归，如果下一次递归不能找到出口，就把之前相关赋值或其他操作重置为初始状态
能使得递归进行的约束条件
递归函数就是自己调用自己的函数
经典例题
有限制条件的
八皇后
主函数
记录可行的方式，定义一个空列表
res = []
if n==0: return res
记录不可行的位置
用set
不可行列
col=set()
不可行主对角线
master=set()
行列值相加固定
不可行负对角线
slave=set()
行列值相减固定
存储queen在的列
stack=[]
调用递归函数
返回结果
出口
参数
列数、当前所在行、皇后个数、列状态、主对角线状态、负对角线状态、皇后摆放位置、结果
递归要用的上一次的状态+递归轮数（会变）
循环体
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) font color=\"#c41230\
逐行，逐列搜索
若都不满足条件则回溯
子主题
条件判断函数
if i not in col and row + i not in master and row - i not in slave:
合理的括号组合
记录可行组合
res = [] if n == 0: return res
注意传入参数设置，一定要这样
return res
出口
if len(cur)==2*n: res.append(cur)
if cur == 2*n:# res.append(self.convert(position))
右括号等于左括号
可以看到递归函数中的参数设置和算法效率有重要关系
递归条件
特殊
有两个
只记左括号
数独
无限制条件的
手机键盘上字母的组合
res = [] if len(digits)==0: return res
定义需要记录状态用的列表
无
_map= {'2':\"abc\
深度优先搜索
递归要用的字符串、下一个数字、记录结果的列表
类型
找出所有可能的组合数
找出所有子集
递归和分治函数
在函数内部可以调用自己
包括出口条件判断和递归体的处理
不是所有递归里面都必须写成循环体的形式，不要被8皇后问题蒙蔽了
道理上讲，所有的递归都可以写成循环的形式，但是递归的逻辑更加清晰
分治用递归实现
如果原问题可以分解成若干个与原问题结构相同但规模较小的子问题时，往往可以用递归的方法解决
能用循环的不要用递归
回溯也可以用递归实现
动态规划是递归的升级版本
例子
汉诺塔问题
n = 1 时，直接把盘子从 A 移到 C；n > 1 时，先把上面 n - 1 个盘子从 A 移到 B（子问题，递归）；再将最大的盘子从 A 移到 C；再将 B 上 n - 1 个盘子从 B 移到 C（子问题，递归）
Sliding Window
原理
通过使用特定大小的子列表，在遍历完整列表的同时进行特定的操作，以达到降低嵌套深度
一般通过双指针实现
确定何时移动慢指针，移动到什么位置是关键
快指针要记得每次循环都要+1
排序算法
冒泡排序
冒泡排序就占有优势：它可以在发现列表已排好时立刻结束
在找到最终位置前需要不断交换
代码
获取列表长度
n = len(alist)
双层循环
外层循环
排第几个位置
设置变量代表是否交换
exchange = False
内层循环
两两逐个比较
循环条件
交换位置
确定排序过程中有没有交换
if not exchange: break
没有交换代表已排好顺序
选择排序
提高了冒泡排序的性能
快速排序
分治算法
每次选择一个元素并且将整个数组以那个元素分为两部分
每部分分别进行快排
在原数组上直接进行操作
选择元素
随机选择
选择第一个元素
选择最后一个元素
核心
分区
传入一个数组和一个选定的元素，把所有小于那个元素的其他元素放在左边，大于的放在右边
复杂度
最好
nlogn
最坏
o(n^2）
稳定性
不稳定
数组只有一个数时返回（左指针=右指针）
if l >= r: return
调用本递归函数（两部分都快排）
alist l r
循环判断条件一般以指针<=len()-1
1. 选择传入数组中的第一个数
v = alist[l]
2. 设置两个变量
记录比指定值小的数的位置
j = l
遍历数组
i = l + 1
3. 循环比较
while i <= r: if alist[i] <= v: font color=\"#c41230\
4. 调整指定值的位置
5. 返回下标j
归并排序
分治原理
归并排序中间劈一刀，数组分两半，两边排好序，最后把左右两个合并。就是先局部有序，再整体有序。
在原数组上操作
把两个排序好了的列表结合在一起组合成一个单以的有序新列表
合并函数
合并有序数列alist[start....mid] 和 alist[mid+1...end]，使之成为有序数列
在原数组操作
需要临时复制alist[start:end+1]
稳定
if start >= end: return
取mid
mid = (start + end) // 2
调用本递归函数（两部分都做归并排序）
传入参数
alist
start
end
事件复杂度
o(nlogn)
参数设置
复制传入的一段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)
待比较的值
currentvalue=alist[i]
遍历所有已排好的项
position=i
要插入currentvalue的位置
while alist[position-1]>currentvalue and position>0: alist[position]=alist[position-1] position=position-1alist[position]=currentvalue
return alist
bitedance专题
字符串
无重复字符的最长子串
滑动窗口算法
一个字典记录出现过的字符
一个头指针0
一个当前指针0
最大长度max初始化为0
编写一个函数查找字符串数组中的最长公共前缀
嵌套循环
选一个最短的开始作为外层循环
分别判断每个字符串中的前缀是否相同
字符串的排列是否是另一个目标字符串的子集
滑动窗口
字符串相乘
不许转成数字
进位问题需要记录下来
可以转为用一个数字每位✖另一个数字（需要记录进位）
保存 num2 第i位数字与 num1 相乘的结果
位数越高需要末尾加0
简化路径
用到栈的思想
主要的思路还是跟提取字符串中的单词差不多，用到了栈的思想。首先对path进行处理，提取出有用的词，主要就是用’/‘分割字符串，连续的’/'忽略，然后对提取出的词进行处理，如果是.则不做处理，如果是..则出栈一个字符，最后将剩下的词处理成字符串返回就行了
复原IP地址
s字符串 f记录已经分配好的总长度 idx记录段数（递归出口条件） res记录最终结果
递归出口和递归体
递归体中也有一个循环，每次切1，2，3种可能
数组与排序
三数之和
先排序再使用对撞指针
最大岛屿面积
递归+深度优先搜索
深度搜索每一个值为1的点，然后找到面积最大的一个，记得要把每一个已经搜索过的点置零，避免重复搜索以减少计算量
递归里面判断下标限制和是否为1，符合条件就返回num，不符合返回0
搜索旋转数组
二分搜索法的关键在于获得了中间数后，判断下面要搜索左半段还是右半段
nums[mid] < nums[0]
target 和nums[0]
最长且连续的的递增序列
设置一个max保存长度，一个头指针和一个当前指针遍历
o(n)复杂度
数组中第k大元素
最大堆排序
最长连续序列的长度
使用一个辅助变量，记录序列长度
螺旋矩阵
再双层嵌套遍历
第k个排列
找规律
以1开头的有(n-1)!个，和k比较
1，2开头的有（n-2)!个
朋友圈
查并集
设置一个额外的字典记录每个人所属类别，每次先查找该类别所有人，再把她们的类别改成一样的
合并重叠区间
将所有区间的开始值和结束值都排好序，这样在合并区间的时候会更简单一些，这也是区间问题常用的套路
是否存在一个区间的结束值大于一个区间开始值
先按区间开始值排序
然后用一个RES记录最终结果，用最后一个区间的end与下一个的start和end比较
链表与树
合并两个有序链表
需要四个指针
最后返回+从头遍历加载+两个链表遍历
设计一个链表
设计节点结构和链表结构
反转链表
维护三个变量指针
法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都大的数即存在
除自身以外数组的乘积
不能用除法
左右数组的乘积
堆栈与队列
最小栈
两个列表
在push和pop时注意检查是否是最小的那个数
“以空间换时间”，使用辅助栈是常见的做法
出栈时，最小值出栈才同步；入栈时，最小值入栈才同步。
注意栈是否为空的判断
数组中的第K个最大元素
小顶堆
基于我们建好的小根堆，可以将需要筛选的元素依次与堆顶元素进行比较，若比堆顶大，则置换堆顶，然后对堆进行调整，我们可以得到序列中前N条最大的记录
排序取第k个
数据流中的第K大元素
堆
heapq.heapify(heapq.nlargest(k，list))
有序矩阵中第K小的元素
得到一个递增序列
排序与检索
在排序数组中查找元素的第一个和最后一个位置
引入参数left 如果 left 为 true ，那么我们递归查询左区间，否则递归右区间
寻找峰值
二分法
创新判断条件为比较i与i+1位置
寻找重复数
先排序再遍历比较i i+1
最大数
自定义排序+初始化
二分查找+先判断字符数组里面的字符是否都小于target
循环条件留l<r-1
搜索二维矩阵
可以把二维矩阵看作一个长度为m*n的有序数组，在整个数组上进行二分查找
h4 data-cypress=\"QuestionTitle\" class=\"css-10c1h40-Title eugt34i1\" style=\
标准二分法
至少有K个重复字符的最长子串
递归法
用出现次数最少的字符分割字符串，递归调用，当该字符出现次数多于k返回len
最长连续序列
遍历列表，如果这个数的小一个数在列表里面，转下一个
遍历一次，如果满足该数是最小数才继续看下一个数在不在列表里
用一个变量保存maxlen
数组和字符串
说起数组就要想到： 双指针/额外数组记录 (考虑需不需要排序）
寻找数组中心索引
一般相加为定值的条件的要记得转换成减法的等式判断条件
至少是其他数字两倍的最大数：if all( max>x*2 for x in nums if x!=m)
加1
通过int和str之间的转换求解 .join()
最长公共前缀 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
不使用额外数组，寻找下标之间的规律
先翻转再按照对角线翻转
删除排序数组中的重复项
一个记录所有不重复的值
另一个遍历数组
寻找不重复的数
难点在于指针移动策略的设计
不要为了用双指针而用，要灵活
排序数组其实只要比较相邻两个数就好了啊
一个用来遍历所有，另一个用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
二叉树
搜索与排序
二叉树的最大深度
如何计算深度，每次都返回左右子树中比较大的深度
二叉树最大路径和
深度优先遍历，分别计算左右增益，计算不再向上的增益，比较得到最大和
二叉树中和为某一值的路径
深度优先遍历+回溯算法
每次判断是否为该值，每轮左右节点判断完就pop
二叉搜索树的最近公共祖先
递归方法
退出条件是root值介于两个待找点之间
非递归方法
while root
二叉树的最近公共祖先
在左右子树上搜索两个值
二叉树的直径
深度优先搜索，结合最大深度寻找，每次迭代都比较l+r与原来max值大小
二叉树的右视图
广度优先
层次遍历，每次把该层最右节点加入结果集合中
while循环，每次获取当前queue的大小并遍历当前层所有节点，加入最右节点在结果集合中
深度优先
按照根节点-右节点-左节点顺序遍历，并且记录该层深度，只有大于深度的节点能加入结果中
求二叉树的左叶子节点的和
递归
非递归
如果是左叶子节点则加上去；如果是左节点进列表；如果是右子节点结束；如果是右节点加进去
每日一题
最接近的三数之和
首先进行数组排序，时间复杂度 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)解法
双指针法，哪边短就移动哪边
双指针搜索寻找最优值
腐烂的橘子
多源广度优先搜索
每次增加的是三元数组，除了坐标外需要有一个记录圈数的值
所谓广度优先搜索，就是从起点出发，每次都尝试访问同一层的节点，如果同一层都访问完了，再访问下一层，最后广度优先搜索找到的路径就是从起点开始的最短合法路径。
观察到对于所有的腐烂橘子，其实它们在广度优先搜索上是等价于同一层的节点的。所以一开始可以把他们都加到队列中
用一个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)
需要想一想切分规则
字符串的最大公因子
最大公约数的概念
时间复杂度：O（（len1+len2）o（ gcd（leni，len2）），其中o（n）表示n的约数个数，gcd（a，b）表示a和b的最大公约数。我们需要线性的时间来两两比较拼接后的字符串和被比较的串是否相等空间复杂度：O（lem+lem），每次枚举比较的过程中需要创建长度为lem和lem2的临时字符串变量，所以需要额外O（em1+lem2）的空间
要求的字符串长度必然是两个输入字符串长度的公约数，而且是最大公因数
也是就取余数为0
再判断由该字符串拼接的和原来两个字符串是否相同
小技巧就是因为求最大所以从后往前试探约数
多数元素
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]
求所有子集
矩阵重叠
判断投影是否交叉
使数组唯一的最小增量
暴力法通不过
面试题62. 圆圈中最后剩下的数字
约瑟夫环
数学问题
总结一下反推的过程，就是 (当前index + m) % 上一轮剩余数字的个数
水壶问题
贝德定理
ax+by=z 有解当且仅当z是x和y的最大公约数的倍数
单词压缩编码问题
其实是找到所有不是其他单词后缀的单词
可以通过维护一个后缀树（用字典）
打印括号组合
接雨水
可以用两个数组保存leftmax和rightmax
我的思路好清奇，先确定一个凹形结构，再确定能容水量，会嵌套很多循环
不要啥都想到动态规划，多动动脑子
双指针left right 缩小距离就要增加柱子高度
丑数
难点在于查找第n个丑数不一定只查找了n次，要是一个一个找的话
可以用三个指针分别寻找*2/*3/*5的大于当前最大值的最小值，再将对应指标+1
这样可以保证事件复杂度o(n)
分析递推公式！！！
螺旋打印
根据边界打印，即将元素按顺序添加至列表 res 尾部；边界向内收缩 11 （代表已被打印）；判断是否打印完毕（边界是否相遇），若打印完毕则跳出。
四个边界条件的分析很精妙
每次边界向内收缩并且判断上下和左右边界是否相遇
栈的压入弹出序列
模拟栈的压入弹出过程：使用一个栈，开始为空持续压入pushed数组元素到栈中，直到栈顶元素和popped首元素相同，开始弹出，若弹出后还是匹配，继续弹出最后判断栈是否为空，空则true，否则false
面试题44. 数字序列中某一位的数字
先判断n处于哪一个位数里面，再判断处于哪一个数字里面
最少移动次数使数组元素相等 II
绝对值和的最小值
两数相加
本题的主要难点在于链表中数位的顺序与我们做加法的顺序是相反的，为了逆序处理所有数位，我们可以使用栈：把所有数字压入栈中，再依次取出相加。计算过程中需要注意进位的情况。
carry=carry+a+b//10 cur=carry+a+b%10 先判断a b是否为0
逆序构建链表
ans=None node.next=ans ans=node
用carry参与计算，注意最后要加一个carry的判断
python可以使用字符串处理
URL化
S.split()默认去掉空格
'%20'.join(S[:length].split(' '))
贪心算法
跳跃游戏
维护一个最远到达距离，只要小于这个距离就是可以到达
要从全局考虑，不要太执着于细节，有几个0啥的
跳跃游戏2
如果我们「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。
在具体的实现中，我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1
用动态规划超出时间限制了
合并数组
我们用数组 merged 存储最终的答案。首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。
斐波那契
统计重复个数
寻找循环节
好难啊，用hash表记录
N*3网格涂色
动态规划+排列组合
有k个奇数的连续子数组个数
前缀和+差分
用一个字典记录每一个前缀和出现的次数，每次遍历都记录答案
[j..i] 这个子数组里的奇数个数恰好为 kk」这个条件我们可以转化为 pre[j−1]==pre[i]−k
pre[i]=pre[i−1]+(nums[i]&1)
数学方法只记录奇数位置，但是边界处理要注意
归并排序扩展-数组的逆序对
数组的逆序对刻画数组混乱程度
那么求逆序对和归并排序又有什么关系呢？关键就在于「归并」当中「并」的过程。
在每次合并的时候计算逆序的个数
情侣牵手
异或操作选择第i个人的情侣
会保证偶数编号的情侣得到比其小1的奇数编号，奇数编号得到比其大一的编号
row[i+1]==row[i]^1
合并k个排序链表
先合并一个大数组在整体快排
两两合并
新21点 概率论和动态规划反序求解
7月加油
靠 归并排序求逆序数也太难了吧
逆序的动态规划 找好初始值
找到奇数个个数的元素
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 的「一比特数」
数组中不重复的两个数
异或操作
相同数字异或结果一定为0
判断字符是否唯一
位运算
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次然后对下标取余数
删除字符串中的重复相邻字符
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();}}
逆波兰表达式
遇到运算符就把栈顶两个元素出栈，执行运算，得到的结果再入栈的原则来进行处理
基本计算器
使用栈记录每次当前数字的正负号，括号内部的符号也受到括号前符号的影响
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;}}
队列的最大值
比实现最小栈更难一些
因为队列和维护最大值的栈出队顺序是相反的
所以最好也用一个队列去维护最大值
在一个数之前入队的数中，比它小的数出队对最大值没有影响
只需要保证辅助队列中的顺序是递减的
深度优先或者广度优先搜索
二维动态规划
二维区域和检索 - 矩阵不可变
记录每一个位置的前缀和，一维或者二维
注意加减关系别搞错
超级零
「最短路」的读者应该知道，我们所说的「超级零」实际上就是一个「超级源点」。在最短路问题中，如果我们要求多个源点出发的最短路时，一般我们都会建立一个「超级源点」连向所有的源点，用「超级源点」到终点的最短路等价多个源点到终点的最短路。
一开始我们就将所有的 0 加入队列，它们的初始距离为 0。这样以来，在广度优先搜索的过程中，我们每遇到一个 1，就得到了它到「超级零」的距离减去一，也就是 这个 1 到最近的 0 的距离
关键怎么设置状态转移
初始值一定要inf
设置初始值0
对于矩阵中的任意一个 1 以及一个 0，我们如何从这个 1 到达 0 并且距离最短呢？根据上面的做法，我们可以从 1 开始，先在水平方向移动，只要与 0 在同一列。随后再在竖直方向上移动，直到到达 0 的位置。这样以来，从一个固定的 1 走到任意一个 0，在距离最短的前提下可能有四种方法，故有4个状态转移函数
我想到了这种方法，但是不知道怎么处理上下左右四个位置，就想要用两个dp存取最小，但是边界难处理，这道题直接用一个数组，每次比较上下左右和自己，很巧妙的动态规划
机器人的运动范围
广度优先搜索，只考虑向右和向下方向，需要一个额外的数组保存该方格是否已经被遍历过的信息
递推：用set保存满足条件的格子，每次只需要判断左侧和上方的格子是否已经在集合中
数据结构设计
设计哈希集合
链地址法设哈希表的大小为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; }}
设计哈希映射
类内设计一个内部类
设计停车系统
为每种车维护一个计数器，初始值为车位的数目。此后，每来一辆车，就将对应类型的计数器减 1。当计数器为 0 时，说明车位已满
模拟
也可以使用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; } } }}
三个易错点
矩阵下标
循环范围
判断条件
回溯法小专题
一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试
组合总和
递归回溯法
组合总和二
有重复的数字，每个数字用一次
转换为不重复数组，用一个字典记录
组合总和三
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
回溯退出条件
分割回文串
确定好回溯函数需要的参数
每次都要判断分割出来的是不是一个回文串
用【：：-1】
退出条件
if index == len(s): res.append(temp.copy()) return
动态规划+回溯
用一个二维数组记录从i到j位置是否是回文串
每次都保证i前面的是回文串并且加入临时数组，然后更新j+1的位置为新的i，继续搜索
一般这种需要搜索每一种情况的都要用到index来作为退出条件，意思是搜索位置
比二重循环灵活
java代码
需要判断每一种遍历结果是否符合条件就用回溯剪枝，无法直接用循环得到，因为不确定是几重循环
全排列
有重复或者没有重复元素
span style=\
无重复字符串排列组合
思路：假设你有abc的所有排列。你怎么用它来得到abcd的所有排列？
你可以通过计算abc的所有排列，然后在每个可能的位置插入d，从而创建abcd的所有排列。
要生成abcd的所有排列组合，请选择每个字符（a、b、c、d）作为首字符。排列剩余的字符并追加首字符。如何排列剩余的字符？使用遵循相同逻辑的递归过程
动态规划背包小专题
组合总和 Ⅳ
求有顺序的排列数量
完全背包，可重复使用元素
外层遍历target，内层遍历元素
零钱兑换
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
外层遍历元素，内层遍历target
完全背包无顺序
策略为：从基本情况没有开始，一一添加。对于每个添加的***，我们从金额 0 到 amount 递归的计算组合数量。算法：以基本情况没有***开始组合数量。dp[0] = 1，然后其余等于 0。遍历所有***面值：对于每个***，我们将从金额 0 遍历到 amount：对于每个 x，计算组合数：dp[x] += dp[x - coin]。返回 dp[amount]
dp[x]表示构成金额x的硬币最少数量
不同的子序列
困难
栈和队列
最大队列
数据取出和输入的端不一样
数据取出和输入端一样
if not self.stack: self.minlist.append(x) else: if x<=self.minlist[-1]: self.minlist.append(x) self.stack.append(x)
队列与广度优先搜索
王子救公主
指定起点和终点
栈与深度优先搜索
矩阵中的路径
字符串解码
每次 [ 入栈另一个元组，保留之前的字符和倍数
股票最大收益
算法
on
前缀和
差分
桶排序
队列
bfs/dfs
拓扑排序
欧拉路
Tarjan求连通分量
KMP
字典树
o(logn）
排序
二分
快速幂
最大公因数
ST表
线段树
树状数组
二叉搜索树
归并/快速排序
最短路
最小生成树
凸包
o(nm)
n个物品m大小
匈牙利匹配
o1
哈希
o(2^n)
搜索
状态压缩
牛客网
获取输入输出
单行输入
input_str = raw_input(\"\
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()
切两刀获得最大奖金
两个指针，注意应该取最大奖金
注意输入输出
最大乘积
每次循环都判断两种情况
max*second*third
把第二大给第3大，第1大给第2大，第一大赋给新的值
打印蛇形矩阵
和之前的螺旋矩阵一样的
除了设置四个边界
可以设置偏移量d=(d+1)%4
外加一个判断是否已经存入数据的矩阵
凑1-m所有面值的硬币最少需要多少
分别确定每个面值需要多少
打怪兽获得武力值消耗金币
修改矩阵
黑白格子实现需要改多少格子数
奇数格子 偶数格子
根据坐标和判断
分别保留奇数格子和偶数格子中出现次数最多的两个数
然后枚举
分为奇偶格子数相等或者不等的情况
最小修改就是最大保留
格子染色
合并区间问题复杂化
横向和纵向都是两个区间合并
然后再减去交叉算重复的点
n*n操场每隔n+1标记一下，问标记不重复至少多少次
整体考虑
（n+1)x=n*4*y
x表示标记个数-1，y表示周长的整数倍
先求左右分别的积
一定是（n+1)和4n的最小公倍数
最小公倍数*最大公约数=a*b
通过转换成最大公约数计算最小公倍数
再求x ans=x-1
乱序字母序列去重以后开头的最小字典序
依次考虑字典序的字母，判断这个字母能否成为第一个字母，也就是前面的数字能不能被删掉
可以把这个字母后面的字母维护一个hashset然后判断前面的字母是不是在后面的set中
换种思路
避嫌抢劫
相隔d的两个点的最大价值和
单边滑动窗口
外层遍历指定每一个要抢劫的银行
内层在给定银行条件下，寻找间隔d的点的最大价值
用一个变量记录每次的ma'x'x
括号交错方式
括号序列
过程中cnt>=0
结束cnt==0
最长公共子序列
卡特兰数
dp
状态表示
集合
第一个序列的前i个括号和第二个序列 的前j个括号拼在一起获得的合法的序列集合
属性
最大最小值或者数量
集合划分
最后一个位置属于哪一个序列为标准
机器人能否回到原点
模拟方法
根据坐标位置判断能否回到原点
0 条评论
回复 删除
下一页
