23届C++秋招刷题总结

求二叉树深度的变种题型。对于每一个结点，我们都可以通过求出他左孩子和右孩子的深度，然后相加得到此结点最大的直径长度。由于我们是遍历了二叉树的所有的结点，对所有的结点都进行了如上的判断，因此遍历完整个树之后，肯定是不会漏掉可能更大的答案的

经典组合问题：回溯问题都可以抽象成一颗树：
树的深度由组合的大小决定，树的宽度由原始集合的长度决定

77题的变种，不仅要在特定数据集合中求出固定长度的组合，还要求组合中的数字和满足题目要求

这个题要建表：把数字对应的字符串提前写好
树的深度由输入字符串的长度决定了，树的遍历方式也固定了，一定是按照拨号顺序来进行组合的
其中变化的就是一个数字对应好几个字符

树的深度不定了，但是树的宽度仍旧取决了输入数组的大小
深度不定，所以需要在超过题目条件后就要停止递归
这道题需要把这棵树都遍历完，找到组合和满足要求的

输入数组中，元素不重复，但是同一元素可以使用多次，只需要在递归到下一层时，idx保持不变即可

难度升级，输入数组中存在重复的元素，但是题目要求，一个元素只能被使用一次

数组中存在重复元素，如何保证结果不重复，这里有两种方法：树枝去重和同层去重。这里使用树层去重

由于组合不强调顺序，所以使用树层去重前，要先对原始数组进行排序，再在每一层，维护一个哈希表，记录使用过的元素

树的深度不定，决定于划分字符串的方式，最大深度就是输入字符串的长度
树的宽度也不定，最大也是输入字符串的长度

在同一层的逻辑是组合出子串，连续的组合，不可以跳过某个字符。
如果这个子串是回文串，则可以递归到下一层去重复这个操作。如果不是，继续组合子串

算是131分割回文串的变种操作
树的深度定死了，4层，并且在第4层之后，要能用完输入字符串的长度

和131的逻辑是一样的，在同一层组合出子串，然后判断子串的合法性，合法的子串才能递归到下一层

通过递归函数，遍历完整个树，不过在遍历的过程中，就要收集得到的遍历结果

包含重复元素的数组，去重，都是用树层去重

树层去重都需要对原始数组进行排序处理，否则得到的结果仍旧有重复得到

和子集问题比较类似。

树的宽度，输入数组的长度
树的深度，不定，最大就是输入数组的长度

处理逻辑也是先同一层，再递归。
在同一层中，选择逐渐增加的数字添加到集合中，然后递归到下一层。对，一层我们只选一个数

这道题有两种视角：站在数字的角度，一颗深度为n，宽度为桶的数量k的多叉树
站在桶的角度，是一颗宽度更宽，但是深度较浅的多叉树

站在数字的角度的多叉树，采用常规的回溯就可以写出来。但是时间复杂度一般较高，很难通过
站在桶的角度，可以用DP的状态压缩（我不知道这是什么解题方法），能够大幅度降低时间

与698是一样的题，属于698的换皮题

全排列函数，今天用了新的做法：
用树枝去重，去记录同一树枝，之前使用过了哪些数字，避免重复使用

树的宽度和深度是数组大小

输入数组中有重复元素了。肯定就要想到使用树层去重

树枝去重的目的，是为了避免使用上面树层已经用过的数字
树层去重，是为了避免回溯这棵树，出现两个相同的树枝，
前者是避免树枝有相同的结点，后者是避免整个树有相同的树枝，作用是不一样的

由于排列是讲究顺序的，排列（1,2）与（2,1）是不同的，但是如果是组合就是一样的。
所以对排列使用树层去重是不需要排序原始数组的

理论上来说，N皇后问题是一个N叉树，树的深度是N

N皇后问题能转换成N叉树问题后，格外简单
皇后不能同一行，这点在递归遍历中已经自动满足
皇后不能同一列，用一个树枝去重就能解决（或者在斜线检查那做）
皇后不能同一斜线，也就是45°和135°，；两个方向取遍历即可，最后输出结果

入门题。可以由常识得到最优解。要么小饼干的大小顺序发，要么先满足要吃大饼干的

