leetcode biweekly contest 507

leetcode contest 507

本周的题目还算是比较经典的题目，确实不错的题目。

3968. 移动后的最大曼哈顿距离

给你一个由字符 'U'、'D'、'L'、'R' 和 '_' 组成的字符串 moves。

从原点 (0, 0) 出发，每个字符表示二维平面上的一次移动：

• 'U'：向上移动 1 个单位。
• 'D'：向下移动 1 个单位。
• 'L'：向左移动 1 个单位。
• 'R'：向右移动 1 个单位。
• '_'：可以独立地替换为 'U'、'D'、'L' 或 'R' 中的任意一个字符。

返回执行完所有移动后，能够达到的距离原点的 最大曼哈顿距离 。

两点 (x1, y1) 和 (x2, y2) 之间的 曼哈顿距离 为 |x1 - x2| + |y1 - y2|。

示例 1：

输入： moves = “LD“

输出： 4

解释：

一种最优选择为：

• 'L'：(0, 0) -> (-1, 0)
• 将 '_' 视为 'D'：(-1, 0) -> (-1, -1)
• 'D'：(-1, -1) -> (-1, -2)
• 将 '_' 视为 'L'：(-1, -2) -> (-2, -2)

最终位置到原点的曼哈顿距离为 |0 - (-2)| + |0 - (-2)| = 4。

示例 2：

输入： moves = “U_R”

输出： 3

解释：

一种最优选择为：

• 'U'：(0, 0) -> (0, 1)
• 将 '_' 视为 'U'：(0, 1) -> (0, 2)
• 'R'：(0, 2) -> (1, 2)

最终位置到原点的曼哈顿距离为 |0 - 1| + |0 - 2| = 3。

提示：

• 1 <= moves.length <= 105
• moves 仅由 'U'、'D'、'L'、'R' 和 '_' 组成。

地址

https://leetcode.cn/problems/maximum-manhattan-distance-after-all-moves/description/

题意

贪心算法

思路

1. 我们仔细想象，由于指定方向的无法进行改变，由于给定的步数无论按照任何顺序走，它到达重点的曼哈顿距离都不会改变。因此我们只需要统计在已经指定方向的操作后，我们可以计算出它的重点，剩余的未指定方向，则沿着一个方向走一定可以得到最大值。
2. 复杂度分析：

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。

代码

class Solution:
    def maxDistance(self, moves: str) -> int:
        return abs(moves.count('R') - moves.count('L')) + abs(moves.count('U') - moves.count('D')) + moves.count('_')

3969. 求和后首尾数字相同的有效子数组 I

给你一个整数数组 nums 和一个整数数字 x。

如果一个 子数组 nums[l..r] 的元素和同时满足以下两个条件，则认为该子数组是 有效子数组：

• 该和的首位数字等于 x。
• 该和的末位数字等于 x。

返回有效子数组的数量。

子数组 是数组中一个连续、非空 的元素序列。

示例 1：

输入： nums = [1,100,1], x = 1

输出： 4

解释：

有效子数组为：

• nums[0..0]：sum = 1
• nums[0..1]：sum = 1 + 100 = 101
• nums[1..2]：sum = 100 + 1 = 101
• nums[2..2]：sum = 1

因此，答案为 4。

示例 2：

输入： nums = [1], x = 2

输出： 0

解释：

唯一的子数组是 nums[0..0]，其和为 1，不满足条件。

因此，答案为 0。

提示：

• 1 <= nums.length <= 1500
• 1 <= nums[i] <= 109
• 1 <= x <= 9

地址

https://leetcode.cn/problems/valid-subarrays-with-matching-sum-digits-i/description/

题意

枚举

思路

1. 直接枚举所有的子数组即可，并计算子数组的和，并去除子数组的第一位和最后一位，判断是否等于 $x$；
2. 复杂度分析：

• 时间复杂度：$O(n^2)$，其中 $n$ 表示给定数组的长度；
• 空间复杂度：$O(1)$，其中 $n$ 表示给定数组的长度；

代码

class Solution {
public:
    int countValidSubarrays(vector<int>& nums, int x) {
        int ans = 0;
        int n = nums.size();
        for (int i = 0; i < nums.size(); i++) {
            long long sum = 0;
            for (int j = i; j < nums.size(); j++) {
                sum += nums[j];
                int first = sum / pow(10, (int)log10(sum));
                int last = sum % 10;
                if (first == x && last == x) {
                    ans++;
                }
            }
        }
        return ans;
    }
};

---

3970. 最多 K 个连续相同字符的最短路径

