提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

LeetCode294，手速场周赛，12分钟切3题卡到比赛结束……

12 分钟 结束 比赛 周赛
2023-06-13 09:13:01 时间

作者 | 梁唐

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

大家好，日拱一卒，我是梁唐。

今天我们照惯例来看下LeetCode周赛，这一场的比赛由普渡机器人赞助，前300名的同学可以获得内推机会。

在分析具体问题之前，先说说我个人对这场比赛的感受。最大的感受就是体验不是很好，前三题过于简单，最后一题过于繁琐。以至于即使我只用了12分钟解决了前面三题，在想到了解法的情况下，仍然没有解出最后一题……

一直到比赛结束，通过第四题的也只有不到150人，可见其难度。

槽先慢点吐，等我们聊到第四题的时候再详细说说。好了，废话不多说，我们来看题吧。

字母在字符串中的百分比

给你一个字符串 s 和一个字符 letter ，返回在 s 中等于 letter 字符所占的 百分比 ，向下取整到最接近的百分比。

题解

考察的是对类型转换的理解，在C++当中，两个整数相除也只会得到整数结果，这会导致丢失小数的部分。

而我们需要求百分比，要求的就是小数。所以必须使用强制转换，先把被除数转成浮点数，再做除法。做完除法之后，最后再转回整形。

class Solution {
public:
    int percentageLetter(string s, char letter) {
        int n = s.length();
        int cnt = 0;
        for (int i = 0; i < n; i++) cnt += s[i] == letter;
        return (int) (((double)cnt / n) * 100);
    }
};

使用Python也有类似的问题，不过Python的规则与C++不同，Python的除法得到的是浮点数。

class Solution:
    def percentageLetter(self, s: str, letter: str) -> int:
        cnt = 0
        for c in s:
            if c == letter:
                cnt += 1
        return (int) (cnt / len(s) * 100)

装满石头的背包的最大数量

现有编号从 0 到 n - 1 的 n 个背包。给你两个下标从 0 开始的整数数组 capacity 和 rocks 。第 i 个背包最大可以装 capacity[i] 块石头，当前已经装了 rocks[i] 块石头。另给你一个整数 additionalRocks ，表示你可以放置的额外石头数量，石头可以往 任意 背包中放置。

请你将额外的石头放入一些背包中，并返回放置后装满石头的背包的 最大 数量。

题解

非常明显的贪心题，很容易想到可以算出每个背包距离装满的差值。然后从小到大进行排序，优先装填消耗比较少的，统计一下能够装满的数量即是答案。

class Solution {
public:
    int maximumBags(vector<int>& cap, vector<int>& rks, int addr) {
        int n = cap.size();
        vector<int> diff;
        for (int i = 0; i < n; i++) {
            diff.push_back(cap[i] - rks[i]);
        }
        
        sort(diff.begin(), diff.end());
        int ret = 0;
        for (int i = 0; i < n; i++) {
            if (diff[i] <= addr) {
                addr -= diff[i];
                ret ++;
                continue;
            }
            if (addr == 0) break;
        }
        
        return ret;
    }
};

表示一个折线图的最少线段

给你一个二维整数数组 stockPrices ，其中 stockPrices[i] = [dayi, pricei] 表示股票在 dayi 的价格为 pricei 。折线图 是一个二维平面上的若干个点组成的图，横坐标表示日期，纵坐标表示价格，折线图由相邻的点连接而成。比方说下图是一个例子：

请你返回要表示一个折线图所需要的 最少线段数 。

img

题解

想要用尽量少的线段表示折线图，也就是说要尽量把连在一条线上的点用同一个线段串起来。会发现其实也是一个贪心问题，对于每个线段我们需要把所有能串起来的点串起来。

由于题目当中说了所有的dayi都各不相同，即所有点的横坐标各不相同。那么我们可以想到根据横坐标进行排序，排序之后， 我们只需要求出相邻两点的斜率，和之前的斜率进行比较，如果斜率相同，则说明可以串在之前的线段上，否则说明需要另外使用一条线段。

由于斜率是一个浮点数，虽然本题当中不会出现斜率无穷的情况，但为了严谨，我们还是使用横纵坐标差值来代替斜率。

