且听疯吟

leetcode contest 341

2023-04-22

leetcode contest 341

T4感觉比较难一些，前三题太水的题目。

6376. 一最多的行

给你一个大小为 m x n 的二进制矩阵 mat ，请你找出包含最多 1 的行的下标（从 0 开始）以及这一行中 1 的数目。

如果有多行包含最多的 1 ，只需要选择 行下标最小 的那一行。

返回一个由行下标和该行中 1 的数量组成的数组。

示例 1：

输入：mat = [[0,1],[1,0]]
输出：[0,1]
解释：两行中 1 的数量相同。所以返回下标最小的行，下标为 0 。该行 1 的数量为 1 。所以，答案为 [0,1] 。

示例 2：

输入：mat = [[0,0,0],[0,1,1]]
输出：[1,2]
解释：下标为 1 的行中 1 的数量最多。该行 1 的数量为 2 。所以，答案为 [1,2] 。

示例 3：

输入：mat = [[0,0],[1,1],[0,0]]
输出：[1,2]
解释：下标为 1 的行中 1 的数量最多。该行 1 的数量为 2 。所以，答案为 [1,2] 。

提示：

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 100
  • mat[i][j] 为 0 或 1

地址

https://leetcode.cn/contest/weekly-contest-341/problems/row-with-maximum-ones/

题意

直接枚举

思路

  1. 求矩阵每行的元素和，并找到元素和最大的行即可。
  2. 复杂度分析：
  • 时间复杂度：$O(m\times n)$。
  • 空间复杂度：$O(1)$。

代码

class Solution {
public:
    vector<int> rowAndMaximumOnes(vector<vector<int>>& mat) {
        vector<int> res(2);
        for (int i = 0; i < mat.size(); i++) {
            int tot = accumulate(mat[i].begin(), mat[i].end(), 0);
            if (tot > res[1]) {
                res[0] = i;
                res[1] = tot;
            }
        }
        return res;
    }
};

6350. 找出可整除性得分最大的整数

给你两个下标从 0 开始的整数数组 nums 和 divisors 。

divisors[i] 的 可整除性得分 等于满足 nums[j] 能被 divisors[i] 整除的下标 j 的数量。

返回 可整除性得分 最大的整数 divisors[i] 。如果有多个整数具有最大得分，则返回数值最小的一个。

示例 1：

输入：nums = [4,7,9,3,9], divisors = [5,2,3]
输出：3
解释：divisors 中每个元素的可整除性得分为：
divisors[0] 的可整除性得分为 0 ，因为 nums 中没有任何数字能被 5 整除。
divisors[1] 的可整除性得分为 1 ，因为 nums[0] 能被 2 整除。 
divisors[2] 的可整除性得分为 3 ，因为 nums[2]、nums[3] 和 nums[4] 都能被 3 整除。 
因此，返回 divisors[2] ，它的可整除性得分最大。

示例 2：

输入：nums = [20,14,21,10], divisors = [5,7,5]
输出：5
解释：divisors 中每个元素的可整除性得分为：
divisors[0] 的可整除性得分为 2 ，因为 nums[0] 和 nums[3] 都能被 5 整除。
divisors[1] 的可整除性得分为 2 ，因为 nums[1] 和 nums[2] 都能被 7 整除。
divisors[2] 的可整除性得分为 2 ，因为 nums[0] 和 nums[3] 都能被5整除。 
由于 divisors[0]、divisors[1] 和 divisors[2] 的可整除性得分都是最大的，因此，我们返回数值最小的一个，即 divisors[2] 。

示例 3：

输入：nums = [12], divisors = [10,16]
输出：10
解释：divisors 中每个元素的可整除性得分为：
divisors[0] 的可整除性得分为 0 ，因为 nums 中没有任何数字能被 10 整除。
divisors[1] 的可整除性得分为 0 ，因为 nums 中没有任何数字能被 16 整除。 
由于 divisors[0] 和 divisors[1] 的可整除性得分都是最大的，因此，我们返回数值最小的一个，即 divisors[0] 。

