leetcode 第 297 场周赛

总结

这次周赛的最后一题很容易把人绕晕，没有考察太难的算法，但是需要较强的分析能力。

题目列表 1.计算应缴税款总额 题目描述

给你一个下标从 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

分析

模拟题，遍历brackets ，如果income大于上一个税级，就将这个税级部分的税加上去。举个例子税级分别是3 7 12，收入是10，初始的上一个税级last是0，10 > 0，然后计算按3税级收税的额度有多少，如果10大于3，则税级3的税额是3，乘上对应税率就是当前税级需要缴纳的税。更新last = 3，来到7这个税级，10 > 3所以可以按照7这个税级收税，税额是7 - 3 = 4。更新last = 7,来到12这个税级，10 > 7，但是10 < 12，所以当前税级的税额是min(10,12) - 7 = 3。

作为签到题，本题友好的设置了最后一个税级不小于income的条件，不然的话还需要判断下边界情况。

代码

class Solution {
public:
    double calculateTax(vector<vector<int>>& brackets, int income) {
        double res = 0;
        int last = 0;
        for(auto x : brackets){
            int p = x[0],q = x[1];
            if(income > last){
                int s = min(income,p);
                res += q * (s - last) / 100.0;
                last = p;
            }
            else{
                break;
            }
        }
        return res;
    }
};

2.网格中的最小路径代价 题目描述

给你一个下标从 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

分析

简单的线性DP问题，属于数字三角形模型。比较花时间的是读懂题目中moveCost这个存储着代价的二维数组的表示方法，周赛时我还花了点时间模拟用例才明白这个代价是怎么表示的。比如moveCost[1][2] = 3，就代表着值为1的单元格移动到下一行第2列单元格需要消耗的代价是3。题目的例子自然是只给出moveCost的值，其下标需要自己计算，这种存储方法还是蛮少见的。

状态表示：f[i][j]表示从第一行任意单元格出发到达(i,j)的最小代价。显然初始状态是第一行的单元格，f[0][i] = grid[0][i]，这是因为本题移动路径的代价等于移动的代价和加上经过单元格的值之和，第一行单元格不需要移动，但是代价需要加上其本身单元格的值的。
状态转移方程为：

f[i][j] = min(f[i][j],grid[i][j] + f[i-1][k] + moveCost[grid[i-1][k]][j]);

第i行的状态可以由上一行不同列的状态转移而来，求其中的代价最小值即可。

代码

class Solution {
public:
    /*f[i][j]表示到达i，j单元格的最小代价*/
    int f[55][55];
    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
        int m = grid.size();
        int n = grid[0].size();
        memset(f,0x3f,sizeof f);
        for(int i = 0;i < n;i++)    f[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++){
                    f[i][j] = min(f[i][j],grid[i][j] + f[i-1][k] + moveCost[grid[i-1][k]][j]);
                }
            }
        }
        int res = 1e9;
        for(int i = 0;i < n;i++)    res = min(res,f[m-1][i]);
        return res;
    }
};

3.公平分发饼干 题目描述

给你一个整数数组 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] <= 10⁵
  2 <= k <= cookies.length

分析

本题数据范围较小，可以使用最基本的DFS解决，也不会TLE。

void dfs(vector<int>& cookies, int u){
        if(u == cookies.size()){
            int res = 0;
            for(int i = 0;i < t;i++)    res = max(res,num[i]);
            ans = min(ans,res);
            return;
        }
        for(int i = 0;i < t;i++){
            num[i] += cookies[u];
            dfs(cookies,u+1);
            num[i] -= cookies[u];
        }
    }

dfs的边界条件是枚举完了，此时在所有分配方案里面找到获得饼干的最大值，尝试取更新最优解。一般情况下，对于当前的第u包饼干，可以由t中不同的分配方法，逐一枚举即可，逐一每次枚举完需要恢复全局数组num才能进行下一次枚举。周赛时最快的AC方法也就是直接纯暴力解决了，一共k个孩子，每每包饼干有k种分法，一共有8⁸ = 2²⁴约等于1600w种状态，还是可以承受的。

当然平时来做本题就不能满足于暴力做法了，至少也要剪枝。

首先考虑最优性剪枝，枚举完一种方案后，求出了ans的一个值，后面只有在ans更小的时候才会取更新它，而ans的值取决于每个人分配饼干的数量，所以一旦某种分配方案分配给一个人的饼干数量大于等于ans，就不需要继续枚举了。加上这个最优性剪枝的语句，dfs的效率会提高十几倍。