给你一个整数 n，表示一个 有向加权 图中的节点数量，节点编号从 0 到 n - 1。该图由二维数组 edges 表示，其中 edges[i] = [ui, vi, wi] 表示一条从节点 ui 指向节点 vi、权重为 wi 的有向边。

另给定一个长度为 n 的字符串 labels，其中 labels[i] 是分配给节点 i 的字符，以及一个整数 k。

返回一条从节点 0 到节点 n - 1 的路径的 最小**总边权 ，并要求该路径上所有节点标签按顺序 拼接 后，最多包含 k 个 连续相同** 字符。如果不存在有效路径，返回 -1。

示例 1：

输入： n = 3, edges = [[0,1,1],[1,2,1],[0,2,3]], labels = “aab”, k = 1

输出： 3

解释：

从节点 0 到节点 2 的最优有效路径如下：

• 使用 edges[2] = [0, 2, 3] 到达节点 2，边权 wi = 3。

对应的标签拼接结果为 "ab"，满足最多有 k = 1 个连续相同字符。因此答案为 3。

示例 2：

输入： n = 3, edges = [[0,1,1],[1,2,1],[0,2,3]], labels = “aab”, k = 2

输出： 2

解释：

从节点 0 到节点 2 的最优有效路径如下：

• 使用 edges[0] = [0, 1, 1] 到达节点 1，边权 wi = 1。
• 使用 edges[1] = [1, 2, 1] 到达节点 2，边权 wi = 1。

对应的标签拼接结果为 "aab"，满足最多有 k = 2 个连续相同字符。因此答案为 2。

示例 3：

输入： n = 3, edges = [[0,1,1],[1,2,1]], labels = “aaa”, k = 2

输出： -1

解释：

不存在从节点 0 到节点 2 的有效路径，使其满足最多有 k = 2 个连续相同字符。因此答案为 -1。

提示：

• 1 <= n == labels.length <= 5 * 104
• 0 <= edges.length <= 5 * 104
• edges[i] == [ui, vi, wi]
• 0 <= ui, vi <= n - 1
• ui != vi
• 1 <= wi <= 104
• labels 由小写英文字母组成
• 1 <= k <= 50

地址

https://leetcode.cn/problems/shortest-path-with-at-most-k-consecutive-identical-characters/description/

题意

优先队列

思路

1. 每次直接从队列选择cost最小的即可，非常模板的题目。
2. 复杂度分析：

• 时间复杂度：$𝑂((n + v) \log nk)$，其中 $n$ 表示给定的数组的长度，$v$ 表示给定的边的数目
• 空间复杂度：$𝑂(𝑛)$，其中 𝑛 表示给定的数组的长度。

代码

struct Element {
    long long cost;
    int u;
    char ch;
    int cnt;
    Element(long long _cost, int _u, char _ch, int _cnt)
        : cost(_cost), u(_u), ch(_ch), cnt(_cnt) {}
};

class Solution {
public:
    int shortestPath(int n, vector<vector<int>>& edges, string labels, int k) {
        vector<vector<pair<int, int>>> graph(n);
        for (const auto& e : edges) {
            graph[e[0]].emplace_back(e[1], e[2]);
        }

        auto cmp = [](const Element& a, const Element& b) {
            return a.cost > b.cost;
        };

        vector<vector<long long>> dist(n, vector<long long>(k + 1, LLONG_MAX));
        priority_queue<Element, vector<Element>, decltype(cmp)> pq(cmp);
        
        dist[0][1] = 0;
        pq.emplace(0, 0, labels[0], 1);

        while (!pq.empty()) {
            auto [cost, u, ch, cnt] = pq.top();
            pq.pop();

            if (u == n - 1) return (int)cost;
            if (cost > dist[u][cnt]) continue;

            for (auto [v, w] : graph[u]) {
                int ncnt = (ch == labels[v]) ? cnt + 1 : 1;
                long long newCost = cost + w;
                
                if (ncnt <= k && newCost < dist[v][ncnt]) {
                    dist[v][ncnt] = newCost;
                    pq.emplace(newCost, v, labels[v], ncnt);
                }
            }
        }

        return -1;
    }
};

3971. 最大总价值

给你两个整数数组 value 和 decay，以及一个整数 m。

• value[i] 表示下标 i 的初始价值。
• decay[i] 表示每次选择下标 i 后，该下标的价值会减少的数值。

你可以多次 选择 任意下标。所有下标的总选择次数不得超过 m。

如果重复选择下标 i，第 t 次（从 1 开始计数）获得的价值为 value[i] - decay[i] * (t - 1)。

返回你能够获得的 最大 总价值。由于答案可能很大，请返回其对 109 + 7 取模后的结果。

