Leetcode - 周赛393

news/2024/5/17 17:31:26

目录

一,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.mrgr.cn/p/74008732

相关文章

java spring boot 2 开发实战笔记

本案例是java sping boot 2.2.1 第一步搭建环境:安装依赖 由于我们公司项目是1.8 环境不能乱,我现在自己的电脑是1.8环境,所以本次整理的boot 代码 也只能用1.8 boot版本为:2.2.1,新建项目后,在xml 文件中复制上以下代码 xml配置,最精简运行起来的需要配置一个数据库…

【代码随想录】【动态规划】day51:● 309.最佳买卖股票时机含冷冻期 ● 714.买卖股票的最佳时机含手续费

股票含冷冻期 def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""if len(prices)<1:return 0else:dp[[0]*2 for _ in range(len(prices))]dp[0][0]-prices[0]dp[0][1]0dp[1][0]max(dp[0][0],dp[0][1]-prices[1])dp[1][1]…

Github 2024-04-16Python开源项目日报 Top10

根据Github Trendings的统计,今日(2024-04-16统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Python项目10TypeScript项目1Vue项目1系统设计指南 创建周期:2507 天开发语言:Python协议类型:OtherStar数量:241693 个Fork数量:42010 次…

个人 Scrum Day 4

一、项目总结 昨天已完成的工作:食堂列表界面 今日计划完成工作:用户登录系统 工作中遇到的困难:使用新版微信小程序的api接口和设计登录弹窗。 二、代码签入 https://github.com/gdut-canteen/gdut-canteen/commit/79cb13c09bc60343e20561a989d3eaaf8dc7075f 三、运行部分截…

aaPanel面板和宝塔(BT)面板安装及命令

aaPanel面板和宝塔面板都是同一家公司在运营,只是aaPanel面板主要服务于海外客户,宝塔面板服务于本地客户。通常如果使用的是海外的服务器部署web环境,建议使用aaPanel面板。宝塔面板是一款基于 Web 的管理服务器的面板软件,它可以帮助用户方便地管理服务器的各种功能。面板…

租用境外服务器,越南服务器的优势有哪些

自从中国加入世界贸易组织之后&#xff0c;国内经济增加速度非常快&#xff0c;同时越来越多的人选择去东南亚国家发展&#xff0c;因为当地的中国人很多&#xff0c;所以中国企业在当地面临着更小的文化差异。东南亚地区也是最新的经济体&#xff0c;互联网正处于蓬勃发展的阶…

数据结构:线性表————单链表专题

&#x1f308;个人主页&#xff1a;小新_- &#x1f388;个人座右铭&#xff1a;“成功者不是从不失败的人&#xff0c;而是从不放弃的人&#xff01;”&#x1f388; &#x1f381;欢迎各位→点赞&#x1f44d; 收藏⭐️ 留言&#x1f4dd; &#x1f3c6;所属专栏&#xff1…

vue和react通用后台管理系统权限控制方案

1. 介绍 在任何企业级应用中&#xff0c;尤其是后台管理系统&#xff0c;权限控制是一个至关重要的环节。它确保了系统资源的安全性&#xff0c;防止非法访问和操作&#xff0c;保障业务流程的正常进行。本文件将详细解析后台管理系统中的权限控制机制及其实施策略。 那么权限…

使用Docker部署开源建站工具—Halo,并实现个人博客公网访问

目录 推荐 前言 1. Docker部署Halo 1.1 检查Docker版本 如果未安装Docker可参考&#xff1a; 已安装Docker步骤&#xff1a; 1.2 在Docker中部署Halo 2. Linux安装Cpolar 2.1 打开服务器防火墙 2.2 安装cpolar内网穿透 3. 配置Halo个人博客公网地址 4. 固定Halo公网…

如何使用XSSFWorkbook读取文本薄?

本篇文章暂不对XSSFWorkbook类进行解析和说明,仅附有实现代码。 如果文中阐述不全或不对的,多多交流。【版权声明】未经博主同意,谢绝转载!(请尊重原创,博主保留追究权) https://www.cnblogs.com/cnb-yuchen/p/18146625 出自【进步*于辰的博客】1、文件兼容类型。 // 兼…

GAMES101 作业7 踩坑指南

首先回顾路径追踪的原理,如下图基本思想 wo是射向眼镜(相机)的光线,包含来自光源的直接光照ws,来自其他物体的间接光照wi两部分。 在实现path tracing时,我们考虑的是黄色线的方向,即光线从相机射向p点(实际上是从p点射向相机),然后通过多次随机采样从p点射出(实际上…

MoJoCo 入门教程(七)XML 参考

系列文章目录 前言 表格第二列中的符号含义如下&#xff1a; ! 必填元素&#xff0c;只能出现一次 ? 可选元素&#xff0c;只能出现一次 * 可选元素&#xff0c;可多次出现 R 可选元素&#xff0c;可递归出现多次 一、简介 本章是 MuJoCo 中使用的 MJCF 建模语言的参考手册。…

【继承】菱形继承以及虚拟菱形继承

文章目录 什么叫菱形继承菱形继承带来的问题 虚拟继承虚拟继承的内存布局总结&#xff1a; 关于继承和组合组合的优势代码复用最常见的几种手段有&#xff1a;继承的合理使用场景总结 什么叫菱形继承 菱形继承是多继承的一种特殊情况。什么叫多继承呢&#xff1f; 多继承又称多…

实验一原型设计-汽水音乐app

一、对比墨刀、Axure、Mockplus等原型设计工具的各自的适用领域及优缺点墨刀 • 适用领域:主要专注于app原型设计,适合高保真原型、复杂多交互项目以及安卓/ios端项目。 • 优点:操作效率高,易于上手,特别适合设计移动应用的交互原型。 • 缺点:在后台和网页设计方面稍显…

数据库的物化视图

数据库的物化视图 数据库的物化视图(Materialized View)是一种预先计算和存储的查询结果集,可以提高查询性能和减少查询开销。与普通视图不同,物化视图是实际存储在磁盘上的表,而不是只是一个查询语句。物化视图可以在需要时更新,以保持其数据的实时性。 优点提高查询性能…

LCD显示屏 --- 介绍

LCD数据手册关键信息提取 LCD说明 LCD 即 液晶显示器,依据驱动方式可以分为静态驱动,简单矩阵驱动,主动矩阵驱动三种,其中简单矩阵分为TN和STN两种,主动矩阵则以薄膜式晶体管(TFT)为主。TFT LCD的现实质量是最佳的,从硬件角度看,一块LCD屏显示图像不但需要LCD驱动器,还…

艾拓琪光电威灏光电携手无锡哲讯启动SAP ERP数字化转型项目,共创未来发展

4月16日,艾拓琪光电&威灏光电携手SAP实施商无锡哲讯举行SAP数字化转型项目启动会,全面推动企业数智化转型。启动会受到双方企业高度重视,苏州艾拓琪总经理何总、安徽威灏光电总经理刘总,无锡哲讯总经理崔新华先生及全体项目团队成员出席本次SAP ERP项目启动会。苏州艾拓…

PgSQL之WITH Queries/Statement

PostgreSQL WITH 子句 在 PostgreSQL 中&#xff0c;WITH 子句提供了一种编写辅助语句的方法&#xff0c;以便在更大的查询中使用。 WITH 子句有助于将复杂的大型查询分解为更简单的表单&#xff0c;便于阅读。这些语句通常称为通用表表达式&#xff08;Common Table Express…

在 Elasticsearch 中扩展 ML 推理管道:如何避免问题并解决瓶颈

作者&#xff1a;来自 Elastic Iulia Feroli 是时候考虑语义搜索运营了吗&#xff1f; 无论你是一位经验丰富的搜索工程师&#xff0c;希望探索新的人工智能功能&#xff0c;还是一位机器学习专家&#xff0c;希望更多地利用搜索基础设施来增强语义相似性模型 —— 充分利用这…