Leetcode - 周赛401
目录
一,3178. 找出 K 秒后拿着球的孩子
二,3179. K 秒后第 N 个元素的值
三,3180. 执行操作可获得的最大总奖励 I
四,3181. 执行操作可获得的最大总奖励 II
一,3178. 找出 K 秒后拿着球的孩子
本题可以直接模拟,遇到 0 或 n - 1 下标,就反转一下。
代码如下:
class Solution {public int numberOfChild(int n, int k) {int i = 0, t = 1;while(k > 0){i += t;if(i == 0 || i == n-1){t *= -1;}k--;}return i;}
}
二,3179. K 秒后第 N 个元素的值
本题也是一道模拟题,对数组 a 不断的求前缀和,最后返回a[n-1].
代码如下:
class Solution {public int valueAfterKSeconds(int n, int k) {int MOD = (int)1e9 + 7;int[] a = new int[n];Arrays.fill(a, 1);while(k > 0){for(int i=1; i<n; i++){a[i] = (a[i] + a[i-1])%MOD;}k--;}return a[n-1];}
}
三,3180. 执行操作可获得的最大总奖励 I
本题可以使用dfs中的选或不选来做,这里需要知道当前的下标 i ,以及前面所选的数的和 x,需要使用 x < rewardValues[i] 来判断该点能否选。(注意,题目对选择的下标没有进行限制,我们可以先将数组排序,这样就只需要向后遍历)
定义 dfs(i,x):在[0,i)所选择的所有数的和为x时,[i,n]的最大总奖励。
- 选择 i 下标(必须先满足 x < rewardValues[i]),这时下一个状态就是 dfs(i+1,x+rewardValues[i])
- 不选 i 下标,下一个状态是 dfs(i+1, x)
- 结束条件,i == n,返回 0
- 返回两者的较大值
这里记忆化的时候只需要记录 x 就行,我们只需要关注在当前和为 x 时,能取到的最大值memo[x],代码如下:
class Solution {public int maxTotalReward(int[] rewardValues) {Arrays.sort(rewardValues);memo = new int[4001];Arrays.fill(memo, -1);return dfs(0,0,rewardValues);}int[] memo;int dfs(int i, int x, int[] rewardValues){if(memo[x] != -1) return memo[x];if(i == rewardValues.length) return 0;int res = dfs(i+1, x, rewardValues);if(x < rewardValues[i]){res = Math.max(res, dfs(i+1, x+rewardValues[i], rewardValues)+rewardValues[i]);}return memo[x] = res;}
}
递推做法(0-1背包)
定义f[i][j]:能否从前 i 个数得到总奖励为 j
- 选(满足 j > rewardValues[i] && j-rewardValues[i] < rewardValues[i]),f [ i ][ j ] = f [ i-1 ][ j-rewardValues[i] ]
- 不选,f [ i ][ j ] = f [ i-1 ][ j ]
- f [ i ][ j ] = f [ i-1 ][ j ] || f [ i-1 ][ j-rewardValues[i] ]
class Solution {public int maxTotalReward(int[] rewardValues) {Arrays.sort(rewardValues);boolean[] f = new boolean[4001];int res = 0;f[0] = true;for(int i=0; i<rewardValues.length; i++){for(int x=rewardValues[i]-1; x>=0; x--){f[x+rewardValues[i]] = f[x+rewardValues[i]] || f[x];res = Math.max(res,f[x+rewardValues[i]]?x+rewardValues[i]:res);}}return res;}
}
四,3181. 执行操作可获得的最大总奖励 II
该问无法使用上述的做法,还需要进行优化,这里使用的是 bitset优化,它的原理就是直接使用二进制进行上述的或运算,这样就可以优化掉一层for循环。这里二进制位1-表示能得到当前数,0-表示不能得到当前数。代码如下:
//这里使用py是因为更加直接易懂
class Solution:def maxTotalReward(self, rewardValues: List[int]) -> int:f = 1for v in sorted(rewardValues):mask = (1 << v) - 1# t = (f & mask) << v : 表示如果选择v时,且 x < v 时, x + v 的所有能表示的值# f |= t : 为了计算不选择v时,x 的所有能表示的值f |= (f & mask) << vreturn f.bit_length() - 1//Java版
import java.math.BigInteger;class Solution {public int maxTotalReward(int[] rewardValues) {BigInteger f = BigInteger.ONE;for (int v : Arrays.stream(rewardValues).distinct().sorted().toArray()) {BigInteger mask = BigInteger.ONE.shiftLeft(v).subtract(BigInteger.ONE);f = f.or(f.and(mask).shiftLeft(v));}return f.bitLength() - 1;}
}
相关文章:

