Leetcode - 周赛435

目录

  • 一、3442. 奇偶频次间的最大差值 I
  • 二、3443. K 次修改后的最大曼哈顿距离
  • 三、3444. 使数组包含目标值倍数的最少增量
  • 四、3445. 奇偶频次间的最大差值 II

一、3442. 奇偶频次间的最大差值 I

题目链接
在这里插入图片描述
本题使用数组统计字符串 s s s 中每个字符的出现次数，然后求出现次数为奇数的最大值和出现次数为偶数的最小值，将它们相减得到答案。

代码如下：

class Solution {
    public int maxDifference(String s) {
        int[] cnt = new int[26];
        for(char c : s.toCharArray()){
            cnt[c-'a']++;
        }
        int mx = 0, mn = Integer.MAX_VALUE;
        for(int x : cnt){
            if(x % 2 == 1){
                mx = Math.max(mx, x);
            }else if(x > 0){
                mn = Math.min(mn, x);
            }
        }
        return mx - mn;
    }
}

二、3443. K 次修改后的最大曼哈顿距离

题目链接
在这里插入图片描述
曼哈顿距离求两个坐标点 ( x i , y i ) (x_i,y_i) (xi​,yi​) 和 ( x j , y j ) (x_j,y_j) (xj​,yj​) 的横坐标距离绝对值与纵坐标距离绝对值之和，即 ∣ x i − x j ∣ + ∣ y i − y j ∣ |x_i-x_j|+|y_i-y_j| ∣xi​−xj​∣+∣yi​−yj​∣，也就是说，可以将横纵坐标分开来计算：

  • 对于 x x x 轴来说（东西方向）：比如说，此时向东移动了 a a a 步，向西移动了 b b b 步， a > b a > b a>b，肯定是将向西移动转换成向东移动，才会使得它距离原点距离越远。假设转换了 d d d 次，此时距离原点的距离就变成了 a + d − ( b − d ) = a − b + 2 ∗ d a + d - (b - d) = a - b + 2 * d a+d−(b−d)=a−b+2∗d，如果 a < b a < b a<b，那么就是 b − a + 2 ∗ d b-a+2*d b−a+2∗d，所以一合并变成了 a b s ( a − b ) + 2 ∗ d abs(a-b)+2*d abs(a−b)+2∗d，这里的 d = m i n ( a , b , k ) d=min(a,b,k) d=min(a,b,k)， k = k − d k = k- d k=k−d
  • 对于 y y y 轴来说（南北方向）也是同理.

代码如下：

class Solution {
    public int maxDistance(String s, int k) {
        String str = "NSWE";
        int[] f = new int[4];
        int ans = 0;
        for(char c : s.toCharArray()){
            f[str.indexOf(c)]++;
            int left = k - Math.min(Math.min(f[0], f[1]), k);
            int res = get(f[0], f[1], k) + get(f[2], f[3], left);
            ans = Math.max(ans, res);
        }
        return ans;
    }
    int get(int x, int y, int k){
        int a = Math.max(x, y);
        int b = Math.min(x, y);
        int d = Math.min(b, k);
        return a - b + 2 * d;
    }
}
//也可以换一个角度思考，设当前位置为(x,y):
//由上一种方法可知，每一次修改都会使得曼哈都距离增加 2,最多不会超过 i + 1
class Solution {
    public int maxDistance(String s, int k) {
        int ans = 0;
        int x = 0, y = 0;
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(c == 'N') y++;
            else if(c == 'S') y--;
            else if(c == 'W') x--;
            else x++;
            ans = Math.max(ans, Math.min(Math.abs(x) + Math.abs(y) + 2 * k, i + 1));
        }
        return ans;
    }
}

三、3444. 使数组包含目标值倍数的最少增量

题目链接
在这里插入图片描述
对于 n u m s nums nums 数组中的任意一个元素来说，它可以成为 t a r g e t target target 数组中任意非空子集（从 t a r g e t target target 中任意选几个元素）的倍数，所以可以定义 d f s ( i , j ) dfs(i,j) dfs(i,j)： [ 0 , i ] [0,i] [0,i] 满足集合 j j j 中所有倍数条件的最小操作次数（用集合 j = { x , y , z , . . . } j=\{x,y,z,...\} j={x,y,z,...} 表示 t a r g e t target target 数组中还剩下几个元素没有满足倍数条件）

