IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 2022 第297周周赛 -> 正文阅读

[数据结构与算法]2022 第297周周赛

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 。

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

  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;
    }
};

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

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

给你一个下标从 0 开始的整数矩阵 grid ,矩阵大小为 m x n ,由从 0m * 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:

img

输入: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 表示在公司命名过程中使用的名字列表。公司命名流程如下:

  1. ideas 中选择 2 个 不同 名字,称为 ideaAideaB
  2. 交换 ideaAideaB 的首字母。
  3. 如果得到的两个新名字 不在 ideas 中,那么 ideaA ideaB串联 ideaAideaB ,中间用一个空格分隔)是一个有效的公司名字。
  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"):在原数组中存在交换后形成的两个名字。

示例 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;
    }
};
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-06-29 19:19:22  更:2022-06-29 19:22:39 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 5:20:09-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码