leetcode biweekly contest 294

感觉第四题确实是个不错的题目，前三题都太普通的题目。少见的高质量的题目。

2278. 字母在字符串中的百分比

题目

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

示例 1：

输入：s = "foobar", letter = "o"
输出：33
解释：
等于字母 'o' 的字符在 s 中占到的百分比是 2 / 6 * 100% = 33% ，向下取整，所以返回 33 。

示例 2：

输入：s = "jjjj", letter = "k"
输出：0
解释：
等于字母 'k' 的字符在 s 中占到的百分比是 0% ，所以返回 0 。

提示：

• 1 <= s.length <= 100
• s 由小写英文字母组成
• letter 是一个小写英文字母

ln -s /usr/local/python3/bin/python3 /usr/bin/python3
pip3 install mkdocs-material

地址

https://leetcode.cn/problems/percentage-of-letter-in-string

题意

直接遍历

思路

1. 直接统计字符的个数即可，返回值为 $\lfloor \dfrac{100 * c}{n} \rfloor$。
2. 复杂度分析：

• 时间复杂度：$O(n)$, 其中 $n$ 为字符串的长度。
• 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int percentageLetter(string s, char letter) {
        int cnt = 0;
        int n = s.size();
        for (auto c :s) {
            if (c == letter) {
                cnt++;
            }
        }
        return cnt * 100 / n;
    }
};

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

题目

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

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

示例 1：

输入：capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
输出：3
解释：
1 块石头放入背包 0 ，1 块石头放入背包 1 。
每个背包中的石头总数是 [2,3,4,4] 。
背包 0 、背包 1 和 背包 2 都装满石头。
总计 3 个背包装满石头，所以返回 3 。
可以证明不存在超过 3 个背包装满石头的情况。
注意，可能存在其他放置石头的方案同样能够得到 3 这个结果。

示例 2：

输入：capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100
输出：3
解释：
8 块石头放入背包 0 ，2 块石头放入背包 2 。
每个背包中的石头总数是 [10,2,2] 。
背包 0 、背包 1 和背包 2 都装满石头。
总计 3 个背包装满石头，所以返回 3 。
可以证明不存在超过 3 个背包装满石头的情况。
注意，不必用完所有的额外石头。

提示：

• n == capacity.length == rocks.length
• 1 <= n <= 5 * 104
• 1 <= capacity[i] <= 109
• 0 <= rocks[i] <= capacity[i]
• 1 <= additionalRocks <= 109

地址

https://leetcode.cn/problems/maximum-bags-with-full-capacity-of-rocks

题意

贪心算法

思路

1. 由于额外的石头有限，肯定是有限将其放置在需要数量最少的背包中，将每个背包装满需要的数量按照从小到大进行排序，然后依次填放即可。
2. 复杂度分析：

• 时间复杂度：$O(n \log n)$，其中 $n$ 为数组中的长度。
• 空间复杂度：$O(\log n)$, 排序需要的栈空间为 $O(\log n)$.

代码

class Solution {
public:
    int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
        int n = rocks.size();
        int ans = 0;
        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            arr[i] = capacity[i] - rocks[i];
        }
        sort(arr.begin(), arr.end());
        for (int i = 0; i < n; i++) {
            if (arr[i] <= additionalRocks) {
                additionalRocks -= arr[i];
                ans++;
            }
        }
        return ans;
    }
};

2280. 表示一个折线图的最少线段数

题目

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

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

示例 1：

输入：stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]
输出：3
解释：
上图为输入对应的图，横坐标表示日期，纵坐标表示价格。
以下 3 个线段可以表示折线图：
- 线段 1 （红色）从 (1,7) 到 (4,4) ，经过 (1,7) ，(2,6) ，(3,5) 和 (4,4) 。
- 线段 2 （蓝色）从 (4,4) 到 (5,4) 。
- 线段 3 （绿色）从 (5,4) 到 (8,1) ，经过 (5,4) ，(6,3) ，(7,2) 和 (8,1) 。
可以证明，无法用少于 3 条线段表示这个折线图。