但这又有另外一个问题，我们把横纵坐标的差值表示成二元组，上图当中(1, 1)和(4, 4)的差值对应的斜率是一样的。所以我们还需要把这个差值除去它们的最大公约数。好在C++有内置的gcd函数可以使用，不用我们自己手写辗转相除法。

bool cmp(const vector<int> &a, const vector<int> &b) {
    return a[0] < b[0];
}

class Solution {
public:
    int minimumLines(vector<vector<int>>& stk) {
        int n = stk.size();
        if (n == 1) return 0;
        sort(stk.begin(), stk.end(), cmp);
        auto last = make_pair(0, 0);
        int ret = 0;
        for (int i = 1; i < n; i++) {
            int difx = stk[i][0] - stk[i-1][0], dify = stk[i][1] - stk[i-1][1];
            int _g = gcd(difx, dify);
            auto tmp = make_pair(difx / _g, dify / _g);
            if (tmp != last) {
                last = tmp;
                ret ++;
            }
        }
        return ret;
    }
};

巫师的总力量和

作为国王的统治者，你有一支巫师军队听你指挥。

给你一个下标从 0 开始的整数数组 strength ，其中 strength[i] 表示第 i 位巫师的力量值。对于连续的一组巫师（也就是这些巫师的力量值是 strength 的 子数组），总力量 定义为以下两个值的 乘积 ：

  • 巫师中 最弱 的能力值。
  • 组中所有巫师的个人力量值 之和 。

请你返回 所有 巫师组的 总 力量之和。由于答案可能很大，请将答案对 109 + 7 取余 后返回。

子数组 是一个数组里 非空 连续子序列。

题解

这题看起来非常吓人，首先数据范围不小，有1e5，其次计算逻辑非常复杂。又是求区间最小数又是求区间和，哪个看起来都不是省油的灯。

在这个数据量级之下，我们是不可能枚举所有的区间的，这一定会超时。既然不能枚举区间，那么我们只能反其道而行之，从每个数入手。怎么做？考虑每个数对于答案的贡献。很明显，无论一个数有多大，它至少在它自己单独构成的区间里是最小的，也就是说每一个数都必然对答案有贡献。

接下来，我们要做的就是想办法算出每个数对答案的贡献，再把这些贡献全部累加。相当于我们换了一种方法拆解答案的组成，初次接触会觉得有些反直觉，但这是算法题当中的常见套路，之前的LeetCode周赛当中也有过类似的问题。

下一个问题就是我们怎么求每个数对答案的贡献呢？

这个问题需要我们结合题意，题意说了，要求每个区间的和与区间最小值的乘积。也就是说一个数要想对答案有贡献，它必须是某个区间的最小数。那么就好办了，对于下标x的数来说，我们只要找到以它为最小数所有的区间和对应的区间和。

由于区间中，必须以strength[x]（之后简写成s[x]）为最小值，即区间里不能有比s[x]更小的数。围绕s[x]我们可以找到一个区间[l, r]，保证l <= x, r >= x且区间内的所有值都大于s[x]，不包含相等的情况，我们可以假设如果两个数相等且为同一个区间的最小值，贡献属于前者。我们前面说了，最坏也能找到[x, x]的区间，也就是说这个区间一定存在。

有了这个区间之后，我们可以做什么事情呢？很明显，我们可以发现对于[l, r]当中的任意两个点比如ll, rr，只要满足ll <= x, rr >= x，那么区间[ll, rr]中最小的数一定是s[x]。那么，我们只需要枚举出所有的ll, rr的组合，就得到了所有以s[x]为最小值的区间。

到这里，我们有两个问题要解决，一个问题是如何找到x对应的l, r，第二个问题是如何快速求出所有[ll, rr]的区间和？

我们一个一个来解决， 先看第一个问题。这个问题在LeetCode问题当中反复出现，解法就是使用数据结构——单调栈。我们维护一个栈，保证栈中元素递增。读入s[x]之后，我们弹出栈中所有大于等于它的数。弹出完成之后，栈顶的元素一定小于s[x]。当未来读入了新的元素它出栈的时候，使它出栈的元素也一定小于等于它。那么这两个位置之间的所有元素一定都大于s[x]。

通过使用单调栈，我们可以快速求出所有x对应的l, r。

