LeetCode---428双周赛

题目列表

3386. 按下时间最长的按钮
3387. 两天自由外汇交易后的最大货币数
3388. 统计数组中的美丽分割
3389. 使字符频率相称的最少操作次数
一、按下时间最长的按钮

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

1. class Solution {
2. public:
3.     int buttonWithLongestTime(vector<vector<int>>& events) {
4.         int n = events.size();
5.         int diff = events[0][1], idx = events[0][0];
6.         for(int i = 1; i < n; i++){
7.             int x = events[i][1] - events[i-1][1];
8.             if(x > diff || x == diff && idx > events[i][0]){
9.                 diff = x, idx = events[i][0];
10.             }
11.         }
12.         return idx;
13.     }
14. };

复制代码

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

这题题目意思比力绕，简单来说就是给你两张汇率的表，分别表示第一天和第二天中差别货币间的汇率， 然后给你一张货币，通过货币间的不停兑换，使得我们所拥有的原始货币的数目最多，可以理解为一张货币能最多变成多少张货币(此中初始的货币和末了的货币一样)。
我们可以把问题抽象成一个图，每一种货币代表一个结点，结点之间的边是有向的，边权表示一种货币到另一种货币的汇率，求到终点的路径边权乘积最大为多少。由于两天的汇率不一样，所以我们必要建两张图分别对第一题和第二天的汇率举行处置惩罚，此中我们遍历第一张图，得到初始节点到达各个结点的汇率乘积，然后让这些结点遍历第二张图，找到到达终止结点的最大汇率乘积。代码如下

1. class Solution {
2. public:
3.     double maxAmount(string initialCurrency, vector<vector<string>>& pairs1, vector<double>& rates1, vector<vector<string>>& pairs2, vector<double>& rates2) {
4.         unordered_map<string, vector<pair<string, double>>> g;
5.         for(int i = 0; i < pairs1.size(); i++){
6.             auto & e = pairs1[i];
7.             g[e[0]].emplace_back(e[1], rates1[i]);
8.             g[e[1]].emplace_back(e[0], 1/rates1[i]); // 题目允许货币进行来回转换
9.         }
10.         unordered_map<string, double> mp;
11.         auto dfs = [&](this auto && dfs, string x, string fa, double rate)->void{
12.             mp[x] = rate; // 记录到达每一种货币的汇率
13.             for(auto [y, r]: g[x]){
14.                 if(y != fa){ // 由于题目中保证不出现循环，所以我们只要不让结点走到父结点就能保证遍历完整个图
15.                     dfs(y, x, rate * r);
16.                 }
17.             }
18.         };
19.         dfs(initialCurrency, "", 1);
20.         g.clear();
21.         for(int i = 0; i < pairs2.size(); i++){
22.             auto & e = pairs2[i];
23.             g[e[0]].emplace_back(e[1], rates2[i]);
24.             g[e[1]].emplace_back(e[0], 1/rates2[i]); // 题目允许货币进行来回转换
25.         }
26.         double ans = 1;
27.         auto dfs1 = [&](this auto && dfs, string x, string fa, double rate)->void{
28.             if(x == initialCurrency){
29.                 ans = max(ans, rate);
30.                 return;
31.             }
32.             for(auto [y, r]: g[x]){
33.                 if(y != fa){ // 由于题目中保证不出现循环，所以我们只要不让结点走到父结点就能保证遍历完整个图
34.                     dfs(y, x, rate * r);
35.                 }
36.             }
37.         };
38.         for(auto [x, r] : mp){
39.             // 从每一种货币出发，计算到达初始货币的最大汇率
40.             dfs1(x, "", r);
41.         }
42.         return ans;
43.     }
44. };

复制代码

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

1. class Solution {
2. public:
3.     double maxAmount(string initialCurrency, vector<vector<string>>& pairs1, vector<double>& rates1, vector<vector<string>>& pairs2, vector<double>& rates2) {
4.         unordered_map<string, vector<pair<string, double>>> g;
5.         // 建立第一天的汇率图
6.         for(int i = 0; i < pairs1.size(); i++){
7.             auto & e = pairs1[i];
8.             g[e[0]].emplace_back(e[1], rates1[i]);
9.             g[e[1]].emplace_back(e[0], 1/rates1[i]); // 题目允许货币进行来回转换
10.         }
11.         // 将两天的汇率图进行连接
12.         for(auto [x,_]:g){
13.             g[x].emplace_back(x + "2", 1);
14.         }
15.         // 建立第二天的汇率图
16.         for(int i = 0; i < pairs2.size(); i++){
17.             auto & e = pairs2[i];
18.             g[e[0] + "2"].emplace_back(e[1] + "2", rates2[i]);
19.             g[e[1] + "2"].emplace_back(e[0] + "2", 1/rates2[i]); // 题目允许货币进行来回转换
20.         }
21.         double ans = 1;
22.         string res = initialCurrency + "2";
23.         auto dfs = [&](this auto && dfs, string x, string fa, double rate)->void{
24.             if(x == res){
25.                 ans = max(ans, rate);
26.                 return;
27.             }
28.             for(auto [y, r]: g[x]){
29.                 if(y != fa){ // 由于题目中保证不出现循环，所以我们只要不让结点走到父结点就能保证遍历完整个图
30.                     dfs(y, x, rate * r);
31.                 }
32.             }
33.         };
34.         dfs(initialCurrency, "", 1);
35.         return ans;
36.     }
37. };