示例 2：

输入：stockPrices = [[3,4],[1,2],[7,8],[2,3]]
输出：1
解释：
如上图所示，折线图可以用一条线段表示。

提示：

• 1 <= stockPrices.length <= 105
• stockPrices[i].length == 2
• 1 <= dayi, pricei <= 109
• 所有 dayi 互不相同 。

地址

https://leetcode.cn/problems/minimum-lines-to-represent-a-line-chart

题意

数学

思路

1. 这个题目毫无意义，感觉就是个简单题目。首先我们将所有的点按照横坐标的大小进行排序，连续的三个点如果不在一条直线上，此时则需要新的折线。设连续的三个点为 $p_1, p_2,p_3$，此时我们只需要判断 $p_3$ 是否在 $p_1$ 与 $p_2$ 构成的直线上即可。
2. 复杂度分析：

• 时间复杂度：$O(n \log n)$, 其中 $n$ 为数组的长度。
• 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int minimumLines(vector<vector<int>>& stockPrices) {
        int n = stockPrices.size();
        int res = 1;
        if (n == 1) {
            return 0;
        }
        sort(stockPrices.begin(), stockPrices.end());
        for (int i = 2; i < n; i++) {
            long long x1 = stockPrices[i-2][0] - stockPrices[i-1][0];
            long long y1 = stockPrices[i-2][1] - stockPrices[i-1][1];
            long long x2 = stockPrices[i-1][0] - stockPrices[i][0];
            long long y2 = stockPrices[i-1][1] - stockPrices[i][1];
            if (x1 * y2 != x2 * y1) {
                res++;
            }
        }
        return res;
    }
};

2281. 巫师的总力量和

题目

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

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

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

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

示例 1：

输入：strength = [1,3,1,2]
输出：44
解释：以下是所有连续巫师组：
- [1,3,1,2] 中 [1] ，总力量值为 min([1]) * sum([1]) = 1 * 1 = 1
- [1,3,1,2] 中 [3] ，总力量值为 min([3]) * sum([3]) = 3 * 3 = 9
- [1,3,1,2] 中 [1] ，总力量值为 min([1]) * sum([1]) = 1 * 1 = 1
- [1,3,1,2] 中 [2] ，总力量值为 min([2]) * sum([2]) = 2 * 2 = 4
- [1,3,1,2] 中 [1,3] ，总力量值为 min([1,3]) * sum([1,3]) = 1 * 4 = 4
- [1,3,1,2] 中 [3,1] ，总力量值为 min([3,1]) * sum([3,1]) = 1 * 4 = 4
- [1,3,1,2] 中 [1,2] ，总力量值为 min([1,2]) * sum([1,2]) = 1 * 3 = 3
- [1,3,1,2] 中 [1,3,1] ，总力量值为 min([1,3,1]) * sum([1,3,1]) = 1 * 5 = 5
- [1,3,1,2] 中 [3,1,2] ，总力量值为 min([3,1,2]) * sum([3,1,2]) = 1 * 6 = 6
- [1,3,1,2] 中 [1,3,1,2] ，总力量值为 min([1,3,1,2]) * sum([1,3,1,2]) = 1 * 7 = 7
所有力量值之和为 1 + 9 + 1 + 4 + 4 + 4 + 3 + 5 + 6 + 7 = 44 。

示例 2：

输入：strength = [5,4,6]
输出：213
解释：以下是所有连续巫师组：
- [5,4,6] 中 [5] ，总力量值为 min([5]) * sum([5]) = 5 * 5 = 25
- [5,4,6] 中 [4] ，总力量值为 min([4]) * sum([4]) = 4 * 4 = 16
- [5,4,6] 中 [6] ，总力量值为 min([6]) * sum([6]) = 6 * 6 = 36
- [5,4,6] 中 [5,4] ，总力量值为 min([5,4]) * sum([5,4]) = 4 * 9 = 36
- [5,4,6] 中 [4,6] ，总力量值为 min([4,6]) * sum([4,6]) = 4 * 10 = 40
- [5,4,6] 中 [5,4,6] ，总力量值为 min([5,4,6]) * sum([5,4,6]) = 4 * 15 = 60
所有力量值之和为 25 + 16 + 36 + 36 + 40 + 60 = 213 。

