美团内推

选择题跳过。编程题三题T1 签到，排序去重即可。T2 问刚好等于x。考虑01背包（下标从1开始）。dp[i][j][k]表示到第i个数，总共选取了j个，k=0表示[1~i]都没多次操作（都没加倍）。k=1表示[1~i]存在加倍的情况，可能是i，也可能是之前的某次。列出状态转移方程：dp[i][j][0] = min(dp[i-1][j][0], dp[i-1][j-a[i]/2][0]+1) 表示不选和选的情况。dp[i][j][1] = min(dp[i-1][j][1], dp[i-1][j-a[i]/2][1]+1, dp[i-1][j-a[i]][0]+1) 表示不选、选择但是不多次操作、选择并多次操作的情况。最后输出min(dp[n][x][0],dp[n][x][1])即可，若为inf则输出-1.第一维可以优化掉，空间O(x)，时间O(nx)。T3 样例给的比较号是<和>这种，很神秘，最后发现直接改成都行。也考虑dp。先把等号去掉，那个不影响答案。假设有len个运算符dp[i][j]表示到第i个运算符右侧的数，选择j，所得到的方案数。如果第i个运算符是 > ，说明右侧的数更小，则 dp[i][j] = dp[i-1][j+1] + dp[i-1][j+2] + ... + dp[i-1][m]如果第i个运算符是 初始化dp[0][1~m] = 1，表示最左侧的数取任何数的方案数都是1最后对dp[len][1~m]求和即可。当然直接算会超时，毕竟要求和。实际上如果第i个运算符是 >，那么由于dp[i][j+1] = dp[i-1][j+2] + ... + dp[i-1][m]，因此dp[i][j] = dp[i][j+1] + dp[i-1][j+1]。同理如果第i个运算符是 由于i只用到2个，因此可以压缩一维到大小为2.最后空间复杂度O(2*m) = O(m)，时间复杂度O(n*m)#笔试##小红书#

1.问了一下学校 哪里人2.问了一下有没有做过数据挖掘 机器学习的项目/竞赛3.问项目4.有没有其他offer 想做什么方向

1. 选择题 20道， 考察了https首部头, STL中的入出栈顺序, Linux 命令, sql 语法, 智能指针，struct与class区别等八股。    我的情况：保守估计做对了至少一半。2. 三道编程题：    2.1 好像是给n个字符串，然后按顺序输出第一次出现的字符串，  解：unordered_map 哈希一下。    2.2 背包，问题描述有点麻烦，反正就是问 通过已有账号引流到x需要至少多少个账号，其中可以只对一个账号多次引流，解：dp[i][j][0 or 1],也可以滚动数组优化一下，最后一维度0表示对第i个账号没多次引流的最少次数，1则~引流后的最少次数。    2.3 好像是给个数字的上限，然后让你找出排列组合的方案数，需要对1e9+7取模， 给了的符号表示排列组合要满足的大小关系。解：从前往后dp一下    我的情况： 100 100 100求个面试啊，鼠鼠找不到暑期实习了

三志愿复活赛（1）自我介绍（还问了到岗时间和实习时长）（2）深挖论文（让我共享屏幕，打开论文讲）（3）八股（model.train()和eval()区别，BN和LN的区别）（4）算法题：leetcode原题---编辑距离（边界没处理好，只通过了样例）（5）面试官：如果给你offer但是业务方向不是CV，你愿意吗？答：不愿意，只想做CV（现在回想过来，真想给当时自己一巴掌）（6）反问： 我：为什么没有问我大模型方面的问题？面试官：我看你简历上没有大模型的内容。（我寻思你都知道我简历上没内容，干嘛还找我约面阿）状态：面完三个小时后，回到人才库再见了团子