leetcode contest biweekly 297

早上太忙，匆匆参加了周赛，感觉第三题竟然出了点小意外，有个小的符号错误没有检查出来。

5259. 计算应缴税款总额

题目

给你一个下标从 0 开始的二维整数数组 brackets ，其中 brackets[i] = [upperi, percenti] ，表示第 i 个税级的上限是 upperi ，征收的税率为 percenti 。税级按上限 从低到高排序（在满足 0 < i < brackets.length 的前提下，upperi-1 < upperi）。

税款计算方式如下：

• 不超过 upper0的收入按税率 percent0 缴纳
• 接着 upper1 - upper0 的部分按税率 percent1 缴纳
• 然后 upper2 - upper1 的部分按税率 percent2 缴纳
  以此类推
  给你一个整数 income 表示你的总收入。返回你需要缴纳的税款总额。与标准答案误差不超 10-5 的结果将被视作正确答案。

示例 1：

输入：brackets = [[3,50],[7,10],[12,25]], income = 10
输出：2.65000
解释：
前 $3 的税率为 50% 。需要支付税款 $3 * 50% = $1.50 。
接下来 $7 - $3 = $4 的税率为 10% 。需要支付税款 $4 * 10% = $0.40 。
最后 $10 - $7 = $3 的税率为 25% 。需要支付税款 $3 * 25% = $0.75 。
需要支付的税款总计 $1.50 + $0.40 + $0.75 = $2.65 。

示例 2：

输入：brackets = [[1,0],[4,25],[5,50]], income = 2
输出：0.25000
解释：
前 $1 的税率为 0% 。需要支付税款 $1 * 0% = $0 。
剩下 $1 的税率为 25% 。需要支付税款 $1 * 25% = $0.25 。
需要支付的税款总计 $0 + $0.25 = $0.25 。

示例 3：

输入：brackets = [[2,50]], income = 0
输出：0.00000
解释：
没有收入，无需纳税，需要支付的税款总计 $0 。

提示：

• 1 <= brackets.length <= 100
• 1 <= upperi <= 1000
• 0 <= percenti <= 100
• 0 <= income <= 1000
• upperi 按递增顺序排列
• upperi 中的所有值 互不相同
• 最后一个税级的上限大于等于 income

地址

https://leetcode.cn/problems/calculate-amount-paid-in-taxes

题意

直接模拟

思路

1. 每次求出区间 $[upper_i, upper_{i+1}]$ 内的值然后将其乘以 $percent_i$ 即为区间内缴纳的税，最后统计所有的税收之和即可。
2. 复杂度分析：

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

代码

class Solution {
public:
    double calculateTax(vector<vector<int>>& brackets, int income) {
        double res = 0;
        int last = 0;
        for (int i = 0; i < brackets.size(); i++) {
            if (income >= last) {
                int x = min(income, brackets[i][0]) - last;
                res += x * 1.0 * brackets[i][1] / 100.0;
            }
            last = brackets[i][0];
        }
        return res;
    }
};

5270. 网格中的最小路径代价

题目

给你一个下标从 0 开始的整数矩阵 grid ，矩阵大小为 m x n ，由从 0 到 m * n - 1 的不同整数组成。你可以在此矩阵中，从一个单元格移动到 下一行 的任何其他单元格。如果你位于单元格 (x, y) ，且满足 x < m - 1 ，你可以移动到 (x + 1, 0), (x + 1, 1), ..., (x + 1, n - 1) 中的任何一个单元格。注意： 在最后一行中的单元格不能触发移动。

每次可能的移动都需要付出对应的代价，代价用一个下标从 0 开始的二维数组 moveCost 表示，该数组大小为 (m * n) x n ，其中 moveCost[i][j] 是从值为 i 的单元格移动到下一行第 j 列单元格的代价。从 grid 最后一行的单元格移动的代价可以忽略。

grid 一条路径的代价是：所有路径经过的单元格的 值之和 加上 所有移动的 代价之和 。从 第一行 任意单元格出发，返回到达 最后一行 任意单元格的最小路径代价。

示例 1：

输入：grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
输出：17
解释：最小代价的路径是 5 -> 0 -> 1 。
- 路径途经单元格值之和 5 + 0 + 1 = 6 。
- 从 5 移动到 0 的代价为 3 。
- 从 0 移动到 1 的代价为 8 。
路径总代价为 6 + 3 + 8 = 17 。

示例 2：

输入：grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]]
输出：6
解释：
最小代价的路径是 2 -> 3 。 
- 路径途经单元格值之和 2 + 3 = 5 。 
- 从 2 移动到 3 的代价为 1 。 
路径总代价为 5 + 1 = 6 。

提示：

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 50
• grid 由从 0 到 m * n - 1 的不同整数组成
• moveCost.length == m * n
• moveCost[i].length == n
• 1 <= moveCost[i][j] <= 100

地址

