2022 第297周周赛

2303. 计算应缴税款总额

难度简单5收藏分享切换为英文接收动态反馈

给你一个下标从 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 。
1
2
3
4
5
6
7

示例 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 。
1
2
3
4
5
6

示例 3：

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

解题，就是简单的模拟，并没有太多的技巧。主要训练思维逻辑

1. 如果没有超过uper,那么剩余部分按照该汇率
2. 如果超过，超过部分另算，中间区间部分按照该汇率

class Solution {
public:
    double calculateTax(vector<vector<int>>& brackets, int income) {
        double res = 0;
        int remain = income;
        for(int i=0;i<brackets.size();i++) {
            int uper = brackets[i][0];
            int percentage = brackets[i][1];

            if(income >= uper) {
                if(i==0) {
                    res += (uper*percentage)/100.0;
                    remain -= uper;
                } else {
                    res += (uper - brackets[i-1][0])*percentage/100.0;
                    remain -= uper-brackets[i-1][0];
                }
            } else {
                res += remain*percentage/100.0;
                break;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

难度中等12收藏分享切换为英文接收动态反馈

给你一个下标从 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 。
1
2
3
4
5
6
7

示例 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 。
1
2
3
4
5
6
7

这个个选择问题：

首先暴力解法，就不不断的选择，然后选取最小的结果，当然可以剪枝。

我们可以自底向上，也就是动态规划

dp[i][j]表示到达 （i，j）的最小代价，之后就可以根据这个含义去进行递推

class Solution {
public:
    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
        // 动态规划 dp[i][j] 代表到达i，j位置的最小代价
        vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size() , 0));
        for(int i=0; i<grid[0].size();i++) {
            dp[0][i] = grid[0][i];
        }

        for(int i=1; i<grid.size();i++) {
            for(int j=0; j<grid[0].size(); j++) {
                for(int k=0; k<grid[0].size(); k++) {
                    int lastVal = grid[i-1][k];
                    int nowVal = grid[i][j];
                    int cost = dp[i-1][k] + moveCost[lastVal][j] + nowVal;
                    dp[i][j] = dp[i][j] == 0 ? cost : min(dp[i][j], cost);
                }
            }
        }

        int minVal = dp[grid.size()-1][0];
        for(int i=0;i<grid[0].size();i++) {
            minVal = min(minVal, dp[grid.size()-1][i]);
        }
        return minVal;
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2305. 公平分发饼干

难度中等25收藏分享切换为英文接收动态反馈

给你一个整数数组 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 的分发方案。
1
2
3
4
5
6
7

示例 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 的分发方案。
1
2
3
4
5
6
7
8

解法： 暴力加剪枝，就是通过不断的分配求解出所有的组合，在选出最优组合

class Solution {
public:
    // 分发饼干
    // 1. 所有零食包必须分发，同一个零食包中的所有饼干只能发给一个好走 
    // 返回最小的不公平程度，其实就是两包尽可能的平均
    // 其实也可以变为一个背包问题
    int minVal = INT_MAX;

    int distributeCookies(vector<int>& cookies, int k) {
        queue<int> que;
        for(auto v : cookies) {
            que.push(v);
        }   
        vector<int> money(k,0);
        backtrack(money,que);
        return minVal;
    }

    void backtrack(vector<int>& money, queue<int>& cookies) {
        if(cookies.empty()) {
            int val = *max_element(money.begin(),money.end());
            minVal = min(val, minVal);
            return;
        }

        int v = cookies.front();
        cookies.pop();
        for(int i=0; i< money.size();i++) {
            money[i] += v;
            if(money[i] > minVal) {
                money[i] -= v;
                continue;
            }
            backtrack(money,cookies);
            money[i] -= v;
        }
        cookies.push(v);

    } 
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

2306. 公司命名

难度困难29收藏分享切换为英文接收动态反馈

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

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

返回 不同 且有效的公司名字的数目。

示例 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")：在原数组中存在交换后形成的两个名字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

示例 2：

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

关键是这样的。

设置pre[i][j] 代表的含义就是，将首字母i变为j后不在队列中的idea个数

这时候就知道，如果pre[j][i] 代表的是将首字母从j变成i后不在队列的idea的个数

含义就是 axx 与 bxxx相互交换首字母后都不在队列里面。

using ll = long long;

class Solution {
public:
    long long distinctNames(vector<string>& ideas) {
        unordered_set<string> s(ideas.begin(), ideas.end());
        vector<vector<ll>> cnt(26, vector<ll>(26));

        for(string& is : ideas){
            int pre = is[0] - 'a';
            for(int i = 0; i < 26; ++i){
                is[0] = (i + 'a');
                if(!s.count(is)) cnt[pre][i]++;
            }
        }

        ll ans = 0;
        for(int i = 0; i < 26; ++i){
            for(int j = 0; j < 26; ++j) ans += cnt[i][j] * cnt[j][i];
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24