Leetcode - 周赛393

news/2025/3/21 1:40:13/

目录

一,3114. 替换字符可以得到的最晚时间

二,3115. 素数的最大距离

三,3116. 单面值组合的第 K 小金额

四, 3117. 划分数组得到最小的值之和


一,3114. 替换字符可以得到的最晚时间

本题是一道模拟题,直接上代码。

代码如下:

class Solution {public String findLatestTime(String s) {char[] t = s.toCharArray();if(t[0] == '?')t[0] = t[1]=='?'||t[1]<='1'?'1':'0';if(t[1] == '?')t[1] = t[0]=='1'?'1':'9';if(t[3] == '?')t[3] = '5';if(t[4] == '?')t[4] = '9';return new String(t);}
}

二,3115. 素数的最大距离

本题主要考察素数的定义,需要注意的是该题的范围包括1,所以需要额外判断一下。

代码如下: 

class Solution {public int maximumPrimeDifference(int[] nums) {int n = nums.length;int i = 0, j = n - 1;while(i < n){if(is_prime(nums[i])){//找第一个出现的素数break;}i++;}while(j >= 0){if(is_prime(nums[j])){//找最后一个出现的素数break;}j--;}return j-i;}boolean is_prime(int x){//校验是否是素数for(int i=2; i<=Math.sqrt(x); i++){if(x%i == 0)return false;}return x>=2;}
}

三,3116. 单面值组合的第 K 小金额

二分 + lcm + 容斥原理

根据题目和它给的数据范围,可以发现直接求第k小是非常困难的,所以直接想到二分答案,想使用二分,还要看题目是否有单调的性质,可以发现,当枚举的数越大,所能创造的金额就越多,就越容易满足条件,所以可以二分

接下来就是实现check方法,该方法需要统计在【0,二分答案】之间可以产生多少不重复的金额,再具体一点,就是计算在【0,二分答案】之间,coins数组中每个数及其倍数的并集,这里就要使用到容斥原理:

  • |A∪B| = |A| + |B| - |A∩B|
  • |A∪B∪C| = |A| + |B| - |A∩B| + |C| - |A∩C| - |B∩C| + |A∩B∩C|
  • ......

发现当求∩的集合的数量为单数时,它前面的符号是 +,为偶数时,它前面的符号是 -,也就是奇正偶负

搞清楚了符号问题,那么这里A∩..这个集合的大小该如何计算呢?举个例子,coins=[2,3]

求在【0,14】范围内 |2的倍数∩3的倍数| 的大小,2的倍数=[2,4,6,8,10,12,14],3的倍数=[3,6,9,12],它们的交集=[6,12],而这恰好是[2,3]最小公倍数的倍数,所以交集的大小就等于【二分答案(在这里指14) / 最小公倍数(在这里指6)】

而两个数的最小公倍数 = 两个数的乘积 / 两个数的最大公约数,如果最大公约数不会求,可以去网上学习一下辗转相除法,这里就不过多介绍了.

代码如下:

class Solution {public long findKthSmallest(int[] coins, int k) {Arrays.sort(coins);long l = k - 1;long r = (long)coins[0] * k;while(l <= r){//二分答案long mid = (l + r) / 2;if(check(mid, coins, k)){r = mid - 1;} else {l = mid + 1;}}return r + 1;}boolean check(long m, int[] coins, int k){int n = coins.length;long cnt = 0;for(int i=1; i<(1<<n); i++){//枚举子集long res_lcm = 1;for(int j=0; j<n; j++){if((i>>j&1) == 1){//如果i>>j&1为1,说明子集包括coins[j]res_lcm = lcm(res_lcm, coins[j]);}}cnt += Integer.bitCount(i)%2==1?m/res_lcm:-m/res_lcm;}return cnt >= k;}long lcm(long a, long b){//最小公倍数return a*b/gcd(a,b);}long gcd(long a, long b){//最大公约数return b==0?a:gcd(b,a%b);}
}

 

四, 3117. 划分数组得到最小的值之和

划分dp

使用dfs来实现,dfs(i,j,and)的定义:前 i 个数分成 j 段所得到的最小子数组值之和,and是第 j 段的&值

dfs(i,j,and)有两个来源:

  • 当前nums[i]不划分,划分段数不变,即 j 不增加,用dfs表示就是 dfs(i+1,j,and)
  • 当前nums[i]划分到新的子数组中,划分段数 j 加一,用dfs表示就是 dfs(i+1,j+1,and) + nums[i],不过还需要注意的是,只有 and == andValue[j]时,才能划分
  • 根据上述可以推出 dfs(i,j,and) = Math.min(dfs(i+1,j,and),dfs(i+1,j+1,and) + nums[i])

dfs终止条件(n=nums.length,m=andValues.length):

