2020年腾讯精选面试题及答案
1.
删除字符串S1中在字符串S2中岀现的字符。
基本思路:把si的字符存到一个曙七里面，然后遍历麗,看是否出现过，出现过就erase 掉。但是直接输出set的元素这样会改变顺序，要想顺序不变，就顺序遍历一下si看 是否出现，出现就输出。 #include
#include 〈Map, using namespace std; typedef long long LL; const int maxn=1005; set string si,s2; cin?sl?s2; int len=sl. length(); for (int i=0;i s. insert (si [i]); len=s2. length(); for (int i=0;i if (s. count(s2[i])) s? erase(s?find(s2[i])); 1 len=sl. length(); for (int i=0;i if (s. count(si[i])) cout?sl[i]; cout< 2. 求一个论坛的在线人数，假设有一个论坛，其注册ID有 两亿 个，每个ID从登陆到退岀会向一个日志文件中记下登陆 时间和退岀时间，要求写一个算法统计一天中论坛的用户在 线分布，取样粒度为秒。 —天总共有3600*24=86400秒。 定义一个长度为86400的整数数组intdelta [86400],每个整数对应这一秒的人数变化 值，可能为正也可能为负。开始时将数组元素都初始化为0。 然后依次读入每个用户的登录时间和退出时间，将与登录时间对应的整数值加1,将与 退出时间对应的整数值减1。 这样处理一遍后数组中存储了每秒中的人数变化情况。 定义另外一个长度为86400的整数数组intonline.num [86400],每个整数对应这一秒 的论坛在线人数。 假设一天开始时论坛在线人数为0,则第1秒的人数online_num[0]=delta[0] o第n+1 秒的人数 online_num [n] =online_num [n~l] +de 11 a [n]。 这样我们就获得亍一天中任意时间的在线人数。 3. 有序链表合并. /林 * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }； */ class Solution { public： ListNode* mergeTwoLists(ListNode* 11, ListNode* 12) { if (11 == NULL) { return 12; } else if (12 == NULL) { return 11; } else { if (ll->val <= 12->val) { ll->next = mergeTwoLists(ll->next, 12); return 11; se { 12~>next = mergeTwoLists(11, 12->next); return 12; 4. 有n种硬币，面额分别为Ln,每种硬币都有无限个，假 设要付 款的金额为mo m/n+J J(m%n) 5. 一个数列:-12-34-56…询问q次，每次询问区间[l,r] 的区间和， 输岀每个询问的答案。 第1个和第2个加起来为1,第3, 4个加起来也为1…… 所以前i项和为： i/2+(i&l)*i; 区间和可以用前i项和算出来了 6. 牛妹有剪刀，石头，布(以0, 1, 2表示)三种卡片无限 张。现在 牛妹拿岀n张排成一排。然后你也拿岀n张牌一一 对应比对。若赢一局则获得一分。若你想得k分。现在输入 n, k和牛妹的n张牌分别是什么，你想要恰好得k分，有多 少种方法。 很容易想到答案跟牛妹每一张牌是什么'没有关系。没一张牌只需要考虑嬴、不嬴。 嬴k分，那就是从n张牌中篁出k张嬴， 其他输，所以组合数c (n, k).对于嬴了答k张，只有一种方法，但是对于剩下的n-k张, 都有平局和输掉两种情况，所以是2的n-k次方。 两者相乘就是答案。 结果很大对mod=le9+7职余，用到同余定理。 求2的幕直接暴力求(当然也可以快速嘉) 求组合数的时候用到除法， 又要职余,所以用到逆元。所以用到逆元公式(当然还有其他求法)：Pow (x, mod-2)%mod; 但是mod=le9+7,所以暴力求幕会超时, 方法是用快速求幕法压缩时间(快速幕就不贴代码了) typedef long long 11; 11 fast (11 a, 11 n) // 快速幕 pow(a,n) 11 inv(ll x, 11 mod) [ return fast (x, mod~2); 7. const的含义及实现机制,比如:const int 1,是怎么做到i只 可读 的？ const用来说明所定义的变量是只读的。 这些在编译期间完成，編译器可能使用常数直接替换掉对此变量的引用。 8.有一个射击游戏有m种颜色的气球，颜色分别为此m现 在一个 人开了n枪，告诉你一个数列，表示打爆的气球颜色 分别是多少。(注意，0表示这一枪没有打中，mmp这里害 得我debug T好久)求一个最小区间[l,r],在区间内包含了 所有l~m颜色。输岀区间长度。 这个題是XUPT 2019寒假训练最后一场比呑的原題的强化版。刚好我做了并且在 biiibix±给学弟学妹们讲了，很奈斯。 用一个变量维护当前区间里有多少种颜色，用book数组表示第i种颜色在当前区间内 出现了多少次。 然后尺取。 9.到商店里买200的商品返还100优惠券（可以在本商店代 替现 金）。请问实际上折扣是多少？ 由于优惠券可以代替现金,所以可以使用200元优惠券买东西，然后还可以获得100元的 优惠券。 假设开始时花了 x元,那么可以买到xM/2枝/4+.的东西。所以实际上折扣是50%（当然， 大部分 时候很难一直兑换下去，所以50%是折扣的上限） 如果使用优惠券买东西不能获得新的优惠券，那么总过花去了 200元，可以买到200+100 元的商品，所以实际折扣为200/300=67%。 10. TCP三次握手的过程,accept发生在三次握手哪个阶段？ accept发生在三次握手之后。 第一次握手:客户端发送syn包（syn=j）到服务器。 第二次握手:服务器收到syn包，必须确认客户的sY（ack=j+l）,同时自己也发送一个ASK 包（ask=k）。 第三次握手:客户端收到服务器的SYN+ACK包,向服务器发送确认包ACK（ack=k+l）。 握手完成后，客户端和服务器就建立了 tcp连接。这时可以调用accept函数获得此连 接。 11. 用UDP协议道讯时怎样得知目标机是否获得了数据包？ 可以在每个数据包中插入一个唯一的ID,比如timestamp或者逢増的into 发送方在发送数据时将此ID和发送时间记录在本地。 接收方在收到数据后将ID再发给发送方作为回应。 发送方如果收到回应，则知道接收方已经收到相应的数据包；如果在指定时间内没有收 到回应，则数据包可能丢失，需要重复上面的过程重新发送一次，直到确定对方收到。 12. 求一个论坛的在线人数，假设有一个论坛,其注册ID有两 亿 个，每个ID从登陆到退岀会向一个日志文件中记下登陆时 间和退岀时间，要求写一个算法统计一天中论坛的用户在线 分布，取样粒度为秒。 —天总共有3600*24=8600秒。 定义一个长度为86400的整数数组int delta[86400],每个整数对应这一秒的人数变化 值，可能为正也可能为负。开始时将数组元素都初始化为0。 然后依次读入每个用户的登录时间和退出时间，将与登录时间对应的整数值加L将与 退出时间对应的整数值减1。 这样处理一迷后数组中存储了每秒中的人数变化情况。 定义另外一个长度为86400的整数数组mt online num [86400, §个整数对应这一秒的 论坛在线人数。 假设一天幵始时论坛在线人数为。，则第：秒的人数online num[0]= delta [0] o第n+1 秒的人数 line num[n]= online num[n\ 这样我们就获得了一天中任意时间的在线人数。 13. 从10G个数中找到中数在一个文件中有10G个整数，乱序
2020年腾讯精选面试题及答案
