LeetCode双周赛第70场，考察你的基本功
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
昨天有一场LeetCode双周赛，不知道有没有小伙伴参加，老梁连夜肝出了题解。
这场比赛是由六方云赞助，并提供了小霸王游戏机等精美礼品……只要打进前五就可以玩了呢……
话不多说，让我们一起看看题目吧。
打折购买糖果的最小开销
一家商店当中有n个糖果，商店规定每买两枚糖果就可以免费赠送一颗，赠送的糖果大小不能超过购买的这两颗的任意一颗。
现在我们要买下商店中所有的糖果，请问最少需要多少花费？
解法
数据范围很小，我们可以随意操作。
不难发现这是一道典型的贪心问题。
首先考虑对糖果进行排序，显然对于最大的两颗糖果是必须要花钱买的。而买下了最大的两颗糖果之后，我们一定是免费获得第三大小的糖果最优。如此我们可以循环往复操作，直到买完所有的糖果。
代码如下：
int main(){
int cur = 0, ans = INT_MIN, cursum = 0;
char c='0';
do{
while(c == ' '){
c = getchar();
}
cin >> cur;
cursum += cur;
ans = max(ans, cursum);
if(cursum < 0){
cursum = 0;
}
c = getchar();
}while(c != '\n');
cout << ans << endl;
return 0;
}
统计隐藏数组数目
给定一个长度为n的数组diff，它表示原数组的差值，其中diff[i] = hidden[i+1] - hidden[i]。
现在给定原数组的上下界lower和upper，要求原数组的所有元素必须在区间[lower, upper]之间。请问，这样的原数组一共有多少种构成的方式，如果不存在可能，返回0.
解法
由于我们已经知道了原数组中每两个相邻元素的差值，也就是说只要我们确定了其中任意一个数字，就可以确定其他的。
进而我们可以想到，原数组的最大和最小值的差值也是确定的。我们要做的就是保证原数组的最大值不超过upper，最小值不低于lower。我们假设原数组的最大最小值的差值是gap，那么答案就是upper - lower - gap + 1。
最简单的做法就是给原数组的第0位一个假定的值，然后求最大最小值计算gap。当然我们也可以不这么做，直接求解。为了方便理解， 我们可以简单做个图，以样例[3,-4,5,1,-2]为例。作图之后得到：
我们来思考最大值和最小值之间的关系，如果最小值出现在最大值左侧，gap体现在图中就是一系列递增得到的顺差：
反之，如果最小值出现在最大值的右侧，那么gap就是通过一系列下降得到的逆差：
我们只需要同时维护一下最大的顺差和逆差，其中绝对值最大（顺差大于0，逆差小于0）的那个就是答案。
求最大顺差和最大逆差用到了求数组区间最大和的思路：维护一个tmp值，保存中间结果。每次读入新值时和tmp相加，接着判断tmp大小。当tmp小于0时，说明之前的序列已经不构成增益，舍弃，将tmp置为0。如此，中途出现的tmp最大值即为答案。
class Solution {
public:
int numberOfArrays(vector<int>& diff, int lower, int upper) {
int n = diff.size();
// maxi 记录顺差, mini 记录逆差
long long tmp = 0, maxi = INT_MIN, tmpi = 0, mini = INT_MAX;
for (int i = 0; i < n; i++) {
// tmp记录当前累加的顺差
tmp += diff[i];
// tmpi记录当前累加的逆差
tmpi += diff[i];
// 顺差大于0，所以要记录最大值
maxi = max(maxi, tmp);
// 逆差小于0，记录最小值
mini = min(mini, tmpi);
// 如果tmp小于0，那么清零
tmp = max(0LL, tmp);
// 如果tmpi大于0，则清零
tmpi = min(0LL, tmpi);
}
long long gap = max(maxi, abs(mini));
return max(0LL, (long long)upper - (long long)lower - gap + 1);
}
};
价格范围内最高排名的 K 样物品
给定一个 n x m的迷宫grid，迷宫内有墙和物品，grid[i][j] = 0，表示i, j位置为墙，大于0为商品，表示商品的价格。
我们无法移动到墙的位置，每次移动到商品可以拿取商品。
接着给定起点以及价格范围和一个整数k，我们只会考虑价格范围在lower和upper之间的商品，且最多只会拿取k个。当有超过k个商品符合要求时，会根据以下关键字进行排序：
距离：定义为从 start 到一件物品的最短路径需要的步数（较近 距离的排名更高）。价格：较低 价格的物品有更高优先级，但只考虑在给定范围之内的价格。行坐标：较小 行坐标的有更高优先级。列坐标：较小 列坐标的有更高优先级。
最后要求返回排名最高的k件商品，如果小于k个，则全部返回。
解法
由于需要走迷宫，且需要求每一个位置的最短距离，所以考虑使用宽度优先搜索。
使用宽度优先搜索求出每一个商品的最短距离，然后维护符合价格区间要求的商品再进行排序即可。
需要注意在搜索时需要做好去重，一方面为了防止答案重复记录，另外一方面防止死循环导致超时。
AC代码：
// 创建结构体存储答案
struct P {
int dis, price, x, y;
P() {}
P(int d, int p, int _x, int _y): dis(d), price(p), x(_x), y(_y) {}
};
class Solution {
public:
vector<vector<int>> highestRankedKItems(vector<vector<int>>& grid, vector<int>& pricing, vector<int>& start, int k) {
typedef pair<int, int> pii;
vector<P> ans;
queue<P> que;
map<pii, int> mp;
int lower = pricing[0], upper = pricing[1];
que.push(P(0, grid[start[0]][start[1]], start[0], start[1]));
// 方向数组用来遍历上下左右四个方向
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
int n = grid.size(), m = grid[0].size();
set<pii> st;
while (!que.empty()) {
auto u = que.front();
que.pop();
pii poi = make_pair(u.x, u.y);
// 如果价格满足要求，且之前没有拿到过，放入候选答案数组ans
if (u.price >= lower && u.price <= upper && st.count(poi) == 0) {
ans.push_back(u);
st.insert(poi);
}
// 对四个方向进行遍历
for (int i = 0; i < 4; i++) {
int x = u.x + dir[i][0], y = u.y + dir[i][1];
// 超界判定
if (x < 0 || x >= n || y < 0 || y >= m) continue;
// 墙判定
if (grid[x][y] == 0) continue;
pii poi = make_pair(x, y);
// 是否遍历过判定
if (mp.count(poi) && mp[poi] <= u.dis+1) continue;
mp[poi] = u.dis+1;
que.push(P(u.dis+1, grid[x][y], x, y));
}
}
// 对ans数组进行多关键字排序，用到了匿名函数
sort(ans.begin(), ans.end(), [](auto &x, auto & y)->bool {
if (x.dis != y.dis) return x.dis < y.dis;
if (x.price != y.price) return x.price < y.price;
if (x.x != y.x) return x.x < y.x;
return x.y < y.y;
});
vector<vector<int>> ret;
for (int i = 0; i < min(k, (int)ans.size()); i++) {
vector<int> cur = {ans[i].x, ans[i].y};
ret.push_back(cur);
}
return ret;
}
};
分隔长廊的方案数
在图书馆里有一个长廊，当中要摆放若干椅子和若干植物。用一个字符串进行表示，其中S表示座位，P表示植物。
要求将这些椅子和植物分组，保证每组当中必须有两张椅子，植物数量可以随意，要求满足条件的方案数。
解法
显然这是一道数学题，由于要求每一个分组内恰好有两张椅子，我们假设在第三张椅子出现之前存在的植物数量为x。x个植物一共有x+1个间隙，那么对于当前分组来说一共存在x+1种划分方法。
我们只需要分别求出每一个分组的划分方法，然后乘在一起即可。
注意由于要对1e9+7取模，取模之后再做乘法可能会超过int范围， 所以得使用long long。
还有一个trick是最后一个分组可能不一定满足两张椅子的要求，要对此进行特判。
AC代码：
class Solution {
public:
int numberOfWays(string corr) {
int n = corr.size();
// cont表示出现的椅子数量，conp表示连续出现的植物数量，仅仅需要考虑出现两张椅子之后的情况
int cont = 0, conp = 0;
long long ret = 1;
long long mod = 1e9+7;
for (int i = 0; i < n; i++) {
// 如果当前是植物，当椅子数量小于2时不做处理，等于2时+1
if (corr[i] == 'P') {
if (cont < 2) continue;
else conp++;
}else {
// 椅子为0时直接+1
if (cont == 0) {
cont++;
// 椅子为1时满足分组要求，将植物数量清零
}else if (cont == 1) {
cont++;
conp = 0;
}else {
// 当有两张椅子时，表示进行到下一个分组，将椅子数量置为1
cont = 1;
// 维护答案
ret = ret * (conp + 1);
ret = ret % mod;
}
}
}
// 判断最后一个分组是否满足两张椅子的条件
if (cont != 2) return 0;
return ret;
}
};腾讯云开发者
