LeetCode---428双周赛

devtools/2024/12/23 21:04:51/

题目列表

3386. 按下时间最长的按钮

3387. 两天自由外汇交易后的最大货币数

3388. 统计数组中的美丽分割

3389. 使字符频率相等的最少操作次数

一、按下时间最长的按钮

题意要求找到按钮按下时间(即与它前一次按下按钮的时间差)最大的下标,如果存在两个相同的最大按下时间,取下标小的那个,其中第一次按下按钮的时间记为它与0的时间差。直接模拟即可,代码如下

class Solution {
public:int buttonWithLongestTime(vector<vector<int>>& events) {int n = events.size();int diff = events[0][1], idx = events[0][0];for(int i = 1; i < n; i++){int x = events[i][1] - events[i-1][1];if(x > diff || x == diff && idx > events[i][0]){diff = x, idx = events[i][0];}}return idx;}
};

二、两天自由外汇交易后的最大货币数量

这题题目意思比较绕,简单来说就是给你两张汇率的表,分别表示第一天和第二天中不同货币间的汇率, 然后给你一张货币,通过货币间的不断兑换,使得我们所拥有的原始货币的数量最多,可以理解为一张货币能最多变成多少张货币(其中初始的货币和最后的货币一样)。

我们可以把问题抽象成一个图,每一种货币代表一个结点,结点之间的边是有向的,边权表示一种货币到另一种货币的汇率,求到终点的路径边权乘积最大为多少。由于两天的汇率不一样,所以我们需要建两张图分别对第一题和第二天的汇率进行处理,其中我们遍历第一张图,得到初始节点到达各个结点的汇率乘积,然后让这些结点遍历第二张图,找到到达终止结点的最大汇率乘积。代码如下

