腾讯10.16客户端笔试
半个多月没刷题，完全没手感，菜的不行。
虽然知道没戏，还是做了一下，应该是秋招的最后一场笔试了，记录一下吧。
1. tecent no.1 90% 两个链表异或操作
#if 0
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
ListNode* xorList(ListNode* a, ListNode* b) {
// write code here
int len_a = 0;
int len_b = 0;
ListNode* heada = a;
ListNode* headb = b;
string sa = "";
string sb = "";
while (heada) {
if (heada) {
sa += to_string(heada->val);
}
heada = heada->next;
len_a++;
}
// cout<<len_a<<endl;
// cout<<sa<<endl;
while (headb) {
if (headb) {
sb += to_string(headb->val);
}
headb = headb->next;
len_b++;
}
// cout<<len_b<<endl;
// cout<<sb<<endl;
reverse(sb.begin(), sb.end());
int diff;
if (len_a >= len_b) {
diff = len_a - len_b;
for (int i = 0; i < diff; i++) {
sb.insert(sb.begin(), '0');
}
}
else {
diff = len_b - len_a;
for (int i = 0; i < diff; i++) {
sa.insert(sa.begin(), '0');
}
}
string res = "";
for (int i = 0; i < max(len_a, len_b); i++) {
if (sa[i] == sb[i]) {
res += '0';
}
else {
res += '1';
}
}
int index = 0;
while (res[index] == '0') {
index++;
}
string ret(res.begin() + index, res.end());
cout << ret << endl;
ListNode* head_ret = new ListNode(-1);
ListNode* dummy = head_ret;
for (int i = 0; i < ret.size(); i++) {
int val = ret[i] - '0';
ListNode* node = new ListNode(val);
dummy->next = node;
dummy = dummy->next;
}
return head_ret->next;
}
};
#endif
只想到了暴力解法，然而case通过率感人。 求助大佬们给个最优解
#if 0
#include<iostream>
#include<vector>
#include<bitset>
#include<limits.h>
using namespace std;
int res = INT_MAX;
int qiuhe(vector<int>& nums) {
int res = 0;
for (int val : nums)
res += val;
return res;
}
void tranverse(vector<int>& nums, int index, int k) {
if (index == k) {
int he = qiuhe(nums);
res = min(res, he);
return;
}
for (int i = 0; i < nums.size(); i++) {
bitset<32> val(nums[i]);
int ori = nums[i];
int cnt = val.count();
nums[i] = cnt;
tranverse(nums, index + 1, k);
nums[i] = ori;
}
}
int main() {
int n, k;
cin >> n >> k;
vector<int> nums(n, 0);
for (int i = 0; i < n; i++) {
int val;
cin >> val;
nums[i] = val;
}
tranverse(nums, 0, k);
cout << res;
}
#endif 3. tecent no.3 输出-1 16.67% 题目好像是，某商品有两种，一个是打折的一个是没有打折的，有不同的价格和幸福度，并且打折和不打折商品只能选择一个，求用指定的金钱购买商品，使得幸福度最高，不能刚好花完钱则输出-1.
应该是背包问题，用动态规划解决，之前做过类似的题目，可惜晚上做题大脑短路，不想思考，直接输出-1骗了点分。
#include<iostream>
#include<vector>
#include<bitset>
#include<limits.h>
using namespace std;
int main() {
int n, x;
cin >> n >> x;
vector<int> x1(n, 0);
vector<int> w1(n, 0);
vector<int> x2(n, 0);
vector<int> w2(n, 0);
for (int i = 0; i < n; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
x1[i] = a;
w1[i] = b;
x2[i] = c;
w2[i] = d;
}
cout << -1;
}
#endif 3. tecent no. 4 deque模拟 100% 模拟问题 比较简单，直接 ac
#if 1
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<deque>
using namespace std;
int main() {
int n;
cin >> n;
deque<int> arr(n, 0);
for (int i = 0; i < n; i++) {
int val;
cin >> val;
arr[i] = val;
}
vector<int> shunxu;
int front;
int back;
for (int i = 0; i < n; i++) {
front = arr.front();
back = arr.back();
if ((i + 1) % 2 == 1) {
if (front > back) {
shunxu.push_back(front);
arr.pop_front();
}
else {
shunxu.push_back(back);
arr.pop_back();
}
}
else {
if (front < back) {
shunxu.push_back(front);
arr.pop_front();
}
else {
shunxu.push_back(back);
arr.pop_back();
}
}
}
int len = shunxu.size() - 1;
for (int i = 0; i < len; i++) {
cout << shunxu[i] << " ";
}
cout << shunxu[len];
return 0;
}
#endif 5. tecent no.5 随便输出n, 骗了18.18% 好像左右脚 什么的，忘记题目了，
最后剩了了些时间本来想把动规那道题做做的，想了想鹅的hc, 哎，自己这么菜，算了吧，
笔试应该寄了，纪念秋招最后一场笔试吧，虽然没做好。
----------------------------------------------------------------------
最后祈祷一波，
希望下周百度有消息~
祝自己好运。
投递百度等公司10个岗位 >