万游笔试试题

开发工程师笔试题

开始时间：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 的方法，而是一个通用函数