3月13日携程（暑期实习）机考思路分享

第一题:模拟。直接循环枚举一遍即可

第二题:贪心枚举

1.先考虑如果选上所有数，答案就是 数组最小值 + n 。

2.如果需要取消选择某个数，一定是从最小值开始取消。所以排序，从小到大以此取消选择，每次更新最小值即可

第三题:滑动窗口

先计算每个数字的质因子个数，将问题转化为找到长度为k的连续子数组中权值和最小的部分，从而使剩余部分的权值和最大。这个问题直接滑动窗口或者前缀和解决即可

注意：求解质因子的方法应该使用根号算法 ， 否则会超时

第四题:DFS + 简单数学

1.发现gcd(arr) 是 偶数 等价于 arr里不能有奇数

2.挖掉树上所有奇数节点之后，剩下的连通块里的所有简单路径都是合法答案

问题化简为：统计偶数节点连通块内所有简单路径数，每个连通块的路径数为 k*(k+1)/2

关注我：二仙桥耐笔王 ，带你做好每一场大厂笔试！

#技术岗笔试题求解# #哪些公司笔/面试难度大？#