没感觉到最优。数组技巧，取反的次数只有三种可能：将部分负数取反得正、将全部负数取反得正、要对正数进行取反。重点是要排序，对负数取反要优先取反绝对值最大的；对正数取反要优先取绝对值最小的。这样会有最大收益

挺简单的。没感觉到贪心，算是读题之后领悟到解题技巧。找零时优先使用大面额的零钱，把小面额的5元留在包里。算是一种生活常识吧。之前看别人面试实习还做不出这题呢

376.摆动序列

738.单调递增的数字

135.分发糖果

406.根据身高重建队列

11. 盛最多水的容器

55.跳跃游戏

45.跳跃游戏II

452.用最少的箭引爆气球

435.无重叠区间

56.合并区间

763.划分字母区间

加油站是属于贪心中，找不出反例那就是正解的一道题。要能跑完，加的油总量要大于等于消耗的油，这个证明有效吗？无法证明，但是你也找不到反例

解题思路是，从当前i出发，计算剩余油量，如果到j站，剩余油量小于0，那么说明i肯定不是起点，起点另设为j+1，j站不行，正是因为J的消耗田太多才导致没油了。还有一个变量统计总的剩余油量，总的剩余大于0，寻找的i才有意义

这道题用DP或者贪心都能做，抓住解题核心：累加和如果小于0了，那么代表这段累加和肯定不满足要求了，从下一个位置开始，重新计算累加和

1.后序遍历
2.设置状态标记，区别三种状态，得到不同的返回值

简单题，没啥说的

状态转移公式。dp[0]没有意义。这个题可以拓展成完全背包问题

楼梯要爬完，楼梯下标从0开始，一直到i-1结束
要爬过最后一个楼梯，也就要爬到第i个位置，所以dp数组初始化长度为size+1
状态转移公式：dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

这道题我记得第一次做，想不出来怎么做。这个算法是N^2的
这个题，每一个数，必须要两个数，取乘积最大，利用dp可以获取i之前的数，如果拆分了的话，能够获得的最大乘积
也即是说，一个数n，要拆分后乘积更大，还是不拆分大，通过dp数组的记录，都可以获得
因为一个数被拆分后，被拆分的数还可以继续拆分。这时就要判断，是拆分好，还是不拆分好，max比较嘛

这道题容易被二叉搜索树给迷惑住了。心里总想着有什么捷径去构造出结点更多的BST
实际上，还是依赖于dp数组对之前的结点数量的BST种类的保存，
结点数量为n，一定是有左子树和右子树之分的，变化的地方在左右子树结点的变化
dp[i] += dp[j-1] + dp[i-j]
空节点也算是一个BST

62.不同路径

63.不同路径II

221. 最大正方形

416. 分割等和子集

1049. 最后一块石头的重量 II

494. 目标和

474 一和零

518 零钱兑换 II

377. 组合总和 Ⅳ

爬楼梯进阶

322. 零钱兑换

279. 完全平方数

139. 单词拆分

常规的状态转移公式，当天的状态是由前面两天推导出来的
dp[i]=max(dp[i-1], dp[i-2]+nums[i])
遍历顺序没有讲究（毕竟是一维数组）
初始化就根据题意初始化好前两个就行

这个题要转换一下思路，首尾不能挨在一起——抢劫1-n-1或者2-n
两种抢劫方式的最大值就是题解

记忆化搜索：通过后序遍历，当前结点有两种选择，偷当前或者偷左右孩子
偷了当前结点，左右孩子就跳过去；不偷当前，就偷左右孩子

只能买入和卖出一次
使用二维dp数组，0表示持有股票，1表示不持有（卖出）股票
初始化很重要，起始持有的话，便是-prices[0]
状态转移通过前一天的持有和不持有进行推导，最后返回值一定是不持有的更大

和121只有一个地方有区别：可以无限次数买卖股票。买股票时，荷包里的钱再也不是0了，而是前面买卖股票的最大收益，再去买

多了一笔手续费罢了，手续费你可以在买入的时候就算上，也可以在卖出的时候才算上。买入+卖出才算做是一笔交易

限制了购买次数为2次

购买次数限制到了k次。递推公式和上面的123是一样的，只不过要用for循环罢了

