9月15日腾讯 C++游戏客户端 笔试分享
前排先说一下，根据个人经验，笔试基本上只要能过线就行，对后续流程影响真的不大。
我已经不知道有多少家公司，笔试题全A，然后简历被刷，或是一面后被刷了。
我腾讯的流程其实已经结束了。
所以诸位不用对笔试成绩过分看重。
奇怪了，我发布时代码选的是C++，发出来变成plain text了
腾子这次笔试题难度还是不太大的，比美团难一些，不过肯定比米哈游网易雷火这种笔试简单的多。
1、对k个链表进行排序。
思路：初看以为是k个升序链表（样例是升序），仔细一看题目描述链表是乱序的，所以直接摧毁原始链表，提取所有数值并排序，最后用排序好的数值重新建一个链表即可，没必要在链表上进行操作。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回一个指向链表头部的指针。
* @param a ListNode类vector 指向这些数链的开头
* @return ListNode类
*/
ListNode* solve(vector<ListNode*>& a) {
vector<int> nums;
for (auto& head : a)
{
while (head != nullptr)
{
nums.emplace_back(head->val);
auto node_next = head->next;
delete(head);
head = node_next;
}
}
sort(nums.begin(), nums.end(), [](int a, int b) {return a < b; });
ListNode* head = new ListNode(nums[0]);
ListNode* tmp_node = head;
for (int i = 1; i < nums.size(); i++)
{
tmp_node->next = new ListNode(nums[i]);
tmp_node = tmp_node->next;
}
return head;
}
};
2、对一个正整数数组中的数字执行k次操作，求k次操作后数组和的最小值。对数字的操作如下：
如果x是偶数，则操作后x = 2*x + 1
如果x是奇数，则操作后x = 2*x
思路：简单贪心即可，每次操作最小的那个数字即可。用优先队列更好，但是忘了如何规定优先队列升序还是降序，所以用了map
#include<iostream>
#include<map>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
long long sum = 0;
map<long long, int> nums;
for (int i = 0; i < n; i++)
{
long long num;
cin >> num;
nums[num]++;
sum += num;
}
for (int i = 0; i < k; i++)
{
auto it = nums.begin();
long long num = it->first;
sum -= num;
if (num % 2 == 0)
num = num * 2 + 1;
else
num = num * 2;
it->second--;
if (it->second == 0)nums.erase(it);
nums[num]++;
sum += num;
}
cout << sum << endl;
return 0;
}
3、有n辆赛车，以及所有赛车的当前位置p，速度v，假设赛车均做匀速直线运动。问你t时刻后，有多少赛车的名次发生了改变？
思路：初始输入是有序的，只用对t时刻后的位置重新排序重新计算名次即可。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct car
{
int pos = 0;
int rank_now = 0;
int rank_new = 0;
};
int main()
{
int n, t;
cin >> n >> t;
vector<car> cars(n);
for (int i = 0; i < n; i++)
{
cin >> cars[n - 1 - i].pos;
}
cars[0].rank_now = 1;
for (int i = 1; i < n; i++)
{
if (cars[i].pos == cars[i - 1].pos)
cars[i].rank_now = cars[i - 1].rank_now;
else
cars[i].rank_now = i + 1;
}
for (int i = 0; i < n; i++)
{
int v;
cin >> v;
cars[n - 1 - i].pos += v * t;
}
sort(cars.begin(), cars.end(), [](car a, car b) {return a.pos > b.pos; });
int count = 0;
cars[0].rank_new = 1;
if (cars[0].rank_now > cars[0].rank_new)count++;
for (int i = 1; i < n; i++)
{
if (cars[i].pos == cars[i - 1].pos)
cars[i].rank_new = cars[i - 1].rank_new;
else
cars[i].rank_new = i + 1;
if (cars[i].rank_now > cars[i].rank_new)
count++;
}
cout << count << endl;
return 0;
}
4、对于一个字符串，将其首字符放在末尾，这个操作称为旋转字符串("abcdef" -> "bcdefa") 。对于两个字符串，如果其中一个字符串可以通过一次或多次旋转变成另一个字符串，则这两个字符串“互旋”
给你T组数据，问你每组数据中是否存在两个字符串“互旋”？
思路：观察数据量，字符串数量很多，字符串长度不长，如果两两比较肯定超时，应当用哈希表匹配。
#include<iostream>
#include<string>
#include<unordered_set>
using namespace std;
int main()
{
int T;
cin >> T;
for (int i = 0; i < T; i++)
{
int n;
cin >> n;
bool isFind = false;
unordered_set<string> strs;
for (int j = 0; j < n; j++)
{
string str;
cin >> str;
if (isFind)continue;
for (int k = 0; k < str.length(); k++)
{
std::rotate(str.begin(), str.begin() + str.length() - 1, str.end());
if (strs.find(str) != strs.end())
{
isFind = true;
break;
}
}
if (!isFind)
strs.insert(str);
}
if (isFind)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
5、有n个数字，数字可能为0可能为1，告诉你每个数字的坐标值。你可以将k个1变为0。
你每次操作可以让一个0的位置+1或是-1,。
问你最少需要几次操作使得所有0之间没有1。（如果0和1重合，视为中间有1）
思路：对于所有1
计算将1左侧所有0移动到1右侧的操作数（表示将所有0移动到这个1右侧需要的代价lcost）
计算将1右侧所有0移动到1左侧的操作数（表示将所有0移动到这个1左侧需要的代价rcost）
在所有数字左侧添加一个1，其左代价lcost = 0；在所有数字右侧添加一个1，其右代价rcost = 0；
那么，对于两个1，左侧的1的lcost和右侧的1的rcost加起来，即是将所有0移动到这两个1之间所需要的操作数。
遍历所有1，求lcost[i] 与rcost[i + k + 1]（因为可以将中间k个1变为0，所以右侧选i + k + 1）的最小值即可
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<long long> pos(n);
vector<int> color(n);
vector<int> blue_idx;
for (int i = 0; i < n; i++)
{
cin >> pos[i];
}
for (int i = 0; i < n; i++)
{
cin >> color[i];
if (color[i] == 1)
{
blue_idx.emplace_back(i);
}
}
int num_blue = blue_idx.size();
vector<long long> lcost(num_blue + 2, 0);
vector<long long> rcost(num_blue + 2, 0);
int lnum = 0;
long long lpos = 0;
long long lidx = -1;
for (int i = 0; i < num_blue; i++)
{
long long pos_now = pos[blue_idx[i]];
lcost[i + 1] = lcost[i] + (pos_now - lpos) * lnum;
for (int p = lidx + 1; p < blue_idx[i]; p++)
{
lcost[i + 1] += pos_now - pos[p] + 1;
lnum++;
}
lpos = pos_now;
lidx = blue_idx[i];
}
int rnum = 0;
long long rpos = pos[n - 1];
long long ridx = n;
for (int i = num_blue; i > 0; i--)
{
long long pos_now = pos[blue_idx[i - 1]];
rcost[i] = rcost[i + 1] + (rpos - pos_now) * rnum;
for (int p = ridx - 1; p > blue_idx[i - 1]; p--)
{
rcost[i] += pos[p] - pos_now + 1;
rnum++;
}
rpos = pos_now;
ridx = blue_idx[i - 1];
}
long long cost_min = lcost[num_blue];
for (int i = 0, j = k + 1; j <= num_blue + 1; i++, j++)
{
long long cost_now = lcost[i] + rcost[j];
if (cost_now < cost_min)
cost_min = cost_now;
//if (cost_now == 0)
//{
// int p = j - 1;
// while (p > i && lcost[i] + rcost[p] == 0)p--;
// if (cost_min > p - i)
// cost_min = p - i;
//}
//else
//{
// int p = j - 1;
// while (p > i && lcost[i] + rcost[p] == cost_now)p--;
// if (cost_min > cost_now + p - i)
// cost_min = cost_now + p - i;
//}
}
cout << cost_min << endl;
return 0;
}
第五题做了四十分钟，放弃了
腾讯一面1094人在聊