复制代码

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

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

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

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

代码如下

1. class Solution {
2.     vector<int> getz(const vector<int>& nums){
3.         int n = nums.size();
4.         vector<int> z(n); z[0] = n;
5.         int l = 0, r = 0;
6.         for(int i = 1; i < n; i++){
7.             if(i <= r){
8.                 z[i] = min(r - i + 1, z[i - l]);
9.             }
10.             while(i + z[i] < n && nums[z[i]] == nums[i + z[i]])
11.                 z[i]++;
12.             if(i + z[i] - 1 > r){
13.                 l = i, r = i + z[i] - 1;
14.             }
15.         }
16.         return z;
17.     }
18. public:
19.     int beautifulSplits(vector<int>& nums) {
20.         int n = nums.size();
21.         auto z0 = getz(nums);
22.         int ans = 0;
23.         for(int i = 1; i < n - 1; i++){
24.             auto z = getz(vector<int>(nums.begin() + i, nums.end()));
25.             for(int j = i + 1; j < n; j++){
26.                 if(z0[i] >= i && i <= j - i
27.                 || z[j - i] >= j - i && j - i <= n - j){
28.                     ans++;
29.                 }
30.             }
31.         }
32.         return ans;
33.     }
34. };
37. // 也可以通过计算lcp来判断前缀关系
38. class Solution {
39. public:
40.     int beautifulSplits(vector<int>& nums) {
41.         int n = nums.size();
42.         vector<vector<int>> lcp(n + 1, vector<int>(n + 1));
43.         // lcp[i][j] 表示[i,n)的子串和[j,n)的子串的最长公共前缀
44.         // lcp[i][j] = lcp[i+1][j+1] + nums[i] == nums[j]
45.         for(int i = n - 2; i >= 0; i--){
46.             for(int j = n - 1; j > i; j--){
47.                 if(nums[i] == nums[j]){
48.                     lcp[i][j] = lcp[i+1][j+1] + 1;
49.                 }
50.             }
51.         }
52.         int ans = 0;
53.         for(int i = 1; i < n; i++){
54.             for(int j = i + 1; j < n; j++){
55.                 if(i <= j - i && lcp[0][i] >= i
56.                 || j - i <= n - j && lcp[i][j] >= j - i){
57.                     ans++;
58.                 }
59.             }
60.         }
61.         return ans;
62.     }
63. };

复制代码

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

该题是一个思维题，详细的解题思绪如下
关键性质：对一连的字符举行 操作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 个字符的频率均为 target 的最小操作次数
f = f[i+1] + min(x, abs(target - x))  不举行操作3
if(y < target) 举行操作3

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

此中 x = cnt, y = cnt[i+1]
代码如下

1. class Solution {
2. public:
3.     int makeStringGood(string s) {
4.         int n = s.size();
5.         vector<int> cnt(26);
6.         for(auto e : s) cnt[e-'a']++;
7.         int mx = ranges::max(cnt), mn = ranges::min(cnt);
8.         int ans = INT_MAX;
9.         for(int target = mn; target <= mx; target++){
10.             vector<int> f(27);
11.             f[25] = min(cnt[25], abs(target - cnt[25]));
12.             for(int i = 24; i >= 0; i--){
13.                 int x = cnt[i], y = cnt[i+1];
14.                 f[i] = f[i+1] + min(x, abs(target - x));
15.                 if(y < target){
16.                     if(x < target){
17.                         f[i] = min(f[i], f[i+2] + max(x, target - y));
18.                     }else{
19.                         f[i] = min(f[i], f[i+2] + max(x - target, target - y));
20.                     }
21.                 }
22.             }
23.             ans = min(ans, f[0]);
24.         }
25.         return ans;
26.     }
27. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。