https://leetcode.cn/problems/minimum-path-cost-in-a-grid

题意

动态规划

思路

1. 简单的规划，常规题目，设 $dp[i][j]$ 表示到达 $i,j$ 的最小代价，则可以知道递推公式为 $dp[i][j] = min(dp[i-1][k] + \textit{moveCost}[dp[i-1][k]][j]) + \textit{grid}[i][j]$, 根据以上递推公式求出到达第 $m-1$ 行的最小值即可。
2. 复杂度分析：

• 时间复杂度：$O(m \times n^2)$，其中 $m$ 为矩阵的行数， $n$ 表示矩阵的列数。
• 空间复杂度：$O(m \times n)$, 可以使用滚动数组优化到 $O(n)$。

代码

class Solution {
public:
    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
        int m = grid.size();
        int n = grid[0].size();
        int res = 0;
        vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
        for (int i = 0; i < n; i++) {
            dp[0][i] = grid[0][i];
        } 
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    dp[i][j] = min(dp[i][j], grid[i][j] + dp[i-1][k] + moveCost[grid[i-1][k]][j]);
                }
            }
        }
        return *min_element(dp[m-1].begin(), dp[m-1].end());
    }
};

5289. 公平分发饼干

题目

给你一个整数数组 cookies ，其中 cookies[i] 表示在第 i 个零食包中的饼干数量。另给你一个整数 k 表示等待分发零食包的孩子数量，所有 零食包都需要分发。在同一个零食包中的所有饼干都必须分发给同一个孩子，不能分开。

分发的 不公平程度 定义为单个孩子在分发过程中能够获得饼干的最大总数。

返回所有分发的最小不公平程度。

示例 1：

输入：cookies = [8,15,10,20,8], k = 2
输出：31
解释：一种最优方案是 [8,15,8] 和 [10,20] 。
- 第 1 个孩子分到 [8,15,8] ，总计 8 + 15 + 8 = 31 块饼干。
- 第 2 个孩子分到 [10,20] ，总计 10 + 20 = 30 块饼干。
分发的不公平程度为 max(31,30) = 31 。
可以证明不存在不公平程度小于 31 的分发方案。

示例 2：

输入：cookies = [6,1,3,2,2,4,1,2], k = 3
输出：7
解释：一种最优方案是 [6,1]、[3,2,2] 和 [4,1,2] 。
- 第 1 个孩子分到 [6,1] ，总计 6 + 1 = 7 块饼干。 
- 第 2 个孩子分到 [3,2,2] ，总计 3 + 2 + 2 = 7 块饼干。
- 第 3 个孩子分到 [4,1,2] ，总计 4 + 1 + 2 = 7 块饼干。
分发的不公平程度为 max(7,7,7) = 7 。
可以证明不存在不公平程度小于 7 的分发方案。

提示：

• 2 <= cookies.length <= 8
• 1 <= cookies[i] <= 105
• 2 <= k <= cookies.length

地址

https://leetcode.cn/problems/fair-distribution-of-cookies

题意

数位动态规划

思路

1. 感觉是老掉牙的题目了，一点新意都没有，基本上妥妥的模板题目了。。设 $dp[i][state]$ 表示前 $i$ 孩子分配 $state$ 表示的饼干所取得的最小不公平值，此时我们可以知道 $dp[i+1][j] = \min(\max(dp[i][s] + sum[j \oplus s])) \qquad s \in j$，状态 $s$ 是 $j$ 的二进制子集。
2. 复杂度分析：

• 时间复杂度：$O(k \times 3 ^ n)$, 其中 $k$ 人数，$n$ 表示饼干的数目。
• 空间复杂度：$O(k \times 2 ^ n)$，其中 $k$ 人数，$n$ 表示饼干的数目, 可以进行滚动数组优化空间为 $2^n$。

代码

• 反向 dp:

  class Solution { public: int distributeCookies(vector<int>& cookies, int k) { int n = cookies.size(); vector<vector<int>> dp(k + 1, vector<int>(1<<n, INT_MAX)); vector<int> sum(1<<n); for (int i = 1; i < (1<<n); i++) { for (int j = 0; j < n; j++) { if (i & (1<<j)) { sum[i] += cookies[j]; } } } dp[0][0] = 0; for (int i = 1; i <= k; i++) { for (int j = 0; j < (1 << n); j++) { if (dp[i-1][j] != INT_MAX) { for (int k = j; k < (1 << n); k = (k + 1) | j) { if ((j | k) == k) { dp[i][k] = min(dp[i][k], max(dp[i - 1][j], sum[k ^ j])); } } } } } return dp[k][(1<<n) - 1]; } };

