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;
}