Leetcode - 周赛401
目录 一,3178. 找出 K 秒后拿着球的孩子 二,3179. K 秒后第 N 个元素的值 三,3180. 执行操作可获得的最大总奖励 I 四,3181. 执行操作可获得的最大总奖励 II 一,3178. 找出 K 秒后拿着球的孩子 本题可以直接模拟&a…...

Java | Leetcode Java题解之第171题Excel表列序号
题目: 题解: class Solution {public int titleToNumber(String columnTitle) {int number 0;int multiple 1;for (int i columnTitle.length() - 1; i > 0; i--) {int k columnTitle.charAt(i) - A 1;number k * multiple;multiple * 26;}ret…...

【uni-app学习手札】
uni-app(vue3)编写微信小程序 编写uni-app不必拘泥于HBuilder-X编辑器,可用vscode进行编写,在《微信开发者工具》中进行热加载预览, 主要记录使用uni-app过程中自我备忘一些api跟语法,方便以后编写查找使用…...

ASP.NET Core 中使用 Dapper 的 Oracle 存储过程输出参数
介绍 Oracle 数据库功能强大,在企业环境中使用广泛。在 ASP.NET Core 应用程序中使用 Oracle 存储过程时,处理输出参数可能具有挑战性。本教程将指导您完成使用 Dapper(适用于 . NET 的轻量级 ORM(对象关系映射器)&am…...

C++的动态内存分配
使用new/delete操作符在堆中分配/释放内存 //使用new操作符在堆中分配内存int* p1 new int;*p1 2234;qDebug() << "数字是:" << *p1;//使用delete操作符在堆中释放内存delete p1;在分配内存的同时初始化 //在分配内存的时初始化int* p2 n…...

【论文阅读】-- TSR-TVD:时变数据分析和可视化的时间超分辨率
TSR-TVD: Temporal Super-Resolution for Time-Varying Data Analysis and Visualization 摘要1 引言2 相关工作3 我们的循环生成方法3.1 损失函数3.2 网络架构 4 结果与讨论4.1 数据集和网络训练4.2 结果4.3 讨论 5 结论和未来工作致谢参考文献附录1 训练算法及优化2 网络分析…...
《web应用技术》第12次课后作业
1、了解servlet技术 Servlet(server applet):运行在服务器的小程序,Servlet就是一个接口,定义了Java类被浏览器访问到的规则。将来我们自定义一个类,实现Servlet接口,复写方法。 Servlet本身不能独立运行,…...

【初阶数据结构】深入解析带头双向循环链表:探索底层逻辑
🔥引言 本篇将介绍带头双向循环链表底层实现以及在实现中需要注意的事项,帮助各位在使用过程中根据底层实现考虑到效率上问题和使用时可能会导致的错误使用 🌈个人主页:是店小二呀 🌈C语言笔记专栏:C语言笔…...

【面试干货】Java中的访问修饰符与访问级别
【面试干货】Java中的访问修饰符与访问级别 1、public2、protected3、默认(没有访问修饰符)4、private 💖The Begin💖点点关注,收藏不迷路💖 在Java中,访问修饰符用于控制类、变量、方法和构造器…...

Oracle最终还是杀死了MySQL
起因 大约15年前,Oracle收购了Sun公司,从而也拥有了MySQL,互联网上关于Oracle何时会“扼杀MySQL”的讨论此起彼伏。 当时流传着各种理论:从彻底扼杀 MySQL 以减少对 Oracle 专有数据库的竞争,到干掉 MySQL 开源项目&…...
【Python的随机数汇总】
我们写python代码的时候,很少能用得上随机数,但是随机数有很多妙用。例如,在我们做测试数据集的时候,可以构建一个随机的dataframe; 或者在保存数据的时候,可以在每条数据前插入一列作为,不重…...
[状态压缩 广搜BFS]Saving Tang Monk
描述 《Journey to the West》(also 《Monkey》) is one of the Four Great Classical Novels of Chinese literature. It was written by Wu Chengen during the Ming Dynasty. In this novel, Monkey King Sun Wukong, pig Zhu Bajie and Sha Wujing, escorted Tang Monk to…...

Flutter 实现软鼠标
文章目录 前言一、如何实现?1、记录鼠标偏移2、MouseRegion获取偏移3、Transform移动图标 二、完整代码三、使用示例总结 前言 flutter在嵌入式系统中运行时,有可能遇到drm鼠标无法使用的情况,但鼠标事件却可以正常接收,此时如果…...

使用 MLRun 和 MinIO 设置开发机器
MLOps 之于机器学习,就像 DevOps 之于传统软件开发一样。两者都是一组旨在改善工程团队(开发或 ML)和 IT 运营 (Ops) 团队之间协作的实践和原则。目标是使用自动化来简化开发生命周期,从规划和开发到部署和…...
资质申请表详解:填写《建筑幕墙工程设计专项资质申请表》的要点
填写《建筑幕墙工程设计专项资质申请表》的要点如下,按照清晰、分点表示和归纳的方式整理,并参考了文章中的相关数字和信息: 一、封面 申报企业名称:按照工商营业执照内容填写全称,并加盖企业公章。填报日期…...

华为手机怎么找回删除的照片?掌握3个方法,恢复不是梦
由于误删、设备故障、软件更新等原因,我们有时可能会不慎丢失这些宝贵的照片。当面对空空如也的相册时,那种失落感无法言喻。华为手机该怎么找回删除的照片呢?但是,请不要绝望!在科技的帮助下,我们可以采取…...

数据结构试题 20-21
真需要就死记吧 二叉树遍历-先序(非递归)【图解代码】_哔哩哔哩_bilibili 解释一下步骤: 一个循环为: 1.取节点 2.放右子树 3.放左子树 每次循环,都要从栈里取出一个节点 先放右子树,再放左子树 那这道题就是,先放1&am…...

vscode插件开发之 - TestController
TesController概要介绍 TestController 组件是用于实现自定义测试框架和集成测试结果的。它允许开发者定义自己的测试运行器,以支持在VSCode中运行和展示测试。以下是一些使用 TestController 组件的主要场景: 自定义测试框架:如果你正在开发…...
QBitArray使用详解
QBitArray使用详解 一、创建和初始化 QBitArray1.1 QBitArray默认构造1.2 QBitArray指定大小的构造1.3 QBitArray指定大小和初始值的构造 二、设置和访问位2.1 QBitArray设置单个位2.2 QBitArray访问单个位2.3 QBitArray使用下标操作符 三、设置所有位3.1 QBitArray将所有位设置…...
基于Python的自然语言处理项目 ChatTTS 推荐
**项目名称:ChatTTS** ChatTTS是一个基于Python的自然语言处理项目,旨在实现一个简单的文本到语音转换系统。它使用深度学习技术,通过自然语言处理和语音合成算法,将文本转换为语音输出。 **项目介绍**: Chat…...

第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...

.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...

React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...