2022.5.15 微众银行 C++后端开发笔试真题
题型
选择题：20道
编程题：3道
选择题：
20道选择题，涉及的知识比较广泛：数据库，数据结构，编译原理，c++,网络等都有涉及。而且不允许离开页面，离开页面会被记录，应该可以看手机，但是我这边信号不好，手机在很远的地方开热点，所以搭的也比较差，时间原因没有记录下来。印象深刻的题目有：
8题：那种文法可以用下推自动机推导？盲选三型文法。
6题：动态规划和贪心的区别？我感觉应该是最优子结构的不同，选了这个。
9题：关于存储过程的题目，找描述错的。我选了可以用控制结构，这个确实一点都不记得了。
编程题：
三道代码题，前两道都A了，最后一个82%。但是最后一个比较奇怪。
第一题：十六进制
题目描述:
Kimi同学最近在学习进制转换。众所周知，在表示十六进制数时，除了0-9这十个阿拉伯数字外，还引入了"A" 、"B”、 "C" 、"D"、 "E" 和"F"这六个英文字母(不区分大小写)。现在给你一个十进制正整数， 请问在将其转换为十六进制之后，对应的十六进制表示中有多少位是字母?
输入描述
单组输入。输入一个十进制正整数N (N<=10^6)。
输出描述
输出将N转换成t六进制数字后所包含的字母位的数量，如果没有字母位则输出0。
我的题解：
// 第一题
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
int main(){
unsigned long long int n,x;
string s;
char c;
cin >> n;
int ch_size=0;
// cout << sizeof(bool) << " -- " << sizeof(int) << endl;
while(n != 0){
x = n % 16;
// cout << x << endl;
if(x < 10){
c = x + '0';
}else{
ch_size++;
c = x + 'A' - 10;
}
s = c + s;
n = n / 16;
}
// if(s == ""){
// cout << 0;
// }else{
// cout << s;
// }
cout << ch_size << endl;
return 1;
}
/*
测试用例
20
*/
结果
AC
第二题：努力的人
题目描述:
小亮来到了一个特殊的国度，这个国家的人有一个奇特的地方:如果一个人身边的人都比自己强，那么这个人会开始努力提升自己。 现在有n个人排成一排，因为视线是有限的，所以每个人只能看见左边的x个人和右边的y个人。每个人都有一个能力值a_ i,如果他视线能看到的人能力值都比他高，则他会开始努力提升自己。如果左边人数不足x个人，则左边的视线能看见左边所有人，如果右边并没有y个人，那么右边的视线仅仅覆盖右边的所有人。 已知这n个人的编号从左到右为1~n，请问努力的人中最左边的人编号是多少。 保证这n个人的能力值都不重复，且都在10^6以内。
输入描述
输入第一行包含三个空格隔开的正整数，n x y,含义如题。 (1<=n<=10^5，1<=xy<= 0000 第二行有n个正整数，表示n个人的能力值，中间用空格隔开。
输出描述
输出努力的人最左边的人的编号。
我的题解：
// 第二题
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,x,y,tmp;
vector<int> a;
cin >> n >> x >> y;
for(int i=0;i<n;i++){
cin >> tmp;
a.push_back(tmp);
}
// for(int i=0;i<n;i++){
// cout << a[i] << endl;
// }
// cout << "read over! " << endl;
for(int i=0;i<n;i++){
bool flag = true;
int left=i-x>0?i-x:0;
int right=i+y>n-1?n-1:i+y;
int j;
// cout <<"i=" << i << " L :" << left << " -- R : " << right << endl;
for(j=left;j<=right;j++){
if(a[j] < a[i]){
flag=false;
}
}
if(flag == true){
cout << i+1 << endl;
break;
}
}
return 0;
}
/*
测试用例
6 2 2
10 8 2 7 3 1
10 2 3
10 8 7 1 9 2 6 4 3 5
5 2 2
10 8 2 7 1
*/
结果
AC
第三题：k字符子串
题目描述:
给定一个长度为n的字符串s，如果-个字符串的子串包含k个字符x，那么我们就认为这个子串是"k字符子串”。 对于一个字符串s，串中任意个连续的字符组成的子序列称为该串的子串，空串不参与计算。故在本题中字符串”acd" 的子串就有"a”"c","d"，"ac"，"cd"，”acd"六个子串。 特别的，如果原串里面的...[r]，为个子串时，只要|和r不同， 就认为是不同子串。例如字符串aa的子串就有”a"”a"”aa"，因为第一一个a和第二 个a的位置不同，所以被看作为两个不同的子串。 现在你需要计算一共有多少个"k字符子串”。
输入描述
第一行两个整数n和k分别表示字符串长度和需要包含的字符个数，紧接着一个字符x表示需要计算的字符。
输出描述
"k字符子串”的数量。
我的题解：
// 第三题
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
char a,tmp;
int count=0;
vector<char> arr;
cin >> n >> k >> a;
for(int i=0;i<n;i++){
cin >> tmp;
arr.push_back(tmp);
}
// for(int i=0;i<n;i++){
// cout << arr[i] << endl;
// }
// counting(arr,a,k,&count);
for(int i=0;i<=n-1;i++){
for(int j=i+k;j<=n;j++){
int tmp_count=0;
for(int kk=i;kk<j;kk++){
if(arr[kk] == a){
tmp_count ++;
}
}
if(tmp_count == k){
count ++;
}
}
}
cout << count << endl;
return 1;
}
/*
5 1 a
babab
4 1 a
aaaa
*/
结果
过了82%,提示超时。 赛码有bug，刚开始一直是0%，后来啥也没改，又变成82%了，可笑的是我代码一点都没改。
总结
这次有点紧张，第二题的输入处理浪费了一点时间，还有第三个，刚开始以为和leetcode的K字符子串一样，花了一点时间去找，结果发现不一样，确没有及时做，还在尝试找思路，最后才开始暴利穷举，确实耗费了不少时间，最后这个题确实应该还可以优化。
另外，这个赛码的平台也有问题。😂
#实习##笔试题目#
小米三面59人在聊
投递华为等公司10个岗位