腾讯2022实习生笔试情况与题解
5道编程题，2个小时，提前AK了，先占坑，等10点以后发题解，看看
1.竖读
模拟题，一到二星左右
只需竖着把字符放进去，转数字去掉前导零排序即可。
#include<bits/stdc++.h>
using namespace std;
string s[111111],t[11];
int a[101010];
int main(){
int n,i,j;cin>>n;
for(i=0;i<n;i++)cin>>t[i];
for(i=0;i<n;i++){
for(j=0;j<t[i].length();j++){
s[j]+=t[i][j];
}
}
for(i=0;i<t[0].length();i++)a[i]=stoi(s[i]);
sort(a,a+t[0].length());
for(i=0;i<t[0].length();i++)cout<<a[i]<<' ';
}
2.质数下标
模拟题，二星左右
可以先 O(nlogn) 或者 O(n根号n)预处理出所有素数，然后模拟就行了。
4.合并链表形成环状链表
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param a int整型vector
* @return int整型
*/
int ok[201010];
vector<int> f(vector<int>a){
vector<int>res;
for(int i=2;i<=a.size();i++){
if(!ok[i])res.push_back(a[i-1]);
}
return res;
}
int getNumber(vector<int>& a) {
// write code here
int i,j;
for(i=2;i<=2e5;i++){
if(!ok[i])
for(j=i*2;j<=2e5;j+=i)ok[j]=1;
}
while(a.size()>1)a=f(a);
return a[0];
}
};
3.攻与防
题目:
n个战士站成一排，分别编号为 1,2,3...n，战士的战斗力等于他的编号 ，有一些战士只会进攻，有一些战士只会防守。现在我们要将他们从某个点开始分成两个阵营，假设这个点为pos(0<=pos<=n) ，则编号为1,2,3....pos 的战士为第一个阵营，pos+1,pos+2...n 的战士为第二个阵营。假设 pos为 0 时，说明第一阵营没有战士，所有战士都在第二阵营。我们令第一个阵营为进攻方，第二个阵营为防守方，假设第一个阵营中能够进攻的战士战斗力总和为 w，第二个阵营中能够防守的战士战斗力总和为 v，我们希望 |w-v|的值最小，其中 || 为绝对值符号。求 |w-v|最小值
输入:
7 1000101输出:
2
前缀和，三星左右，不会的可以去刷刷牛客的动态规划专题里面有个前缀和
遍历一遍攻和防的界限即可，要用前缀和预处理之后就可以O(1)查询了。
#include<bits/stdc++.h>
using namespace std;
long long op[101010],ed[202020];
int main(){
int n,i;
string s;
cin>>n>>s;
long long sum=0;
for(i=1;i<=n;i++){
op[i]=sum+=i*(s[i-1]=='0');
}
sum=0;
for(i=n;i>=0;i--){
ed[i]=sum+=i*(s[i-1]=='1');
}
long long res=1e15;
for(i=1;i<=n+1;i++){
res=min(res,abs(op[i-1]-ed[i]));
}
cout<<res;
}
题目:
给出一个链表数组，该链表数组均是某一个环状链表的一部分，请你将这些链表数组合并成环状链表，然后需要找到一个位置，使得从这个位置将环切开后，按照顺序或逆序遍历这个环，形成的链字典序尽量小，并返回这条链。
1.链表字典序的定义：对于两个链表a,b，从头节点到尾节点遍历，找到第一个不相同的节点值，如果存在i使得a[i].val<b[i].val，那么我们就认为，a的字典序较小；比如链表{1,2,3} < 链表{1,2,4}, 链表{3,4,5}< 链表{6,7}
2.环状链表不存在相同的节点值
3.该题环状链表节点个数最小为2
4.每个链表都是在环状链表上的顺时针的一部分
5.给定的链表数组一定能组成一个环状链表
输入:
[{1,2,3},{2,3,4},{4,1}]
输出:
{1,2,3,4}
输入:
[{3,7,4},{7,4,5,1,10,3}]
输出:
{1,5,4,7,3,10}
4星模拟题
用map存每个下标的前驱和后继，然后即可还原链表的环。字典序最小意味着头节点为最小值，下一个节点为头节点前驱、后继中更小的那个。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param a ListNode类vector 指向每段碎片的开头
* @return ListNode类
*/
map<int,int>l,r;
ListNode* solve(vector<ListNode*>& a) {
// write code here
int i,mi=1e9;
ListNode*p;
for(i=0;i<a.size();i++){
p=a[i];
mi=min(mi,p->val);
if(!p)continue;
while(p->next){
r[p->val]=p->next->val;
l[p->next->val]=p->val;
p=p->next;
mi=min(mi,p->val);
}
}
ListNode*out=new ListNode(mi);
p=out;
if(l[mi]>r[mi]){
while(r[p->val]!=mi){
p->next=new ListNode(r[p->val]);
p=p->next;
}
}
else{
while(l[p->val]!=mi){
p->next=new ListNode(l[p->val]);
p=p->next;
}
}
return out;
}
};
5.小Q的最大总资产
题目:
现在有一个长度为n的价格数组a，表示某只股票每天的价格，你每天最多买入或卖出该只股票的1手股票，买入或者卖出没有手续费，且卖出股票前必须手里已经有股票才能卖出，但是持有的股票数目不受限制，并且初始资金为m元，你在任意时刻都不能进行透支，所以你的资金必须始终大于等于 0 。请问你在n天结束之后，拥有最大的总资产是多少?（总资产:股票数目*股票价格+现金)
输入
6 2 2 3 1 1 1 2输出:
6
4星dp
老话：刷牛客动态规划专题
01背包变种。定义dp[i][j]代表前i天，手上当前持有j只股票的最大现金数。那么可以根据每天选择买入还是卖出达成转移。
01背包变种。定义dp[i][j]代表前i天，手上当前持有j只股票的最大现金数。那么可以根据每天选择买入还是卖出达成转移。
#include<bits/stdc++.h>
using namespace std;
long long dp[2020][2020],a[2222];
int main(){
int n,m,i,j;
cin>>n>>m;
for(i=0;i<=n+1;i++)for(j=0;j<=n+1;j++)dp[i][j]=-1e16;
dp[0][0]=m;
for(i=1;i<=n;i++)cin>>a[i];
for(i=1;i<=n;i++){
for(j=0;j<=n;j++){
//持有不动的情况
dp[i][j]=dp[i-1][j];
//如果j大于0而且前一天的现金数目大于今天的股票价格，即股票数目大于0有可能是持有不动或者买入1只股票转化而来的状态
if(j&&dp[i-1][j-1]>=a[i])dp[i][j]=max(dp[i][j],dp[i-1][j-1]-a[i]);
// 前一天卖出一只股票和持有不动，哪个现金数目更多
dp[i][j]=max(dp[i][j],dp[i-1][j+1]+a[i]);
}
}
long long res=0;
for(i=0;i<=n;i++)res=max(res,dp[n][i]+i*a[n]);
cout<<res;
}
#include<bits/stdc++.h>
#define ll long long
using namespace std;
// 6 2
// 2 3 1 1 1 2=> 6
ll a[2002];
// dp[i][j]是指前i天手里股票个数为j的最大资产
ll dp[2002][2002];
int main() {
ll n, m;
cin >> n >> m;
for (ll i = 1; i <= n; i++) {
cin >> a[i];
}
for (ll i = 0; i < 2002; i++) {
for (ll j = 0; j < 2002; j++) {
dp[i][j] = -1e18;
}
}
ll maxAsset = m;
dp[1][0] = m;
if (m >= a[1]) {
dp[1][1] = m;
}
for (ll i = 2; i <= n; i++) {
for (ll j = 0; j <= n; j++) {
//只能卖出成0只股票或者不动
if (j == 0) {
// dp[i - 1][1] - a[i - 1] 是前一天的现金
dp[i][0] = max(dp[i - 1][1] - a[i - 1] + a[i], dp[i - 1][0]);
} else {
//如果前一天的现金数目大于今天的股票数目，那么可以买入
if (dp[i - 1][j - 1] - (a[i - 1] * (j - 1)) >= a[i]) {
//买入，前一天的现金数目减去现在的股票价格，就是现在的现金数目，然后加上股票资产，或者不动
dp[i][j] = max(dp[i - 1][j - 1] - (a[i - 1] * (j - 1)) - a[i] + j * a[i], dp[i - 1][j] + (a[i] - a[i - 1]) * j);
//卖出
dp[i][j] = max(dp[i][j], dp[i - 1][j + 1] - (j + 1) * a[i - 1] + a[i] + j * a[i]);
} else {
//只能卖出,或者不动
dp[i][j] = max(dp[i - 1][j] + (a[i] - a[i - 1]) * j, dp[i - 1][j + 1] - (j + 1) * a[i - 1] + a[i] + j * a[i]);
}
}
// maxAsset = max(dp[i][j], maxAsset);
}
}
for (ll j = 0; j <= n; j++) {
maxAsset = max(dp[n][j], maxAsset);
}
cout << maxAsset << endl;
return 0;
}
总结：不算特别难，但是代码量不小
