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 。
示例 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 。
解题，就是简单的模拟，并没有太多的技巧。主要训练思维逻辑
- 如果没有超过uper,那么剩余部分按照该汇率
- 如果超过，超过部分另算，中间区间部分按照该汇率
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;
}
};
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 。
示例 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 。
这个个选择问题：
首先暴力解法，就不不断的选择，然后选取最小的结果，当然可以剪枝。
我们可以自底向上，也就是动态规划
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;
}
};
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 的分发方案。
示例 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 的分发方案。
解法： 暴力加剪枝，就是通过不断的分配求解出所有的组合，在选出最优组合
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);
}
};
2306. 公司命名
难度困难29收藏分享切换为英文接收动态反馈
给你一个字符串数组 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 。
关键是这样的。
设置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;
}
};