Leetcode - 周赛393

news/2024/5/19 21:54:21/ 标签: leetcode, 算法, 职场和发展, 数据结构, java

目录

一,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标准库里…

监督算法建模前数据质量检查

一、定义缺失值检测函数 def missing_values_table(df):# 总的缺失值mis_val df.isnull().sum()# 缺失值占比mis_val_percent 100 * df.isnull().sum() / len(df)# 将上述值合并成表mis_val_table pd.concat([mis_val, mis_val_percent], axis1)# 重命名列名mis_val_table_…

数据结构—顺序表实现通讯录

在上一节我们基本了解了顺序表的基本知识&#xff0c;接下来我们就用顺序表来实现一下通讯录。 一、基于动态顺序表实现通讯录 1.1 功能介绍 1. 能够保存用户信息&#xff1a;姓名&#xff0c;性别&#xff0c;年龄&#xff0c;电话&#xff0c;地址等 2. 添加联系人信息 3. …

js自动缩放页面,html自动缩放页面,大屏自动缩放页面,数字看板自动缩放页面,大数据看板自动缩放页面

js自动缩放页面,html自动缩放页面,大屏自动缩放页面,数字看板自动缩放页面,大数据看板自动缩放页面 由纯JS实现 html代码 <!DOCTYPE html> <html lang="en"><head><meta charset="UTF-8"><meta http-equiv="X-UA-C…

组合预测 | Matlab实现ICEEMDAN-SMA-SVM基于改进完备集合经验模态分解-黏菌优化算法-支持向量机的时间序列预测

组合预测 | Matlab实现ICEEMDAN-SMA-SVM基于改进完备集合经验模态分解-黏菌优化算法-支持向量机的时间序列预测 目录 组合预测 | Matlab实现ICEEMDAN-SMA-SVM基于改进完备集合经验模态分解-黏菌优化算法-支持向量机的时间序列预测预测效果基本介绍程序设计参考资料预测效果 基本…

【opencv】示例-videocapture_obsensor.cpp 读取和处理通过OBSENSOR摄像头获取的视频流数据...

/*** 注意: Astra2、Gemini2 和 Gemini2L 相机目前仅支持 Windows 以及 Linux 内核版本不高于4.15&#xff0c;更高版本的 Linux 内核可能会有异常。 */#include <opencv2/videoio.hpp> // 包含为视频捕捉提供的功能 #include <opencv2/highgui.hpp> // 包含高…

良心无广的4款软件,每一款都逆天好用,且用且珍惜

闲话少说&#xff0c;直上干货&#xff01; 清浊 清浊是一款异常强大的国产手机清理应用&#xff0c;其设计理念崇尚简洁&#xff0c;用户界面清晰明快&#xff0c;且无任何弹窗广告干扰。更难能可贵的是&#xff0c;这款应用提供全程免费服务&#xff0c;功能多样&#xff0…

python django mvc

MVC框架: 1、URL映射到方法 [rootzz mysite]# cat urls.py """mysite URL Configuration The urlpatterns list routes URLs to views. For more information please see: https://docs.djangoproject.com/en/1.11/topics/http/urls/ Examples: Function …

R语言计算:t分布及t检验

t分布理论基础 t分布也称Student’s t-distribution&#xff0c;主要出现在小样本统计推断中&#xff0c;特别是当样本量较小且总体标准差未知时&#xff0c;用于估计正态分布的均值。其定义基于正态分布和 X 2 X^{2} X2分布&#xff08;卡方分布&#xff09;。如果随机变量X服…

轻量级Rust异步运行时

在Rust编程语言的世界中&#xff0c;异步编程是提高程序效率和性能的重要手段。现代软件开发中&#xff0c;随着并发编程需求的不断增加&#xff0c;异步运行时处理诸如I/O操作、网络通信等任务变得尤为重要。smol是Rust语言中的一个小巧而快速的异步运行时&#xff0c;尽管特性…

拼多多评论怎么删除?拼多多已评价不能删掉吗?

拼多多作为国内知名的电商平台&#xff0c;吸引了大量消费者的关注和参与。在购物过程中&#xff0c;我们经常会看到各种各样的评论&#xff0c;这些评论对于其他消费者来说&#xff0c;具有重要的参考价值。有时我们可能会因为各种原因需要删除自己的评论。那么&#xff0c;拼…

开发语言漫谈-JavaScript

JavaScript、Java名字很相近&#xff0c;但它们没有任何亲缘关系&#xff0c;是由不同公司开发的编程语言。Java由Sun公司&#xff08;后被Oracle收购&#xff09;开发&#xff0c;JavaScript最初是由Netscape公司开发的&#xff08;当年浏览器的霸主&#xff09;。JavaScrip…

Android Gradle 开发与应用 (七) : 实现打包自动复制文件插件

1. 前言 项目中遇到了一个问题 : 其中一个模块MyLibrary的assets文件夹中,需要存放很多文件(每个文件对应一个功能)。 这样导致的问题是MyLibrary打出的这个aar包体积特别大。 如果把MyLibrary严谨地拆解成若干个Module又比较费时,对于现在业务现状来说也显得没那么必要。…