再来考虑优化搜索顺序，cookies里面饼干数较大的值如果先分配，前面几个分配饼干的人的饼干数量增加得更快，也更容易剪枝，所以优先分配饼干数值大的，dfs前对cookies进行从大到小的排序即可。加上搜索顺序的优化，dfs的速度可以再快上3倍。

当然还存在冗余性搜索，比如第一包饼干给第一个人，第二包饼干给第二个人的方案和第一包给第二个人，第二包给第一个人的方案对问题的解的影响是一致的，我们只关心分配的组合方案，而不关心排列顺序，排除等效冗余的确可以再大幅提升效率，比如我们固定第一包饼干只分给第一个人，因为不论给谁都是一样的。由于这题每个人可以获得多包饼干，实行记忆化搜索不好表示，所以这里的代码就不排除冗余搜索了。

再来考虑状态压缩DP的解法，周赛时写状态压缩肯定没有DFS完成的速度快，但是平时还是可以研究下的，毕竟效率更高。

我们DFS时是枚举饼干，再来考虑分配给哪个人，现在换一种枚举方式，按顺序枚举每个人，尝试给每个人分配饼干。第i个人的分配方案仅取决于前i - 1个人的分配方案，由于饼干的包数不多，所以已经分配的饼干状态可以使用状态压缩。

状态表示：f[i][j]表示给前i个人分配饼干，饼干的分配状态是j的最小不公平程度，比如f[2][3]就表示前两个人里面分配了第1,2包的饼干，因为3用二进制表
示就是11，表示前两包饼干被分配了。
状态转移：既然前i个人的分配状态是j，那么j的任一个子集都可以是第i个人的分配方案，所以我们可以枚举j的子集x，前i-1个人的分配状态就是j - x，也可
以表示为j ^ x，举个例子j = 1101，x = 0100，j ^ x = 1001,j ^ x就是x相对于j的补集了。
状态转移方程：f[i][j] = min(f[i][j],max(f[i-1][j^x],sum[x]))，也就是前i个人的分配方案的不公平程度等于前i-1个人的最优解与第i个人分配的饼干
数量中的较大者，在所有分配方案里去最小值就是f[i][j]的最优解了。
状态边界：f[0][0] = 0，其他状态INF。

现在还有两个问题需要解决，第一个问题是如何状态压缩如何枚举集合的子集。比如j = 1101时，j的子集有1100,1001.1000.0101.0100.0001这些，常用的枚举子集的代码是for(int x = j;x;x=(x-1)&j)，也就是说j与j-1相与得到第一个子集1100，相当于给j最右边的1去掉了，然后1100减去1再与j相与，得到1001，这样枚举下去枚举的顺序就是从大到小对子集的枚举顺序。详细的分析可以参考关于状压DP枚举子集的方法与理解。

第二个问题是如何快速求一种分配方案的分配饼干数，因为第i个人分配的方案是x，需要求给这个人分了多少饼干。我们可以按照1 2 4 8…的顺序去分配饼干，比如比1小的状态只有0，那么0 | 1 = 1，sum[0 | 1] = sum[0] + cookies[0]；然后看比2小的状态有0和1，sum[0 | 2] = sum[0] + cookies[1]；sum[1 | 2] = sum[1] + cookies[1]，这种状态转移方式很简单，只需要在加上第i包饼干数量时给它的状态也或上1 << i，但是状态转移的顺序还是挺难想的。

代码

DFS + 剪枝

class Solution {
public:
    int t,num[8];
    int ans = 1e9;
    void dfs(vector<int>& cookies, int u){
        if(u == cookies.size()){
            int res = 0;
            for(int i = 0;i < t;i++)    res = max(res,num[i]);
            ans = min(ans,res);
            return;
        }
        for(int i = 0;i < t;i++){
            num[i] += cookies[u];
            if(num[i] < ans)    dfs(cookies,u+1);
            num[i] -= cookies[u];
        }
    }
    int distributeCookies(vector<int>& cookies, int k) {
        t = k;
        sort(cookies.begin(),cookies.end(),[](int a,int b){return a > b;});
        dfs(cookies,0);
        return ans;
    }
};

状态压缩DP

