Algorithm
2020-03-02 10:00:00 +0800
做题路径-重要算法思想
##EASY：
- 两数之和，目标值是数组中两个数字的和，求这两数字
用dp保存遍历结果，遍历数组，获取目标值和遍历值的差值，在dp中找是否存在该值 =N 排序，双指针不断更新靠近目标值 =NlogN
- 罗马数字转整数
遍历输入串，将罗马数字转化成数字并append到一个暂存list中，下一次判断list最后一位是否和罗马数字相减要求的一致，pop掉，并将新数字减掉1 10 100，最终对list中的int相加
- n以内所有素数的数量，n是不是素数
埃式筛法，从i**2开始+=i，筛掉，最终留下的就是全素数集合 无重复的欧拉筛法
- 合并两个有序链表
比对l1和l2的大小，将最小的放在新链表的next上，更新l1或者l2，直到其中一个链表为空 while l1 and l2；最终返回新链表的next。T = M + N
- 删除排序数组中的重复项
快慢双指针，快慢从0 1出发，如果快慢不相等，慢指针每次都更新为快慢不相等的慢的下一个，也就是慢指针前面的数没有相等的，如果相等，停止更新慢指针，直到找到下一个不相等，开始更新慢指针的值，也就是快指针向前移动一次慢指针更新一次 T = N S = 1
- 实现 strStr() 返回子串开始的索引，空串返回0
一次遍历，更新第一个发现匹配位置的索引，匹配后更新，不匹配更新为-1，一直到剩下长度不足找到needle，或者匹配后i-第一匹配点为len needle
- 最大子序和，找到序列中最大和的自序，N，贪心、滑动窗口、分治
贪心算法也可以求解，局部最优解，需要两个变量1存储当前窗口移动到的位置的最大值，第二个存储到当前节点为止的最大值，每次比较当前值和更新后的窗口值的大小；滑动窗口：窗口在数组上滑动，在滑动的同是，用常量记录一些状态，如当前的窗口值或者当前值，或者其和差等；这里的窗口记录的是到当前窗口处序列和或者重新开始序列的值，另一个变量保存当前最大和； 本题的动态规划其实就是贪心算法，贪心每次记录的window值就是到当前节点的最大子序列和，包括当前节点哦
- 合并两个有序数组, m个n个元素长度 m数组 > n数组
双指针比对法，从尾部向前每次比对m和n中最大的一个数放在m数组尾部，这样需要第三个指针来记录当前尾部更新的位置，当n数组全部比对完成后，就可以返回答案了
- 对称二叉树，左右互为镜像
递归或者迭代的广度，然后得到广度的遍历的每一个level的结果后，检查数组是否是镜像的； 递归，从root的左右子树开始，检查左右val是否相等，然后递归在左的左右，和右的左右
- 路径总和
迭代的广度优先遍历，使用队列存储一个tuple元组，元组的0位置上放广度遍历的记录值，1位置上放当前路径到该点的差值，如root节点存储sum-rootv，当每次到达叶子节点时，判断节点的sum是否为0
- 广度，队列，记忆
- 验证回文串
- 双指针，将不符合条件的字符都跳过，值比较字母和数字，知道指针相遇或是指针重叠；
- 相交链表， 两个链表有相交的部分，找到相交点
- 双指针，分别从两个链表同时出发，先遍历个字节点，完成后从对方节点再开始遍历，如果相遇就是相交起始点，m + k + n = n + k + m
- Excel表列名称
ASC中A从65开始，a从97开始，python中分别有 ord 和 chr 函数来转换，本题其实就是一个进制问题，将数组转换为字母的进制问题，但是因为本题没有0，所以z和A0都可以表示26的时候要选择Z，
- 始值是字符串，对26取余数，当余数为0的情况下，证明此时必须保留最后一位Z，所以将m改为26用来转Z，更新n为n-26，后续再得到n=n/26，循环开始前要检查n是否大于26，否则直接转n；
- Excel表列序号
获取每个字母，ord-65+1获取十进制数的大小k，然后k*26**m m次方就是总字母数-1-i for i in range(l): r += (ord(s[i]) - 65 + 1) * (26 ** (l-1-i))
- 旋转数组， 右移动k步。S 1 原地
- i i+k交换，记录i，并填充 N N
- 原地且空间为1，循环替换，0 - k - 2k - 3k 当替换次数到达数组长度是，证明所有替换完成，记录每次替换的开始点，如nums0，当没有完成所有替换的同时且循环又一次回到了开始点，则下一个开始点更新为cur+1，且下一个cache点也为nums i+1；tmp = nums[cur] nums[cur] = cache cache = tmp
- 位1的个数
while n > 0: result += 1 n &= n - 1
- 对于一个二进制来说，最低位的1，一定会因为 n - 1 而变成0，这时候对n和n-1做与操作，，就可以得到去掉最低位1的结果
- 计数质数，小于n的所有素数的数量
埃式筛法： 待筛开始数，为2到根号n，每个数开始筛的起始数为i**2，然后每次+i； 时间复杂度：nlognlogn -> 素数分布定理 + 微积分基本定理 求解
if n < 2: return 0 # visited = [False]*n # ans = n - 2 # i = 2 while i <= n/i: if not visited[i]: j = i * i while j < n: if not visited[j]: ans -= 1 visited[j] = True j += i i += 1 - 反转链表
# 指针操作，需要留意暂存next和更新last已经current，1. 暂存next 2. 当前的next为cachelast 3. cachelast更新位当前 4. 当前为暂存的next
- 删除链表中的节点
和next交换值，并更新next为next next t = node.next; node.val = t.val; node.next = t.next; t = None
- 字符串中的第一个唯一字符，只有小写字母
第一次遍历n的字符，用哈希表更新count，用一个新的数组保存字母顺序，第二次遍历数组取hash值，当值为1就返回，这样时间是N空间是两个26所以是1
- 压缩字符串，原地算法
- 实现空间复杂度为1的原地算法 # python 使用暂存值存储索引值和重复字符的索引，并存储重复字符的字符 一个读一个写指针同时出发，当遇到于前一个字符相同的字符是写指针暂停，读指针继续，当遇到第一个不同字符时，写指针写入压缩长度，读指针+1并写入新值，读指针继续读取和计数，如果没有重复就前移且写指针不断写入并前移，知道再次重复为止；最终的结果就是原地到读指针的位置；
##MIDDLE：
- 两数相加，逆序数字链表，相加得到新链表 (2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8
数学问题，while循环，得出每次相加的和，并更新新的l1，l2，如果发现其中一个链表比另一个短，和为存在值；更新新链表如果有进位下一个next的val就设置为1，下一次也要加上 T = max(m,n) S = m+n
- 最长回文子串，最长回文子串 ABA AA
中心扩展法，n个ABA类中心，n-1个AA中心，顺序遍历字符串，将i i和i i+1分别由中心扩展求其最大会回文长度，然后在外层循环中更现要返回的最大长度和坐标索引，T=N**2 S=1 动态规划法和中心扩展一样T更大S，Manacher极其复杂
- 字符串转换整数 (atoi)，符合规则，rstrip前面空格，以+-号或者数字开始，只保留数字
直接处理，先rstrip前面空格，遍历读取，+-加到结果串，数字加到结果串，遇到不是数字break，要求要在32位int范围内，所有可以转为64位int做判断，超过就返回边缘 T=N
- 三数之和，找到所以三元组符合他们的总和是目标值=0
先直接排序，这样将时间锁定在nlogn，三个数字和为0，必然有一数字小于等于0，遍历所有小于0的数字，然后参考两数之和排序的做法，从i位置前面的一个位置和最后一个位置各自一个指针，直到相遇，找他们三个数字和为0的数字，（如果遇到相等的数，直接更新指针）；nlogn 排序双指针法
- 有效的括号，这种左右两个对称元素的题目，一定要想到用栈，栈先进后出，可以判断括号闭合后，直接都出栈
栈顶存储的，就是最新的左括号，如果栈为空来右括号，直接break，如果不为空，比对栈顶元素和遍历元素是否是同一种括号，是就ok，否就break
- 两两交换链表中的节点
指针操作容易出错，使用递归，暂存next指针，递归更新当前指针的next为暂存的next，更新暂存的next为curr 例如：1 - 2 - 3 - 4，暂存2，递归更新1的next为3的递归，2的next设置为1，递归返回2 第一步暂存1.next 也就是2，第二步更新1的next为2的next，这里就是次操作的递归，第三部更新暂存的2的next为1 思考： 先换第一个和第二个，然后在思考后面怎么换
- 全排列，递归回溯，backtrack
123 -A- 123，213，312 -backtrack- 23 32，13，31，12，21 – Afor循环将start位置和所有位置swap，然后回溯对剩下位置的数做同样的操作（start+1），1次回溯完成后需要将start和swap在换回来，保证下一次swap操作无误
- 全排列 II，有重复数字的全排列，需要去除重复的排列
和全排列I同样的循环+回溯+归位，只需要在每一次循环前定义一个set，将每个遍历的数字放入set，如果出现重复直接continue
- 旋转图像，matrix顺时针90度旋转，原地算法
转置矩阵，这表示上下和左右调换，然后在左右翻转 每圈旋转，圈数等于n/2,每圈旋转 T n**2
- 螺旋矩阵，用顺时针螺旋的方式将矩阵输出为数组
模拟旋转，暴力将原矩阵上右下左切除，最终留下的一个元素就是tail
- 跳跃游戏，每个元素代表能够跳的最大步数，求能不能跳到末尾元素
反证法，不论多少种方式，只要能到末尾就是合法，所以从末尾元素往回跳，如果能到起始元素就，那就表示True 回溯，模拟所有可能性，动态规划在回溯的基础上更新每个点能否跳到末尾，记录memo中，这就是记忆法 检查每一坨0是否能被跳过
- 合并区间，这题和箭射气球异曲同工，都是要把区间进行合并
必须先排序在做合并，因为如果不做排序需要每次都把剩下的所有区间遍历一次做对比，如果排序之后，就可以直接顺序合并区间，排序的key使用区间的左边界； 气球的问题也类似，因为气球是每次寻找最小集合来射箭，如果不做排序那么有可能会无法处理边界的气球，导致无法达到最优解
- 简化路径
本题，直接用split函数，直接可以忽略所有的多///和空，包括单点.,用stack存储路径字符，如果遇到双点则直接pop出来前一个目录，最后将join
- 矩阵置零，一个点为0将所有行列设置为0，原地算法
不使用m+n的空间而使用常数空间，本题就是要做记录，然后置0，记录0点所在的行和列，最后统一置0，时间上m*n，如果使用常识空间那就直接用第一行第一列进行记录，但是开始前先用常识记录第一行第一列是否自己有0，最后统一置0
- 颜色分类，国旗颜色问题，只有012的序列原地排序
双指针边缘监控法，前面的指针放在0的下一个左边，后一个指针放在2的前一个左边，也就是保证指针前后符合要求，cur指针遍历数组，遇到0和前指针互换且指针都前移，遇到2和后指针互换且指针都后移，知道cur和2指针相遇；
- 单词搜索，在二维网格中搜索单词，上下左右相邻字母连接
类似图的深度优先遍历，一次找到和单词中第一个字母相同的字母，从第一个开始就开始用“递归”遍历，当未找到某个字母的时候，回溯在前一个字母，直到回溯回第一个字母还是没有找到结果，就开始对第二个找到的字母做同样的递归，递归需要注意：边界条件和return点，return决定了回溯的情况；对于已经找到的结果可以存储在栈中，python使用list来模拟栈；记得要标记已经使用过的点；
- 解码方法 A-Z的字母由1-26编码，给一个只包含数字的非空串，解答出所有可能的解码数；关于0，0只有在前面是1和2的时候才有意义，如果是0分割了前后的数字则，返回0；
动态规划：1. dp保存到点i为止出现的所有可能之和 2. 通过21～26和11～19可知，对于这种情况的i处的状态就是 dp[i] = dp[i -1] + dp[i-2], 其他情况就是 dp[i] = dp[i - 1] 3. 一次遍历并将条件带入状态转移方程，最终得到结果，特殊情况是0值的考虑，如果是不符合条件的0直接返回0，这样的串无法解码
- 二叉树的中序遍历，涉及知识点：二叉树的广度优先 深度优先-先中后 栈 队列 迭代 递归
二叉树的深度+递归，先：append 左递归 右递归，中：左递归 append 右递归 后：左递归 右递归 append 二叉树的深度+迭代，栈，用栈来保存每次遍历的节点，每次用while循环找到最后一个左节点
- 先：同理，将获取值放在找左和取右前 while current: stack.append(current); current = current.left \N current = stack.pop(-1) ###result.append(current.val)### current = current.right
- 中：stack不为空：pop，然后while 循环来找到最左节点，全部push入栈，然后pop出第一个，将其值append到结果，再将其右子树push入栈或者用一个变量暂存右子树，为空就直接pop
- 后：Append操作在迭代中的位置
- 先：pop出第一个值放入result，然后pop出的存在就是先右后左入栈
- 中：先找最左，全都入栈，出第一个，给result，然后将cur更新为右
- 后：和先相同，但是改为先左后右，最终在reverse结果串
- 二叉树的广度遍历，层次遍历：
- 递归法：于深度遍历的情况相似，就是需要传递一个level参数，这样在每次递归的时候只要更新level+1就可以，按照顺序将result[level].append(val) 当前level初始化前，需要先加入一个空串
- 迭代法：用队列的方式保存当前的读取的节点，步骤 1. 从队列pop出第一个元素 2. 将其左右儿子放入队列，如果不存在，则current_null += 1, 维护一个当前为空的数量 那怎么读取呢：0. 检查当前queue中节点数是否=当前level数的二次方 - last_null *2 - current_null, 符合条件的情况下就是可以完整的读取一个level了，当然每次还要更新last_null = last_null *2 + current_null; current_null = 0
- 验证二叉搜素数，左边叶子小于根，右边叶子大于根，二叉搜索树的中序遍历就是有序数组
直接左中序遍历，当有小于排序数组最新点的数字时，返回False，如果用递归的话这里的return要特别注意，左右节点都要检查，且每个节点递归如果返回False，也返回False
- 二叉树的层次遍历
二叉树的广度遍历，并用level记录高度
- 二叉树的锯齿形层次遍历
递归，迭代，与二叉树的广度遍历相同的逻辑，就是检查当前level的奇偶，然后做insert或者append操作
- 从中序与后序遍历序列构造二叉树
从后序遍历中的末尾元素可以找到第一个根结点，找到该节点在中序遍历中的位置，此时该位置前的元素为左孩子，后面的元素为又孩子，递归继续对前后两个孩子进行同样操作，难度： 1. 树的还原 2. 递归返回 代码实现：1. 从后序遍历中pop给cur，并获取val， 生成新节点node，2.然后在中序中获取cur的index，3. node right先对右子树进行递归，再对左子树进行递归，因为是反后序遍历的顺序，递归时传入左右边界参数， 这里传入的参数有两个作用，第一用来限定递归次数也就是分割次数，第二使用来判断是否已经到达叶子节点； 0 判断方式就是如果左边界比右边大，那就证明左右边界分割到了同一个点； 时间复杂度分析：本题的时间复杂度设计到主定理，每次将问题分为了2个子问题的规模，并且每次划分为左右子树n的规模变成n/2，由于fn是渐进函数，包含分解问题的代价，但是fn是小于 n的，所以时间复杂度为On
- 二叉树展开为链表， 给定一个二叉树，原地将它展开为链表
从右向左的后续遍历 6 5 4 3 2 1，用一个常量记录last值，把last给当前节点的right，并把当前节点左置空，last更新为当前节点
# 1 # / \ # 2 5 # / \ \ # 3 4 6 - 填充每个节点的下一个右侧节点指针 – 完全二叉树、二叉树
- 还是广度遍历，对每个level的节点进行遍历设置next，除了每个level的开始节点为，其他节点都要在pop完成后left right set null，level开始节点如果存在左右子树，就将右置空
- 从右向左的广度遍历，在一个level的list内的就暂存到下一点将其设为next，检查nextOBJ是否为空，为空赋值，不空获取为next，并更新
- 二叉树中的最大路径和 在二叉树中，求可能的最大路径和
边界情况：如果节点为空，那么最大权值是 0 。 对该节点的所有孩子递归调用 max_gain，计算从左右子树的最大权值：left_gain = max(max_gain(node.left), 0) 和 right_gain = max(max_gain(node.right), 0)。 检查是维护旧路径还是创建新路径。创建新路径的权值是：price_newpath = node.val + left_gain + right_gain，当新路径更好的时候更新 max_sum。 对于递归返回的到当前节点的一条最大路径，计算结果为：node.val + max(left_gain, right_gain)。
- 深度遍历计算每个节点的权值
- 复制带随机指针的链表
回溯记忆法，用递归回溯的方式扫描整个链表，并存储已经创建的拷贝；
- hash_map用来保存当前访问的节点深拷贝出来的新节点 1. hash_map 中保存了当前访问节点和初始化的拷贝节点，如果不存在则证明该节点还没创建，拷贝值创建新节点， 并存入hash_map 2. 在已经拷贝过的node里找到了已经新建的node就要直接返回，否则会导致循环递归，最终达到递归上限，3. 同样用递归创建新节点的next，和random，如果存在直接返回；
- 环形链表 给定一个链表，检查是否存在环
快慢指针游戏，快指针一次走两步，慢指针一次走1步，如果快指针的next为慢指针，或两指针再次相遇，则证明有环；没有的话，指针都会指向NULL
- LRU缓存机制 get(key) - 如果(key) 存在于缓存中，则获取密钥的值（总是正数），否则-1。put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
解法1. 使用python标准库中的driectdic有序字典，新add的元素在末尾，每次被访问的也geng更新到末尾，如果超出capacity就pop0 解法2. 需要一个有序数据结构，不需要遍历就可以获取对象，并调整顺序，并且可以直接add del，双向链表，初始化capacity和head tail的双向链表，新添加的元素放在head之后的第一个，get一次的元素直接找到它并更新到head之后第一个，所以约接近尾部的元素就是超出容量时要删除的，也就是tail的pre指针指向的对象； LinkedHashMap
- 翻转字符串里的单词, 按照单词翻转串
解法1: 先用strip，然后split，然后反向读取list在转为字符串 解法2: 不使用额外n空间，先strip，然后在字符串前加两个空格，然后读取到第一个单词，将开始坐标和单词结束坐标的字符加到字符串末尾并删除，依次对所有单词做同样操作，直到找到末尾坐标（后面出现两个连续空格） 解法3：不使用额外n空间，原地算法，ij双指针，交换每一个元素，原地完全翻转字符串，然后开始遍历，将每一个单词翻转成正向的，还是两个指针，第一个记录每个单词的开始位置，第二个到单词的末尾，开始交换；On O1的原地算法，题目之所以要求使用C语言是因为C的字符串是Char数组结构，可以不开辟新的空间而改变值，其他语言可能是静态量无法直接修改；
- 寻找旋转排序数组中的最小值
直接遍历，找到最小值，返回时间是On 复杂度降低到 logn，做法是对数组进行二分搜索，每次搜索只保留之后，将中间点和数组第一个元素比较大小，如果大，那就是最小值在右侧，如果小则在左侧，直到找到第一个小于其前值的元素，因为翻转后的最小值一定在二分查找分出来的两个序列中，时间复杂度可以从n降低到logn 本题和在一个数组中搜索第n大的数相似，也是使用二分搜索，快速选择法，每次可以确定一个第k大的数，只需要判断第m大的数在其左还是右就可以
- 寻找峰值 - 找到数组中所有波峰，找到一个就可以 logN
把数组看作二维图表，使用迭代的二分查找或者递归的二分搜索的方法，解法： 1. 递，找出二分搜索的中间，比较是否 中间点的值大于其后一个值，如果大于则证明，中间点位于一个局部下降的位置，那么它左边肯定有至少一个peek点，那么继续对左边做二分搜，如果，中间点的值小于其后面一个值，那么中间点在一个局部上升位，那么它右边肯定有一个peek，递，最终l r相等就可以得到结果；
- \ down from middle to middle + 1 就证明左边绝对有波峰，/ up from middle to middel +1 就证明右边绝对有波峰 -如果找出所有的波峰，那就只能N了
- 比较版本号 .分割，可能有前导0
用split从.分割成数组，然后按照max m n遍历，短的数组，初始值为0，转int比大小 T = O(max(m,n)) S = n, 直接用串比较可以降低空间
- 二叉搜索树迭代器
首先根据题意，要实现的是一个每次取出最小数的操作，所以，对于一个二叉搜索树，只需要进行中序遍历即可得到一个排序序列 但是要求空间复杂度只能小于等于这个树的高度，且取出和查看都是O(1)
- 对于此要求，第一对树只进行中序的遍历的左边，并将值存入一个栈中
- 每次取出的时候需要对pop出来节点，查看其是否存在右子树，如果存在则将其右子树进行递归，找到下一个最小值
- 递归的过程中，将找到的值push入栈 时间复杂度上 next操作的平均时间复杂度近似为1，最差时间复杂度依然为N
- 岛屿数量 – 二维数组中找到所有的联通的1，图的遍历， 图的基本算法
BFS - 本题为计算图中的联通图的总数，在一个无向图中找连通分量的数量 BFS，遍历数组从第一个点开始找到第一个不为0的点，以该点为广度优先的起始点，广度优先使用queue保存每个符合条件的1的坐标，按照左上右下的顺序，将符合条件坐标add入queue，并将该点的值设置为0，迭代下一次从队列中poll元素继续order > left - up - right - down 如果只再poll元素出来的时候再将其配置为0，会导致，元素重复添加，导致进入死循环；所以记录完成符合条件的坐标后，直接将状态改变；
- 实现 Trie (前缀树) - 字典树 相似题目：
- 添加与搜索单词 - 数据结构设计
- 单词搜索 II HARD
- 数组中两个数的最大异或值
实现方式：初始化一个字典，每次有新单词更新字典树并添加末尾元素 for a in word: if a not in tree: tree[a] = {}; tree = tree[a] tree[”#”] = “#”，搜索单词只要能找到结束符就返回true，找前缀无需匹配#，只要能找到就返回true
- 打家劫舍 I II III 题目条件I：不能偷相邻的房间 II：环，最后一间房和第一件也是连在一起的 III：二叉树，不能偷相连的两个
I：动态规划 1. dp状态定义， 将nums中的到当前天的最大金额为dp[i]，每次只有偷和不偷的两种情况 2. 根据要求，不能连续获取数字，可以相隔1到n-2个房间获取，dp[i] = max[dp[i-1], dp[i-2] + nums[i]], 每次遍历获取一个max II：需要考虑条件为首元素和末尾元素相连，那么只有三种情况，偷首不偷尾，偷尾不偷首，都不偷，所以沿用I中的方式，计算两次，第一次1到n-1，第二次0到n-2 III：动态规划 + 二叉树的深度遍历:
对于二叉树，满足条件的情况下，必须每次抢劫都隔一层 0 1 1 1 0 0 0 0 0 0都是可以抢的 所以抢了根节点就不能再抢他的字节点 深度遍历，从左下开始，求每个根节点要抢和不抢的大小 dp: [not_r, r] dp[r] = ndoe.val + dp_sub_l[0] + dp_sub_r[0] 必须是其和其子节点不抢的和，抢了自己就不能在抢自己节点 dp[not_r] = max(dp_sub_l[1],dp_sub_l[0]) + max(dp_sub_r[1],dp_sub_r[0]) 如果该点不抢的话， 它自己的字节点可以抢也可以不抢，抢不抢它的左节点取决于，抢的利润和不抢的利润，所以这里右边也一样
def dp_recursive(node):
if not node:
return [0,0]
dp_sub_l = dp_recursive(node.left)
dp_sub_r = dp_recursive(node.right)
dp_r = node.val + dp_sub_l[0] + dp_sub_r[0]
dp_not_r = max(dp_sub_l[1],dp_sub_l[0]) + max(dp_sub_r[1],dp_sub_r[0])
return [dp_not_r, dp_r]
return max(dp_recursive(root))
- 数组中的第K个最大元素，找到未排序数组总第k个最大的数
一次快排，最终达成的目的就是在序列的n-k的位置， 快速选择，与快速排序类似，快速选择算法在平均状况下有着不错的表现，但是对于基准值的选择十分敏感。如果基准值选择上佳，搜索范围每次能够指数级减少，，这样一来所耗时间是线性的(即O(n))。但如果基准值选择非常不好， 实现，找到基准值，完成第一次排序，检查当前基准值的坐标和n-k的大小，如果小，在左侧继续排序，右侧同理，左右选择函数和排序函数可以分开写；排序可以双指针替换或者单指针比较；
- 最坏时间复杂度 О(n2) 最优时间复杂度 О(n) 平均时间复杂度 O(n) 最坏空间复杂度 O(1)
- 用栈实现队列
Queue, Stack 一进一出两个栈实现队列，in用来add新元素，peek和pop操作，把in中的全部pop出来然后取最后一个剩下的push入out，获取到值后，在把out中的push入in
- Stack: push to top, peek/pop from top, size,is empty
- Queue: push, pop, peek, empty
- 二叉搜索树的最近公共祖先
对于找到二搜索树的最近祖先，考虑四种情况，1.p或者q就是root 2.root在p q之间，直接返回root 3. p q都在root左边，更新root left 3. p q都在root右边，更新root right
- 二叉树的最近公共祖先 递归，回溯
- 对二叉树进行深度优先遍历并将每一个非叶子节点添加到缓存栈中
- 当找到第一个匹配后，立即停止再向缓存栈中添加节点，因为此时的答案已经在栈中了
- 递归回溯，将没有匹配的节点从缓存栈中移除
- 找到第二个匹配项后，返回栈顶节点 @@ 需要考虑跟节点就是匹配节点的情况，需要考虑叶子节点的情况，需要考虑匹配节点本身就是答案的情况； 找到第二个元素返回True，这时候整个递归都会返回，并且不再修改结果 if find: return True 找到第一个元素后在find数组中标记 并且将第一个找到的元素也考虑在可能的答案根结点上 考虑末尾节点，当节点为叶子节点时，直接对该节点返回False return False 如果当前匹配第一次的节点就是叶子节点，需要将该节点移除缓存栈 if stack[-1] == node: stack.pop(-1) 没有匹配的情况下，需要将每个非叶子节点加入缓存栈 if not find: stack.append(node) 对左右子树递归 if node.left: if depth_search(node.left, p, q): return True 如果没有一次匹配则回溯到本节点后从缓存栈移除 if not find or stack[-1] == node: stack.pop(-1) 如果当前节点就是缓存栈顶部节点，则移除，因为上面的左右子树递归没有找到第二个匹配项
- 除自身以外数组的乘积 1. dp i的结果等于dpinumsi dp0=1 2.相反的顺序做同样的操作dpi = dpi p * numsi-1
# a1, a2, a3, a4 # 1, 1*a1, 1*a1*a2, 1*a1*a2*a3 # a1, a2, a3, a4 # a4*1*a3*a1, a4*1*a3, a4*1, 1 - 各位相加 数学问题，10x + y = z； x + y = z - 9x； a + b + c = z - (99a + 9b) = z - 9(11a + b) =》z - 9k z%9
if num == 0: return 0； eturn num % 9 if num % 9 > 0 else 9
- 缺失数字 [3,0,1] 输出：2 异或的第一个数字为数组长度是因为，如果是正常数组，最大值就是少一位的数组长度
位运算，位运算中相同数字经过^异或运算后得到0，所以对整个序列好正常序列经过异或后的到的就是： 缺失值^目标序列最大值 而目标序列最大值正好就是目标序列的长度
- 最长上升子序列
解法1: 使用动态规划：
- 状态定义： dp[i] 表示到索引i为止的最长升序序列的长度值
- 状态转移：转移条件：序列索引上升，这时候需要考虑此索引前面每一个状态长度和当前值的关系得到最佳结果，如：比较当前值和该索引i前的每一个值的大小，如果出现大于前面索引值dp[j]的情况需要考虑在当前值和dp[j] + 1 中获取最大值，即表示最长升序
- 解法2 动态规划 + 二分查找
- 对解法1中的状态定义换一个角度，解法1中的状态定义的长度为dp[i]的值，这里的状态定义将换成保存到i为止的升序（严格来说不是i-1处的真正的升序序列）序列，而1中的dp值就是现在的dp序列的长度；这样就可以在此dp序列上进行目标元素的替换从而不影响上一个序列的长度；
- 例如：2， 3， 4， 7， 10， 11， 6， 8， 9 ，10
- i = 5， dp = 2，3，4，7，10，11
- i = 6， dp = 2，3，4，6，10，11
- 这里状态的转移是将7替换成了6从而能够在目标序列中继续找升序序列，但是并没有影响当前找到的最大升序序列的长度，最终如果找到了新最小值（7被6替换表示，6替换了dp中第一个大于它自身的数字）从而得到了一个更长的序列例如找到最大数后append操作，最终新的长度也覆盖了上一次最长上升长度，而替换和append操作则可以使用二分查找的方式来实现；
- 这里的难点在于： dp数组会对当前最长的长度进行保留并且也会在每个索引的位置上讲后续升序的潜在可能性提高到最高，比如大于6的正整数比大于7的正整数多； 重点： dp数组，1. 保存了到当前索引的最大升序长度 2. 保存了当前索引前替换发生前的dp状态和替换后的双重状态；
- 水壶问题
数学问题， 类似3加仑和4加仑的桶到处5加仑水的问题： 数学问题 裴蜀定理，任意两个正整数a，b的公约数d，有xa+yb = d的倍数，也就是此题中结果想要得到的水的容量需要“满足他是两个水壶容量的最大公约数的倍数”； def _gcd(x, y): if y == 0: return x; z = x % y; return _gcd(y, z); x和y的公约数
- 甲板上的战舰，和岛屿问题属于同一种类型，就是使用图的广度遍历找特殊条件的连通分量
if board[i][j] == “X”: if (i > 0 and board[i - 1][j] == “X”) or (j > 0 and board[i][j - 1] == “X”): continue count += 1
- 两数相加 II 链表-(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出: 7 -> 8 -> 0 -> 7 高位在左
解法1: 思想：暂存栈，存储之后pop相加，对L1 L2两个链表进行暂存存储在栈中，因为栈的push和pop操作又后进先出的特点，所以对两个栈进行相加并生成新的链表，就可以得到最终L1 L2之和的链表的结果；Om+n 解法2: 获取长度，对同位部分使用递归的方式相加，递归的return可以返回相加的进位，如此就可以处理进位的问题； 重点看下解法2: 1. 先同时遍历两个链表，获取两个链表的长度，n1 n2，确保n1 l1永远都是长的那个， 2. 开始递归操作， nums1为长串，在长串本身上进行修改，temp值为该点值加进位值，递归调用i.next — if num1 > num2: temp = i.val + add(num1 - 1, num2, i.next, j) 递归调用直到两个长度相等，继续递归相同长度的两个链表，— else: temp = i.val + j.val + add(num1, num2, i.next, j.next) 当i next和j next到达末尾时，第一次返回，相加并修改i的值为tmp%10，返回进位值1或者0 — i.val = temp % 10 前一个相加会继续更新，直到返回到num1》num2的位置 — return temp // 10， 最后的答案如果有进位则在l1前加一个1
- 用最少数量的箭引爆气球 - 排序后找最小相交点，所以能最小相交的则用一个箭
贪心算法 贪心算法的思想是每一步都选择最佳解决方案，最终获得全局最佳的解决方案。
- 对于此题来说所有气球坐标最小和坐标最大的之间尽量使用最少的箭来引爆，对于每一个气球来说最好能找到与其坐标香蕉的气球，对每一个气球来说都是找到该气球下的最优解；sorted(points, key= lambda x:x[1]) 用右边排序是要将最小范围放在最左边，遍历每次更新l r的值，直到找到一个不符合的
- for v1, v2 in points: if v1 > end: arr_n += 1 end = v2;
- 找树左下角的值 - 广度优先，从右往左开始遍历，最后一个就是树左下角的值，最低一层
迭代，使用队列从右往左广度优先遍历整个树，输出最后一个元素就是最后一行最左边的元素 广度的迭代需要加 level + 1，每次遍历一次就更新一次值，遍历完成了也就是答案了
- 字符串的排列
暴力法就是生成s1的所有排列，也就是s1的全排列，在使用KMP法再s2中进行子串搜索； 与kmp类似的方法是滑动窗口，通过子串在目标串的滑动过程中来记录窗口中的关键信息，从而实现算法时间复杂度的最优； 窗口前后元素更新比对法，在s1中找到所有字符的数量，不断更新map2直到map2于map1相等，如果遇到没有的元素直接跳过 count法，第一次去l1 l2的相同索引元素，并且把已经符合条件的做一个count，然后更新map2，map2的新入元素和出元素不同的情况下，如果构成了新的map1i=map2i count就加一，如果出现超出一个元素则count–
- 所以股票问题
买卖股票的最佳时机，动态规划 ``` 状态穷举： dp[i][k][0]: 表示第i天剩余k次交易的时候，没持有股票时手上的利润，两种可能延续了前一天没有股票，今天刚刚卖出股票，在这两种可能中找出最大值 dp[i][k][1]: 表示第i天剩余k次交易的时候，持有股票时手上的利润，两种可能延续了前一天持有的股票，今天刚买进股票，在这两种可能中找出最大值
base case： dp[-1][k][0] = dp[i][0][0] = 0 dp[-1][k][1] = dp[i][0][1] = -infinity
状态转移方程： dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
52. 只有两个键的键盘 对于n个A，的最少操作次数
> n = x*y*z 表示 1次复制，x-1次粘贴，刚好是x次操作，完成后是x个A，这里得到的结果就是 x +y+z要求是最小，那么xyz一定都是素数
> 对n分解素数： pn_start = 2; while n > 1: while n%pn_start == 0: result += pn_start n /= pn_start pn_start += 1
> T = 根号n
53. 最大二叉树，无重复数组中，最大值左边是左子树，右边是右子树
> 实现两个函数，第一个是生成 node node.left node.right 的递归函数，用来构造二叉树，第二个是一个输入为一个l和r的着l r之间最大值的函数；两个函数都需要传入l r
54. 灯泡开关I II
> I： 分析方法，画出自定义的n个灯泡的情况，不难发现，每个数字都有奇数个或者偶数个因数，比如9 1 9 3而12为1 12 3 4，从而可以看出只有奇数个因数的序号的灯泡会进行奇数次操作，最终结果为亮着的状态，而判断一个数字的因数是否为奇数个也很简单就是看该数字是否是平方数；答案为返回平方数的个数；
> II： > Solution: 状态枚举，按位操作
> 解法，首先列出前6个灯的所有可能性
> Light 1 = 1 + a + c + d
> Light 2 = 1 + a + b
> Light 3 = 1 + a + c
> Light 4 = 1 + a + b + d
> Light 5 = 1 + a + c
> Light 6 = 1 + a + b
> 前三个灯已经包含了所有会出现的可能性，第五个和第六个灯的状态和第三个第二个完全一致，第四个灯地状态等于前三种开关状态之和，也就是前三种状态完全决定了第四个灯的状态；
> 此时由上述分析可知，前三个灯的状态决定了全部灯在序列里状态的可能性，所以只需要分析前三个灯在所有操作次数的可能性所有情况
> 只需要考虑m分别为0，1，2的三种特殊情况下的前三灯的特殊状态，当m>=3的时候前三个灯将包括他所有可能的亮灭过程，分别为2，4，8；
> 重点：1.分析前三个灯决定了所有灯的状态，2.分析操作次数大于等于3的情况下前三个灯将包含其所有可能的状态，因为前三个灯最多操作的是三种操作叠加，所以当操作次数为3的情况下，前三灯的所有的情况都可以包括；
> T: O(1) S: O(1)
python
class Solution(object): def flipLights(self, n, m): n = min(n, 3) if m == 0: return 1 if m == 1: return [2, 3, 4][n-1] if m == 2: return [2, 4, 7][n-1] return [2, 4, 8][n-1 ]
55. 删除注释
in_block = False ans = [] for line in source: i = 0 if not in_block: newline = [] while i < len(line): if line[i:i+2] == ‘/’ and not in_block: in_block = True i += 1 elif line[i:i+2] == ‘/’ and in_block: in_block = False i += 1 elif not in_block and line[i:i+2] == ‘//’: break elif not in_block: newline.append(line[i]) i += 1 if newline and not in_block: ans.append(““.join(newline))
return ans ```
重要定理及延伸
- 主定理：
情况1, 若𝑓(𝑛) < 𝑛𝑙𝑜𝑔𝑏𝑎, 则复杂度为 T(n)=O(n ^ {log_b a}); 情况2, 若f(n) = n ^ {log_b a}, 则复杂度为T(n)= O(n ^ {log_b a} * lgn); 情况3, 若f(n) > n ^ {log_b a}, 则复杂度为T(n)=O(f(n));
快排： T(n) = 2T(n/2) + n
- 斐波那契
fib if N <= 1: return N return self.fib(N-1) + self.fib(N-2)斐波那契数列在数学中的重要意义
3.常见排序思想：
- 快速排序：利用二分法，每次的基准数和其他数比较大小，找到自己位置，在对两边做二分递归。时间复杂度使用主定理
- 桶排序，0～n之间的数，要n个桶，每个桶装和自己序号相等的数的数量，最后遍历桶，将数展开；m+n m是桶长度
- 冒泡排序，每次两两比较，将最大数放在最后一个位置，然后继续找第二大的数，用n**2的时间复杂度，将所有的数冒泡到自己的位置；
- 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。 a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆; b.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端; c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
###HARD的题目 待完成题目： 211. 添加与搜索单词 - 数据结构设计 212. 单词搜索 II 421. 数组中两个数的最大异或值
##HARD：HARD的题目至少每个要看一遍
寻找两个有序数组的中位数，将一个集合划分为长度相等的子集的数字 https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu-b/
- 合并K个排序链表
基于两个链表合并的算法，我们将k中每两个链表合并一次得出的新的集合再进行同样的操作，最终得到一个集合，T = kN 将 k 个链表配对并将同一对中的链表合并。第一轮合并以后， k 个链表被合并成了 k/2 个链表，平均长度为 2N/k 重复这一过程，直到我们得到了最终的有序链表。每次k的数目指数型下降，例如k k/2 k/4 k/8 S = Nlogk
- K 个一组翻转链表
类似两两交换，使用递归，先检查当前cur=cur.next指针是不是有k个点，有的话当前的cur为第k+1个点并进行递归返回反转完成后的head，没有则直接返回cur， 那么第一个进行反转的一定是最后一个k，反转的方法是 head.next = cur，cur = head，将head的next指向cur也就是尾部，更新尾部为head，这样head就被放在了尾部和尾部的前一个直接，记得保存head.next最后更新head，迭代操作直到k次，此时cur就是真正的head，将head返回给上一个递归重复此操作
- 搜索旋转排序数组，nums = [4,5,6,7,0,1,2], target = 6
解法1: 两次二分查找，第一次找到分界点，数组中点i i-1 i+1 是否升序是否都比第一个数小，找到第一个比index0小的数字就向左边找； 找到分界点后再用二分搜索目标值 解法2: 一次二分查找，其实就是将两次二分查找相结合，重点在于利用index0的值，先比较目标值和index的大小，确定是在分界点左边还是右边，然后二分，二分点如果大于index0，证明二分点在左，小于证明二分点在右边，这样就可以定位下一次二分是在左还是在右，二分点和目标值也要对比； 时间复杂度logn，二分查找快速选择都是logn
- 地下城游戏
- 单词搜索 II
- 天际线问题
- 整数转换英文表示 分治具体的方法实现；
- 每三位分出当前总数，题目要求是小于2**31 -1 = 1024 * 1024 * 1024 -1 所以可以确定需要转换的数在百万以内，确定数字的 bilion million thousand
- 将每个3位的单位数前面的数字转换成因为，有三种转换方式第一10以内，第二100以内，第三999以内，并且不重复；
- 将三种方法的函数实现并将进位的函数实现，题目就可以解出；
- 二叉树的序列化与反序列化
string += str(node.val) + “,” string = recursive_serializer(node.left, string) string = recursive_serializer(node.right, string) node = TreeNode(data[0]) data.pop(0) node.left = recursive_serializer(data) node.right = recursive_serializer(data)
其他
数组处理： 查找、排序、排列、搜索、合并、子串搜索、滑动窗口、贪心、局部最优，kmp-确定有限状态自动机 动态规划：最长升序数组、打家劫舍问题、股票问题 图处理：二维数组中找联通图数量，找特殊条件的连通图数量，深度广度 二叉树：前中后，深度广度、二叉搜索树、完全二叉树、满二叉树、迭代和递归 链表：指针操作，next指针的操作变化
其他特殊： 素数求解，筛就完事了，欧拉筛法
python的list的底层是一个C的结构体，类似于vector，有自身的capacity，存储结构就是一个数组，存储list的每个对象的指针，不是链表
假设有数组 [a b c d e f g h ]，一个大小为 3 的 滑动窗口 在其上滑动，则有： [a b c] [b c d] [c d e] [d e f] [e f g] [f g h] 一般情况下就是使用这个窗口在数组的 合法区间 内进行滑动，同时 动态地 记录一些有用的数据，很多情况下，能够极大地提高算法地效率。 本题求解思路：