再来看第二个问题，求所有[ll, rr]的区间和。显然我们不可能枚举所有的ll, rr的组合，这样做一定会超时。我们必须要想出更好的办法来，这个办法干想是不行的，需要我们动手算一算。

对于区间[ll, rr]来说，我们可以使用前缀和数组快速求出这个区间的区间和，我们假设前缀和数组叫做ps(prefix_sum的缩写)。那么区间和可以写成ps[rr+1] - ps[ll]，ps[i] = s[0] + s[1] + ... + s[i-1]。

然后，我们把所有的式子都写出来：

ps[x+1] - ps[x]
ps[x+2] - ps[x]
...
ps[r+1] - ps[x]

ps[x+1] - ps[x-1]
ps[x+2] - ps[x-1]
...
ps[r+1] - ps[x-1]
...
...
ps[r+1] - ps[l-1]

一共有多少项？在x及左侧选择左端点一共有x-l+1种情况，在x及右侧选择右端点一共有r-x+1种情况，排列组合，就是(x-l+1) * (r-x+1)种。

然后我们合并相同的项，会发现x及左侧的项出现了r-x+1次，x及右侧的项出现了x-l+1次。我们令L=x-l+1, R=r-x+1，于是[l, r]中的所有区间和为：L*(ps[x+1]+ps[x+2]+...+ps[r+1]) - R*(ps[l-1] + ps[l+1] +...+ps[x])

这么转化一波之后，这个式子是不是也是一个累加式？我们是不是又可以用一个前缀和来解决了？

我们创建pps数组，令pps[i] = ps[0] + ps[1] + ... + ps[i]（注意下标），这样上式又可以转化成：L*(pps[r+1] - pps[x]) - R*(pps[x]-pps[l-1])，对于确定的l, r, x来说，这个式子的计算复杂度是O(1)，而ps, pps数组都可以提前预处理，这样一来，这个问题就算是解决了。

对于原问题，我们兜了超级大一个圈子，做了各种分析假设和变形才终于搞定。但这里只是第一步，想要把代码完整地写出来调试通又是一个巨大的挑战。我就因为下标的问题导致比赛的时候没能顺利调试成功。

想要挑战自己的同学不妨试试看，看看在不看题解的情况下，多久能把整个逻辑完全实现。

最后，附上代码：

class Solution {
public:
    long long Mod = 1e9 + 7;
    long long get_value(vector<long long>& pps, int l, int m, int r, int v) {
        long long left = m-l+1, right = r-m+1, leftsum = 0, rightsum = 0;  
        leftsum = l == 0 ? pps[m] : pps[m] - pps[l-1];
        rightsum = pps[r+1] - pps[m];
        long long ret = 0;
        
        long long cursum = (left * rightsum % Mod) - (right * leftsum % Mod);
        cursum = (cursum % Mod + Mod) % Mod;
        ret = cursum * v % Mod;
        return ret;
    }
    
    int totalStrength(vector<int>& str) { 
        int n = str.size();
        
        vector<long long> ps(n+1, 0);
        vector<long long> pps(n+1, 0);
        // 预处理ps和pps
        for (int i = 0; i < n; i++) {
            ps[i+1] = (ps[i] + str[i]) % Mod;
            pps[i+1] = (pps[i] + ps[i+1]) % Mod;
        }
        
        vector<int> sk;
        
        long long ret = 0;
        
        // 单调栈
        for (int i = 0; i < n; i++) {
            while (!sk.empty() && str[i] < str[sk.back()]) {
                int m = sk.back();
                int r = i-1;
                int l = 0;
                if (sk.size() > 1) l = sk[sk.size() - 2] + 1;
                // 计算出栈元素的贡献
                ret += get_value(pps, l, m, r, str[m]);
                ret = ret % Mod;
                sk.pop_back();
            }
            sk.push_back(i);
        }
        
        // 将栈中剩余的元素出栈，此时每个元素的右侧边界都是n-1
        while (sk.size() > 0) {
            int m = sk.back();
            int r = n-1;
            int l = 0;
            if (sk.size() > 1) l = sk[sk.size() - 2] + 1;
            ret += get_value(pps, l, m, r, str[m]);
            ret = ret % Mod;
            sk.pop_back();
        }
        return ret;
    }
};

这次的比赛就先聊到这里，感谢大家的阅读。

喜欢本文的话不要忘记三连~

相关文章