如果从后往前遍历 n u m s nums nums 数组，对于 x = n u m s [ i ] x = nums[i] x=nums[i] 来说，它有选或不选两种情况：

  • 如果不选，即 x x x 不会进行递增操作，就不会变成集合 j j j 中任意元素的倍数，接下来问题变成前 i i i 个数满足集合 j j j 中所有元素倍数条件的最小操作次数，即 d f s ( i − 1 , j ) dfs(i-1,j) dfs(i−1,j)
  • 如果选，即 x x x 会进行递增操作，就一定要变成集合 j j j 中任意非空子集的倍数，枚举集合 j j j 的所有非空子集 s u b sub sub，接下来问题变成前 i i i 个数满足集合 j − s u b j-sub j−sub（即去除已选择的子集 s u b sub sub） 中所有元素倍数条件的最小操作次数，即 d f s ( i − 1 , j − s u b ) dfs(i-1,j-sub) dfs(i−1,j−sub)
  • d f s ( i , j ) = m i n ( d f s ( i − 1 , j ) , d f s ( i − 1 , j − s u b ) + o p e r a t i o n s ) dfs(i,j)=min(dfs(i-1,j),dfs(i-1,j-sub)+operations) dfs(i,j)=min(dfs(i−1,j),dfs(i−1,j−sub)+operations)， s u b ⊆ j sub\subseteq j sub⊆j， o p e r a t i o n s operations operations 表示 n u m s [ i ] nums[i] nums[i] 变成 s u b sub sub 中所有元素的倍数的操作次数。

要计算 o p e r a t i o n s operations operations，需要先知道子集 s u b sub sub 中所有元素的最小公倍数，这里可以预处理出集合 j j j 所有子集的最小公倍数 l c m lcm lcm。这里介绍一个简单做法，定义 l c m s [ x ] lcms[x] lcms[x]：集合 x x x 中所有元素的最小公倍数。从小到大枚举集合 j j j 子集的大小，令 b i t = 1 < < i bit = 1<<i bit=1<<i，枚举所有大小小于 i i i 的子集 m a s k mask mask，可以得到 f [ b i t ∣ m a s k ] = l c m ( f [ m a s k ] , t a r g e t [ i ] ) f[bit | mask] = lcm(f[mask],target[i]) f[bit∣mask]=lcm(f[mask],target[i])

令 l = l c m s [ s u b ] l = lcms[sub] l=lcms[sub]， o p e r a t i o n s = ( l − n u m s [ i ] % l ) % l operations=(l-nums[i]\%l)\%l operations=(l−nums[i]%l)%l

代码如下：

class Solution {
    long gcd(long x , long y){
        return y == 0 ? x : gcd(y, x % y); 
    }
    long lcm(long x, long y){
        return x * y / gcd(x, y);
    }
    public int minimumIncrements(int[] nums, int[] target) {
        int n = target.length;
        //预处理 lcms
        long[] lcms = new long[1<<n];
        lcms[0] = 1;
        for(int i=0; i<n; i++){
            int bit = 1 << i;
            for(int j=0; j<bit; j++){
                lcms[bit|j] = lcm(target[i], lcms[j]);
            }
        }
        int m = nums.length;
        memo = new long[m][1<<n];
        for(long[] r : memo) Arrays.fill(r, -1);
        return (int)dfs(m-1, (1<<n)-1, nums, lcms);
    }
    long[][] memo;
    long dfs(int i, int j, int[] nums, long[] lcms){
        if(j == 0) return 0;
        if(i < 0) return Long.MAX_VALUE/2;
        if(memo[i][j] != -1) return memo[i][j];
        long res = dfs(i-1, j, nums, lcms);
        int sub = j;
        //枚举 j 的子集
        while(sub > 0){
            long l = lcms[sub];
            res = Math.min(res, dfs(i-1, j^sub, nums, lcms) + (l - nums[i] % l) % l);
            sub = (sub - 1) & j;
        }
        return memo[i][j] = res;
    }
}

