周赛 - 🏆 第 294 场力扣周赛 - 《学习笔记》

6074. 字母在字符串中的百分比
6075. 装满石头的背包的最大数量
6076. 表示一个折线图的最少线段数
6077. 巫师的总力量和

寄，掉大分，t4有思路，但代码没写完。

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

给你一个字符串 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 是一个小写英文字母

思路：
统计目标字符出现的次数，计算占比

class Solution {
    public int percentageLetter(String s, char c) {
        int n = s.length(), cnt = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == c)
                    cnt++;
        }
        return cnt * 100 / n;
    }
}

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

现有编号从 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

思路：
贪心，按剩余可装石块数从小到大排序，尽可能多的装

class Solution {
    public int maximumBags(int[] c, int[] r, int add) {
        int n = c.length;
        int[] need = new int[n];
        for (int i = 0; i < n; i++)
            need[i] = c[i] - r[i];
        Arrays.sort(need);
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (add >= need[i]) {
                cnt++;
                add -= need[i];
            } else
                break;
        }
        return cnt;
    }
}

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

给你一个二维整数数组 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 互不相同 。

思路：
按横坐标排序，比较相邻线段的斜率即可
如何比较？都转换成最简分数形式，比较分子和分母

class Solution {
    public int minimumLines(int[][] s) {
        Arrays.sort(s, (o1, o2) -> (o1[0] - o2[0]));
        int cnt = 0;
        int px = 0, py = 0;
        for (int i = 1; i < s.length; i++) {
            int x1 = s[i - 1][0], y1 = s[i - 1][1];
            int x2 = s[i][0], y2 = s[i][1];
            if (i == 1) {
                cnt++;
            } else {
                int a1 = x2 - x1, b1 = y2 - y1;
                int a2 = x1 - px, b2 = y1 - py;
                int g1 = gcd(Math.abs(a1), Math.abs(b1));
                int g2 = gcd(Math.abs(a2), Math.abs(b2));
                a1 /= g1; b1 /= g1;
                a2 /= g2; b2 /= g2;
                if (a1 != a2 || b1 != b2)
                    cnt++;
            }
            px = x1;
            py = y1;
        }
        return cnt;
    }
    int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }
}

6077. 巫师的总力量和

作为国王的统治者，你有一支巫师军队听你指挥。
给你一个下标从 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

思路：
单调栈 + 前缀和 + 带系数的前缀和和后缀和 :::danger 特别注意：计算前缀和的时候下标不要搞错，还有就是一定要注意溢出问题 :::

class Solution {
    int N = 100010, MOD = (int)(1e9 + 7);
    long[] s = new long[N];
    long[] s1 = new long[N], s2 = new long[N];
    int[] pre = new int[N], last = new int[N];
    int n;
    int[] stk = new int[N];
    public int totalStrength(int[] c) {
        n = c.length;
        // 前缀和
        for (int i = 1; i <= n; i++)
            s[i] = s[i - 1] + c[i - 1];
        // 前缀前缀和
        for (int i = 1; i <= n; i++)
            s1[i] = s1[i - 1] + 1L * i * c[i - 1];
        // 后缀后缀和
        for (int i = n; i > 0; i--)
            s2[i] = s2[i + 1] + (n - i + 1L) * c[i - 1];
        // 单调栈找左侧小于当前数的数的下标
        Arrays.fill(pre, -1);
        int p = -1;
        for (int i = 0; i < n; i++) {
            while (p > -1 && c[stk[p]] >= c[i])
                p--;
            if (p > -1) pre[i] = stk[p];
            stk[++p] = i;
        }
        // 单调栈找右侧小于等于当前数的数的下标
        Arrays.fill(last, n);
        p = -1;
        for (int i = n - 1; i >= 0; i--) {
            while (p > -1 && c[stk[p]] > c[i])
                p--;
            if (p > -1) last[i] = stk[p];
            stk[++p] = i;
        }
        // debug
        // System.out.println(Arrays.toString(s));
        // System.out.println(Arrays.toString(s1));
        // System.out.println(Arrays.toString(s2));
        // System.out.println(Arrays.toString(pre));
        // System.out.println(Arrays.toString(last));
        long res = 0;
        for (int i = 0; i < n; i++) {
            int l = pre[i], r = last[i];
            long cl = i - l, cr = r - i;
            long left = getPre(i, l + 2) * c[i] % MOD * cr % MOD;
            long right = getLast(i + 2, r) * c[i] % MOD * cl % MOD;
            long cur = c[i] * cl % MOD * cr % MOD * c[i] % MOD;
            res = ((res + (left + right) % MOD) % MOD + cur) % MOD;
        }
        return (int)(res % MOD);
    }
    long getLast(int l, int r) {
        if (l > r) return 0;
        return (s2[l] - s2[r + 1] - (n - r) * (s[r] - s[l - 1])) % MOD;
    }
    long getPre(int r, int l) {
        if (r < l) return 0;
        long res = (s1[r] - s1[l - 1] - (l - 1) * (s[r] - s[l - 1])) % MOD;
        return res;
    }
}