示例 1：

输入： value = [6,5,4], decay = [2,1,1], m = 4

输出： 19

解释：

一种最优选择序列如下：

• 选择下标 0，获得的价值为 6。
• 选择下标 1，获得的价值为 5。
• 选择下标 2，获得的价值为 4。
• 再次选择下标 0，获得的价值为 6 - 2 = 4。

总价值为 6 + 5 + 4 + 4 = 19。在至多 4 次选择中，没有其他选择序列能获得更高的总价值。

示例 2：

输入： value = [7,2,2], decay = [3,2,1], m = 2

输出： 11

解释：

一种最优选择序列如下：

• 选择下标 0，获得的价值为 7。
• 再次选择下标 0，获得的价值为 7 - 3 = 4。

总价值为 7 + 4 = 11。

示例 3：

输入： value = [4,3], decay = [5,4], m = 5

输出： 7

解释：

一种最优选择序列如下：

• 选择下标 0，获得的价值为 4。
• 选择下标 1，获得的价值为 3。

总价值为 4 + 3 = 7。

提示：

• 1 <= value.length == decay.length <= 105
• 1 <= value[i], decay[i] <= 109
• 1 <= m <= 109

地址

https://leetcode.cn/problems/maximum-total-value/description/

题意

二分查找

思路

1. 题目还是比较经典的题目，首先我们知道如果 $m$ 足够小，我们可以很容易想到使用优先队列，即每次从优先队列中选择最大的元素，然后减去 $decay$ ,然后将其再将其入队列，然后继续贪心取最大元素即可。但本题中给定的 $m$ 足够大，这种优先队列的方法显然不行，我们休要再思考一下，我们可以使用二分查找，找到所有可选的选择元素的最小值 $val$，此时我们可以尝试使用二分查找：

   • 当我们使用二分查找时，枚举最小值 $val$, 然后我们计算如果将数组中的每个元素减小到最接近 $val$ 时，需要选择的此时。由于对于每个元素 $value[i]$，每次选择时会减少 $decay[i]$，此时有可能 $value[i] - val$ 无法被 $decay[i]$ 整除，此时我们只能取上界。
   • 由于对于每个元素 $value[i]$，每次选择时会减少 $decay[i]$，此时有可能 $value[i] - val$ 可以被 $decay[i]$ 整除，这时的关键在于这样的 $value[i]$ 可能存在多个，此时我们可以统计可以到达 $val$ 的元素的数目，由于 $val$ 为最小值，则意味着至少有一个值可以到达 $val$，此时我们要检测最坏的情况是否可以到达，此时最多保留一个 $val$ 即可；
   • 我们通过二分查找找到所有可以取得目标值的下限；
   • 接着我们计算在此下限时，可以取得的最大值；但是在此下限时由于可能存在多个元素都取得了最小值 $target$，可能存在多取的可能，即此时选择元素次数大于 $m$，此时我们需要将多取的数目减去即可。

2. 复杂度分析：

• 时间复杂度：$𝑂(n \log k )$，其中 𝑛 表示给定数组的长度, $k$ 表示给定数组的最大值.
• 空间复杂度：$𝑂(1)$；

代码

class Solution {
public:
    int maxTotalValue(vector<int>& value, vector<int>& decay, int m) {
        int n = value.size();
        long long mod = 1e9 + 7;

        int lo = 0, hi = *max_element(value.begin(), value.end());
        int minVal = 0;
        while (lo <= hi) {
            long long mid = (lo + hi) / 2;
            int cnt = 0;
            long long total = 0;
            for (int i = 0; i < n; i++) {
                if (value[i] < mid) continue;
                long long x = value[i] - mid;
                if ((x % decay[i]) == 0) {
                    cnt++;
                } 
                total += x / decay[i] + 1;
            }
            total -= max(0, cnt - 1);
            if (total <= m) {
                minVal = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }

        long long ans = 0;
        int total = 0;
        int target = INT_MAX;
        for (int i = 0; i < n; i++) {
            if (value[i] < minVal) continue;
            int t = (value[i] - minVal) / decay[i] + 1;
            ans += (long long)t * (value[i] + value[i] - (t - 1) * decay[i]) / 2;
            // 计算最终的阈值
            target = min(target, value[i] - (t - 1) * decay[i]);
            total += t;
        }
        
        ans -= max(0LL, (long long)(total - m)) * target;
        return ans % mod;
    }
};

欢迎关注和打赏，感谢支持！

• 关注我的博客: https://mike-box.github.io/

• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu

• 关注我的微信公众号: 哪些奋斗者