leetcode-weekly-contest-297

刷题

发布日期: 2022-06-12

Problem List

[1] 计算应缴税款总额
[2] 网格中的最小路径代价
[3] 公平分发饼干
[4] 公司命名

1. 计算应缴税款总额

1.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 表示你的总收入。返回你需要缴纳的税款总额。与标准答案误差不超 10e-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.2 思路

直接模拟即可。

class Solution {
public:
    double calculateTax(vector<vector<int>>& brackets, int income) {
        double ans = 0;
        for(int i = 0; i < brackets.size(); ++i){
            if(income >= brackets[i][0]){
                if(i == 0){
                    ans += 1.0*brackets[i][0]*brackets[i][1];
                }else{
                    ans += (1.0*brackets[i][0]-brackets[i-1][0])*brackets[i][1];
                }
            }else{
                if(i == 0){
                    ans += 1.0*income*brackets[i][1];
                }else{
                    ans += (1.0*income-brackets[i-1][0])*brackets[i][1];
                }
                break;
            }
        }
        return ans / 100;
    }
};

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

2.1 题目描述

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

2.2 思路

动态规划，创建dp[][]数组, 其中dp[i][j]表示到达第i行第j列所需要的路径代价，由于本题求的是最小路径代价，而路径代价为经过的单元格上的值以及单元格之间移动时的代价之和，因而可以初始化dp[0][i]=grid[0][i],即到达第0行第i列的代价为单元格的值。然后遍历行和列，dp[i][j]的更新应该为从上一行到当前行当前列中代价最小的那一个，那么容易得到更新公式为：

$dp[i][j] = \max\limits_{0\le k < n}(dp[i-1][k]+grid[i][j]+moveCost[grid[i-1][k]][j])$

class Solution {
public:
    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
        int m = grid.size(), n = grid[0].size();
        int dp[m][n];
        memset(dp, 1, sizeof(dp));
        int ans = INT_MAX;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; ++j){
                if(i > 0){
                    for(int k = 0; k < n; ++k){ // 上一层
                        dp[i][j] = min(dp[i][j], dp[i-1][k] + grid[i][j] + moveCost[grid[i-1][k]][j]);
                    }
                    continue;
                } 
                dp[i][j] = grid[i][j];
            }
        }
        for(int i = 0; i < n; ++i){
            ans = min(ans, dp[m-1][i]);
        }
        return ans;
    }
};

3. 公平分发饼干

3.1 题目描述

给你一个整数数组 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

3.2 思路

由于题目中cookies.length()和k较小，因而可以直接进行进行回溯求解，最差的情况下时间复杂度为$8^8$.

class Solution {
    int kk, n, ans;;
    vector<int> tmp;
    void dfs(vector<int>& cookies, int index){
        if(index == n){
            int max = INT_MIN;
            for(int i = 0; i < kk; ++i){
                max = std::max(max, tmp[i]);
            }
            ans = min(max, ans);
            return;
        }
        for(int i = 0; i < kk; ++i){
            tmp[i] += cookies[index];
            dfs(cookies, index+1);
            tmp[i] -= cookies[index];
        }
    }
public:
    int distributeCookies(vector<int>& cookies, int k) {
        kk= k, n = cookies.size(), ans = INT_MAX;
        tmp = vector<int>(k, 0);
        dfs(cookies, 0);
        return ans;
    }
};

4. 公司命名

4.1 题目描述

给你一个字符串数组 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 。

4.2 思路

按首字母进行分组

通过首字母分组，对于不同的两个分组，当左分组中的字符串在右分组中出现了，那么这个字符串不能用来和右分组的进行交换构成有效方案，因而可以转变为求不同组之间的交集数m，从而两个组间的有效方案数为:

$2*(left.size() - m)*(right.size()-m)$

class Solution {
public:
    long long distinctNames(vector<string>& ideas) {
        unordered_set<string> s[26];
        for(string idea: ideas){
            s[idea[0] - 'a'].insert(idea.substr(1));    // 按首字母进行分组
        }
        long long ans = 0;
        for(int i = 1; i < 26; ++i){
            for(int j = 0; j < i; ++j){
                int m = 0;
                for(auto it: s[i]){
                    m += s[j].count(it);    // 计算两个组的交集数
                }
                ans += (1LL * s[i].size() - m) * (s[j].size() - m);
            }
        }
        return ans*2;
    }
};

按除去首字母外的字符串分组

以首字母称为前缀，以剩余字符串称为后缀。由于ideas中的字符串都是不同的，因而不存在前缀后缀均一致的字符串。通过对后缀进行分组，其组中元素至多有26个元素，因而可以采用一个数组来存放前缀，或者用一个整数来存放(位运算)。那么如何求有效方案数呢？考虑两个组的有效方案，左分组中的字符在右分组中未出现，则该字符可以和右分组的成员匹配，同样的，右分组中的字符如果在左分组中为出现则可以与左分组成员匹配。即必须在存在i不存在j的时候、或者不存在i而存在j的时候才可以算作有效分组。进一步，用一个数组cnt[26][26], 我们对分完组的组别进行遍历，遍历26个字母，看当前遍历到的组别中含有什么字母，如果包含某个字母i，则将cnt[i][j]加到答案中，否则则更新cnt[i][j].(即有i就把没i的加上，没i就等有i的来).

cnt[i][j]的意义为不存在字符i而存在字符j的字符串数量.

class Solution {
public:
    long long distinctNames(vector<string>& ideas) {
        map<string, int> m;
        for(string idea: ideas){
            m[idea.substr(1)] |= (1 << (idea[0]-'a'));
        }
        int cnt[26][26] = {0};
        long long ans = 0;
        for(auto it: m){
            int mask = it.second;
            for(int i = 0; i < 26; ++i){
                if(((mask>>i)&1) == 0){
                    for(int j= 0; j < 26; ++j){
                        if((mask>>j)&1){
                            ++cnt[i][j];
                        }
                    }
                }else{
                    for(int j= 0; j < 26; ++j){
                        if(((mask>>j)&1) == 0){
                            ans += cnt[i][j];
                        }
                    }
                }
            }
        }
        return ans * 2;
    }
};