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

Leetcode - 周赛428

article 2024/12/24 0:45:32

目录

一，3386. 按下时间最长的按钮

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

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

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

一，3386. 按下时间最长的按钮

本题就是求最短的时间间隔下的indexi，如果时间间隔相同，返回最小的indexi。

代码如下：

class Solution {
    public int buttonWithLongestTime(int[][] events) {
        int pre = 0;
        int ans = 0;
        int idx = -1;
        for(int[] e : events){
            int t = e[1] - pre;
            if(ans == t && e[0] < idx || ans < t){
                ans = t;
                idx = e[0];
            }
            pre = e[1];
        }
        return idx;
    }
}

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

本题实际上是一个图论题，这里介绍两种做法：

  • 双层图：直接建立一个图计算一次dfs，画个图理解一下：

class Solution {
    Map<String, List<Data>> map = new HashMap<>();
    String initial;
    double ans = 1.0;
    public record Data(String key, double val){}
    public double maxAmount(String initialCurrency, List<List<String>> pairs1, double[] rates1, List<List<String>> pairs2, double[] rates2) {
        //图一的双向边
        for(int i=0; i<rates1.length; i++){
            List<String> x = pairs1.get(i);
            String a = x.get(0), b = x.get(1);
            map.computeIfAbsent(a, e -> new ArrayList<Data>()).add(new Data(b, rates1[i]));
            map.computeIfAbsent(b, e -> new ArrayList<Data>()).add(new Data(a, 1/rates1[i]));
        }
        //连单向边
        for(String a : map.keySet()){
            map.computeIfAbsent(a, e -> new ArrayList<Data>()).add(new Data(a+"2", 1.0));
        }
        //图二的双向边
        for(int i=0; i<rates2.length; i++){
            List<String> x = pairs2.get(i);
            String a = x.get(0)+"2", b = x.get(1)+"2";
            map.computeIfAbsent(a, e->new ArrayList<>()).add(new Data(b, rates2[i]));
            map.computeIfAbsent(b, e -> new ArrayList<Data>()).add(new Data(a, 1/rates2[i]));
        }
        //终点 = initialCurrency+"2"
        initial = initialCurrency+"2";
        dfs(initialCurrency, "-1", 1.0);
        return ans;
    }
    void dfs(String x, String fa, double s){
        if(x.equals(initial)){
            ans = Math.max(ans, s);
            return;
        }
        for(Data y : map.getOrDefault(x, new ArrayList<Data>())){
            if(!y.key().equals(fa)){
                dfs(y.key(), x, s*y.val());
            }
        }
    }
}
  • Floyd算法：建立两个图，相当于dfs两次，分别计算第一天货币之间的最大汇率（f1[x][y]）和第二天货币之间的最大汇率（f2[x][y]），枚举第一天和第二天交接的货币i，要计算从initialCurrency(简写 t ) 经过转换之后的最大汇率，就是计算max(f1[t][i] * f2[i][t])

代码如下：

class Solution {
    public double maxAmount(String initialCurrency, List<List<String>> pairs1, double[] rates1, List<List<String>> pairs2, double[] rates2) {
        Map<String, Integer> map = new HashMap<>();
        int k = 0;
        for(List<String> x : pairs1){
            String a = x.get(0), b = x.get(1);
            if(!map.containsKey(a)) map.put(a, k++);
            if(!map.containsKey(b)) map.put(b, k++);
        }
        for(List<String> x : pairs2){
            String a = x.get(0), b = x.get(1);
            if(!map.containsKey(a)) map.put(a, k++);
            if(!map.containsKey(b)) map.put(b, k++);
        }
        double[][] f1 = new double[k][k];
        for(int i=0; i<rates1.length; i++){
            String a = pairs1.get(i).get(0), b = pairs1.get(i).get(1);
            int x = map.get(a), y = map.get(b);
            f1[x][y] = rates1[i];
            f1[y][x] = 1/rates1[i];
        }
        for(int a=0; a<k; a++){
            for(int x=0; x<k; x++){
                for(int y=0; y<k; y++){
                    if(x!=y && x!=a && y!=a){
                        f1[x][y] = Math.max(f1[x][a] * f1[a][y], f1[x][y]);
                    }
                }
            }
        }
        int t = map.getOrDefault(initialCurrency, -1);
        if(t == -1) return 1.0;
        double[][] f2 = new double[k][k];
        for(int i=0; i<rates2.length; i++){
            String a = pairs2.get(i).get(0), b = pairs2.get(i).get(1);
            int x = map.get(a), y = map.get(b);
            f2[x][y] = rates2[i];
            f2[y][x] = 1/rates2[i];
        }
        for(int a=0; a<k; a++){
            for(int x=0; x<k; x++){
                for(int y=0; y<k; y++){
                    if(x!=y && x!=a && y!=a){
                        f2[x][y] = Math.max(f2[x][a] * f2[a][y], f2[x][y]);
                    }
                }
            }
        }
        double ans = 1.0;
        for(int i=0; i<k; i++){
            ans = Math.max(ans, f1[t][i] * f2[i][t]);
        }
        return ans;
    }
}

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