//递推写法
class Solution {
    long gcd(long x , long y){
        return y == 0 ? x : gcd(y, x % y); 
    }
    long lcm(long x, long y){
        return x * y / gcd(x, y);
    }
    public int minimumIncrements(int[] nums, int[] target) {
        int n = nums.length;
        int m = target.length;
        long[] lcms = new long[1<<m];
        lcms[0] = 1;
        for(int i = 0; i < m; i++){
            int bit = 1 << i;
            for(int mask = 0; mask < bit; mask++){
                lcms[bit | mask] = lcm(target[i], lcms[mask]);
            }
        }
        long[][] f = new long[n+1][1<<m];
        Arrays.fill(f[0], Long.MAX_VALUE/2);
        for(int i = 0; i < n; i++){
            f[i][0] = 0;
            for(int j = 0; j < 1 << m; j++){
                f[i+1][j] = f[i][j];
                for(int sub = j; sub != 0; sub = (sub - 1) & j){
                    long l = lcms[sub];
                    f[i+1][j] = Math.min(f[i+1][j], f[i][j^sub] + (l - nums[i] % l) % l);
                }
            }
        }
        return (int)f[n][(1<<m)-1];
    }
}

四、3445. 奇偶频次间的最大差值 II

题目链接
在这里插入图片描述
题目中字符串 s s s 仅由数字 0 , 1 , 2 , 3 , 4 0,1,2,3,4 0,1,2,3,4 构成，所以可以枚举出现奇数次的字符 x x x 和出现偶数次的字符 y y y （ x ! = y x != y x!=y），求子串中两个字符出现的频次之差，就是求区间中字符 x x x 、 y y y 的出现次数，然后相减。这个可以使用前缀和来进行计算：

假设数组 p r e x [ i + 1 ] pre_x[i+1] prex​[i+1] 表示前 i i i 个元素中字符 x x x 的出现次数， p r e y [ i + 1 ] pre_y[i+1] prey​[i+1] 表示前 i i i 个元素中字符 y y y 的出现次数，求区间 [ l , r ] [l,r] [l,r] 中 x x x、 y y y 出现频次之差为 p r e x [ r + 1 ] − p r e x [ l ] − ( p r e y [ r + 1 ] − p r e y [ l ] ) pre_x[r+1]-pre_x[l]-(pre_y[r+1]-pre_y[l]) prex​[r+1]−prex​[l]−(prey​[r+1]−prey​[l])，把式子中 r + 1 r+1 r+1 放到一边， l l l 放到一边，得到 p r e x [ r + 1 ] − p r e y [ r + 1 ] − ( p r e x [ l ] − p r e y [ l ] ) pre_x[r+1]-pre_y[r+1]-(pre_x[l]-pre_y[l]) prex​[r+1]−prey​[r+1]−(prex​[l]−prey​[l]) ，此时发现，本题可以使用滑动窗口中的枚举右，维护左来做：

  • 本题要求子字符串的长度至少为 k k k，且子字符串中 x , y x,y x,y 的出现次数大于 0 0 0，即 r − l + 1 ⩾ k r-l+1 \geqslant k r−l+1⩾k， p r e x [ r + 1 ] > p r e y [ r + 1 ] pre_x[r+1]>pre_y[r+1] prex​[r+1]>prey​[r+1]， p r e x [ l ] > p r e y [ l ] pre_x[l]>pre_y[l] prex​[l]>prey​[l]
  • 本题求最大差值，在右端点固定的情况下，要想使得 p r e x [ r + 1 ] − p r e y [ r + 1 ] − ( p r e x [ l ] − p r e y [ l ] ) pre_x[r+1]-pre_y[r+1]-(pre_x[l]-pre_y[l]) prex​[r+1]−prey​[r+1]−(prex​[l]−prey​[l]) 越大，就是要 p r e x [ l ] − p r e y [ l ] pre_x[l]-pre_y[l] prex​[l]−prey​[l] 的值越小，所以需要维护 p r e x [ l ] − p r e y [ l ] pre_x[l]-pre_y[l] prex​[l]−prey​[l] 的最小值。又因为本题要求子字符串中 x x x 的出现次数必须为奇数， y y y 的出现次数必须为偶数（ > 0 >0 >0），这里可以使用数组 m e m o [ p ] [ q ] memo[p][q] memo[p][q] 来记录 x x x、 y y y 的出现次数是为 p p p、 q q q 时， p r e x [ l ] − p r e y [ l ] pre_x[l]-pre_y[l] prex​[l]−prey​[l] 的最小值（ p , q p,q p,q 只表示奇偶性）
  • 更新答案 a n s = m a x ( a n s , p r e x [ r + 1 ] − p r e y [ r + 1 ] − m e m o [ p ] [ q ] ) ans = max(ans,pre_x[r+1]-pre_y[r+1]-memo[p][q]) ans=max(ans,prex​[r+1]−prey​[r+1]−memo[p][q])，这里的 p p p 的奇偶性与 p r e x [ r + 1 ] pre_x[r+1] prex​[r+1] 相反， q q q 的奇偶性与 p r e y [ r + 1 ] pre_y[r+1] prey​[r+1] 相同。

