万游笔试题
0
2023-03-22
开发工程师笔试题
开始时间：2023-03-22 19:40 结束时间：2023-03-22 20:45
题1
100 个小朋友围成一个圈，设定编号为 1~100，依次按 1、2、3、4、5、6、7、8、9 循环报数，报到 9 的出圈，直到所有小朋友出圈。请写代码打印出各个小朋友出圈顺序，语言不限。
代码——C++
#include "iostream"
#include "vector"
using namespace std;
int main()
{
vector<int> v; // 存放1到100
// 初始化vector
for (int i = 1; i <= 100; i++)
{
v.push_back(i);
}
// 计算部分
int i = 0;
int j = 0;
while(v.size() > 0)
{
if(i == 9){
i = 0;
}
if(j == v.size()){
j = 0;
}
if(i == 8){
cout << v[j] << " ";
v.erase(v.begin() + j);
i++;
continue; // 当删除改元素后v[j]指向的不再是删除的元素，而是删除元素的下一个元素
}
// 递推
i++;
j++;
}
}
题2
商场新进了两种商品 A 和 B，现在有 A 和 B 商品的购买记录，例如 A=[1,2,2,3,4,5], B=[2,4,1,2,3]。1,2,3,4,5 为用户编号。现在需要求出购买过 A、B 两种商品的用户，语言不限。 （结果中的每个用户编号必须是唯一的）
输入输出
Input:
1,2,2,3,4,5
2,4,1,2,3
output:
1,2,3,4
代码——C++
#include "iostream"
#include "vector"
#include <sstream>
#include "algorithm"
using namespace std;
vector<int> split(string str, char delimiter) {
vector<int> internal;
stringstream ss(str); // 将字符串str转换为字符串流ss
string tok; // 用于存放分割后的字符串
// 开始循环，当getline函数返回false时，表示已经读取完毕
while(getline(ss, tok, delimiter)) {
internal.push_back(stoi(tok));
}
return internal;
}
int main(){
string commodityA, commodityB;
cin >> commodityA >> commodityB;
vector<int> A = split(commodityA, ',');
vector<int> B = split(commodityB, ',');
vector<int> result;
// vector，从小到大排序并去重
sort(A.begin(), A.end());
sort(B.begin(), B.end());
A.erase(unique(A.begin(), A.end()), A.end());
B.erase(unique(B.begin(), B.end()), B.end());
// 找出两个vector中相同的元素
// TODO: 优化思路：1. 两个vector都是有序的，可以比较大小后使用双指针的方法，时间复杂度为O(n)；2. 使用set_intersection函数
for (int i = 0; i < A.size(); i++) {
for (int j = 0; j < B.size(); j++) {
if (A[i] == B[j]) {
result.push_back(A[i]);
i++; // 由于元素已经去重，即可跳过相同的元素
}
}
}
// 输出结果
for (int i = 0; i < result.size()-1; i++) {
cout << result[i] << ",";
}
if(result.size() > 0){
cout << result[result.size()-1] << endl;
}
return 0;
}
代码——C++（利用set_intersection优化后）
当时写第一遍的时候忘记set_intersection具体是咋用的了，就直接用了暴力法，双重循环解决问题
#include "iostream"
#include "vector"
#include <sstream>
#include "algorithm"
using namespace std;
vector<int> split(string str, char delimiter) {
vector<int> internal;
stringstream ss(str); // 将字符串str转换为字符串流ss
string tok; // 用于存放分割后的字符串
// 开始循环，当getline函数返回false时，表示已经读取完毕
while(getline(ss, tok, delimiter)) {
internal.push_back(stoi(tok));
}
return internal;
}
int main(){
string commodityA, commodityB;
cin >> commodityA >> commodityB;
vector<int> A = split(commodityA, ',');
vector<int> B = split(commodityB, ',');
vector<int> result;
// vector，从小到大排序并去重
sort(A.begin(), A.end());
sort(B.begin(), B.end());
A.erase(unique(A.begin(), A.end()), A.end());
B.erase(unique(B.begin(), B.end()), B.end());
// 找出两个vector中相同的元素
set_intersection(A.begin(), A.end(), B.begin(), B.end(), back_inserter(result));
// 输出结果
for (int i = 0; i < result.size()-1; i++) {
cout << result[i] << ",";
}
if(result.size() > 0){
cout << result[result.size()-1] << endl;
}
return 0;
}
std::set_intersection( ) 函数用法
求交集的函数
set_intersection( )、求集合差的函数set_difference( )和合并两个集合的函数set_union( )
OutputIt set_intersection( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );
使用要求：
- 传递的容器必须是排序的
set_intersection( )中最后存放交集的容器的容量必须要足够大到能放下所有的元素（即函数只执行复制，不是插入）set_intersection( )不是 set 的方法，而是一个通用函数