提示：

  • 1 <= nums.length, divisors.length <= 1000
  • 1 <= nums[i], divisors[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-341/problems/find-the-maximum-divisibility-score/

题意

暴力枚举

思路

  1. 直接枚举即可，求每个整数被 $nums$ 整除的元素的统计数目，然后求出最大的即可，感觉就是个简单题目。
  2. 复杂度分析：
  • 时间复杂度：$O(n \times m)$，其中 $n,m$ 为数组的长度。
  • 空间复杂度：$O(\log n)$。其中 $n$ 为数组的长度。

代码

class Solution {
public:
    int maxDivScore(vector<int>& nums, vector<int>& divisors) {
        int n = nums.size();
        int tot = 0;
        sort(divisors.begin(), divisors.end());
        int res = divisors[0];
        for (int i = 0; i < divisors.size(); i++) {
            int cnt = 0;
            for (auto v : nums) {
                if (v % divisors[i] == 0) {
                    cnt++;
                }
            }
            if (cnt > tot) {
                res = divisors[i];
                tot = cnt;
            }
        }
        return res;
    }
};

6375. 构造有效字符串的最少插入数

给你一个字符串 word ，你可以向其中任何位置插入 “a”、”b” 或 “c” 任意次，返回使 word 有效 需要插入的最少字母数。

如果字符串可以由 “abc” 串联多次得到，则认为该字符串 有效 。

示例 1：

输入：word = "b"
输出：2
解释：在 "b" 之前插入 "a" ，在 "b" 之后插入 "c" 可以得到有效字符串 "abc" 。

示例 2：

输入：word = "aaa"
输出：6
解释：在每个 "a" 之后依次插入 "b" 和 "c" 可以得到有效字符串 "abcabcabc" 。

示例 3：

输入：word = "abc"
输出：0
解释：word 已经是有效字符串，不需要进行修改。

提示：

  • 1 <= word.length <= 50
  • word 仅由字母 “a”、”b” 和 “c” 组成。

地址

https://leetcode.cn/contest/weekly-contest-341/problems/minimum-additions-to-make-valid-string/

题意

动态规划

思路

  1. 设 $dp[i]$ 表示将前 $i$ 个字母变成 $abc$ 的序列的最小插入字符的数目，此时有以下几种情况：
    • 当前的两个字符分别为 $”ab”,”ac”,”bc”$ 时，此时我们只需要在当前位置插入一个字符即可， $dp[i] = dp[i-2] + 1$；
    • 当前的三个字符分别为 $”abc”$ 时，此时我们不需要插入字符 , $dp[i] = dp[i - 3] + 1 $；
    • 其余情况我们需要插入两个字符，$dp[i] = dp[i - 1] + 2$；
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 为字符串的长度。
  • 空间复杂度：$O(n)$，其中 $n$ 为字符串的长度。

代码

class Solution {
public:
    int addMinimum(string word) {
        int n = word.size();
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        dp[1] = 2;
        for (int i = 1; i < n; i++) {
            dp[i + 1] = dp[i] + 2;
            if ((word[i] == 'b' && word[i - 1] == 'a') || 
                (word[i] == 'c' && word[i - 1] == 'a') || 
                (word[i] == 'c' && word[i - 1] == 'b')) {
                dp[i + 1] = min(dp[i + 1], dp[i - 1] + 1);
            }  
            if (i - 2 >= 0 && word[i - 2] == 'a' && word[i - 1] == 'b' && word[i] == 'c') {
                 dp[i + 1] = min(dp[i + 1], dp[i - 2]);
            }
        }
        return dp[n];
    }
};

6378. 最小化旅行的价格总和

现有一棵无向、无根的树，树中有 n 个节点，按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。

每个节点都关联一个价格。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价格。

给定路径的 价格总和 是该路径上所有节点的价格之和。

另给你一个二维整数数组 trips ，其中 trips[i] = [starti, endi] 表示您从节点 starti 开始第 i 次旅行，并通过任何你喜欢的路径前往节点 endi 。

在执行第一次旅行之前，你可以选择一些 非相邻节点 并将价格减半。

返回执行所有旅行的最小价格总和。

示例 1：

img

输入：n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
输出：23
解释：
上图表示将节点 2 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 、2 和 3 并使其价格减半后的树。
第 1 次旅行，选择路径 [0,1,3] 。路径的价格总和为 1 + 2 + 3 = 6 。
第 2 次旅行，选择路径 [2,1] 。路径的价格总和为 2 + 5 = 7 。
第 3 次旅行，选择路径 [2,1,3] 。路径的价格总和为 5 + 2 + 3 = 10 。
所有旅行的价格总和为 6 + 7 + 10 = 23 。可以证明，23 是可以实现的最小答案。

示例 2：

img

输入：n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
输出：1
解释：
上图表示将节点 0 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 并使其价格减半后的树。 
第 1 次旅行，选择路径 [0] 。路径的价格总和为 1 。 
所有旅行的价格总和为 1 。可以证明，1 是可以实现的最小答案。

提示：

  • 1 <= n <= 50
  • edges.length == n - 1
  • 0 <= ai, bi <= n - 1
  • edges 表示一棵有效的树
  • price.length == n
  • price[i] 是一个偶数
  • 1 <= price[i] <= 1000
  • 1 <= trips.length <= 100
  • 0 <= starti, endi <= n - 1

地址

https://leetcode.cn/contest/weekly-contest-341/problems/minimize-the-total-price-of-the-trips/

题意

树形dp

思路

  1. 首先我们可以观察到树中的所有路径均是确定的，即从 $x$ 到 $y$ 只有唯一的一条路径，在所有的行程中每个节点经过的次数是固定的，因此我们可以利用深度优先搜索将所有点的经过次数统计出来，而此时如果没有路径减半的操作，我们可以知道总的路径和为 :

    $$
    total = \sum_{i=0}^{n}price[i] * cnt[i]
    $$

  2. 如果数量减半，我们即将 $price[i]$ 除以 $2$ 即可，本题则编程了另一个经典题目打家劫舍 III，此时就变的非常简单了，树上的动态规划，感觉还是脑袋秀逗了，在这个 $tricky$ 的地方卡住了。

  3. 复杂度分析：

  • 时间复杂度：$O(n^2 + m \times n)$，其中 $n$ 为节点的数目,$m$ 表示查询的次数。
  • 空间复杂度：$O(n)$，其中 $n$ 为节点的数目。

代码

 class Solution {
public:
    int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
        vector<vector<int>> adj(n);
        for (int i = 0; i < edges.size(); i++) {
            int x = edges[i][0], y = edges[i][1];
            adj[x].emplace_back(y);
            adj[y].emplace_back(x);
        }
        vector<int> cnt(n);
        function<bool(int, int, int)> dfs = [&](int fa, int curr, int end) -> bool {
            if (curr == end) {
                return true;
            }
            for (auto v : adj[curr]) {
                if (v != fa && dfs(curr, v, end)) {
                    cnt[v]++;
                    return true;
                }
            }
            return false;
        };
        for (auto v : trips) {
            cnt[v[0]]++;
            dfs(-1, v[0], v[1]);
        }
        for (int i = 0; i < n; i++) {
            price[i] = cnt[i] * price[i];
        }
        function<pair<int,int>(int, int)> dfs1 = [&](int fa, int curr) -> pair<int,int> {
            int half = price[curr] / 2;
            int total = price[curr];
            for (auto v : adj[curr]) {
                if (v == fa) continue;
                auto [ch_half, ch_total] = dfs1(curr, v);
                total += min(ch_half, ch_total);
                half += ch_total;
            }
            return {half, total};
        };
        auto [half, total] = dfs1(-1, 0);
        return min(half, total);
    }
};

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

Tags: 力扣周赛 题解
← leetcode weekly contest 339 leetcode contest 340 →

扫描二维码，分享此文章