class Solution {
public:
    int f[10][1<<8],sum[1<<8];
    int distributeCookies(vector<int>& cookies, int k) {
        int n = cookies.size();
        for(int i = 0;i < n;i++){
            int j = 1 << i;
            for(int k = 0;k < j;k++)    sum[k | j] = sum[k] + cookies[i];
        }
        memset(f,0x3f,sizeof f);
        f[0][0] = 0;
        for(int i = 1;i <= k;i++){
            for(int j = 1;j < (1 << n);j++){
                for(int x = j;x;x=(x-1)&j){
                    int t = max(f[i-1][j ^ x],sum[x]);
                    f[i][j] = min(f[i][j],t);
                }
            }
        }
        return f[k][(1<<n)-1];
    }
};

4. 公司命名 题目描述

给你一个字符串数组 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 * 10⁴
  1 <= ideas[i].length <= 10
  ideas[i] 由小写英文字母组成
  ideas 中的所有字符串 互不相同

分析

本题没有考察什么复杂的算法，但是解题逻辑还是很绕的，很容易把人绕晕，尽量简洁的分析下本题。

给定字符串序列，对于字符串序列a和b，如果交换a和b首字母后形成的两个字符串没有在字符串序列中出现过，则这两个字符串可以作为一个合法的公司名字出现，求一共有多少个合法的公司名字。暴力做法二重循环枚举的复杂度是平方级别的，计算量是2.5 * 10⁹，还是会TLE的，因此我们最多只能枚举两个字符串对中的一个字符串。

暴力做法是对每个字符串，枚举剩下的字符串，交换两个字符串的首字母，如果交换后两个字符串没有在字符串序列中出现过，就可以增加方案数了，什么办法可以快速求一个字符串序列中与某个字符串交换首字母后合法字符串的数量呢？举个例子A = “abcd”，B=“bcda”，我们交换AB的首字母后得到bbcd和acda，然后判断bbcd有没有出现过，acda有没有出现过。可以发现，对于A来说，我们只关心与它交换的首字母是什么，不管B后面的字符是什么，只要B的首字母替换掉A的首字母后的字符串没有出现过，则替换后的A就是合法的。而本题中字符串都是由小写字母构成的，最多26种，所以可以根据首字母的不同将字符串序列分为26组字符串序列：
A组：以a开头的字符串，B组：以b开头的字符串，…，Z组：以z开头的字符串。

在原字符串序列中，我们需要任取两个字符串，判断其能否构成合法的公司名。现在我们对字符串序列进行了分组，同一组字符串序列中，由于首字符相同，交换首字符后字符串不变，肯定是不能构成合法的公司名的，那么两个字符串的选取只能在两个不同组里面选了。比如在A组里面选一个字符串，B组里面选一个字符串，要想两个字符串能够构成合法的公司名，那么A组选的字符串首字符替换为b后需要没有在字符串序列里出现过，B组里面选的字符串的首字符替换为a后也需要没有在字符串序列里出现过。如果A组里有x个首字符替换为b后没有出现过的字符串，B组里有y个首字符替换为a后没有出现过的字符串，那么在A组和B组里一共能选出x * y个合法的公司名，也就是C(x,1) * C(y,1) = x * y。所以我们需要知道字符串序列里以字符c1开头替换为c2后没有在原字符串序列里出现过的字符串的数量，可以用一个26 * 26的二维数组f来存储。

根据上面的分析，我们需要统计字符串序列中以c1开头的字符串中将首字母替换为c2，使得新字符串没有出现过的字符串个数，可以遍历下字符串序列，将每个字符串首字母替换为a~z中的一个字符，统计下合法的方案数。之后在对f[i][j] * f[j][i]进行求和，就是本题的解了。

代码

class Solution {
public:
    unordered_map<string,bool> m;
    long long distinctNames(vector<string>& ideas) {
        for(auto s : ideas) m[s] = true;
        int n = ideas.size();
        int f[26][26] = {0};
        for(auto s : ideas){
            int c = s[0] - 'a';
            for(int i = 0;i < 26;i++){
                s[0] = 'a' + i;
                if(!m.count(s)) f[c][i]++;//c替换为i后的合法方案数++
            }
        }
        long long res = 0;
        for(int i = 0;i < 26;i++)
            for(int j = 0;j < 26;j++)
                res += f[i][j] * f[j][i];
        return res;
    }
};