type
status
date
slug
summary
tags
category
icon
password
Last edited time
Apr 28, 2024 09:47 AM
携程春招实习笔试题解
📝 主旨内容
最少加几个o(贪心，模拟)
游游拿到了一个仅由小写字母组成的字符串，她准备向其中添加一些'0'字符，使得操作后的字符串中，有尽可能多的连续子串恰好等于"you"。游游想知道最少需要添加几个字符？
输入描述：
输出描述：
示例 1
贪心，有
yu就加上o 注意不是统计最后you的数量重排c数组(哈希)
游游拿到了3个大小为n的数组a, b, c。他准备重排c数组，使得有尽可能多的下表i满足ai+bi=ci,你能帮帮他吗
输入描述
输出描述
示例1
对数组c用哈希表计数即可，注意数字不能重复使用(如果是Java/C++注意
a[i]+b[i]会溢出整型，如果溢出了肯定凑不出，因为数组c最大不超过整型范围)素数合并(贪心，思维)
游游拿到了一个数组，她每次操作可以将相邻的两个素数元素进行合并，合并后的新数为原来的两个数之和，并删除原来两个数。游游希望最终数组的元素数量尽可能少，你能帮帮她吗?
输入描述：
输出描述：
示例
除2以外所有的质数都是奇数，两个奇数相加一定是偶数，一定有2这个约数，所以一定不是质数。但是2加上一个奇数可能是质数也可能不是，例如2+7=9不是质数，2+5=7是质数，所以优先处理2，如果左右相邻有质数并且合并之后仍是质数的，最后贪心合并全部的相邻质数
加入新节点后的直径(树形DP，BFS)
游游定义一棵树的直径为:任意两个节点的距离的最大值。现在游游拿到了一棵树，她定义f(i)为:对i号节点上再连接一个新的叶子节点后，树的直径长度。游游希望你求出f(1)到f(n)的值。
输入描述：
输出描述：
示例：
如果某个不是树的直径上的点，那么即使添加了一个点，树的直径也不变。两次BFS求出树的直径(大小和端点到各点距离)，不用DFS避免爆栈
🤗 总结归纳
感觉第三题还是有思维在里面的，虽然想到了2，但是实现起来还是需要些功夫的，因为不可能真的“合并”或者删除
📎 参考文章
- 作者:ziuch
- 链接:https://ziuch.com/article/Ctrip-Spring-Recruitment-Internship-Test
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。