2022-4-24腾讯技术后端场笔试

2022-4-24腾讯技术后端场笔试

Tans 3,064 2022-04-24

T1:竖着读

给n个数字字符串，每个字符串长度都为m，然后按照每一列从上往下读构成m个字符串，求这m个排序后的字符串，排序输出。

直接按列存储，然后将其转换为long long类型的值，排序即可，顺便解决了前导0问题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s,val) memset(s, val, sizeof(s))
const int inf = INT_MAX;
const int MAXN = 1e5 + 10;
int T;
int main(int argc, char * argv[]){
	int n, len;
	cin >> n;
	vector<string> g(MAXN);
	for(int i = 0; i < n; i++){
		string str;
		cin >> str;
		len = str.size();
		for(int j = 0; j < len; j++){
			g[j].push_back(str[j]);
		}
	}
	vector<ll> nums;
	for(int i = 0; i < len; i++){
		nums.push_back(stoll(g[i]));
	}
	sort(nums.begin(),nums.end());
	for(int i = 0; i < len; i++){
		cout << nums[i];
		if(i != len-1) cout << " ";
	}
 
    return 0;
}

T2: 删除非质数下标后的最终元素

给一个数组，下标从1-n，每次淘汰下标非质数的数字，问最后剩下的一个数字是什么？

这里没想到暴力可以解决的，直接先把小于1e5的所有质数筛出来，这里我用了质数筛，然后每次模拟删除即可。直至最后元素个数为1

const int MAXN = 1e5+10;
int prime[MAXN+1];
//prime[0]表示小于MAXN的素数的个数
void getPrime(){
	memset(prime, 0, sizeof(prime));
	for(int i = 2; i <= MAXN; i++){
		if(!prime[i]) prime[++prime[0]] = i;
		for(int j = 1; j <= prime[0] and prime[j] <= MAXN /i; j++){
			prime[prime[j]*i] = 1;
			if(i % prime[j] == 0) break;
		}
	}
}
class Solution {
public:
    int getNumber(vector<int>& a) {
    	getPrime();
        
        //将所有素数存入set中
    	unordered_set<int> st;
    	for(int i = 1; i <= prime[0]; i++) st.insert(prime[i]);
        
     	//这里使用两个交替数组，用来存储剩余数字
    	vector<int> old = a, neww;
    	while(neww.size() != 1){
    		neww.clear();
    		for(int i = 1; i <= old.size(); i++){
    			if(st.count(i)) neww.push_back(old[i-1]);
    		}
    		old = neww;
    	}
        cout << neww[0];
        return neww[0];
    }
};

T3:防御攻击最小距离

给一堆字符串代表一排士兵，士兵编号1~n，字符串中’0’的士兵代表进攻性的，‘1’的代表防御性的，每个士兵的攻击力或守备力为其下标值。将士兵分组，0~pos的是进攻组，只算攻击力，pos+1~n的是防御组，只算防御力。pos可以取0~n。求攻击组的攻击力和防御组的防御力的差的绝对值的最小值。

这里分别对攻击值做前缀，防御值做后缀，然后遍历下标即可，取最小即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s,val) memset(s, val, sizeof(s))
const int inf = INT_MAX;
int n, len;
int main(int argc, char * argv[]){
	string str;
	cin >> n >> str;
	len = n;
	vector<ll> attack(n+2, 0), protect(n+2, 0);
    	//攻击做前缀
	for(int i = 1; i <= len; i++){
		attack[i] = attack[i-1];
		if(str[i-1] == '0') attack[i] += i;
	}
    	//防御做后缀
	for(int i = len; i >= 1; i--){
		protect[i] = protect[i+1];
		if(str[i-1] == '1') protect[i] += i;
	}
	ll  value = INT_MAX;
	for(int i = 0; i <= len; i++){
		ll cur = abs(attack[i] - protect[i+1]);
		if(cur < value) value = cur;
	}
     cout << value;
     return 0;
}

T4:构造链表