提示：

• 1 <= strength.length <= 105
• 1 <= strength[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-294/problems/sum-of-total-strength-of-wizards/

题意

单调栈、动态规划

思路

1. 动态规划解法思路，需要参考「907. 子数组的最小值之和」, 知道这个题目这个题目就非常好做了。

• 设数组的长度为 $n$, 数组 $s$ 的前 $i$ 项的前缀和为 $$\textit{sum}[i] = \sum_{j=0}^{i}s[i]$$，前 $i$ 项的前缀和的前缀和为: $$\textit{ssum}[i] = \sum_{j=0}^{i}sum[j] = \sum_{j=0}^{i}\sum_{k=0}^{j}s[k]$$
• 设数组中以 $i$ 为起点，以 $j$ 且满足 $(i \le j)$ 的连续子数组的最小值为 $\textit{min}(i,j)$, 设以 $i$ 为起点的子数组的最小值的和为 $\textit{minSum}[i] = \sum_{j=i}^{n-1}\textit{min}(i,j)$。此处可以利用单调栈来求出 $\textit{minSum}[i]$，具体可以参考「907. 子数组的最小值之和」的解法即可。
• 设 $dp[i]$ 表示以 $i$ 为起点的子数组构成的魔力值之和，则此时我们可以知道如下公式:
  $$dp[i] = \sum_{j=i}^{n-1}(sum[j] - sum[i-1]) \times min(i,j)$$
• 我们假设数组中 $i$ 的右侧第一个小于 $s[i]$ 的元素为 $s[j]$，且满足 $i < j \le n - 1$，则此时我们知道当 $i \le k < j $ 时，此时区间 $[i,j-1]$ 之间 $s[i]$ 最小，因此 $min(i,k) = s[i]$；当满足 $j \le k < n$ 时，则此时区间 $[i,k]$ 之间可定不是 $s[i]$ 最小，因为此时已知 $s[i] < s[j]$ 最小的值一定在 $j$ 的右侧，因此 $min(i,k) = min(j,k)$。此时我们将上述式子从 $j$ 处拆分可以得到如下:
  $$
  dp[i] = \sum_{k=i}^{n-1}(sum[k] - sum[i-1]) \times min(i,k) \
  = \sum_{k=i}^{j-1}(sum[k] - sum[i-1]) \times min(i,k) + \sum_{k=j}^{n-1}(sum[k] - sum[i-1]) \times min(i,k) \
  = \sum_{k=i}^{j-1}(sum[k] - sum[i-1]) \times s[i] + \sum_{k=j}^{n-1}(sum[k] - sum[i-1]) \times min(j,k) \
  = (\sum_{k=i}^{j-1}sum[k] - (j - i)\times sum[i-1]) \times s[i] + \sum_{k=j}^{n-1}(sum[k] - sum[j-1] + sum[j-1] - sum[i-1]) \times min(j,k) \
  = (\sum_{k=i}^{j-1}sum[k] - (j - i)\times sum[i-1]) \times s[i] + \sum_{k=j}^{n-1}(sum[k] - sum[j-1] ) \times min(j,k) + \sum_{k=j}^{n-1}(sum[j-1] - sum[i-1]) \times min(j,k)\
  = (ssum[j-1] - ssum[i-1] + (j-i) \times sum[i-1]) + (sum[j-1] - sum[i-1]) \times \sum_{k=j}^{n-1}min(j,k) + \sum_{k=j}^{n-1}(sum[k] - sum[j-1] ) \times min(j,k) \
  = (ssum[j-1] - ssum[i-1] + (j-i) \times sum[i-1]) + (sum[j-1] - sum[i-1]) \times minSum[j] + dp[j]
  $$
  以上即为我们推导出的动态规划递推公式。

2. 求每个数的贡献值，设以 $s[i]$ 为最小值得区间为 $[l,r]$，此时以 $s[i]$ 为最小值的子数组的魔力值之和为 $s[i] \times \sum_{j=l}^{i}\sum_{k=i}^{r}s[k]$，此时我们只需要求出 $[l,r]$ 即可，可以用用单调栈解决上述问题，可以参考题解,写的很清晰。上述解法难点有两点比较难以处理:

• 左右区间中遇到相同的元素如何处理，当时也很疑惑这个问题，没有想明白，后来看了题解，可以用一边严格的小于，另一边小于等于即可规避相同元素的问题，确实非常巧妙。
• 计算 $s[i] \times \sum_{j=l}^{i}\sum_{k=i}^{r}s[k]$ 需要用到一些数学变换的技巧，不过还是蛮有意思的思考题目。

3. 复杂度分析：

• 时间复杂度：$O(n)$, 其中 $n$ 为数组的长度，只需要遍历数组两次即可完成。
• 空间复杂度：$O(n)$, 其中 $n$ 为数组的长度。

代码

• 参考: 单调栈 + 计算贡献值

  class Solution { public: const int mod = 1e9 + 7; int totalStrength(vector<int>& strength) { int n = strength.size(); // 步骤1. 求左侧第一个 <= x 的坐标，和右侧第一个 < x 的坐标 stack<int> st; vector<int> left(n, -1), right(n, n); for(int i = 0; i < n; ++i) { while(st.size() && strength[st.top()] > strength[i]) { right[st.top()] = i; st.pop(); } if(st.size()) { left[i] = st.top(); } st.push(i); } // 步骤2. 准备前缀和 psum 和 前缀和的前缀和 ppsum vector<int> psum = strength; for(int i = 1; i < n; ++i) { psum[i] = (psum[i] + psum[i-1]) % mod; } vector<int> ppsum = psum; for(int i = 1; i < n; ++i) { ppsum[i] = (ppsum[i] + ppsum[i-1]) % mod; } auto f = [&](int l, int r) { if(r < 0) return 0; if(l < 0) return ppsum[r]; return (ppsum[r] - ppsum[l] + mod) % mod; }; // 步骤3. 针对每个 min 值计算结果 // 对于 a[i], 其管辖区间为 [left[i] + 1, right[i] - 1] // 问题归结, 将 l = left[i] + 1, r = right[i] - 1 代入上面的式子求解即可 int res = 0; for(int i = 0; i < n; ++i) { int l = left[i] + 1, r = right[i] - 1; int sleft = 1ll * f(l-2, i-1) * (r - i + 1) % mod; int sright = 1ll * f(i-1, r) * (i - l + 1) % mod; res += 1ll * strength[i] * (((sright - sleft) + mod) % mod) % mod; res %= mod; } return res; } };

• 单调栈 + 动态规划

  class Solution { public: int totalStrength(vector<int>& strength) { int n = strength.size(); long long mod = 1e9 + 7; long long ans = 0; vector<long long> rminsum(n + 1); vector<long long> sum(n + 1); vector<long long> ssum(n + 1); vector<long long> dp(n + 1); stack<pair<int,int>> st; for (int i = 0; i < n; i++) { sum[i + 1] = (strength[i] + sum[i]) % mod; ssum[i + 1] = (sum[i + 1] + ssum[i]) % mod; } st.emplace(0, n); for (int i = n - 1; i >= 0; i--) { while (!st.empty() && strength[i] <= st.top().first) { st.pop(); } int j = st.top().second; rminsum[i] = (rminsum[j] + (long long)(j - i) * (long long)strength[i]) % mod; dp[i] = (dp[j] + rminsum[j] * (sum[j] - sum[i])) % mod; dp[i] = (dp[i] + mod + ((ssum[j] - ssum[i] - ((long long)(j - i) * sum[i])) % mod) * strength[i] % mod) % mod; st.emplace(strength[i], i); ans = (ans + dp[i]) % mod; } return ans; } };