class Solution {
public:double maxAmount(string initialCurrency, vector<vector<string>>& pairs1, vector<double>& rates1, vector<vector<string>>& pairs2, vector<double>& rates2) {unordered_map<string, vector<pair<string, double>>> g;for(int i = 0; i < pairs1.size(); i++){auto & e = pairs1[i];g[e[0]].emplace_back(e[1], rates1[i]);g[e[1]].emplace_back(e[0], 1/rates1[i]); // 题目允许货币进行来回转换}unordered_map<string, double> mp;auto dfs = [&](this auto && dfs, string x, string fa, double rate)->void{mp[x] = rate; // 记录到达每一种货币的汇率for(auto [y, r]: g[x]){if(y != fa){ // 由于题目中保证不出现循环,所以我们只要不让结点走到父结点就能保证遍历完整个图dfs(y, x, rate * r);}}};dfs(initialCurrency, "", 1);g.clear();for(int i = 0; i < pairs2.size(); i++){auto & e = pairs2[i];g[e[0]].emplace_back(e[1], rates2[i]);g[e[1]].emplace_back(e[0], 1/rates2[i]); // 题目允许货币进行来回转换}double ans = 1;auto dfs1 = [&](this auto && dfs, string x, string fa, double rate)->void{if(x == initialCurrency){ans = max(ans, rate);return;}for(auto [y, r]: g[x]){if(y != fa){ // 由于题目中保证不出现循环,所以我们只要不让结点走到父结点就能保证遍历完整个图dfs(y, x, rate * r);}}};for(auto [x, r] : mp){// 从每一种货币出发,计算到达初始货币的最大汇率dfs1(x, "", r);}return ans;}
};

当然,我们也可以通过建立分层图,来实现一次dfs遍历,就计算出答案。假设有三种货币为A、B、C,其中A 为 初始货币,则我们可以对A1,B1、C1进行建图,表示第一天的汇率变化情况,用A2、B2、C2建图表示第二天的汇率变化,我们只要额外添加A1->A2,B1->B2,C1->C2这三条边权为1的边,就能通过求A1->A2的边权乘积最大的值,找到答案。这种建图的方式就跟一栋楼的上下层一样,故称为分层图,代码如下

class Solution {
public:double maxAmount(string initialCurrency, vector<vector<string>>& pairs1, vector<double>& rates1, vector<vector<string>>& pairs2, vector<double>& rates2) {unordered_map<string, vector<pair<string, double>>> g;// 建立第一天的汇率图for(int i = 0; i < pairs1.size(); i++){auto & e = pairs1[i];g[e[0]].emplace_back(e[1], rates1[i]);g[e[1]].emplace_back(e[0], 1/rates1[i]); // 题目允许货币进行来回转换}// 将两天的汇率图进行连接for(auto [x,_]:g){g[x].emplace_back(x + "2", 1);}// 建立第二天的汇率图for(int i = 0; i < pairs2.size(); i++){auto & e = pairs2[i];g[e[0] + "2"].emplace_back(e[1] + "2", rates2[i]);g[e[1] + "2"].emplace_back(e[0] + "2", 1/rates2[i]); // 题目允许货币进行来回转换}double ans = 1;string res = initialCurrency + "2";auto dfs = [&](this auto && dfs, string x, string fa, double rate)->void{if(x == res){ans = max(ans, rate);return;}for(auto [y, r]: g[x]){if(y != fa){ // 由于题目中保证不出现循环,所以我们只要不让结点走到父结点就能保证遍历完整个图dfs(y, x, rate * r);}}};dfs(initialCurrency, "", 1);return ans;}
};

三、统计数组中的美丽分割

看到判断前缀,很容易想到扩展KMP算法(又叫Z函数算法)。对于给定的字符串,会得到一个z数组,z[i] 表示从 i 往后的字符串与原字符串的最长公共前缀长度。下面是z函数的详细计算过程

假设我们将数组分为 [0,i)[i,j)[j,n) 三部分

  • 如果 [0,i)是 [i,j)的前缀,则 i <= j - i (保证长度符合条件) 并且 z[i] >= i (保证满足前缀关系)
  • 如果 [i,j)是 [j,n) 的前缀,则 j - i <= n - j (保证长度符合条件) 并且 z[j] >= j - i (保证满足前缀关系)

代码如下

class Solution {vector<int> getz(const vector<int>& nums){int n = nums.size();vector<int> z(n); z[0] = n;int l = 0, r = 0;for(int i = 1; i < n; i++){if(i <= r){z[i] = min(r - i + 1, z[i - l]);}while(i + z[i] < n && nums[z[i]] == nums[i + z[i]])z[i]++;if(i + z[i] - 1 > r){l = i, r = i + z[i] - 1;}}return z;}
public:int beautifulSplits(vector<int>& nums) {int n = nums.size();auto z0 = getz(nums);int ans = 0;for(int i = 1; i < n - 1; i++){auto z = getz(vector<int>(nums.begin() + i, nums.end()));for(int j = i + 1; j < n; j++){if(z0[i] >= i && i <= j - i || z[j - i] >= j - i && j - i <= n - j){ans++;}}}return ans;}
};// 也可以通过计算lcp来判断前缀关系
class Solution {
public:int beautifulSplits(vector<int>& nums) {int n = nums.size();vector<vector<int>> lcp(n + 1, vector<int>(n + 1));// lcp[i][j] 表示[i,n)的子串和[j,n)的子串的最长公共前缀// lcp[i][j] = lcp[i+1][j+1] + nums[i] == nums[j] for(int i = n - 2; i >= 0; i--){for(int j = n - 1; j > i; j--){if(nums[i] == nums[j]){lcp[i][j] = lcp[i+1][j+1] + 1;}}}int ans = 0;for(int i = 1; i < n; i++){for(int j = i + 1; j < n; j++){if(i <= j - i && lcp[0][i] >= i || j - i <= n - j && lcp[i][j] >= j - i){ans++;}}}return ans;}
};

四、使字符频率相等的最少操作次数

该题是一个思维题,具体的解题思路如下

关键性质:对连续的字符进行 操作3 只会让首尾两个字符的出现频率有-1 和 +1 的效果,不如直接用 2 次增/删 操作操作3 只有当相邻元素需要一减一加时,才能让操作次数变少

枚举频率 target,找最小的操作次数,则对于一个字符,它的频率要么变为 0,要么变为 target(因为我们很难贪心地确定哪一个频率是操作次数最少的频率,且它不具有单调性,也不能进行二分,同时数据范围也在一定范围内,所以我们考虑枚举频率,算操作次数)

如果一个字符 ? 的出现频率为 x,有如下情况

1、只进行前两个操作,则需要 min(x, abs(target - x)) 次操作

2、需要进行 操作3 【根据性质,只考虑相邻的字符即可】

如果 ?+1 的出现频率为 y

1) target <= y 只能进行前两个操作,因为进行一次操作3,就必然需要一次操作1使得 ?+1 恢复原来的频率,得不偿失

2) target > y

    如果 x < target,让 x = 0,则操作次数为 max(x, target - y)

    如果 x >= target,让 x = target,则操作次数为 max(x - target, target - y)

此外我们还需要知道哪些数字需要进行操作3,而对于字符 ? 的操作,只和 ? + 1 字符的频率有关,且根据性质我们知道操作3 不能连续使用,类似打家劫舍的一种,可以用 dp 求解

设 f[i] 表示 后 i 个字符的频率均为 target 的最小操作次数

f[i] = f[i+1] + min(x, abs(target - x))  不进行操作3

if(y < target) 进行操作3

  •     if(x < target) f[i] = min(f[i], f[i+2] + max(x, target - y));
  •     if(x >= target) f[i] = min(f[i], f[i+2] + max(x - target, target - y));

其中 x = cnt[i], y = cnt[i+1]

代码如下

class Solution {
public:int makeStringGood(string s) {int n = s.size();vector<int> cnt(26);for(auto e : s) cnt[e-'a']++; int mx = ranges::max(cnt), mn = ranges::min(cnt);int ans = INT_MAX;for(int target = mn; target <= mx; target++){vector<int> f(27);f[25] = min(cnt[25], abs(target - cnt[25]));for(int i = 24; i >= 0; i--){int x = cnt[i], y = cnt[i+1];f[i] = f[i+1] + min(x, abs(target - x));if(y < target){if(x < target){f[i] = min(f[i], f[i+2] + max(x, target - y));}else{f[i] = min(f[i], f[i+2] + max(x - target, target - y));}}}ans = min(ans, f[0]);}return ans;}
};

http://www.ppmy.cn/devtools/144792.html

相关文章

【C语言1】C语言常见概念(总结复习篇)——库函数、ASCII码、转义字符

文章目录 前言一、C语言是什么&#xff1f;二、编译器的选择——VS2022三、main函数四、printf函数五、库函数六、关键字七、字符和ASCII编码八、字符串和\0九、转义字符十、注释总结 前言 上周考完四级(明年再战hh)和两门考试&#xff0c;接下来一个月将迎来其他学科的期末考…

Mac/Linux 快速部署TiDB

1.下载TiUP TiDB 是一个分布式系统。最基础的 TiDB 测试集群通常由 2 个 TiDB 实例、3 个 TiKV 实例、3 个 PD 实例和可选的 TiFlash 实例构成。通过 TiUP Playground&#xff0c;可以快速搭建出上述的一套基础测试集群&#xff0c;步骤如下&#xff1a; curl --proto https -…

C语言:排序

1. 插入排序 (Insertion Sort) 插入排序是一种简单直观的排序算法&#xff0c;它的工作原理类似于整理扑克牌。它的基本思想是将数组分为已排序部分和未排序部分&#xff0c;每次从未排序部分取出一个元素&#xff0c;插入到已排序部分的合适位置。 步骤&#xff1a; 从数组…

《机器学习》第四章信息熵 信息增益率决策树怎么写

信息熵 信息熵是信息论中用来度量信息含量不确定性的一种指标。简单来说&#xff0c;熵越大&#xff0c;表示信息的不确定性越高&#xff0c;信息量越大&#xff1b;熵越小&#xff0c;表示信息的不确定性越低&#xff0c;信息量越小。 所以&#xff0c;信息熵是大好还是小好…

【Lua热更新】下篇

上篇链接&#xff1a;【Lua热更新】上篇 文章目录 三、xLua热更新&#x1f4d6;1.概述&#x1f4da;︎2.导入xLua框架&#x1f516;3. C#调用Lua3.1Lua解析器3.2Lua文件夹的重定向3.3Lua解析器管理器3.4全局变量获取3.5全局函数获取3.6映射到List和Dictionary3.7映射到类3.8映…

如何在谷歌浏览器中开启安全浏览

在数字化时代&#xff0c;网络安全变得愈发重要。作为全球最受欢迎的网络浏览器之一&#xff0c;谷歌浏览器提供了多种功能来保护用户的在线安全。本文将详细介绍如何在谷歌浏览器中开启安全浏览&#xff0c;并额外提供一些有用的页面滚动设置、地址栏快捷搜索和跟踪防护的相关…

中宇联与亚马逊云科技共同推出Well-Architected联合解决方案

数字化转型正如火如荼地进行&#xff0c;云计算已逐渐成为企业发展的核心动力。亚马逊云科技积极承担起数字经济时代基础设施提供者及企业成长的高质量伙伴角色&#xff0c;全心全意深化客户服务&#xff0c;赋能企业迈向成功之路。基于多年服务各行各业客户的经验总结&#xf…

JAVA没有搞头了吗?

前言 今年的Java程序员群体似乎承受着前所未有的焦虑。投递简历无人问津&#xff0c;难得的面试机会也难以把握&#xff0c;即便成功入职&#xff0c;也往往难以长久。于是&#xff0c;不少程序员感叹&#xff1a;互联网的寒冬似乎又一次卷土重来&#xff0c;环境如此恶劣&…