  • 要保证剩下的数 n-i 可以分成 m-j 段,即 if ( n-i < m-j ),返回 Integer.MAX_VALUE/2
  • 当数组已经划分成了m段 j == m,如果 i == n,说明刚好划分完,返回 0;如果 i != n,说明还有数没划分,返回Integer.MAX_VALUE/2
  • 根据&的数量越多,&值越小这个性质,可以剪枝,if (and < andValue[j]),return Integer.MAX_VALUE/2.

这里使用Integer.MAX_VALUE/2是为了防止溢出

代码如下:

class Solution {//划分dp - 前i个数分成j段//&越多,&值越小Map<String,Integer> map = new HashMap<>();int n, m;int[] nums, andValues;public int minimumValueSum(int[] nums, int[] andValues) {n = nums.length;m = andValues.length;this.nums = nums;this.andValues = andValues;int ans = dfs(0,0,-1);return ans == Integer.MAX_VALUE/2 ? -1 : ans;}int dfs(int i, int j, int and){String key = i + "-" + j + "-" + and;if(!map.isEmpty() && map.containsKey(key)) return map.get(key);//记忆化if(n-i < m-j) return Integer.MAX_VALUE/2;//剩下的数不足以分成m-j段if(j == m) return i==n?0:Integer.MAX_VALUE/2;and &= nums[i];if(and < andValues[j])//剪枝return Integer.MAX_VALUE/2;int res = dfs(i+1, j, and);if(and == andValues[j])res = Math.min(res, dfs(i+1, j+1, -1) + nums[i]);map.put(key, res);return res;}
}

 


http://www.ppmy.cn/news/1424469.html

相关文章

51单片机串口输出问题(第一个字符重复,自动循环输出第一个字符)

遇到的问题描述 51单片机使用串口发送数据时出现只循环发送字符串的第一个字符的情况。就算发送的是第一个字符也有时候一直发送。 串口函数代码 参考串口发送注意 #include <reg52.h> //此文件中定义了单片机的一些特殊功能寄存器void UsartInit() {SCON0X50; /…

Windows上构建 Chisel-Bootcamp

windows环境构建本地Chisel-Bootcamp 安装摘要Chisel-boocamp环境搭建安装java安装Anaconda安装scala 下载Chisel-bootcamp 环境Reference 安装摘要 在windows上安装chisel-boocamp&#xff0c;与linux过程类似。 安装java8安装anaconda安装scala下载Chisel-bootcamp环境 Ch…

并发场景下 缓存击穿 穿透 雪崩如何解决

最近建了一个技术交流群&#xff0c;欢迎志同道合的同学加入&#xff0c;群里主要讨论&#xff1a;分享业务解决方案、深度分析面试题并解答工作中遇到的问题&#xff0c;同时也能为我提供写作的素材。 群号 208236931&#xff0c;欢迎进群交流学习&#xff0c;一起进步、进步、…

泛型的初步认识(1)

前言~&#x1f973;&#x1f389;&#x1f389;&#x1f389; hellohello~&#xff0c;大家好&#x1f495;&#x1f495;&#xff0c;这里是E绵绵呀✋✋ &#xff0c;如果觉得这篇文章还不错的话还请点赞❤️❤️收藏&#x1f49e; &#x1f49e; 关注&#x1f4a5;&#x…

【Linux】地址空间虚拟地址

个人主页 &#xff1a; zxctscl 如有转载请先通知 文章目录 1. 虚拟地址1.1 虚拟地址引入1.2 虚拟地址理解1.3 虚拟地址细节问题 2. 地址空间2.1 理解地址空间2.2 页表和写时拷贝 3. 进程调度 1. 虚拟地址 1.1 虚拟地址引入 先先来一个测试代码&#xff1a; 1 #include<st…

深入探讨虚拟现实中的新型安全威胁:“盗梦攻击”及其防御策略

随着虚拟现实&#xff08;VR&#xff09;技术的飞速发展&#xff0c;用户体验达到了前所未有的沉浸水平&#xff0c;但也暴露在一系列新的安全威胁之下。本文着重介绍了近期出现的一种高度隐秘且影响深远的攻击手段——“盗梦攻击”。这一概念由芝加哥大学的研究人员提出&#…

【每日刷题】Day7

【每日刷题】Day7 &#x1f955;个人主页&#xff1a;开敲&#x1f349; &#x1f525;所属专栏&#xff1a;每日刷题&#x1f34d; &#x1f33c;文章目录&#x1f33c; 1. 206. 反转链表 - 力扣&#xff08;LeetCode&#xff09; 2. 203. 移除链表元素 - 力扣&#xff08;…

C++反向迭代器的封装和模板进阶(个人笔记)

C反迭代器和模板进阶 1.反向迭代器2.模板2.1非类型模板参数2.2模板的特化2.2.1函数模板2.2.2类模板特化2.2.2.1 全特化2.2.2.1 偏特化 2.3模板的分离编译2.4模板的优缺点 1.反向迭代器 用正向迭代器适配出反向迭代器 这里是自己实现的反向迭代器版本&#xff0c;与STL标准库里…