2021年腾讯精选面试题及答案
根据给定文件的信息，我们可以总结出以下几个IT领域的知识点：
1. 字符串操作：删除字符串S1中在字符串S2中出现的字符
题目描述： 编写一段程序来删除字符串S1中所有在字符串S2中出现的字符。
解决思路：
-
初始化集合：使用一个
set来存储S1中的所有字符。 -
遍历S1并插入集合：遍历字符串S1，并将S1中的每个字符插入set中。
-
遍历S2并删除：再次遍历字符串S2，如果S2中的字符存在于set中，则从set中删除该字符。
-
输出最终结果：最后遍历S1，如果S1中的字符依然存在于set中，则输出该字符。
示例代码：
#include <iostream>
#include <set>
#include <string>
using namespace std;
int main() {
string s1, s2;
cin >> s1 >> s2;
set<char> charsInS1;
for (char c : s1) {
charsInS1.insert(c);
}
for (char c : s2) {
if (charsInS1.find(c) != charsInS1.end()) {
charsInS1.erase(c);
}
}
for (char c : s1) {
if (charsInS1.find(c) != charsInS1.end()) {
cout << c;
}
}
cout << endl;
return 0;
}
char>string>set>iostream>2. 在线人数统计算法
题目描述： 假设有一个论坛，其注册ID有两亿个，每个ID从登录到退出会向一个日志文件中记录登录时间和退出时间。要求设计一个算法统计一天中论坛的用户在线分布，取样粒度为秒。
解决方案：
-
定义数组delta[]：创建一个长度为86400的整数数组
int delta[86400]，用于记录每秒钟的人数变化情况。 -
读取登录和退出时间：读取每个用户的登录时间和退出时间，并更新delta数组。
-
计算在线人数：创建另一个长度为86400的整数数组
int onlineNum[86400]来记录每一秒的在线人数。利用delta数组来计算每秒钟的在线人数。
示例代码：
#include <iostream>
using namespace std;
int main() {
int delta[86400] = {0}, onlineNum[86400];
// Read login and logout times and update delta[]
// ...
onlineNum[0] = delta[0];
// Assume forum starts empty
for (int i = 1; i < 86400; ++i) {
onlineNum[i] = onlineNum[i - 1] + delta[i];
}
// Output the online number distribution
for (int i = 0; i < 86400; ++i) {
cout << \"Second \" << i << \": \" << onlineNum[i] << \" users online\" << endl;
}
return 0;
}
iostream>3. 有序链表的合并
题目描述： 合并两个已排序的单链表。
解决思路：
-
检查空链表：如果任一链表为空，则返回另一链表。
-
递归合并：比较当前节点的值，将较小的节点连接到合并后的链表，并递归地调用函数合并剩余部分。
示例代码：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL) return l2;
else if (l2 == NULL) return l1;
else if (l1->val <= l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};
4. 组合问题：计算特定条件下可能的方法数量
题目描述： 牛妹有无限张剪刀（0）、石头（1）、布（2）三种卡片，现在她拿出n张卡片排成一行。你同样拿出n张卡片与之比较。如果你希望得到k分，有多少种方法可以实现这个目标？
解决思路：
-
确定赢得分数的方法数： C(n, k)表示从n张牌中选出k张来赢得的方法数。
-
考虑平局和输的情况：对于剩余的(n - k)张牌，每张牌都有平局或输两种选择，因此总的可能性数为2^(n - k)。
-
最终结果：结果是C(n, k) * 2^(n - k)，并对其取模1e9 + 7。
示例代码：
typedef long ll;
ll fast(ll a, ll n, ll mod) {
ll res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
ll inv(ll x, ll mod) {
return fast(x, mod - 2, mod);
}
ll C(ll n, ll k, ll mod) {
ll res = 1;
for (ll i = 1; i <= k; ++i) {
res = res * (n - k + i) % mod * inv(i, mod) % mod;
}
return res;
}
int main() {
ll n, k, mod = 1000007;
cin >> k;
ll ans = C(n, k, mod) * fast(2, n - k, mod) % mod;
cout << ans << endl;
return 0;
}
以上是基于给定文件中的描述和部分代码示例所整理的关键知识点。
