文末免费送电子书：七月在线干货组最新 升级的《2021 最新大厂 AI 面试题》免费送！
问题 1：删除链表倒数第 K 个节点
该题为 leetcode 第 19 题。
在对链表进行操作时，一个常用的技巧就是添加一个哑结点（dummy node）,它的 next 忠贞纸箱链表的头结点，这样就不需要对头结点进行特殊判断了。
- 思路一：计算链表长度
先对链表进行一次遍历，得到链表的长度 L，随后再从头节点开始对链表进行一次遍历，当遍历到第 L-n+1 个节点时，就是需要删除的节点。当我们在头结点前面加上 dummy 节点后，删除的节点就变为了 L-n+1 的下一个节点，通过修改指针来完成删除操作。
代码如下：
时间复杂度：O(L)，其中 L 是链表的长度。
空间复杂度：O(1)。
- 方法二：栈
在对链表进行遍历时将所有的节点依次放入栈，根据栈先进后出的原则，我们弹出的第 n 个节点就是需要删除的节点，且此时栈顶的节点就是待删除节点的前驱节点。
代码如下：
时间复杂度：O(L)，其中 L 是链表的长度。
空间复杂度：O(L)，其中 L 是链表的长度。主要为栈的开销。
- 方法三：双指针
该方法的优点在于不需要预处理链表的长度
使用两个指针 first 和 second 同时对链表进行遍历，并且 first 比 second 超前 n 个节点。当 first 遍历到链表的末尾时 second 就恰好处于倒数第 n 个节点。
代码如下：
时间复杂度：O(L)，其中 LL 是链表的长度。
空间复杂度：O(1)。
今天给大家一个超棒的课程福利——【金融欺诈比赛与序列模型】特训课程！限时 1 分秒杀！
本课从 kaggle 欺诈比赛和序列模型两个角度带你深入了解金融风控领域知识！
kaggle 欺诈比赛中：会从比赛背景知识介绍、效率优化，到数据分析、特征工程，再到模型分析、超参数调优，给你一个参赛必备整体思路；
序列模型中：会从 RNN、LSTM、GRU，到 Seq2seq、Attention，再到 Transformer 及案例，带你充分了解金融风控领域中需要掌握的序列模型。
课程配备优秀讲师和助教团队跟踪辅导、答疑，班主任督促学习，群内学员一起学习，对抗惰性。同时课程还配备专业职业规划老师，为你的求职规划，涨薪跳槽保驾护航。
课程链接：https://www.julyedu.com/course/getDetail/303
问题 2：将数组划分为给定和为 k 的 2 部分。
该题为 leetcode416 题，结题思路如下：
背包问题——能不能装满容量为 target 的背包
本题要求把数组分成两个等和的子集，相当于找到一个子集，其和为 sum/2，这个 sum/2 就是 target
具体步骤如下：
- 本文地址：2021 年七月中旬，虾皮北京提前批 - 算法工程师 5 道面试题
- 本文版权归作者和AIQ共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出
- 特例：如果 sum 为奇数，那一定找不到符合要求的子集，返回 False。
- dp[j]含义：有没有和为 j 的子集，有为 True，没有为 False。
- 初始化 dp 数组：长度为 target + 1，用于存储子集的和从 0 到 target 是否可能取到的情况。
比如和为 0 一定可以取到（也就是子集为空），那么 dp[0] = True。
- 接下来开始遍历 nums 数组，对遍历到的数 nums[i]有两种操作，一个是选择这个数，一个是不选择这个数。
－不选择这个数：dp 不变
－选择这个数：dp 中已为 True 的情况再加上 nums[i]也为 True。比如 dp[0]已经为 True，那么 dp[0 + nums[i]]也是 True
- 在做出选择之前，我们先逆序遍历子集的和从 nums[i]到 target 的所有情况，判断当前数加入后，dp 数组中哪些和的情况可以从 False 变成 True。
（为什么要逆序，是因为 dp 后面的和的情况是从前面的情况转移过来的，如果前面的情况因为当前 nums[i]的加入变为了 True，比如 dp[0 + nums[i]]变成了 True，那么因为一个数只能用一次，dp[0 + nums[i] + nums[i]]不可以从 dp[0 + nums[i]]转移过来。如果非要正序遍历，必须要多一个数组用于存储之前的情况。而逆序遍历可以省掉这个数组）
dp[j] = dp[j] or dp[j - nums[i]]
这行代码的意思是说，如果不选择当前数，那么和为 j 的情况保持不变，dp[j]仍然是 dp[j]，原来是 True 就还是 True，原来是 False 也还是 False；
如果选择当前数，那么如果 j - nums[i]这种情况是 True 的话和为 j 的情况也会是 True。比如和为 0 一定为 True，只要 j - nums[i] == 0，那么 dp[j]就变成了 True。
dp[j]和 dp[j-nums[i]]只要有一个为 True，dp[j]就变成 True，因此用 or 连接两者。
最后就看 dp[-1]是不是 True，也就是 dp[target]是不是 True
代码如下：
时间复杂度：O(n * target)
空间复杂度：O(target)
问题三：二叉树的后序遍历（非递归）
- 方法一：递归
树本身就有递归的特性，因此递归方法最简单。
代码如下：
时间复杂度：O(n)，n 为树的节点个数
空间复杂度：O(h)，h 为树的高度
- 方法二：迭代
注意：该代码是基于前序遍历改来的，由于前序遍历是中左右，后序遍历是左右中，所以只需要写出中右左，再进行反转即可得到左右中。
代码如下：
时间复杂度：O(n)，n 为树的节点个数
空间复杂度：O(h)，h 为树的高度
问题 4：怎么求特征重要性（GBDT RF 等）
RF 有两种方法：
- 通过计算 Gini 系数的减少量 VIm=GI−(GIL+GIR) 判断特征重要性，越大越重要。
- 对于一颗树，先使用 OOB 样本计算测试误差 a，再随机打乱 OOB 样本中第 i 个特征（上下打乱特征矩阵第 i 列的顺序）后计算测试误差 b，a 与 b 差距越大特征 i 越重要。
GBDT 计算方法：所有回归树中通过特征 i 分裂后平方损失的减少值的和/回归树数量 得到特征重要性。
在 sklearn 中，GBDT 和 RF 的特征重要性计算方法是相同的，都是基于单棵树计算每个特征的重要性，探究每个特征在每棵树上做了多少的贡献，再取个平均值。
Xgb 主要有三种计算方法：
- importance_type=weight（默认值），特征重要性使用特征在所有树中作为划分属性的次数。
- importance_type=gain，特征重要性使用特征在作为划分属性时 loss 平均的降低量。
- importance_type=cover，特征重要性使用特征在作为划分属性时对样本的覆盖度。
评论区回复 “2021”，七月在线干货组最新升级的《2021 大厂最新 AI 面试题 [含答案和解析， 更新到前 121 题]》，免费送！
持续无限期更新大厂最新面试题，AI 干货资料，目前干货组汇总了今年 3 月-6 月份，各大厂面试题。
注意：本文归作者所有，未经作者允许，不得转载
