前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode双周赛第70场,考察你的基本功

LeetCode双周赛第70场,考察你的基本功

作者头像
TechFlow-承志
发布2022-09-22 14:49:07
2630
发布2022-09-22 14:49:07
举报
文章被收录于专栏:TechFlow

作者 | 梁唐

出品 | 公众号:Coder梁(ID:Coder_LT)

大家好,我是梁唐。

昨天有一场LeetCode双周赛,不知道有没有小伙伴参加,老梁连夜肝出了题解。

这场比赛是由六方云赞助,并提供了小霸王游戏机等精美礼品……只要打进前五就可以玩了呢……

话不多说,让我们一起看看题目吧。

打折购买糖果的最小开销

一家商店当中有n个糖果,商店规定每买两枚糖果就可以免费赠送一颗,赠送的糖果大小不能超过购买的这两颗的任意一颗。

现在我们要买下商店中所有的糖果,请问最少需要多少花费?

解法

数据范围很小,我们可以随意操作。

不难发现这是一道典型的贪心问题。

首先考虑对糖果进行排序,显然对于最大的两颗糖果是必须要花钱买的。而买下了最大的两颗糖果之后,我们一定是免费获得第三大小的糖果最优。如此我们可以循环往复操作,直到买完所有的糖果。

代码如下:

代码语言:javascript
复制
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]

现在给定原数组的上下界lowerupper,要求原数组的所有元素必须在区间[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最大值即为答案。

代码语言:javascript
复制
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,我们只会考虑价格范围在lowerupper之间的商品,且最多只会拿取k个。当有超过k个商品符合要求时,会根据以下关键字进行排序:

距离:定义为从 start 到一件物品的最短路径需要的步数(较近 距离的排名更高)。价格:较低 价格的物品有更高优先级,但只考虑在给定范围之内的价格。行坐标:较小 行坐标的有更高优先级。列坐标:较小 列坐标的有更高优先级。

最后要求返回排名最高的k件商品,如果小于k个,则全部返回。

解法

由于需要走迷宫,且需要求每一个位置的最短距离,所以考虑使用宽度优先搜索。

使用宽度优先搜索求出每一个商品的最短距离,然后维护符合价格区间要求的商品再进行排序即可。

需要注意在搜索时需要做好去重,一方面为了防止答案重复记录,另外一方面防止死循环导致超时。

AC代码:

代码语言:javascript
复制
// 创建结构体存储答案
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代码:

代码语言:javascript
复制
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;
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-01-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Coder梁 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 打折购买糖果的最小开销
    • 解法
    • 统计隐藏数组数目
      • 解法
      • 价格范围内最高排名的 K 样物品
        • 解法
        • 分隔长廊的方案数
          • 解法
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档