Shopee 春招笔试分享

首先吐槽一下，急急忙忙花了30分钟做完选择题之后才发现选择题占分 60，后面三个编程题才占 40 ...

第一题比较版本号

给两个版本号 a 和 b ，用逗号和一个空格分隔开，判断大小。假设两个版本的版本段是一致的.

a<b 输出 -1
a=b 输出 0
a>b 输出 1

样例输入
1.10.2, 1.2.10
样例输出
1

思路

split(str): 将两个版本号 string 分割，得到两个 vector
trim(str): 对于 vector里的每个元素, 去掉前面多余的 0, 例如 {10,0001,11}，做 trim 后得到 {10,1,11}
compare_str(a, b)：从头到尾对两个 vector 做比较

trim 操作我不知道是不是必须的，我这里一次性考虑了。

代码

100% 测试样例

#include<iostream>
#include<string>
#include<vector>
using namespace std;

void trim_str(string& a){
    int i=0;
    while(i<a.size() && (a[i]=='0'||a[i]==' ')) i+=1;
    a = a.substr(i);
}

int compare_str(string a, string b){
    trim_str(a);
    trim_str(b);
    if (a.size() > b.size()) return 1; // a>b;
    else if (a.size() < b.size()) return -1; // a<b;
    else{
        if (a<b) return -1;
        else if (a==b) return 0;
        else return 1;
    }
}

vector<string> split(string a, char seg){
    vector<string> result;
    string tmp_str = "";
    for(auto c: a){
        if( c==seg ){
            result.push_back(tmp_str);
            tmp_str = "";
        }else{
            tmp_str.push_back(c);
        }
    }
    result.push_back(tmp_str);
    return result;
}

int main(){
    string v1;
    string v2;
    while(cin >> v1 >> v2){
        v1 = v1.substr(0, v1.size()-1);
        vector<string> v1_segs = split(v1, '.');
        vector<string> v2_segs = split(v2, '.');

        int cmp = 0;
        for(int i=0; i<v1_segs.size(); i++){
            cmp = compare_str(v1_segs[i], v2_segs[i]);
            if (cmp!=0)
                break;
        }
        cout << cmp << endl;
    }
}

第二题数组去重

输入一个有序 int 数组，去重规则：数字 x 的出现次数不超过 x，问去重后数组的最大长度

样例输入
1 1 1 2 2 2 3 3 3
样例输出
6

思路

这道题我觉得主要是怎么方便的把一行输入读进来，其他的逻辑非常简单。

代码

100% 测试样例

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main(){
    int a;
    vector<int> input;
    while(cin>>a){
        char ch = getchar();
        input.push_back(a);
        if (ch == '\n'){
            // 开始处理 input 数组
            int curr_num=-1;
            int curr_rest=-1;
            int l=0;
            for(auto c: input){
                if(curr_num != c){
                    curr_num = c;
                    curr_rest= c-1;
                    l ++;
                }else{
                    if (curr_rest>0){
                        curr_rest --;
                        l++;
                    }
                }
            }
            cout << l << endl;
            // input 数组处理结束，重新开始。
            input.clear();
        }
    }
}

第三题有多少条路

经典动态规划题，给定 m 和 n 表示矩阵的长宽，小明从左上角走到右下角一共有多少条路，只等向右走或者向下走。注意数字溢出问题。 m n 的值都不超过 50.

样例输入
3 2
样例输出
3

思路

图片说明

数据一定会溢出 int 的，第一考虑的是用动态规划的状态转移矩阵用 unsigned long，但是这样会爆内存。所以用了两个 unsigned 矩阵，一个矩阵用来存 sum/UINT_MAX, 另一个用来存 sum%UINT_MAX。

代码

100% 测试用例

#include <iostream>
#include <vector>
#include <climits>
#define MAX_N 51
using namespace std;

void init(vector<vector<unsigned>>& matrix1, vector<vector<unsigned>>& matrix2){
    for(int i=0;i<MAX_N;i++){
        unsigned z1 = 0;
        unsigned z2 = 1;
        vector<unsigned> line1(MAX_N, z1);
        vector<unsigned> line2(MAX_N, z2);
        matrix1.push_back(line1);
        matrix2.push_back(line2);
    }

    for(int i=1; i<MAX_N;i++){
        for(int j=1;j<=MAX_N;j++){
            unsigned long sum1 = (unsigned long)matrix1[i-1][j]+(unsigned long)matrix1[i][j-1];
            unsigned long sum2 = (unsigned long)matrix2[i-1][j]+(unsigned long)matrix2[i][j-1];
            unsigned long sum = sum1 * UINT_MAX + sum2;
            matrix1[i][j] = (unsigned)(sum/UINT_MAX);
            matrix2[i][j] = (unsigned)(sum%UINT_MAX);
        }
    }
}

int main(){
    int m, n;
    vector<vector<unsigned>> matrix1;
    vector<vector<unsigned>> matrix2;

    init(matrix1, matrix2);
    while (cin>>m>>n) {
        cout << (unsigned long)((unsigned long)matrix1[m-1][n-1]*UINT_MAX + (unsigned long)matrix2[m-1][n-1])<< endl;
    }
}

#Shopee##笔试题目##笔经#