将每一天的状态分为买入、卖出和冷静期。
买入的最大收益只能是前一天已经买入或者前一天是冷静期，然后今天买入
卖出的最大收益只能是今天卖出收益以及前一天卖出的最大收益
冷静期的最大收益来自于前一天卖出的收益

惭愧啊，这道题当时应该是在手机上打出来的，现在就忘记不会做了

- 确定dp数组的形式以及含义
            - 一维数组。dp[i] 表示从0-i严格递增子序列的长度
        - 递推公式？
            for(int j = i-1; j >= 0; --j){
                if(nums[i]>nums[j]){ dp[i] = max(dp[i],dp[j]+1); }
            }
        - 初始化
            全部置为1

这道题是300的简单版。674要求子序列必须是连续的，300没这样的要求。所以300要和i之前的每一个j比较，试图找到最大的递增子序列

开始进入二维dp数组了
这道题不要想复杂了，由于题目要求是连续子数组，所以如果i和j的数字不相同，那么之前的状态是不能在使用的！

当当当当，公共子序列来了。公共子序列和公共子数组，二字之差，差别巨大，子序列不讲究元素的连续性，只要相对顺序不发生改变即可。可以利用之前的状态！

1143最长公共子序列的换皮题，一模一样的解法

有点删除序列那个味道了，删除长的序列中的字符

第一次做不了，第二次还是做不了，哈哈哈
在判断子序列的基础上，还要统计子序列出现的次数，难度陡增

核心点是抓住s[i] 是否等于 t[j]这个点，对于392来说，相等就在上一个匹配的基础+1，不想等就“删除”母序列的长度

然后对于这道题，相等的情况下，可以沿用对角线上一个匹配的值，还可以沿用不使用当前母序列字符匹配的值，如果不相等，只能沿用不使用母序列字符匹配的值

我个人感觉，这个题把dp数组这种数学概念的思维玩尽了
首先要确定dp数组的函数，dp[i][j]表示word1[:i] 与 word2[:j] 相同的最小步数.这里要注意，经过删除之后的字符串一定是相等的
递推公式：由三个方向推导而来，删除i，删除j，或者两个都删除，毕竟左邻居、上邻居、左上角邻居都已经是相等的状态了，删除到哪个状态的次数最少选哪个

这道题还有一种逆向思维的解题方法：先求出最长公共子序列，然后用两个字符串的长度-最长公共子序列长度*2。1143 YYDS

难度升级，操作方式从删除，增加到了删除、插入以及替换三种方式，这意味着题目变得更加复杂

但是，插入和删除其实一个道理，两者相等，较短的插入一个与较长的删除一个，不是一个意思，吗？
替换就是在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

这道题有两种比较好的做法，一是双指针法（从剑指offer学到的），二是dp动态规划

双指针法的思维很巧妙。从起始点出发，向两边拓展开来。遇到不是回文子串了，就退出。对字符串的每一个位置，都要做这样的“测试”，并且，起始点可以是一个字符开始，也可以是两个字符一起开始，也就是a，或者aa。统计最后的结果

双指针法我很熟练的，dp反而不太熟悉。这次的dp也是二维数组，不过和之前有不一样了
二维dp数组出现在【矩阵图】、【背包】、【子序列】这三种问题居多
【矩阵图】的横纵坐标就是图上的坐标，这里没其他的变化
【背包】的横坐标一般表示背包的容量、纵坐标表示物品的选择
【子序列】问题，横纵坐标一般表示不同的字符串
在这道题，dp[i][j]表示用【i-j】组成的字符串是否是回文字符串，这里i肯定是小于等于j的

当i和j指向的字符不想等的话，肯定不是回文字符串
如果相等的话，还需要去判断【i+1,j-1】组成的字符串是否为回文字符串

核心思想和双指针法是类似的

和647基本上一样，通过dp数组来获取回文字符串。
当遇到回文字符串时，判断这个串的长度是不是更长，更长就记录下这个串的起始和终点坐标

回文子序列的题比回文字串要简单一些，应该说是判断情况要简单一点
回文字串要字符匹配相等的时候，需要分两种情况进行讨论：【j-i小于等于1】、【去掉i和j的字符串要是回文】
回文子串字符匹配不上时，就直接是FALSE，不需要理会

