23届C++秋招刷题总结
2023-01-05 19:59:32 9 举报AI智能生成
登录查看完整内容
刷题路线为【代码随想录】
作者其他创作
大纲/内容
需要掌握前缀树的形式：一颗多叉树。字符串之间重合的部分都是一条路径，用一个bool变量表示单词的结束
剑指 Offer II 062. 实现前缀树
- 创建前缀树，用dictionary初始化这颗前缀树 - 将sentence用空格分割成字符串数组 - 将一个个字符串在前缀树中进行查找，若是有匹配到了词根，就用词根进行替换
剑指 Offer II 063. 替换单词
这道题没啥意思，就是对整个树进行爆搜，对于没有更换过字符的单词，要判断成false
剑指 Offer II 064. 神奇的字典
前缀树
堆
101. 对称二叉树
104.二叉树的最大深度
111.二叉树的最小深度
222.完全二叉树的节点个数
110.平衡二叉树
257. 二叉树的所有路径
404.左叶子之和
513.找树左下角的值
112. 路径总和
求二叉树深度的变种题型。对于每一个结点，我们都可以通过求出他左孩子和右孩子的深度，然后相加得到此结点最大的直径长度。由于我们是遍历了二叉树的所有的结点，对所有的结点都进行了如上的判断，因此遍历完整个树之后，肯定是不会漏掉可能更大的答案的
543. 二叉树的直径
二叉树的通用属性
226.翻转二叉树
106.从中序与后序遍历序列构造二叉树
654.最大二叉树
617.合并二叉树
二叉树的修改和构造
236. 二叉树的最近公共祖先
235.BST的最近公共祖先
二叉树公共祖先
700.二叉搜索树中的搜索
98.验证二叉搜索树
530.二叉搜索树的最小绝对差
501.二叉搜索树中的众数
538.把BST转换为累加树
BST的属性
701.二叉搜索树中的插入操作
450.删除二叉搜索树中的节点
669.修剪二叉搜索树
108.将有序数组转换为二叉搜索树
BST的修改和构造
二叉树
经典组合问题：回溯问题都可以抽象成一颗树：树的深度由组合的大小决定，树的宽度由原始集合的长度决定
第77题. 组合
77题的变种，不仅要在特定数据集合中求出固定长度的组合，还要求组合中的数字和满足题目要求
216.组合总和III
这个题要建表：把数字对应的字符串提前写好树的深度由输入字符串的长度决定了，树的遍历方式也固定了，一定是按照拨号顺序来进行组合的其中变化的就是一个数字对应好几个字符
17.电话号码的字母组合
树的深度不定了，但是树的宽度仍旧取决了输入数组的大小深度不定，所以需要在超过题目条件后就要停止递归这道题需要把这棵树都遍历完，找到组合和满足要求的
输入数组中，元素不重复，但是同一元素可以使用多次，只需要在递归到下一层时，idx保持不变即可
39. 组合总和
难度升级，输入数组中存在重复的元素，但是题目要求，一个元素只能被使用一次
数组中存在重复元素，如何保证结果不重复，这里有两种方法：树枝去重和同层去重。这里使用树层去重
由于组合不强调顺序，所以使用树层去重前，要先对原始数组进行排序，再在每一层，维护一个哈希表，记录使用过的元素
40. 组合总和 II
树的深度不定，决定于划分字符串的方式，最大深度就是输入字符串的长度树的宽度也不定，最大也是输入字符串的长度
在同一层的逻辑是组合出子串，连续的组合，不可以跳过某个字符。如果这个子串是回文串，则可以递归到下一层去重复这个操作。如果不是，继续组合子串
131.分割回文串
算是131分割回文串的变种操作树的深度定死了，4层，并且在第4层之后，要能用完输入字符串的长度
和131的逻辑是一样的，在同一层组合出子串，然后判断子串的合法性，合法的子串才能递归到下一层
93.复原IP地址
组合
通过递归函数，遍历完整个树，不过在遍历的过程中，就要收集得到的遍历结果
78.子集
包含重复元素的数组，去重，都是用树层去重
树层去重都需要对原始数组进行排序处理，否则得到的结果仍旧有重复得到
90.子集II
和子集问题比较类似。
树的宽度，输入数组的长度树的深度，不定，最大就是输入数组的长度
处理逻辑也是先同一层，再递归。在同一层中，选择逐渐增加的数字添加到集合中，然后递归到下一层。对，一层我们只选一个数
491.递增子序列
这道题有两种视角：站在数字的角度，一颗深度为n，宽度为桶的数量k的多叉树站在桶的角度，是一颗宽度更宽，但是深度较浅的多叉树
站在数字的角度的多叉树，采用常规的回溯就可以写出来。但是时间复杂度一般较高，很难通过站在桶的角度，可以用DP的状态压缩（我不知道这是什么解题方法），能够大幅度降低时间
698. 划分为k个相等的子集
与698是一样的题，属于698的换皮题
473. 火柴拼正方形
子集
全排列函数，今天用了新的做法：用树枝去重，去记录同一树枝，之前使用过了哪些数字，避免重复使用
树的宽度和深度是数组大小
46.全排列
输入数组中有重复元素了。肯定就要想到使用树层去重
树枝去重的目的，是为了避免使用上面树层已经用过的数字树层去重，是为了避免回溯这棵树，出现两个相同的树枝，前者是避免树枝有相同的结点，后者是避免整个树有相同的树枝，作用是不一样的
47.全排列 II
回溯做排列的题是否有补充？
排列
理论上来说，N皇后问题是一个N叉树，树的深度是N
N皇后问题能转换成N叉树问题后，格外简单皇后不能同一行，这点在递归遍历中已经自动满足皇后不能同一列，用一个树枝去重就能解决（或者在斜线检查那做）皇后不能同一斜线，也就是45°和135°，；两个方向取遍历即可，最后输出结果
N皇后
37. 解数独
棋盘问题
回溯
遍历整个树，收集最后得到的叶子结点
遍历整个树，但是在遍历的过程中，就要收集遍历的结果
排列和组合问题一样，都是求最后的叶子结点之后的结果但是排列讲究元素之间的顺序，这点和组合有很大的差异
入门题。可以由常识得到最优解。要么小饼干的大小顺序发，要么先满足要吃大饼干的
445.分发饼干
没感觉到最优。数组技巧，取反的次数只有三种可能：将部分负数取反得正、将全部负数取反得正、要对正数进行取反。重点是要排序，对负数取反要优先取反绝对值最大的；对正数取反要优先取绝对值最小的。这样会有最大收益
1005.K次取反后最大化的数组和
挺简单的。没感觉到贪心，算是读题之后领悟到解题技巧。找零时优先使用大面额的零钱，把小面额的5元留在包里。算是一种生活常识吧。之前看别人面试实习还做不出这题呢
860.柠檬水找零
简单题目
摆动序列画出来就是有波峰和波谷的折线，两个相邻的元素差值有正有负。用两个变量记录前后两次差值，通过比较便能得知是否为波峰或者波谷，还是连续的递增或者递减
376.摆动序列
这道题的技巧性在于去构造这个数字，也是通过比较前后两个数字的差值，如果低位的数字小于相邻高位的数字，那么高位数字减一，高位之后的低位全部变为9，只要想到这个技巧，这个题就很简单了。
738.单调递增的数字
序列问题
分发糖果是很经典的两个维度去权衡问题。先从左往右遍历，i比i-1的值更大，分的糖果要比前一个多一个；再从后往前遍历，如果i比i+1更大，i的糖果必须要大于i+1的糖果
135.分发糖果
这个题短时间反应不过来是两个维度权衡问题。而且这两个维度如何得到结果其实逻辑有点绕。这题的两个维度分别是身高和位置，要先根据身高从高到低进行排序，然后再按照位置进行插入。按照我的理解，如果插入的位置，已经被其他元素占了，那么先来的元素往后移，为什么？因为先占上的元素肯定是身高更高的，往后移不改变结果的正确性
这道题还有一点让人迷惑的就是，输入数组其实是有很严格的依赖关系的，这种依赖关系会让代码不发生bug。因为这种依赖关系会让数据经过身高重新排序后，再按照位置进行插入排序时，元素的位置一定是挨着的，不会是隔着的
这道题最好用链表完成插入
406.根据身高重建队列
两个维度权衡问题
使用两个指针，指向数组的前面和后面，计算次数接水的量，并和ans进行比较，取较大的。移动指针每次都移动高度较低的，这样我们能保证把潜在的更大的接水量给计算到。
局部最优的思想在于每一次移动指针时，要保留更大的高度，很棒，自己做出来的题
11. 盛最多水的容器
数组问题
中等题目
跳跃游戏看的是覆盖辐射的范围，如果在某一个点能够辐射到区间终点，那就是能跳到
55.跳跃游戏
难度升级，要求跳跃次数最少。解题思路也是类似的。要在一次跳跃能够覆盖的范围内，找到下一次跳跃能够跳的最远位置。说白了也就是每一次要，要最大化跳跃距离，局部最优推导到全局最优。
45.跳跃游戏II
排序+统计重合区间。每找到两个重合的区间，更新区间为两个的交集
452.用最少的箭引爆气球
和452一样的解题，452其实是找，有多少个不重叠的区间，然后435是求多少个重叠区间，两者一个意思
435.无重叠区间
这道题其实更简单了，和上面的题一个解题方法
56.合并区间
解题思路为：统计每一个字符最后的出现位置，在遍历字符串时，收集被遍历字符的最后出现位置，如果此时走到了被收集字符中，最大的一个位置，那么就代表把字符都收集到了，保存结果，进行后面的遍历
763.划分字母区间
区间问题
加油站是属于贪心中，找不出反例那就是正解的一道题。要能跑完，加的油总量要大于等于消耗的油，这个证明有效吗？无法证明，但是你也找不到反例
解题思路是，从当前i出发，计算剩余油量，如果到j站，剩余油量小于0，那么说明i肯定不是起点，起点另设为j+1，j站不行，正是因为J的消耗田太多才导致没油了。还有一个变量统计总的剩余油量，总的剩余大于0，寻找的i才有意义
134.加油站
这道题用DP或者贪心都能做，抓住解题核心：累加和如果小于0了，那么代表这段累加和肯定不满足要求了，从下一个位置开始，重新计算累加和
53.最大子序和
1.后序遍历2.设置状态标记，区别三种状态，得到不同的返回值
968.监控二叉树
困难题目
贪心
简单题，没啥说的
509. 斐波那契数
状态转移公式。dp[0]没有意义。这个题可以拓展成完全背包问题
70.爬楼梯
746. 使用最小花费爬楼梯
这道题我记得第一次做，想不出来怎么做。这个算法是N^2的这个题，每一个数，必须要两个数，取乘积最大，利用dp可以获取i之前的数，如果拆分了的话，能够获得的最大乘积也即是说，一个数n，要拆分后乘积更大，还是不拆分大，通过dp数组的记录，都可以获得因为一个数被拆分后，被拆分的数还可以继续拆分。这时就要判断，是拆分好，还是不拆分好，max比较嘛
343. 整数拆分
这道题容易被二叉搜索树给迷惑住了。心里总想着有什么捷径去构造出结点更多的BST实际上，还是依赖于dp数组对之前的结点数量的BST种类的保存，结点数量为n，一定是有左子树和右子树之分的，变化的地方在左右子树结点的变化dp[i] += dp[j-1] + dp[i-j]空节点也算是一个BST
96.不同的二叉搜索树
二维矩阵经典题了，上一步只有两个方向，对dp数组进行正确的初始化后，取上一步的两个方向和即可
62.不同路径
新增了障碍物，凡是有障碍物的地方，都是0，走不通其余和62没啥区别
63.不同路径II
求二维矩阵中，正方形的最大面积。这个问题，也是两种选择，当前遍历位置，元素==‘1’或者不为1等于1的话，那么加上这个元素，也许能够形成更大的正方形。但是，要形成更大的正方形，旁边的元素都要是1才行，所以这里要去比较三个元素，取最小值。dp[i-1][j-1] dp[i-1][j] dp[i][j-1]三个取最小值然后再加1。如果不为1，直接置为0然后对于整个矩阵的每一次遍历，都要用一个变量记录得到的最大值
221. 最大正方形
二维矩阵问题
dp数组推导问题——基础版
第一次做，总是做不出来。为什么？因为我忽略了01背包中一个隐含的条件：背包中不会放置超过背包容量的物品，这是由遍历方式得到的！
for(int j = bagWeight; j >= weight[i]; --j) 这里的 j>= weight[i] 就以表明，背包中不会放置超过容量的物品。所以这个题，只需要让物品最大化的放在背包中，如果能放满背包就算找到了解
416. 分割等和子集
这个题，第一次碰到的话，打死都想不到用DP的01背包来做从01背包的角度来讲，解题思路是将物品装满半容量的背包，如果能装满，则表示石头能被平分为重量相等的两部分，否则就看两部分的差值算是在416的基础上，换了一层皮
1049. 最后一块石头的重量 II
这道题一定要先做转换，不通过公式，降低解题难度，很难做的从01背包的角度来说，原题意会让背包中装入一个元素后，重量变轻（负值），这就让背包的推导方式变复杂了，目前都是针对正数的背包，所以要将原题进行变换，得到只装正数的背包
494. 目标和
物品是字符串，背包是0和1的个数。这个题有两个维度，类似于分发糖果一样，要从两个方面进行考虑，是一个二维平面背包，除此之外，没有其他区别。
474 一和零
01背包
组合问题，先物品再背包。注意初始化
518 零钱兑换 II
如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。
不适用于01背包的滚动数组。因为01背包的滚动数组严格按照物品的顺序，才能正确推导出结果。但是非滚动数组的话，是可以任意交换遍历背包和物品的顺序的，所以这条法则应该也就是适用的
这个遍历方法适用于01背包吗？
377. 组合总和 Ⅳ
将爬楼梯每一次爬的步伐改为1~m，问爬到楼顶有多少种方式
这就是同377一样是一道完全背包的排列问题。背包是楼梯层数，物品是每一次爬楼梯的梯数，可以重复使用，然后讲究排列
爬楼梯进阶
322. 零钱兑换
和322完全一样，没啥讲的
279. 完全平方数
乍一看，感觉只能回溯能做，细致的分析一下，其实dp也能做物品就是单词集合，可以重复使用，完全背包问题背包是字符串，装满背包==用单词拼凑出字符串1. 这个题，如何表示物品装入了背包？将单词，顶着背包的容量上限，卡进去2. 为什么是先遍历背包？先背包是排列，讲究物品之间的顺序，相较于组合，多了很多不同的顺序排列，用组合，单词也许选对了，但是顺序拼错了。本来是可以拼出字符串的，但是算出来拼不出，这不就错误了吗
139. 单词拆分
完全背包
背包问题
198. 打家劫舍
这个题要转换一下思路，首尾不能挨在一起——抢劫1-n-1或者2-n两种抢劫方式的最大值就是题解
213. 打家劫舍 II
记忆化搜索：通过后序遍历，当前结点有两种选择，偷当前或者偷左右孩子偷了当前结点，左右孩子就跳过去；不偷当前，就偷左右孩子
337. 打家劫舍 III
打家劫舍问题
只能买入和卖出一次使用二维dp数组，0表示持有股票，1表示不持有（卖出）股票初始化很重要，起始持有的话，便是-prices[0]状态转移通过前一天的持有和不持有进行推导，最后返回值一定是不持有的更大
121. 买卖股票的最佳时机
和121只有一个地方有区别：可以无限次数买卖股票。买股票时，荷包里的钱再也不是0了，而是前面买卖股票的最大收益，再去买
122. 买卖股票的最佳时机 II
多了一笔手续费罢了，手续费你可以在买入的时候就算上，也可以在卖出的时候才算上。买入+卖出才算做是一笔交易
714. 买卖股票的最佳时机含手续费
限制了购买次数为2次
123. 买卖股票的最佳时机 III
购买次数限制到了k次。递推公式和上面的123是一样的，只不过要用for循环罢了
188. 买卖股票的最佳时机 IV
将每一天的状态分为买入、卖出和冷静期。买入的最大收益只能是前一天已经买入或者前一天是冷静期，然后今天买入卖出的最大收益只能是今天卖出收益以及前一天卖出的最大收益冷静期的最大收益来自于前一天卖出的收益
309. 最佳买卖股票时机含冷冻期
股票问题
惭愧啊，这道题当时应该是在手机上打出来的，现在就忘记不会做了
300. 最长递增子序列
这道题是300的简单版。674要求子序列必须是连续的，300没这样的要求。所以300要和i之前的每一个j比较，试图找到最大的递增子序列
674. 最长连续递增序列
开始进入二维dp数组了这道题不要想复杂了，由于题目要求是连续子数组，所以如果i和j的数字不相同，那么之前的状态是不能在使用的！
718. 最长重复子数组
当当当当，公共子序列来了。公共子序列和公共子数组，二字之差，差别巨大，子序列不讲究元素的连续性，只要相对顺序不发生改变即可。可以利用之前的状态！
1143. 最长公共子序列
1143最长公共子序列的换皮题，一模一样的解法
1035. 不相交的线
有点删除序列那个味道了，删除长的序列中的字符
392. 判断子序列
第一次做不了，第二次还是做不了，哈哈哈在判断子序列的基础上，还要统计子序列出现的次数，难度陡增
核心点是抓住s[i] 是否等于 t[j]这个点，对于392来说，相等就在上一个匹配的基础+1，不想等就“删除”母序列的长度
然后对于这道题，相等的情况下，可以沿用对角线上一个匹配的值，还可以沿用不使用当前母序列字符匹配的值，如果不相等，只能沿用不使用母序列字符匹配的值
115.不同的子序列
我个人感觉，这个题把dp数组这种数学概念的思维玩尽了首先要确定dp数组的函数，dp[i][j]表示word1[:i] 与 word2[:j] 相同的最小步数.这里要注意，经过删除之后的字符串一定是相等的递推公式：由三个方向推导而来，删除i，删除j，或者两个都删除，毕竟左邻居、上邻居、左上角邻居都已经是相等的状态了，删除到哪个状态的次数最少选哪个
这道题还有一种逆向思维的解题方法：先求出最长公共子序列，然后用两个字符串的长度-最长公共子序列长度*2。1143 YYDS
583. 两个字符串的删除操作
难度升级，操作方式从删除，增加到了删除、插入以及替换三种方式，这意味着题目变得更加复杂
但是，插入和删除其实一个道理，两者相等，较短的插入一个与较长的删除一个，不是一个意思，吗？替换就是在dp[i-1][j-1]的基础上，增加一次操作次数，所以这道题只是在583的基础上，增加了替换的功能，而且替换的递推还贼简单
牛客网NC35变种题，插入、删除、替换分别有一个代价（IC、dc、rc），变种题其实考察的是对于插入和删除的掌握是否透彻。插入操作，就是要在dp[i][j]的基础上，插入一个字符，变成dp[i+1][j]。但是dp[i+1][j]的状态是未知的，所以插入操作等价于str2删除一个元素，也就是从dp[i][j]变成dp[i][j-1]，str2删除一个字符的代价，等价于str1插入一个字符的代价，代价就是ic删除操作，也就是从dp[i][j]变成dp[i-1][j]，代价就是dc替换操作，也就是从dp[i][j]变成dp[i-1[j-1]，代价就是rc
72. 编辑距离
这道题有两种比较好的做法，一是双指针法（从剑指offer学到的），二是dp动态规划
双指针法的思维很巧妙。从起始点出发，向两边拓展开来。遇到不是回文子串了，就退出。对字符串的每一个位置，都要做这样的“测试”，并且，起始点可以是一个字符开始，也可以是两个字符一起开始，也就是a，或者aa。统计最后的结果
双指针法我很熟练的，dp反而不太熟悉。这次的dp也是二维数组，不过和之前有不一样了二维dp数组出现在【矩阵图】、【背包】、【子序列】这三种问题居多【矩阵图】的横纵坐标就是图上的坐标，这里没其他的变化【背包】的横坐标一般表示背包的容量、纵坐标表示物品的选择【子序列】问题，横纵坐标一般表示不同的字符串在这道题，dp[i][j]表示用【i-j】组成的字符串是否是回文字符串，这里i肯定是小于等于j的
核心思想和双指针法是类似的
647. 回文子串
和647基本上一样，通过dp数组来获取回文字符串。当遇到回文字符串时，判断这个串的长度是不是更长，更长就记录下这个串的起始和终点坐标
5.最长回文子串
回文子序列的题比回文字串要简单一些，应该说是判断情况要简单一点回文字串要字符匹配相等的时候，需要分两种情况进行讨论：【j-i小于等于1】、【去掉i和j的字符串要是回文】回文子串字符匹配不上时，就直接是FALSE，不需要理会
但是回文子序列不一样回文子序列在字符匹配上的时候，直接在去掉i和j的结果上+2如果字符匹配不上，可以删除一个字符，删除有两种选择，删除i或者删除j，选择最大的那一种
516. 最长回文子序列
子序列问题
编辑距离（删除操作）四部曲）
动态规划
题目要求什么，dp数组的值就定义成什么，下标一般表示为背包的容量，涉及字符串的，可能会表示成字符串的长度、最后一个下标的位置等。这个点没太多讲究的
确定dp数组（dp table）以及下标的含义
这算是难点。对于01背包来说，一般不会涉及到累加公式。常用的就是比价大小，判断赋值以及累加。这需要根据题意来进行选择，有难度
确定递推公式
初始化其实很重要，在01背包问题上没有得到体现。但是在完全背包上，初始化问题很关键。很多时间初始化难以讲出来意义，比如dp[0]=1对于很多题，其意义都比较牵强。对于求最少使用的完全背包问题，初始化很关键
如何初始化
对于完全背包来讲，先背包是排列、先物品是组合。01背包的滚动数组只能先物品后背包
遍历的顺序
递归四部曲再回首
能不能装满
装满有几种方式
装满后的最大价值
装满后最少物品使用数量
背包一般在求什么问题
物品是否可以重复使用
遍历顺序。完全背包解题时，要选择正确的遍历顺序，01背包不需要。
01 背包和 完全背包的区别
背包总结
332.重新安排行程
就是很常规的，在矩阵中进行搜索。矩阵搜索一般就是四个方向，使用vis数组记录遍历过的点
79. 单词搜索
首先，这个题是针对拓扑排序做的搜索算法什么是拓扑排序呢？就是图中没有成环的，然后对图的遍历得到的序列就是拓扑排序。这个题用来一个新技巧：1. vis的状态从0-1变为0-1-2三种状态，不仅仅表示这个顶点被访问了，还要辨别这个结点是在搜索中，还是搜索过了。因为对于这个题来说，没有相邻结点的时候，就表明这个结点已经遍历干净了，就要置为2这个状态
207. 课程表
同207，方法是一样的，只是需要用数据结构将上课的顺序给保存下来。这里针对示例的返回状态，我们可以发现，用栈这种LIFO特性刚刚满足要求210才是将vis的三种状态应用得很彻底的题，因为只有当vis状态为2时，才能用stack将结点装进去
210. 课程表 II
图论
拒绝采样法：在与圆内切的正方形中，生成两个随机数，如果生成的随机数在圆外，重新生成（我之前也是这么想的。靠！）
记住生成随机数的两个类：default_random_engine gen;uniform_real_distribution<double> dis;double r = dis(gen);
478. 在圆内随机生成点
位运算。两个重复的数字，通过异或运算，找到没有重复的那个数字
异或运算有以下三个性质。任何数和 00 做异或运算，结果仍然是原来的数，即 a \\oplus 0=aa⊕0=a。任何数和其自身做异或运算，结果是 00，即 a \\oplus a=0a⊕a=0。异或运算满足交换律和结合律，即 a \\oplus b \\oplus a=b \\oplus a \\oplus a=b \\oplus (a \\oplus a)=b \\oplus0=ba⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
136. 只出现一次的数字
这道题有三个点要注意：第一是被除数为INT_MIN时，单独判断，由除数是1还是-1直接得到结果，不用运算；第二是要将被除数和除数都转换为负数。这是因为负数的范围更大，如果将负数转换为正数，会导致结果错误；第三是使用二分法加速计算的过程（除数翻倍，类似于2次幂的加速计算一般）
剑指 Offer II 001. 整数除法
此题是模拟二进制加法的过程，类似于两条链表数字相加一般。用一个变量表示进位即可，还是很简单的
剑指 Offer II 002. 二进制加法
两点需要记住：第一是求一个整数的二进制表达的1的个数方法a = a & (a-1）第二是此题可以使用dp加速解题，使得时间复杂度变为O(n)
剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
将所有数字的每一个位相加，能被3整除的就不是那个数字的位，不能整除的就是那个数字的位
剑指 Offer II 004. 只出现一次的数字
数学
最简单的二分查找。有序，无重复数字，寻找元素
704. 二分查找
姑且认为慢指针所覆盖的元素都是不包含val的，所以，快指针遍历到的等于val的元素，都不得加入到慢指针中。相反就可以
27. 移除元素
双指针+辅助数组。输入数组的格式决定了此题能够使用双指针法：数组要么是整段有序的，要么是分段有序的（段次为2），两个指针就能表示这两段有序的数组
977. 有序数组的平方
窗口内的内容是什么？
什么时候扩大窗口？
什么时候缩小窗口
滑动窗口解题
209. 长度最小的子数组
数组
链表的遍历和栈的使用，太简单
剑指 Offer 06. 从尾到头打印链表
经典链表题型。必须时刻都会做。迭代和递归两种做法都要能做。核心思想：取出当前结点，重置结点的指向（脱离当前链表）
剑指 Offer 24. 反转链表
新题型。将链表和哈希表结合在一起，挺有意思。用哈希表创建处一张原结点和副本结点的映射关系。通过原结点查表得到新节点的前后关系（指针指向）
剑指 Offer 35. 复杂链表的复制
用链表表示一个整数（头结点是最低位，头结点是最高位），两个整数相加。难点1：进位；
反转链表
使用栈就可以避免反转链表，是进阶的做法
使用栈保存链表结点，再依次弹栈
如果链表头结点表示的整数的最高位，为了从低位相加，有两种办法：
剑指offer II 25. 链表中的数字相加
这道题一考思维，二考对链表删除插入操作的熟悉程度。根据题意要能明白，只要将链表一分为二，让后半部分链表反转后，两个链表合并即可
第一：反转链表函数
第二：将链表保存早栈中，弹栈即可得到顺序相反的结点
既然涉及到反转链表，那么就有两种办法
剑指offer II 26. 重排链表
链表一分为二，然后反转后半部分链表，按个比较。没有太多难点，掌握分割链表和反转链表即可解题
剑指offer II 27. 回文链表
将链表和DFS结合在一起，思维的体量上有难度。主要是明白如何变换链表，同时紧紧抓住递归函数中当前层和下一层返回结果的关系，这道题通过debug倒也是不难。
剑指offer II 28. 展平多级双向链表
这道题难点在于插入情况的梳理，一共有四种插入情况。着重需要注意有重复元素的case，需要debug检查
剑指offer II 29. 排序的循环链表
考察链表结点的删除和头结点的使用。这个题不使用头结点将会变得十分复杂。
这个题除了用迭代法做，还可以用递归来做。有一些类似于回溯，递归到链表尾部，然后在递归函数返回前，判断是返回nullptr还是当前结点，去更新上一层结点的next指针
203.移除链表元素
链表增删改查全方面考察。这是我力扣上做出来的第一道题
707.设计链表
这道题是模拟。交换链表中的相邻两个结点，还涉及左边的第三个结点。实际上是三个结点的next指针在作改变。第二个是理清楚向后移动的方式要注意，交换完后最右边的结点向后试探两步，如果不行就结束交换
24. 两两交换链表中的节点
技巧：双指针。删除倒数第n个结点，就让两指针间隔n，当right指针到达最后一个结点时，left正是要删除的结点的前一个结点。技巧2：头结点。凡是需要删除结点的题，都优先考虑使用头结点。
19.删除链表的倒数第N个节点
解题方法1：重复走。指针1遍历完链表1后，从头开始遍历链表2，指针2相反。如果两链表相交，必定会在某个结点相遇（走过的结点数量是相同的），如果没有相遇，则代表不相交。
面试题 02.07. 链表相交
经典的数学推导。快指针走过的结点数量是慢指针的2倍，两者相遇的位置+环的长度*n，就是链表头到环入口的长度
142.环形链表II
链表
剑指 Offer 50. 第一个只出现一次的字符
无技巧硬哈希：将单词转换成字符出现次数的新字符
技巧：将单词排序，异位词排序后相等
剑指 Offer II 033. 变位词组
直接哈希，没啥说的
剑指 Offer II 034. 外星语言是否排序
这道题是技巧+哈希。将字符串转换为分钟数，为了比较当天的23:59和第二天的00:00，需要对小于12点的时间增加一天的分钟数1440，从而成为第二天的时间
分钟数存于数组，sort排序，找最小差值：nlogn
分钟数存于multiset，遍历找最下差值：logn
空间换时间
分钟数存于2160长的数组，遍历找最小差值：n
时间效率对比
剑指 Offer II 035. 最小时间差
哈希表统计字符出现的次数，然后进行比较
242.有效的字母异位词
和242类似
383. 赎金信
哈希表统计数字出现的次数，然后进行比较。思路和上面是一样的，处理起来一些许差异
349. 两个数组的交集
要转个弯。无限循环的数字用哈希表保存，出现重复了就能判断为无限循环数字
第202题. 快乐数
哈希表空间换时间。用哈希表的O(1)查询效率去掉一层循环
1. 两数之和
要转一下脑筋。是两数之和的变种题。将a+b+c+d=0转换成a+b=-(c+d)。用空间换时间，将4层循环降到2层循环
第454题.四数相加II
这道题要求是O(n)的时间复杂度。为了做到这一点，这道题有两个技巧：第一是使用哈希表进行查询，将查询的时间复杂度降到O(1)第二是在使用哈希表时，为了避免重复的查询过程，一定是从连续子序列的起点开始查如果不是起点，那么他的左边或者右边（看你的查询方向）一定是在哈希表中的，跳过，这样操作的目的是降低时间复杂度，避免时间复杂度恶化到O(n^2)
128. 最长连续序列
哈希表
哈希表统计次数+滑动窗口
剑指 Offer II 015. 字符串中的所有变位词
同上
剑指 Offer II 016. 不含重复字符的最长子字符串
n2的做法就是每移动一次窗口，就要去检查字符是否全部包含，时间复杂度是n2.
剑指 Offer II 017. 含有所有字符的最短字符串
回文检查+模拟。最多删除一个，当出现不匹配时，可以删除左边，也可以删除右边
剑指 Offer II 019. 最多删除一个字符得到回文
双指针法，从中间往外延展，变大子串的长度，判断是否为回文串。从中间延展，有奇偶之分，从当前位置延展，或者和旁边一起延展
剑指 Offer II 020. 回文子字符串的个数
原地翻转字符串，很简单的交换
344.反转字符串
简单的做法是使用辅助的字符串，进阶的做法是将原先的字符串延展要求的长度，然后从后往前填充字符串
题目：剑指Offer 05.替换空格
这道题是有技巧的：两次翻转字符串就能让整个字符串呈现出字符顺序翻转的效果。如果你自己去推导一下坐标的变换，就能理解其中的缘由
151.翻转字符串里的单词
上面的变种题，先将字符串整体翻转，然后再翻转子字符串，就能实现字符串的左旋效果
题目：剑指Offer58-II.左旋转字符串
KMP算法
28. 实现 strStr()
459.重复的子字符串
字符串
什么时候缩小窗口？
每日一题：本质是翻转字符串，用规定的次数，让翻转后的字符串有最长的连续相同字符。固定翻转的方向，用滑动窗口去找：当翻转次数不超过允许值时，最长的长度
2024. 考试的最大困扰度
这个题同2024一样。都是翻转，只需将0翻转为1，在k次翻转内统计连续1的最大长度
1004. 最大连续1的个数 III
这道题也可以用dp来做
这算是一个滑动窗口题。姑且设定滑动窗口内的元素都是单调递增的，那么窗口最后一个元素就是最大的，如果之后遍历的元素，小于或者等于右窗口值，那么窗口就要重置为1了，慢指针直接移动到右窗口的位置
这道题解法很简单，但是要想到这种解法，需要脑筋转一个弯。这题实际上提炼出来就是找到最长的连续子序列，其序列累加和等于target这么一个问题，而这个target==整个数组累加和 - x
1658. 将 x 减到 0 的最小操作数
1456. 定长子串中元音的最大数目
- 643. 子数组最大平均数 I
- 1052. 爱生气的书店老板
1423. 可获得的最大点数
滑动窗口
统计元音、子数组平均数是一眼看过去就能知道怎么解的简单题，定长的滑动窗口在数组上移动，对窗口内的数据进行操作，得到结果罢了
爱生气的书店老板稍微需要转一个弯，需要先统计出不使用滑动窗口的满意客户人数，再使用定长的滑动窗口在其上面滑动，修改这个值，找到最大值
最大点数需要转个脑筋了。抽牌的次数决定了滑动窗口的长度，通过滑动窗口从前往后的移动，可以模拟出不同的抽牌组合，找到极值就可以解决问题
这四道题可以看做是一种题型：定长的滑动窗口
慢指针指向的是合法元素数组的最后一个元素，快指针是遍历原数组的。由于不能允许重复，且数组是有序的，可以认为，慢指针之前的元素，在快指针之后都不会再遇到了。所以只需将慢指针指向的元素和快指针指向的元素相比较即可
26. 删除有序数组中的重复项
难度升级。允许重复一次。由于数组是有序的，重复的数字是挨在一起的，所以，快指针要和慢指针的前一位作比较。如果这道题改为重复k次，那么快指针就要和慢指针之前的k-1位比较
80. 删除有序数组中的重复项 II
第一种是移动元素的变种。移动元素是用后面合法的元素覆盖掉不合法的元素。在移动元素之后，后面一截补上0即可
第二种方法效率更高。左指针表示不含0元素的序列的end，右指针表示需要处理的序列的begin。右指针凡是遇到一个非0的元素，就将该元素交换到左指针的末尾，同时左指针后移
移动0有两种做法
283. 移动零
这道题虽然有三个元素要操作，但我们可以只排序好0和1或者0和2即可，剩下的就自动排好了
因为我们是从前往后遍历的，在p~back这段区间是没有被遍历过的，如果交换完，p的元素仍然是2，不能跳过，因为不能保证p之后的元素都是2. 但是p == 0就不一样的，p之前的所有元素都已经放入front里了，如果交换完等于0，那只有一个可能，交换前两指针相等。
第一种解法：0移动到最前面，2移动到最后面。先操作2，如果遍历到了2，就将2交换到末尾。但此时有一个注意的，如果交换后还是2，还需要继续交换（back指针已经前移），直接交换后不再是2
75. 颜色分类
双指针解法。先排序，再用指针寻找元素之和
第15题. 三数之和
双指针+排序。题目要求最短的无序数组的长度，使得经过排序之后整个数组都有序了。先将数组进行排序，得到有序版本，并同原数组进行比较时间复杂度O(nlogn)
581. 最短无序连续子数组
双指针法
主栈负责添加元素，子栈负责删除元素
主栈中的元素，先进的在栈底，无法操作。但是将主栈的元素弹栈压栈到子栈后，子栈栈顶的元素即为主栈栈底的元素，刚好反过来了。
232. 用两个栈实现队列
两个栈。主栈正常保存数据，子栈负责保存对应位置的最小元素
这里利用到了栈先进后出的特性：后进的元素如果没有被弹出，那么先进的元素一定就在栈中
155. 最小栈
将左括号压入栈中，遇到右括号弹栈匹配。栈经典应用场景——括号
20. 有效的括号
将数字压入栈中，遇到运算符弹两次栈进行运算
C 语言的字符串转整数的库函数：atoi
150. 逆波兰表达式求值
基本上碰撞问题都能用栈进行解决。想清楚哪些情况会发生碰撞，针对碰撞去写条件，不会碰撞的就不管。
剑指II-037. 小行星碰撞
单调栈本质上也是栈，只是在使用栈时，让栈中的数据满足单调递增或者单调递减的规律，帮助我们解题
经典的单调栈题型。从栈底到栈顶保持单调递减的规律（因为题目要求的是多少天之后温度升高），栈中存放的元素是下标（要求时间间隔）。栈中元素，从栈底到栈顶，每一个都在等待大于他自身温度的那一天到来。
739. 每日温度
每日温度的变种题型。首先挨个计算出nums2数组中，当前元素的下一个更大元素是谁，用哈希表保存，方便查询。再遍历一遍nums1，依次查询哈希表，得到最后结果
496. 下一个更大元素 I
在496的基础上，增加了一个条件，循环数组。一般来说处理循环数组的方法就是将其延长一倍，但是道题由于有重复元素，这样处理起来还挺麻烦。更简单的做法是遍历两次这个数组
503. 下一个更大元素 II
接雨水可以用单调栈做。栈中的元素也是按照从栈底到栈顶单调递减的方式保存，遇到大于栈顶的元素时，弹栈一次，获取两个栈顶元素，加上当前元素，组成一个两高一低的凹形，然后计算凹进去能接的雨水的面积
解题的核心或者技巧就在【弹栈一次，但是要获取栈中两个元素】。遇到更大的高度后，弹栈一次，将最低的高度弹出来，然后再获取下一个栈中的元素（大于等于刚才弹栈的元素），两高一低中间组成凹坑，便能接水了。
42. 接雨水
此题和接雨水很相似，接雨水获取两次栈顶元素，加上当前元素3个值组成凹形，此题是组成凸形。单调栈的顺序和接雨水要相反，然后要在原数组的基础上，前后增加两个0
这道题有一个隐藏满足的条件，中间的最高的柱子，弹栈弹走了之后，其依然会对之后计算产生影响。产生影响的方式便是它的下标位置，
因为我们每次取高度都是取mid对应的，也就是三者之间最高的那个值，但是宽度的取值就不是固定的了，宽度会随着计算的增加，越往后越大。这里一句两句说不清楚。但是和接雨水是很相似的，两者在数据的处理上，都有点奇妙
84. 柱状图中最大的矩形
剑指II-040. 矩阵中的最大矩形
单调栈
栈
滑动串口+优先队列。这道题数据量很大，不作优化的话是会超时的。
优化方法：优先队列top为最大值，如果这个最大值还在滑动窗口中，那么无需对优先队列执行删除元素的操作（删除在滑动窗口之前的元素）。
239. 滑动窗口最大值
前k个最大的，要用小根堆，反之则用大根堆
哈希表+优先队列+大小根堆选择
347. 前 K 个高频元素
队列
二分查找思想很简单，但是细节很恐怖
剑指 Offer 53 - II. 0～n-1中缺失的数字
剑指 Offer 11. 旋转数组的最小数字
34. 在排序数组中查找元素的第一个和最后一个位置
这道题不需要使用DFS或者BFS，直接两个循环遍历即可。常规的做法是对每一行都使用二分查找算法，时间复杂度就是mlogn进阶的做法是Z字形搜索，代码很简单，但是为什么可以这样搜索，需要数学证明，没来得及看
240. 搜索二维矩阵 II
这个比240简单一些，毕竟数组的排序方式变简单了。这道题的解法就是两次二分查找，第一次二分查找是寻找行内元素大于target的行，第二次则是去每一行总查找target
74. 搜索二维矩阵
二分查找
除自身以外，那么就可以分为前缀和后缀，分别计算出前缀乘积数组以及后缀乘积数组，就能在不使用除法的情况下，解出此题
238. 除自身以外数组的乘积
前缀和
刷题总结
1. 常规的括号、表达式、碰撞：一个栈的入栈和出栈很简单就能想出来
2. 最小栈、用栈模拟队列：两个栈，主栈和子栈分别负责不同的共同的功能，空间换时间
3. 单调栈解题。栈中元素都是有序的，要加入栈前需要比较
栈的解题方法：
第一：灵活使用反转，像剑指offerII中好几道，需要使用反转的，解题一下子就轻松了
第二：涉及删除链表结点的题目，优先考虑使用哨兵结点简化
第三：链表和其他算法思想结合：链表+哈希表、链表+DFS
第四：链表的双指针：对称切分链表、倒数第x个结点都需要双指针实现
第五：数学：环形入口、相交问题都需要一定得数学推导。推导的切入点是指针走过的结点数量（长度）
链表解题方法：
1. 用作字符、数字等的次数统计。最简单也最常用
2. 用作空间换时间：例如两数之和等题型
哈希表解题方法：
数组存在于大多数的题中，单独作为数组题的话，一般考察是对数组遍历的熟练度
不涉及哈希、双指针、单调栈等的数组题，闭着眼都能做
数组解题方法：
纯字符串题：翻转、左旋、回文算是纯字符串题，主要是用指针遍历即可做出
涉及双指针的字符串稍微有点复杂，例如回文子字符串的个数、最短/最长xx子串，有些不仅是双指针，还需要配合哈希
字符串解题方法：
1. 简单题：用两个队列模拟一个栈，考察队列的FIFO特性灵活使用
2. 优先队列题：要记住自定义优先队列比较的写法（用自定义函数就好），然后这个比较的方向是和sort排序是刚刚相反的
队列的解题方法：
回溯问题可以分为组合、子集、排列、棋盘问题。做题前，如果题目要求求出所有的可能结果，那必定要用回溯法，再判断是回溯中的哪一种题型1
回溯问题都可以抽象成一颗树
需要注意的是，针对组合问题的树层去重，一定要对原始数组进行排序
回溯的解题方法
1.贪心没有固定的解题模板，简单题可以通过常识进行最优推导，有难度的解需要仔细读题，找题目中的trick点
2.贪心是对解题思维的一种集大成者，就是读题，用脑子去模拟
3.考原题行，新题直接摆烂
贪心的解题方法
1. 常规的dp问题，例如爬楼梯、fib数列等，姑且是能够通过题意找到【递推公式】的。而且这类问题，基本是都是一维数组的
2. 背包问题就比较复杂了，01背包和完全背包。背包问题全是二维数组，背包问题对数组的定义、递推公式、初始化、遍历顺序这四个点要求很高，必须要想清楚了，才能下手。做背包问题，最好写一些注释，帮助自己理清楚解题方法
3. 股票问题。股票问题的核心是抓住【持有】和【卖出】这两个点，后面的进阶升级题都是在这个的基础上进行变动
4. 打家劫舍。这个系列就三道题，常规打劫、环形打劫以及二叉树打劫。二叉树打劫需要再多看几遍
5. 子序列问题。子序列问题有子串和子序列之分，子串要求连续，就不涉及删除操作，匹配不上就没了。匹配上了或许有更多的讲究（回文子串）。子序列可以删除，所以有删除操作。删除操作就是丢弃当前的状态，用上一个的结果，这就是删除。编辑距离那几个题把删除操作玩的淋漓尽致。我觉得要把【最长系列】单独拎出来，体会其中的差异。
动态规划的解题方法
0 条评论
回复 删除
下一页
