简单扎实！详解2021Shopee秋招笔试真题

大家好，难得周末闲暇，加更一篇。

最近到了招聘季，有一些小伙伴私信我说招聘笔试系列已经好久没更新了，想要再多看一些例题。所以响应大家的要求，我们周末临时加更一篇。今天我选择的是最近风头很火的我司的招聘笔试题，让我们一起来看下我司的笔试题究竟是一个什么难度。

题目链接：https://www.nowcoder.com/question/next?pid=28761331&qid=1382578&tid=41640544

好了，废话不多说，让我们进入正文吧。

题意

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

给定一个字符串式子，返回它的计算结果。算术规则为: k*[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。e.g. s = "3*[a2*[c]]", 返回 “accaccacc”

输入例子1:

"3*[a2*[c]]"

输出例子1:

"accaccacc"

题解

很明显，这是一道字符串问题，在C++笔试题当中，字符串问题出现的频率很高。之所以频繁出现字符串相关的问题，除了在实际工作当中经常要求程序员对各种字符串做各种处理之外，另外一个原因是字符串的问题编码往往相对比较繁琐，比较考验选手的基本功。如果能够把字符串的问题处理漂亮，代码也写得好看，显然一定是一个很大的加分项。

简单分析

这道题的题意不长，要求我们根据设计的固定模式来对字符串进行处理。处理的内容也很简单，一共有两个规则，第一个规则是乘法规则，也就是一个数字和字符串相乘，将字符串拷贝N次。第二个规则是嵌套规则，第一条规则可以嵌套使用。

对于乘法规则非常简单，我们只需要拿到乘号之前的数字然后对字符串重复拷贝即可。所以唯一的问题就是嵌套，由于我们在编码的时候是不知道字符串嵌套了多少层的，所以我们需要设计一个算法使得对于任意层嵌套的字符串也一样可以处理。

如果大家刷题经验丰富的话，看到嵌套两个字就应该已经反应过来了。嵌套问题有一个天然的解决方案就是递归。

编码前准备

既然已经想到了使用递归来做，剩下的难度就是编码了。

但很多同学对于递归的编码很恐惧，总是担心自己写不对， 或者是有的时候思维会混乱不知道该如何写。其实递归的核心就是自我调用，也就是套娃，我们用一个函数实现一个功能，然后用这个功能自己实现自己。

我这么说起来显得有些绕，但是我们带入题目一分析其实很简单。

首先我们想一个空函数，假设这个函数已经有了题目要求的功能。

string dfs(string st) {
    return "";
}

然后我们往这个函数里填逻辑，怎么填呢，需要结合样例来。我们来看样例：3*[a2*[c]]。

我们读到了3和[a2*[c]]的一个乘法运算，前面的乘法运算问题不大，我们只需要分析一下字符串把当中的数字抽离出来就行。所有的问题都集中在后面，也就是[a2*[c]]的部分。

我们发现a2*[c]也是一个同样的问题，既然是同样的问题，那么显然也可以被我们dfs函数来解决。所以我们的代码可以写成：

string dfs(string st) {
    // 抽取数字
    int cnt = extractInt(st);
    // 抽取子问题
    string subquery = extractSub(st);
    // 递归调用dfs，解决子问题
    string subret = dfs(subquery);
    
    string ret = ""
    for (int i = 0; i < cnt; i++) {
        ret += subret;
    }
    return ret;
}

这样结束了么？我们再看下样例，会发现其实还没有结束，还有一点点小问题。什么问题呢，就是a2*[c]这个子问题当中有点问题。我们发现在2这个数字之前还有一个字母a，也就是说数字前面可能会有一个前缀字符串。这个字符串不参与乘法操作，但是也需要和答案拼接在一起。所以我们需要把这个情况也纳入考虑，我们只需要加入这个逻辑即可：

string dfs(string st) {
    // 抽取前缀
    string prefix = extractPrefix(st);
    // 抽取数字
    int cnt = extractInt(st);
    // 抽取子问题
    string subquery = extractSub(st);
    // 递归调用dfs，解决子问题
    string subret = dfs(subquery);
    
    string ret = ""
    for (int i = 0; i < cnt; i++) {
        ret += subret;
    }
    return prefix + ret;
}

你看，这样一来我们的算法就可以覆盖所有情况了。其实递归的逻辑就算是写完了，剩下的只需要把我们在代码当中用函数暂时填充的功能实现了就行了。

大家以后在编码的时候不妨也可以尝试一下这种方法，把一些确定的子模块先用函数来代替，这样我们可以省去一些边角的思考，可以帮助我们更专注问题本身。

好了，最后附上完整的代码：

class Solution {
public:
    /**
     * 
     * @param str string字符串 
     * @return string字符串
     */
    string computeString(string st) {
        // write code here
        string number = "";
        string prefix = "";
        string next = "";
        for (int i = 0; i < st.size(); i++) {
            if (st[i] == '*') {
                next = st.substr(i+2, st.size() - i - 3);
                break;
            }
            if (st[i] >= '0' && st[i] <= '9') {
                number += st[i];
            }else {
                prefix += st[i];
            }
        }
        if (number.size() == 0) {
            return st;
        }
        string ret = "";
        int cnt = stoi(number, nullptr, 10);
        string body = computeString(next);
        for (int i = 0; i < cnt; i++) {
            ret += body;
        }
        return prefix + ret;
    }
};

尾声

怎么样，我司的笔试题难度是不是还可以，不算很大？

根据我的判断差不多就是LeetCode Medium-的水平，即使是没有参加过算法比赛的同学，通过练习和准备也完全可以解决。不得不说我司的笔试和招聘还是比较友好的，不会出太难太偏的问题，但是又很考验候选人的基本功和能力。

小伙伴们如果感兴趣也可以上牛客网自己亲手做一做这题，如果做下来感觉很好的话，不要忘了给我投递简历，我帮你内推。

今天的文章就到这里，感谢大家的阅读，喜欢的话不要忘了三连。