算法刷题模型整理（五）

LC046 全排列

解题模型：

​ dfs，标记

核心思路：

​ 添加一个标记数组记录哪些数已被选取，然后即开始dfs

易错点：

• 标记数组应使用unordered_map，因为依题意数字有负数，或者用数组，但是在每次访问时都加最小数的绝对值
• 标记数组记得要初始化

LC051 N皇后

解题模型：

​ dfs，标记

核心思路：

​ 依照题目意思，每行只能放一个皇后，所以以行进行递归，参数为ans，temp，当前行f，皇后数量n，递归n层，表示n行，每层递归n个分支，表示n列，使用三个数组记录每个格子是否符合规则，一个记录列是否合法，一个记录从左到右的斜线，编号可用横纵坐标之差表示，一个记录从右到左的斜线，编号可用横纵坐标之和表示，然后进行回溯

易错点：

• temp数组可以先初始化n个有n个.的字符串，确定位置时修改对应的.为Q，回溯时再重新变回.
• 三个visit数组大小，记录列的数组大小为n，另外两个为2n，注意记录从左到右的斜线数组会有负数，访问时加上n-1

贪心

LC455 分发饼干

解题模型：

​ 双指针

核心思路：

​ 对两个数组进行从小到大排序，双指针分别对两个数组进行遍历，当前饼干若能满足当前孩子，答案加一，两个指针后移，不满足则单独后移饼干指针

易错点：

• 注意边界，指针不要超过数组长度
• 饼干大小等于胃口时也符合条件

LC053 最大子数组和

解题模型：

​ 数组

核心思路：

​ 可以发现，答案子数组的左边和右边再增大时，和就会减少，说明左边和右边的子数组是负数，所以我们只要遍历数组，更新和的值，维护一个最大和变量，当和小于0时就直接清零，从下一个元素重新开始遍历

易错点：

• 最大和变量初始值应为INT_MIN或numeric_limits<int>::min()
• 本题需要维护最大和、当前和两个变量

LC122 买卖股票的最佳时机II

解题模型：

​ 数组

核心思路：

​ 一个区间内能得到的最大利润等于第一天和第二天的利润差、第二天和第三天的利润差……之中大于零的几个的和，所以只要遍历数组即可，若今天利润减前一天利润大于零则加入总利润中

易错点：

• 遍历下标从1开始，然后判断下标为i的利润减去下标为i-1是否加入总利润
• 可以使用max(0，利润差)

LC055 跳跃游戏

解题模型：

​ 数组

核心思路：

​ 维护一个最远可到达距离，初始值0，遍历数组，若当前下标小于等于最远可到达距离，就更新最远可到达距离为max(最远可到达距离，当前下标+当前位置的跳跃距离)，若当前下标大于最远可到达距离则说明不能到达最后一个下标，直接break，若最远距离已经大于最后一个下标也直接break，说明可以到达

易错点：

• 当前下标无法到达时，直接提前退出
• 最远距离已经大于最后一个下标时，直接提前退出

LC406 根据身高重建队列

解题模型：

​ 数组

核心思路：

​ 先对原数组进行排序，先按照身高降序排序，身高相同的按照前面身高大于等于自身的数量升序排序，然后直接遍历排好的数组，按照每个元素的前面身高大于等于自身的数量插入答案数组对应下标，因为后面插入的身高更低，不会对前面造成影响，而身高更高的已经插入完毕了，直接插到要求的位置上刚好满足条件

易错点：

• sort可用lambda表达式
• 这题虽然插入操作多，但是实际上vector性能比list更优，因为cpu缓存可以根据局部性原理存上附近的一整块内存，缓存速度极快，所以数据量不大，要进行频繁插入操作时还是使用vector