腾讯笔试后台开发（4AC，最后一题不会，带代码）

1、链表分组

第一题直接模拟即可，不贴代码了，

超时的估计是在存链表的时候每次都遍历到链表结尾再存，这样肯定超时。

其实就是考了一个翻转链表的套路，每次存的时候存链表尾，然后在最后输出的时候每个依次翻转一次链表就完事了。

2、魔法球

贪心排序

直接对魔法球进行从大到小贪心排序，从头到尾消除即可。

超时的话估计是每消除一个魔法球，就遍历剩余的球加分，这样n平方复杂度肯定超时。

其实思路就是用一个变量保存前面消除魔法球的增量，每消除一个魔方球时，就把当前魔法球和增量都加入ans，然后增量在增加就好了。

坑点：每次加的时候记得取余

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{

	int T;
	cin >> T;
	int mod = 1000000007;
	for (int i = 0; i < T; i++) {
		int n;
		cin >> n;
		
		vector<int> vec;
		for (int j = 0; j < n; j++) {
			int tmp;
			cin >> tmp;
			vec.push_back(tmp);
		}
		sort(vec.begin(), vec.end(), greater<int>());
		long long ans = 0;
		long long sum = 0;
		for (int k = 0; k < n; k++) {
			ans += (sum + vec[k]);
			ans %= mod;
			sum += (sum + vec[k]);
			sum %= mod;
		}
		cout << ans << endl;
	}
}

3、刻舟求剑

很直观的思路，奇数和偶数分组排序，奇数遍历一次，偶数遍历一次，

遍历的时候，双指针首尾，首尾相加小于载重，船+1，left++， right--，大于载重，right--，船+1，因为这个最重的人只能一个人坐船了。

我还用了二分，看别人解法应该不用二分，上述的思路直接得出最小值了，我还是贴我的二分代码出来了，没超时

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


bool findNum(vector<int>& vec1, vector<int>& vec2, int num, int w) {
	int count = 0;
	int left = 0, right = vec1.size() - 1;
	while (left <= right) {
		if (left == right) {
			count++;
			break;
		}
		else {
			int v = vec1[left] + vec1[right];
			if (v <= w) {
				count++;
				left++;
				right--;
			}
			else if (v > w) {
				count++;
				right--;
			}
		}
	}

	if (count > num) {
		return false;
	}

	left = 0, right = vec2.size() - 1;
	while (left <= right) {
		if (left == right) {
			count++;
			break;
		}
		else {
			int v = vec2[left] + vec2[right];
			if (v <= w) {
				count++;
				left++;
				right--;
			}
			else if (v > w) {
				count++;
				right--;
			}
		}
	}
	return count <= num;
}

int main() {

	int T;
	cin >> T;
	while (T > 0) {
		T--;
		int n, w;
		cin >> n >> w;
		vector<int> vec1;
		vector<int> vec2;
		for (int i = 0; i < n; i++) {
			int tmp;
			cin >> tmp;
			if (tmp % 2) {
				vec1.emplace_back(tmp);
			}
			else {
				vec2.emplace_back(tmp);
			}
		}
		sort(vec1.begin(), vec1.end());
		sort(vec2.begin(), vec2.end());
		int left = 1, right = n, pos = -1;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			if (findNum(vec1, vec2, mid, w)) {
				pos = mid;
				right = mid - 1;
			}
			else {
				left = mid + 1;
			}
		}
		cout << pos << endl;
	}
	return 0;
}

4、求字符串

维护一个严格单调递减栈即可，但维护弹栈的时候需要考虑后面的字符还够不够选

#include <iostream>
#include<stack>
#include<string>
using namespace std;

int main()
{
 int n, k;
 cin >> n >> k;
 string s;
 cin >> s;
 stack<char> stk;
 for (int i = 0; i < n; i++) {
  //维护一个严格单调递减栈
  //如果当前字符比栈顶字符大，普通单调递减栈就是直接弹出，直接栈为空，或者遇到栈顶字符比当前字符大
  //但是在该题中需要考虑，如果把栈的字符弹出了，后续字符还够不够选择，所以需要判断一下，也就是n - i > k的作用
  while (!stk.empty() && stk.top() < s[i] && n - i > k) {
   stk.pop();
   //弹出一次，可选字符k++
   k++;
  }
  //如果k小于等于0，不能加字符了
  if (k <= 0) {
   continue;
  }
  //当前字符小于或等于栈顶字符，或者栈空
  stk.push(s[i]);
  k--;
 }
 //逆序输出即可
 string ans = "";
 while (!stk.empty()) {
  ans += stk.top();
  stk.pop();
 }
 reverse(ans.begin(), ans.end());
 cout << ans << endl;
}

5、涂方块

完全不会，暴力也不会，求思路，私聊回复都行。

#腾讯笔试##笔经##腾讯#