• 正向 dp:

  class Solution { public: int distributeCookies(vector<int>& cookies, int k) { int n = cookies.size(); vector<vector<int>> dp(k + 1, vector<int>(1<<n, INT_MAX)); vector<int> sum(1<<n); for (int i = 1; i < (1<<n); i++) { int curr = 0; for (int j = 0; j < n; j++) { if (i & (1<<j)) { curr += cookies[j]; } } sum[i] = curr; dp[1][i] = curr; } dp[0][0] = 0; for (int i = 2; i <= k; i++) { for(int j = 1; j < (1<<n); j++) { for (int s = j; s != 0; s = (s - 1) & j) { if (dp[i-1][s] != INT_MAX) { dp[i][j] = min(dp[i][j], max(dp[i-1][s], sum[j^s])); } } } } return dp[k][(1<<n) - 1]; } };

6094. 公司命名

题目

给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下：

• 从 ideas 中选择 2 个 不同 名字，称为 ideaA 和 ideaB 。
• 交换 ideaA 和 ideaB 的首字母。
• 如果得到的两个新名字 都 不在 ideas 中，那么 ideaA ideaB（串联 ideaA 和 ideaB ，中间用一个空格分隔）是一个有效的公司名字。
  否则，不是一个有效的名字。
  返回 不同 且有效的公司名字的数目。

示例 1：

输入：ideas = ["coffee","donuts","time","toffee"]
输出：6
解释：下面列出一些有效的选择方案：
- ("coffee", "donuts")：对应的公司名字是 "doffee conuts" 。
- ("donuts", "coffee")：对应的公司名字是 "conuts doffee" 。
- ("donuts", "time")：对应的公司名字是 "tonuts dime" 。
- ("donuts", "toffee")：对应的公司名字是 "tonuts doffee" 。
- ("time", "donuts")：对应的公司名字是 "dime tonuts" 。
- ("toffee", "donuts")：对应的公司名字是 "doffee tonuts" 。
因此，总共有 6 个不同的公司名字。

下面列出一些无效的选择方案：
- ("coffee", "time")：在原数组中存在交换后形成的名字 "toffee" 。
- ("time", "toffee")：在原数组中存在交换后形成的两个名字。
- ("coffee", "toffee")：在原数组中存在交换后形成的两个名字。

示例 2：

输入：ideas = ["lack","back"]
输出：0
解释：不存在有效的选择方案。因此，返回 0 。

提示：

• 2 <= ideas.length <= 5 * 104
• 1 <= ideas[i].length <= 10
• ideas[i] 由小写英文字母组成
• ideas 中的所有字符串 互不相同

地址

https://leetcode.cn/problems/naming-a-company

题意

字符串

思路

1. 这个题目很奇怪，不知道想考察什么内容，感觉纯粹的就是考察观察力，不需要什么算法技巧即可。

• 首先我们用$hash$ 表保存所有的字符串，这个主要是为了查找变换后是否出现在字符串数组中很方便。
• 首先我们统计出第 $i$ 个字符串是否可以替换首为字母为 $j$ 的字符串，$\textit{canswap}[i][j]$ 表示第 $i$ 个字符串的首字母可以替换为 $\texttt{`a’} + j$。
• 同时统计字符串中可以由首字母 i 替换为首字符 j 的数目，$\textit{conv}[i][j]$ 表示字符串中为 $i$ 且可以变换为首字母为 $j$ 的字符串的个数。
• 我们遍历每一个字符串是 $s[i]$ 时，设此时 $s[i]$ 的首字母为 $k$， 如果 $s[i]$ 需要将首字母 $k$ 替换为 $j$ 时，此时则与之对应的字符串则需要将首字母 $j$ 替换为 $k$，只有这样才能达到互换，且保证互换后的两个字符串都不在原始数组 $\textit{ideas}$ 中，因此我们可以知道此时可以行程的公司名字数目为 $conv[j][k]$, 我们依次枚举所有可能的互换即可得到最终的结果。

2. 复杂度分析：

• 时间复杂度：$|\Sigma| \times n $，其中 $n$ 表示字符串的长度。
• 空间复杂度：$|\Sigma| \times n $, 其中 $n$ 表示字符串的长度。

代码

class Solution {
public:
    long long distinctNames(vector<string>& ideas) {
        int n = ideas.size();
        unordered_set<string> cnt;
        vector<vector<int>> canswap(n, vector<int>(26));
        vector<vector<int>> conv(26,vector<int>(26));
        long long res = 0;
        for (auto & w : ideas) {
            cnt.emplace(w);
        }
        for (int i = 0; i < n; i++) {
            string curr = ideas[i];
            int x = ideas[i][0] - 'a';
            for(int k = 0; k < 26; k++) {
                if (k != ideas[i][0] - 'a') {
                    curr[0] = 'a' + k;
                    if (!cnt.count(curr)) {
                        canswap[i][k] = 1;
                        conv[x][k]++;
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            int k = ideas[i][0] - 'a';
            for(int j = 0; j < 26; j++) {
                if(canswap[i][j]) {
                    res += conv[j][k];
                }
            }
        }
        
        return res;
    }
};

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

• 关注我的博客: http://mikemeng.org/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