作者 | 梁唐
出品 | 公众号:Coder梁(ID:Coder_LT)
大家好,我是梁唐。
上次我们一起看了shopee秋招提前批选择题的部分,今天我们来看算法题。
这一套试卷当中一共有两道算法题,实话说这两题质量很高,虽然题目不算难,但很考验思维,需要反复思考才能做得出来。出在笔试题当中非常有区分度。
好了,废话不多说,我们来看题。
成对的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序列是什么。
"66"
"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,0,2]
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;
}
};
到这里,这两题就算是讲解完了。这两道题都不算是难题,但乍一看思路都不太明显,需要仔细分析题目。
除了思考算法和思维能力之外,对于题目中信息的敏感和把握也是能力中很重要的一块。有需要的同学可以注意一下这方面的锻炼,最后,感谢大家的阅读。