代码如下：

class Solution {
    public int maxDifference(String s, int k) {
        final int inf = Integer.MAX_VALUE/2;
        int n = s.length();
        int ans = -inf;
        for(int x = 0; x < 5; x++){
            for(int y = 0; y < 5; y++){
                if(x == y) continue;
                int[] pre_x = new int[n+1];
                int[] pre_y = new int[n+1];
                int[][] memo = {{inf, inf}, {inf, inf}};
                for(int l = 0, r = 0; r < n; r++){
                    int a = s.charAt(r) - '0';
                    pre_x[r+1] = pre_x[r] + (a == x ? 1 : 0);
                    pre_y[r+1] = pre_y[r] + (a == y ? 1 : 0);
                    // r - l + 1 >= k
                    // pre_x[r+1] > pre_x[l]
                    // pre_y[r+1] > pre_y[l]
                    while(r - l + 1 >= k && pre_x[r+1] > pre_x[l] && pre_y[r+1] > pre_y[l]){
                        int p = pre_x[l] & 1;
                        int q = pre_y[l] & 1; 
                        memo[p][q] = Math.min(memo[p][q], pre_x[l] - pre_y[l]);
                        l++;
                    }
                    //子字符串长度大于等于 k，才能更新答案
                    if(r + 1 >= k)
                        ans = Math.max(ans, pre_x[r+1] - pre_y[r+1] - memo[pre_x[r+1] & 1 ^ 1][pre_y[r+1] & 1]);
                }
            }
        }
        return ans;
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/968300.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

kafka了解-笔记

kafka了解-笔记

文章目录 kafka快速上手Kafka介绍Kafka快速上手理解Kafka的集群工作机制Kafka集群的消息流转模型 Kafka客户端小型流转流程客户端工作机制 kafka快速上手 Kafka介绍 MQ的作用 MQ&#xff1a;MessageQueue&#xff0c;消息队列&#xff0c;是一种FIFO先进先出的数据结构&#…
阅读更多...
支持向量机原理

支持向量机原理

支持向量机&#xff08;简称SVM&#xff09;虽然诞生只有短短的二十多年&#xff0c;但是自一诞生便由于它良好的分类性能席卷了机器学习领域。如果不考虑集成学习的算法&#xff0c;不考虑特定的训练数据集&#xff0c;尤其在分类任务中表现突出。在分类算法中的表现SVM说是排…
阅读更多...
解决VsCode的 Vetur 插件has no default export Vetur问题

解决VsCode的 Vetur 插件has no default export Vetur问题

文章目录 前言1.问题2. 原因3. 解决其他 前言 提示&#xff1a; 1.问题 Cannot find module ‘ant-design-vue’. Did you mean to set the ‘moduleResolution’ option to ‘node’, or to add aliases to the ‘paths’ option? Module ‘“/xxx/xxx/xxx/xxx/xxx/src/vie…
阅读更多...
常用的python库-安装与使用

常用的python库-安装与使用

常用的python库函数 yield关键字openslide库openslide库的安装-linuxopenslide的使用openslide对象的常用属性 cv2库numpy库ASAP库-multiresolutionimageinterface库ASAP库的安装ASAP库的使用 concurrent.futures.ThreadPoolExecutorxml.etree.ElementTree库skimage库PIL.Image…
阅读更多...
Word成功接入DeepSeek详细步骤

Word成功接入DeepSeek详细步骤

原理 原理是利用Word的VBA宏&#xff0c;写代码接入API。无需下载额外插件。 步骤一、注册硅基流动 硅基流动统一登录 注册这个是为了有一个api调用的api_key&#xff0c;有一些免费的额度可以使用。大概就是这个公司提供token&#xff0c;我们使用这个公司的模型调用deepsee…
阅读更多...
【Ubuntu VScode Remote SSH 问题解决】Resolver error: Error: XHR failed

【Ubuntu VScode Remote SSH 问题解决】Resolver error: Error: XHR failed

1. 问题描述 VScode使用remote ssh 远程服务器&#xff0c;报错类似&#xff1a; [12:06:01.219] Downloading VS Code server locally... [12:06:01.310] Resolver error: Error: XHR failedat k.onerror (vscode-file://vscode-app/private/var/folders/g1/cvs2rnpx60qc3b4…
阅读更多...
系统思考—双环学习

系统思考—双环学习

前几天&#xff0c;一个企业高管向我提到&#xff1a;“我们调整了N次方案&#xff0c;市场策略、团队激励、管理制度&#xff0c;能改的全改了&#xff0c;怎么还是不见起色&#xff1f;” 这让我想到典型的单环学习&#xff0c;简单来说就是&#xff1a;发现问题 → 采取行动…
阅读更多...
2.11寒假

2.11寒假

今天复习了深搜和广搜然后做了作业中的一个题目。 解析&#xff1a;外层 for 循环&#xff1a;for (int i 1; i < n; i)&#xff0c;循环变量 i 从 1 递增到 n&#xff0c;表示要依次将数字 1 到 n 分配到数组 a 中。内层 for 循环&#xff1a;for (int j 1; j < 2; j)…
阅读更多...
使用 AlexNet 实现图片分类 | PyTorch 深度学习实战

使用 AlexNet 实现图片分类 | PyTorch 深度学习实战

前一篇文章&#xff0c;CNN 卷积神经网络处理图片任务 | PyTorch 深度学习实战 本系列文章 GitHub Repo: https://github.com/hailiang-wang/pytorch-get-started 本篇文章内容来自于 强化学习必修课&#xff1a;引领人工智能新时代【梗直哥瞿炜】 使用 AlexNet 实现图片分类…
阅读更多...
基于进化式大语言模型的下一代漏洞挖掘范式：智能对抗与自适应攻防体系

基于进化式大语言模型的下一代漏洞挖掘范式：智能对抗与自适应攻防体系

摘要 本文提出了一种基于进化式大语言模型（Evolutionary LLM）的智能漏洞挖掘框架，突破了传统静态分析的局限，构建了具备对抗性思维的动态攻防体系。通过引入深度强化学习与多模态感知机制，实现了漏洞挖掘过程的自适应进化，在RCE、SQLi、XXE等关键漏洞类型的检测中达到97…
阅读更多...
python自动化测试之Pytest框架之YAML详解以及Parametrize数据驱动!

python自动化测试之Pytest框架之YAML详解以及Parametrize数据驱动!

一、YAML详解 YAML是一种数据类型&#xff0c;它能够和JSON数据相互转化&#xff0c;它本身也是有很多数据类型可以满足我们接口 的参数类型&#xff0c;扩展名可以是.yml或.yaml 作用&#xff1a; 1.全局配置文件 基础路径&#xff0c;数据库信息&#xff0c;账号信息&…
阅读更多...
SQLMesh系列教程-2：SQLMesh入门项目实战（上篇）

SQLMesh系列教程-2：SQLMesh入门项目实战（上篇）

假设你已经了解SQLMesh是什么&#xff0c;以及其他应用场景。如果没有&#xff0c;我建议你先阅读《SQLMesh系列教程-1&#xff1a;数据工程师的高效利器-SQLMesh》。 在本文中&#xff0c;我们将完成一个小项目或教程&#xff0c;以帮助你开始使用SQLMesh。你可以选择一步一步…
阅读更多...
人工智能与低代码如何重新定义企业数字化转型？

人工智能与低代码如何重新定义企业数字化转型？

引言&#xff1a;数字化转型的挑战与机遇 在全球化和信息化的浪潮中&#xff0c;数字化转型已经成为企业保持竞争力和创新能力的必经之路。然而&#xff0c;尽管“数字化”听上去是一个充满未来感的词汇&#xff0c;落地的过程却往往充满困难。 首先&#xff0c;传统开发方式…
阅读更多...
使用云效解决docker官方镜像拉取不到的问题

使用云效解决docker官方镜像拉取不到的问题

目录 前言原文地址测试jenkins构建结果:后续使用说明 前言 最近经常出现docker镜像进行拉取不了&#xff0c;流水线挂掉的问题&#xff0c;看到一个解决方案: 《借助阿里个人版镜像仓库云效实现全免费同步docker官方镜像到国内》 原文地址 https://developer.aliyun.com/artic…
阅读更多...
R语言LCMM多维度潜在类别模型流行病学研究：LCA、MM方法分析纵向数据

R语言LCMM多维度潜在类别模型流行病学研究：LCA、MM方法分析纵向数据

全文代码数据&#xff1a;https://tecdat.cn/?p39710 在数据分析领域&#xff0c;当我们面对一组数据时&#xff0c;通常会有已知的分组情况&#xff0c;比如不同的治疗组、性别组或种族组等&#xff08;点击文末“阅读原文”获取完整代码数据&#xff09;。 然而&#xff0c;…
阅读更多...
java项目之基于用户兴趣的影视推荐系统设计与实现源码(ssm+mysql)

java项目之基于用户兴趣的影视推荐系统设计与实现源码(ssm+mysql)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于ssm的基于用户兴趣的影视推荐系统设计与实现。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 项目简介&#xff1a; 基于用户…
阅读更多...
0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型

0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型

前言&#xff1a;哈喽&#xff0c;大家好&#xff0c;今天给大家分享一篇文章&#xff01;并提供具体代码帮助大家深入理解&#xff0c;彻底掌握&#xff01;创作不易&#xff0c;如果能帮助到大家或者给大家一些灵感和启发&#xff0c;欢迎收藏关注哦 &#x1f495; 目录 0基础…
阅读更多...
vue2 多页面pdf预览

vue2 多页面pdf预览

使用pdfjs-dist预览pdf&#xff0c;实现预加载&#xff0c;滚动条翻页。pdfjs的版本很重要&#xff0c;换了好多版本&#xff0c;终于有一个能用的 node 20.18.1 "pdfjs-dist": "^2.2.228", vue页面代码如下 <template><div v-loading"loa…
阅读更多...
堆排序

堆排序

目录 堆排序&#xff08;不稳定&#xff09;&#xff1a; 代码实现&#xff1a; 思路分析&#xff1a; 总结&#xff1a; 堆排序&#xff08;不稳定&#xff09;&#xff1a; 如果想要一段数据从小到大进行排序&#xff0c;则要先建立大根堆&#xff0c;因为这样每次堆顶上都能…
阅读更多...
【C++】多态原理剖析

【C++】多态原理剖析

目录 1.虚表指针与虚表 2.多态原理剖析 1.虚表指针与虚表 &#x1f36a;类的大小计算规则 一个类的大小&#xff0c;实际就是该类中成员变量之和&#xff0c;需要注意内存对齐空类&#xff1a;编译器给空类一个字节来唯一标识这个类的对象 对于下面的Base类&#xff0c;它的…
阅读更多...
最新文章

Copyright @ 2022~2023