首页 > 腾讯笔试 后台开发(4AC,最后一题不会,带代码)
头像
牛客874966080号
发布于 2021-08-22 23:21
+ 关注

腾讯笔试 后台开发(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、涂方块
完全不会,暴力也不会,求思路,私聊回复都行。

全部评论

(3) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