本题判断前前缀是否相同，直接联想到 z函数算法（z[i] = s[:] 和 s[i:] 的最长前缀），由于数据范围较小，可以直接枚举 nums1 和 nums2，nums2 和 nums3 之间的分割点 i，j

  • nums1 的范围是 [0，i)
  • nums2 的范围是 [i，j)
  • nums3 的范围是 [j，n)

按照题目要求，如果nums1是nums2的前缀或者nums2是nums3的前缀，那么它就满足条件，接下来就是如何使用 z函数来判断 x 是否是 y 的前缀（都有一个大前提 y.length > x.length）。

  • 对于 nums1 和 nums2 来说，z[i] >= i，z[i] 表示 nums[i:] 和 nums 的最长前缀是 nums[0: z[i]]，如果 z[i] < i，说明 nums[0:z[i]] 是 nums[i:]的最长前缀，不满足nums1是nums2的前缀这一条件。（i >= j-i && z[i] >= i）
  • 对于nums2和nums3来说，这里计算z函数它的范围是nums[j:]，和上述一模一样的推理，这里不详写了，结论 n-j >= j-i && z[j-i] >= j-i

代码如下：

class Solution {
    //z函数-前前缀的最长长度
    int[] zBox(int[] nums){
        int n = nums.length;
        int[] z = new int[n];
        int l = 0, r = 0;
        for(int i=1; i<n; i++){
            z[i] = i < r ? Math.min(z[i-l], r-i) : 0;
            while(i+z[i] < n && nums[z[i]] == nums[i+z[i]]){
                z[i]++;
            }
            if(i + z[i] > r){
                l = i;
                r = i + z[i];
            }
        }
        return z;
    }
    public int beautifulSplits(int[] nums) {
        int n = nums.length;
        int ans = 0;
        int[] z0 = zBox(nums);
        for(int i=1; i<n; i++){
            //Arrays.copyOfRange(数组,l,r) -> [l,r)
            int[] z1 = zBox(Arrays.copyOfRange(nums, i, n));
            for(int j=i+1; j<n; j++){
                if(i<=j-i && z0[i] >= i || j-i<=n-j && z1[j-i] >= j-i){
                    ans++;
                }
            }
        }
        return ans;
    }
}

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

本题是一个分类讨论的题，先区分三种操作，（cnt 数组统计每个字符出现次数）：

  • 操作一：删除一个字符，cnt[i]--
  • 操作二：添加一个字符，cnt[i]++
  • 操作三：将一个字符转换成字母表中的下一个字符，cnt[i]-- && cnt[i]++，注：'z' 不能到 'a'

根据上述条件，得到一下结论：

  • 操作三 = 操作二 + 操作一，如果在满足一定的条件下，尽可能使用操作三
  • 操作三不能连续使用，比如 'a' -> 'b' -> 'c' -> ... -> 'z'，实际效果就是cnt['a']--，cnt['z']++，只需要执行2次，使用操作三，也是要执行25次。不能连续执行操作三，可以联想到打家劫舍，也就是说本题可能使用DP

