携程笔试 3.13

第一题:给一个字符串，第i次输出i给字符，输出每次输出的第一个字符，没啥难度。第二题:排序+dp过了第三题:一开始按部就班，先求数组每个数的质因子个数，再找和最小的子数组，一开始只过了76.47，后来用HashMap存了点大数据的质因子个数，过了（没想到，当时觉得过了70已经满足了）第四题:放弃笔试以来做的最好的一次了😭😭

1.自我介绍2.Java中的集合有了解吗3.Arraylist和Linklist的区别4.集合的add和remove，遍历的时候可以add和remove嘛5.平时做项目一般采用什么集合，线程安全的有哪些集合，有没有对fail-fast有了解6.对死锁有没有了解，怎么排查死锁（使用工具，哪一个线程造成的死锁）7.对JVM有没有了解8.如何判断对象是否已经死亡，能被垃圾回收机制进行回收（可达性分析，引用计数法）9.Java的垃圾有哪些算法是否有了解10.网络协议，HTTP的状态码有哪些11.TCP协议和UDP协议的区别12.Http请求时基于TCP的还是UDP的13.Mysql包含哪些存储引擎，区...

1.直接模拟2.从小到大排序，从后往前遍历i，每次取i~n这段数组看看答案会不会更大，即不断更新ans=max(ans, a[i] + n - i + 1)。3.先预处理每个数的质因子个数a[i]。对a数组求前缀和。然后枚举长度为k的滑动窗口往后移动，更新答案4.树形dp，记dp[i]为从结点i往下走的路径为偶数的方案数。可以发现，只有所有数都为偶数时，这些数的gcd才可能为偶数，因此只需要判断数的奇偶性就行，不用去算gcd。dfs每个结点u，枚举以u为路径最高点时路径为偶数的方案数，累加起来就是答案。对于每个偶数结点u，dp[u]=u的儿子的dp和 + 1，这样就完成了dp的更新；累加答案的话，就是枚举u的每个儿子dp[i]，和他左边儿子的dp和sum，ans+=sum*dp[i]，然后sum+=dp[i]，因为以u为最高点的话，u左边和u右边的路径是可以组合起来的；第四题可能讲的不是很清楚，但属于树形dp挺常见的类型

携程笔试主要分三关：一、携程行测笔试携程校园招聘笔试内容为行测，题型包括：言语理解、数字运算、图形推理，其中图形推理包括平面类和空间类。1、言语理解主要测查报考者运用语言文字进行思考和交流、迅速准确地理解和把握文字材料内涵的能力。常见的题型有：阅读理解、言语推理。2、数字运算每道题给出一段材料，包括图表和文字，要求报考者熟练运用加、减、乘、除等基本运算法则，并利用其他基本数学知识，准确迅速地计算或推出结果，难度不大。3、图形推理携程的校招笔试中图形推理主要分为两类——平面图形和空间图形。平面图形类主要包括：既位置类、样式类、属性类和数量类；其中位置类题的特征是各图图形元素组成相同，整体或局部位...