当前位置：首页 > article >正文

LeetCode---428双周赛

article 2024/12/23 18:18:06

题目列表

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.kler.cn/a/448234.html