求将 s 变好的最少操作次数，对于26个字符来说，要么 cnt[i] = 0，要么 cnt[i] = target（target表示最终每个字符出现次数），假设 x，y 是相邻的两个字母，分类讨论：

  • 对 x/y 单独执行操作：1. cnt[x] -> target，需要 abs(cnt[x]-target) 次操作；2. cnt[x] -> 0，需要 cnt[x] 次操作一。
  • cnt[y] >= target 时，由于使用操作三会使得 cnt[y] 变大，需要额外执行多次操作一将 cnt[y] -> target/0，明显使得操作次数增多，不能使用操作三
  • 如果 cnt[y] < target， 有两种情况
  1. cnt[x] >= target，可以将 cnt[x]、cnt[y] 都变成 target，需要 max(cnt[x]-target，target - cnt[y])
  2. cnt[x] < target，可以将 cnt[x] 变成 0、cnt[y] 变成 target，需要 max(cnt[x]，target - cnt[y])

这里画了cnt[x] >= target 的两种情况，cnt[x] < target 的两种情况与之类似，可以自己画一画：

得出上述结论后，就可以使用DP计算了，枚举target的值，定义 f[i]: [i，25]的字母出现次数变成target 所需要的操作次数。

  • 对字母 i 进行单独操作，f[i] = f[i+1] + min(abs(cnt[i] - target), cnt[i])
  • cnt[i+1] < target，可以执行操作三：
  • 1. cnt[i] >= target，f[i] = min(f[i]，f[i+2] + max(cnt[x]-target，target - cnt[y]))
  • 2. cnt[i] < target，f[i] = min(f[i]，f[i+2] + max(cnt[x]，target - cnt[y]))

代码如下:

class Solution {
    //枚举 target
    //对 x 单个字符进行操作:
    //  cnt[x] -> target, abs(cnt[x]-target)
    //  cnt[x] -> 0,      abs(cnt[x])
    //对 x,y 相邻字符进行操作(x < y, cnt[y] < target):
    //  a->b->c->...不能连续使用3
    public int makeStringGood(String s) {
        int[] cnt = new int[26];
        int mx = 0;
        //统计每个字符出现次数 cnt
        for(char c : s.toCharArray()){
            cnt[c-'a']++;
            mx = Math.max(mx, cnt[c-'a']);
        }
        int ans = Integer.MAX_VALUE;
        int[] f = new int[27];
        //枚举 target
        for(int t=0; t<=mx; t++){
            f[25] = Math.min(cnt[25], Math.abs(cnt[25]-t));
            for(int i=24; i>=0; i--){
                int x = cnt[i];
                int y = cnt[i+1];
                f[i] = f[i+1] + Math.min(x, Math.abs(x-t));
                if(y < t){
                    if(x >= t)
                        f[i] = Math.min(f[i], f[i+2]+Math.max(x-t,t-y));
                    else
                        f[i] = Math.min(f[i], f[i+2]+Math.max(x,t-y));
                }
            }
            ans = Math.min(ans, f[0]);
        }
        return ans;
    }
}


http://www.kler.cn/a/448612.html

相关文章：

  • Promise链式调用
  • 探索 Seaborn Palette 的奥秘：为数据可视化增色添彩
  • Mysql复习（二）
  • 【Lua热更新】上篇
  • 数据结构漫游记：初识vector
  • go-zero负载均衡实现原理
  • React性能分析: 使用React Profiler工具
  • 【Java基础面试题027】Java的StringBuilder是怎么实现的？
  • Redis篇--常见问题篇7--缓存一致性2（分布式事务框架Seata）
  • QtitanChart组件——高效、灵活的Qt数据可视化解决方案
  • 项目搭建+姓名唯一性校验
  • CTF入门：以Hackademic-RTB1靶场为例初识夺旗
  • JavaIO 在 Android 中的应用
  • 基于三维先验知识的自监督医学图像分割方法
  • 在福昕(pdf)阅读器中导航到上次阅读页面的方法
  • vue3和element-plus笔记
  • 【刷题23】多源BFS
  • MFC/C++学习系列之简单记录——序列化机制
  • 《机器学习》支持向量机
  • Docker日志与监控
  • Maven的介绍以及安装，仓库的使用和在idea使用maven
  • [Unity Shader]【游戏开发】【图形渲染】Shader数学基础7-矩阵变换概览及其几何意义
  • 前端路由模式详解：Hash 模式、History 模式与 Memory 模式
  • 深度学习作业十一 LSTM
  • 【LeetCode】52、N 皇后 II
  • Python的sklearn中的RandomForestRegressor使用详解