给一个链表数组，数组中的每个链表是一个循环链表中的破碎的部分，且每个链表结点的值唯一且为数值类型，求将这个循环链表复原以后，从链表中任意一个结点正序或逆序遍历 字典序 最小的那个链表，并返回。
思路：链表中结点的值唯一，使用字典记录结点的前驱和后继，并记录最小值，然后从最小值开始遍历，并判断最小值的前驱和后继哪个更小，从更小的开始顺序遍历。

主要分为4步骤，感觉为了出题者凑题意加入了一个链表的概念，其实把链表看成数组就好了。。。。

  1. 这里我们可以先用map来维护当前节点的值和下一节点的值的状态，
  2. 随便找一个切入点，通过map遍历所有元素存到一个数组，
  3. 找到数组中最小值，作为我们的头节点
  4. 判断头节点的前驱或者后继节点的值的大小
    • 如果前驱小，那么逆序构造
    • 如果后继小，那么顺序构造。
class Solution {
public:
    ListNode* solve(vector<ListNode*>& a) {
    	unordered_map<int, int> mp;
    	vector<int> v;
    	//存储此节点和后继节点的值，key：当前节点的值 value:后继节点的值
    	for(auto nodes : a){
    		ListNode* cur = nodes;
    		while(cur){
    			if(cur->next) mp[cur->val] = cur->next->val;
    			cur = cur->next;
    		}
    	}
 
    	//转换为数组
    	int cur = (mp.begin()->first), start = cur;
    	v.push_back(cur);
    	cur = mp[cur];
    	while(cur != start){
    		v.push_back(cur);
    		cur = mp[cur];
    	}
 
    	//找到最小元素下标
    	int len = v.size();
    	auto minn = min_element(v.begin(),v.end());
    	int startIdx = std::distance(std::begin(v), minn);
 
    	//查看前驱或者后继，如果前驱小，那么inv=-1， 如果后继小，那么inv = 1
    	int inv = 1;
    	if(v[(startIdx+1)%len] > v[(startIdx-1+len)%len]) inv = -1; 
 
    	//构造链表
    	ListNode* fake = new ListNode(-1), *curr = fake;
    	for(int i = 0 ; i < len; i++){
    		curr->next = new ListNode(v[(startIdx + inv + len) % len]);
    		curr = curr->next; 
    	}
    	return fake->next;
    }
};

T5: 股票问题

股票问题进阶版本，没时间写了，最后判断了一下如果股票价格是逆序的，那么就输出初始资金，过20%。

dp[i][j]dp[i][j]表示第i天拥有j支股票的现金金额
转移方程：
dp[i][j]=max(dp[i−1][j],dp[i−1][j−1]−price[i],dp[i−1][j+1]+price[i])dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] - price[i], dp[i-1][j+1] + price[i])

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s,val) memset(s, val, sizeof(s))
const int inf = INT_MAX;
 
int T;
int main(int argc, char * argv[]){
	int n, m;
	cin >> n >> m;
	vector<int> price(n);
	for(int i = 0 ; i < n; i++) cin >> price[i];
	ll dp[n][n];
	//初始化
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++) 
			dp[i][j] = -1;
 
	//第0天为m
	dp[0][0] = m;
	if(m >= price[0]){
		dp[0][1] = m - price[0];
	}
	for(int i = 1; i < n; i++){
		for(int j = 0; j < n; j++){
			dp[i][j] = dp[i-1][j];
			//买一
			if(j > 0 and dp[i-1][j-1] != -1 and dp[i-1][j-1] >= price[j]){
				dp[i][j] = max(dp[i][j], dp[i-1][j-1] - price[i]);
			}
			//卖一
			if(j < n-1 and dp[i-1][j + 1] != -1){
				dp[i][j] = max(dp[i][j], dp[i-1][j+1] + price[i]);
			}
		}
	}
	ll ans = 0;
	for(int i = 0; i < n; i++){
		if(dp[n-1][i] == -1) continue;
		ans = max(ans, dp[n-1][i] + i * price[n-1]);
	}
	cout << ans;
    return 0;
}

有思路的小伙伴可以评论区分享一下呀！

牛客上Java版本题解:题解

其他笔试分享

  1. 2022京东春招笔试4-2
  2. 腾讯音乐笔试2022-4-7场
  3. 2022-4-14携程笔试
算法 后端开发 笔试