shopee 2022提前批校招笔试题，算法题篇

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

上次我们一起看了shopee秋招提前批选择题的部分，今天我们来看算法题。

这一套试卷当中一共有两道算法题，实话说这两题质量很高，虽然题目不算难，但很考验思维，需要反复思考才能做得出来。出在笔试题当中非常有区分度。

好了，废话不多说，我们来看题。

匹配的69

成对的69匹配序列定义为：

1、 空串""是一个成对的69序列；

2、如果"X"和"Y"是成对的69序列，那么"XY"也是成对的69序列；

3、如果"X"是一个成对的69序列，那么"6X9"也是一个成对的69序列；

4、每个成对的69序列都可以由以上规则生成。例如，"", "69", "6699", "6969"都是成对的。

现在给出一个序列S，允许你的操作是：在S的开始和结尾处添加一定数量的6或者9，使序列S变为一个成对的69序列。输出添加最少的6或者9之后成对的69序列是什么。

输入例子1:

"66"

输出例子1:

"6699"

解法

题目和我们玩了一个障眼法，其实我们可以把69换成括号，6替换成左括号，9替换成右括号，这其实就成了一个括号匹配的问题，并且匹配的规则和括号都是一样的。

显然，我们不可能在字符串的左侧加上9，右侧加上6，只能在左侧加上6，右侧加上9。所以题目就变成了，我们需要做左右两侧分别加上多少6和9，使得这个字符串能够成为一个合法的匹配？

前文中说了，这题本质上是一个括号匹配的问题，我们自然也可以用括号匹配的思路来解决。不难想到，我们可以先尝试匹配6和9，当发现6不足时在左侧添加6，如果9不足时在右侧添加9即可。

括号匹配可以使用栈来操作，当我们从左往右读入一个6时入栈，读到9时，从栈中取出一个6来构成匹配，如果栈空则匹配失败。如果遍历到末尾，所有的6和9都构成了匹配，中途没有出现6数量不够，结束之后没有多余的情况，那么就认为是匹配成功了。

对应到这道题，我们很容易想到，当我们在匹配6和9时，如果出现6不够的情况，在开头添加6，如果结束之后栈中还有多余的6，则在结尾添加9，即可保证构成一个合法的匹配。

代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param S string字符串 
     * @return string字符串
     */
    string Paired69(string s) {
        // write code here
        vector<char> vt;
        int n = s.length();
        string prefix;
        for (int i = 0; i < n; i++) {
            if (s[i] == '6') vt.push_back('6');
            else {
                if (vt.size()) vt.pop_back();
                else prefix.push_back('6');
            }
        }
        s = prefix + s;
        for (int i = 0; i < vt.size(); i++) s.push_back('9');
        return s;
    }
};

最小金额购买商品

有一排商品，每一个商品都有自己的价值，现在需要花一定金额购买这些商品。规则是：如果一个商品的价值比它旁边的一个商品要高，那么这个商品就必须比它旁边的商品花费更多金额。所有的商品至少要进行一次金额购买。假设一次购买花费金额单位为1，最少需要多少金额可以购买所有商品？

现给定一个数组，数组元素表示每个商品的价值。请编写代码输出最少需要花费的金额。

输入例子1:

[1,0,2]

输出例子1:

5

解法

很容易想到，一个商品的价格是由它的邻居决定的。如果它比它两个邻居的价格都低，那么它的价格就是1，如果它比邻居的价格都高，那么它的价格就是邻居中价格高的那个再加一。如果只比一个邻居价格高，那么它的价格就是这个邻居的价格再加一。

但这里面有一个问题，就是邻居的价格也是不确定的。我们要求邻居的价格又要求邻居的邻居，这就嵌套了，所以得想办法解除这个嵌套。

我们仔细分析一下，一件商品的价格是通过它左右两个邻居的价格确定的。我们可以理解为左侧的邻居确定一个左侧价格，右侧邻居确定一个右侧的价格，它的实际价格是这两个价格当中高的那个。

我们每次求一侧的价格是容易的，比如我们从左往右遍历时，我们已经知道了它左侧邻居的价格，就可以直接求出左侧价格了。同理，我们倒序遍历，就可以求出右侧价格。最后只需要在这两个价格当中选取高值，就是它的实际价格了。

代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型
     */
    int cost(vector<int>& array) {
        // write code here
        int n = array.size();
        vector<int> left(n, 1);
        vector<int> right(n, 1);
        for (int i = 1; i < n; i++) {
            if (array[i] > array[i-1]) left[i] = left[i-1] + 1;
        }
        for (int i = n-2; i > -1; i--) {
            if (array[i] > array[i+1]) right[i] = right[i+1] + 1;
        }
        int ret = 0;
        for (int i = 0; i < n; i++) ret += max(left[i], right[i]);
        return ret;
    }
};

到这里，这两题就算是讲解完了。这两道题都不算是难题，但乍一看思路都不太明显，需要仔细分析题目。

除了思考算法和思维能力之外，对于题目中信息的敏感和把握也是能力中很重要的一块。有需要的同学可以注意一下这方面的锻炼，最后，感谢大家的阅读。