但是回文子序列不一样
回文子序列在字符匹配上的时候，直接在去掉i和j的结果上+2
如果字符匹配不上，可以删除一个字符，删除有两种选择，删除i或者删除j，选择最大的那一种

窗口内的内容是什么？

什么时候扩大窗口？

什么时候缩小窗口

反转链表

使用栈保存链表结点，再依次弹栈

第一：反转链表函数

第二：将链表保存早栈中，弹栈即可得到顺序相反的结点

分钟数存于数组，sort排序，找最小差值：nlogn

分钟数存于multiset，遍历找最下差值：logn

分钟数存于2160长的数组，遍历找最小差值：n

滑动窗口解题

每日一题：本质是翻转字符串，用规定的次数，让翻转后的字符串有最长的连续相同字符。固定翻转的方向，用滑动窗口去找：当翻转次数不超过允许值时，最长的长度

这个题同2024一样。都是翻转，只需将0翻转为1，在k次翻转内统计连续1的最大长度

这道题也可以用dp来做

这算是一个滑动窗口题。姑且设定滑动窗口内的元素都是单调递增的，那么窗口最后一个元素就是最大的，如果之后遍历的元素，小于或者等于右窗口值，那么窗口就要重置为1了，慢指针直接移动到右窗口的位置

这道题解法很简单，但是要想到这种解法，需要脑筋转一个弯。这题实际上提炼出来就是找到最长的连续子序列，其序列累加和等于target这么一个问题，而这个target==整个数组累加和 - x

第一种是移动元素的变种。移动元素是用后面合法的元素覆盖掉不合法的元素。在移动元素之后，后面一截补上0即可

第二种方法效率更高。左指针表示不含0元素的序列的end，右指针表示需要处理的序列的begin。右指针凡是遇到一个非0的元素，就将该元素交换到左指针的末尾，同时左指针后移

因为我们是从前往后遍历的，在p~back这段区间是没有被遍历过的，如果交换完，p的元素仍然是2，不能跳过，因为不能保证p之后的元素都是2. 但是p == 0就不一样的，p之前的所有元素都已经放入front里了，如果交换完等于0，那只有一个可能，交换前两指针相等。

经典的单调栈题型。从栈底到栈顶保持单调递减的规律（因为题目要求的是多少天之后温度升高），栈中存放的元素是下标（要求时间间隔）。栈中元素，从栈底到栈顶，每一个都在等待大于他自身温度的那一天到来。

每日温度的变种题型。首先挨个计算出nums2数组中，当前元素的下一个更大元素是谁，用哈希表保存，方便查询。再遍历一遍nums1，依次查询哈希表，得到最后结果

在496的基础上，增加了一个条件，循环数组。一般来说处理循环数组的方法就是将其延长一倍，但是道题由于有重复元素，这样处理起来还挺麻烦。更简单的做法是遍历两次这个数组

接雨水可以用单调栈做。栈中的元素也是按照从栈底到栈顶单调递减的方式保存，遇到大于栈顶的元素时，弹栈一次，获取两个栈顶元素，加上当前元素，组成一个两高一低的凹形，然后计算凹进去能接的雨水的面积

解题的核心或者技巧就在【弹栈一次，但是要获取栈中两个元素】。遇到更大的高度后，弹栈一次，将最低的高度弹出来，然后再获取下一个栈中的元素（大于等于刚才弹栈的元素），两高一低中间组成凹坑，便能接水了。

此题和接雨水很相似，接雨水获取两次栈顶元素，加上当前元素3个值组成凹形，此题是组成凸形。单调栈的顺序和接雨水要相反，然后要在原数组的基础上，前后增加两个0

这道题有一个隐藏满足的条件，中间的最高的柱子，弹栈弹走了之后，其依然会对之后计算产生影响。产生影响的方式便是它的下标位置，

因为我们每次取高度都是取mid对应的，也就是三者之间最高的那个值，但是宽度的取值就不是固定的了，宽度会随着计算的增加，越往后越大。这里一句两句说不清楚。但是和接雨水是很相似的，两者在数据的处理上，都有点奇妙

前k个最大的，要用小根堆，反之则用大根堆