C语言巨难题:执行操作可获得的最大总奖励 I(C语言版)
1.题目:
给你一个整数数组 rewardValues,长度为 n,代表奖励的值。
最初,你的总奖励 x 为 0,所有下标都是 未标记 的。你可以执行以下操作 任意次 :
- 从区间
[0, n - 1]中选择一个 未标记 的下标i。 - 如果
rewardValues[i]大于 你当前的总奖励x,则将rewardValues[i]加到x上(即x = x + rewardValues[i]),并 标记 下标i。
以整数形式返回执行最优操作能够获得的 最大 总奖励。
示例 1:
输入:rewardValues = [1,1,3,3]
输出:4
解释:
依次标记下标 0 和 2,总奖励为 4,这是可获得的最大值。
示例 2:
输入:rewardValues = [1,6,4,3,2]
输出:11
解释:
依次标记下标 0、2 和 1。总奖励为 11,这是可获得的最大值。
提示:
1 <= rewardValues.length <= 5 * 1041 <= rewardValues[i] <= 5 * 104
该作者解决方法:
不知道C语言要怎么建构bitset,看了其他人的解答后尝试用位运速加速。 假设有一个 bool 数组 dp。在每一次循环中,dp[rewardValues[i] + j] 可以由 dp[j] 转移而来,其中 j 为小于 rewardValues[i] 的非负整数。 为了加速运算并减少空间浪费,可以将 bool 数组改成 unsigned long long。 在C语言中,虽 bool 使用1bit,但最小寻址单位为1字节,所以占用1字节。 现在我们将数组声明成 unsigned long long,此时每次操作最多可以操作64个位元,也就是64个状态。 由于 rewardValues[i] 不一定为64的倍数,为了避免发生溢位的状况,必须将 dp[j] 所代表的64位元拆成两部分。 为了计算正确的下标,我们把 rewardValues[i] 用 index 与 digit 表示,其中 rewardValues[i] = 64 * index + digit:
index = rewardValues[i] / 64
digit = rewardValues[i] % 64
因此,对于每个下标 j,dp[j] 可拆成:
(dp[j] & ((1 << (64 - digit)) - 1)) << digit
dp[j] >> (64 - digit)
假设 rewardValues[i] = 65,那么:
index = 65 / 64 = 1
digit = 65 % 64 = 1
以 dp[0] 的 0 ~ 63 位为例,0 ~ 62 位可以移到 dp[index + 0] 中的 1 ~ 63 位,对应数字 65 ~ 127。而剩下的1个位则放入 dp[index + 1] 的第 0 位,这个过程通过或运算即可。
dp[index + j] |= (dp[j] & ((1 << (64 - digit)) - 1)) << digit;
dp[index + j + 1] |= dp[j] >> (64 - digit);
若 rewardValues[i] 为 64 的倍数可直接转移,不需拆分
代码:
int cmp(const void *a, const void *b)
{return *(int*)a > *(int*)b;
}int maxTotalReward(int* rewardValues, int rewardValuesSize)
{qsort(rewardValues, rewardValuesSize, sizeof(int), cmp);int size = rewardValues[rewardValuesSize - 1] / 32 + 2;unsigned long long dp[size], temp, mask;memset(dp, 0, sizeof(unsigned long long) * size);int index, digit;dp[0] = 1;for (int i = 0; i < rewardValuesSize; ++i) {index = rewardValues[i] / 64;digit = rewardValues[i] % 64;mask = digit ? (1ULL << (64 - digit)) - 1 : 0;for (int j = 0; j < index; ++j){if (digit) {dp[j + index] |= (dp[j] & mask) << digit;dp[j + index + 1] |= dp[j] >> (64 - digit);} else {dp[j + index] |= dp[j];}}if (digit) {temp = dp[index] & ((1ULL << digit) - 1);dp[2 * index] |= (temp & mask) << digit;dp[2 * index + 1] |= temp >> 64 - digit;}}for (int i = size - 1; i >= 0; --i) {if (dp[i])return 64 * i + 63 - __builtin_clzll(dp[i]);}return 0;
}
声明:来源力扣题解
作者:borane
链接:https://leetcode.cn/problems/maximum-total-reward-using-operations-ii/solutions/2805771/01bei-bao-wei-yun-suan-by-modest-nashdn2-svmq/
来源:力扣(LeetCode)
相关文章:
C语言巨难题:执行操作可获得的最大总奖励 I(C语言版)
1.题目: 给你一个整数数组 rewardValues,长度为 n,代表奖励的值。 最初,你的总奖励 x 为 0,所有下标都是 未标记 的。你可以执行以下操作 任意次 : 从区间 [0, n - 1] 中选择一个 未标记 的下标 i。如果…...
【力扣】GO解决子序列相关问题
文章目录 一、引言二、动态规划方法论深度提炼子序列问题的通用解法模式 三、通用方法论应用示例:最长递增子序列(LeetCode题目300)Go 语言代码实现 四、最长连续递增序列(LeetCode题目674)Go 语言代码实现 五、最长重…...
Ubuntu20.04安装VM tools并实现主机和虚拟机之间文件夹共享
1、Ubuntu20.04安装VM tools 参考这个,很详细:Ubuntu 20.04 安装 VMwareTools 教程 2、实现主机与VMware虚拟机共享文件夹 设置共享文件夹参考:windows和虚拟机互传文件的三种方式 挂载操作参考:主机与VMware虚拟机共享文件夹&…...
Linux 学习笔记(十七)—— 文件系统
终极目标:理解 inode 和 软硬连接; 文件系统:Ext2; 文件 文件内容 文件属性; ——> 磁盘上存储的文件 存储的文件内容 存储的文件属性; Linux系统中:文件内容使用数据块存储,文件属性使用inode(固定…...
【计算机网络 - 基础问题】每日 3 题(五十八)
✍个人博客:https://blog.csdn.net/Newin2020?typeblog 📣专栏地址:http://t.csdnimg.cn/fYaBd 📚专栏简介:在这个专栏中,我将会分享 C 面试中常见的面试题给大家~ ❤️如果有收获的话,欢迎点赞…...
Netty入门基础:IO模型中BIO\NIO概念及区别【附演示代码】
文章目录 😀BIO💢实战demo 🌈NIO🏍Buffer核心属性核心方法 🎗Channel🎈Selector核心方法 🧨实战demo 🎨粘包与半包 😀BIO 传统IO模型,同步阻塞,每…...
vue2 使用环境变量
一. 在根目录下创建.env.xxx文件 .env 基础系统变量,无论何种环境,都可使用其中配置的值,其他环境中的变量会覆盖.env中的同名变量。 .env.development 开发环境 .env.production 生产环境 .env.staging 测试环境 二. 内容格式 vue2 使用是以…...
数据预处理
继续提取代码片段: 12. **导入iris数据集并查看前5行数据**: python from sklearn.datasets import load_iris iris load_iris() X iris.data print(iris数据集的维度为:, X.shape) print(iris数据集的前5行数据为:\n, X[:5]) …...
django宠物领养管理系统-计算机毕业设计源码26858
目录 1 绪论 1.1 选题背景与意义 1.2国内外研究现状 1.3论文结构与章节安排 2系统分析 2.1 可行性分析 2.2 系统流程分析 2.2.1 数据流程 3.3.2 业务流程 2.3 系统功能分析 2.3.1 功能性分析 2.3.2 非功能性分析 2.4 系统用例分析 2.5本章小结 3 系统总体设计 3…...
使用TeamViewer远程局域网内的两台电脑
有个场景,有人还不知道TV可以局域网操作,记录一下。 主要就是修改设置,将取消激活改为接受 然后输入受控端的ip即可...
GUI简介、Swing的常用组件、java程序的运行过程、class文件、JAR、runable_jar、双括号初始化
GUI简介 GUI:图形用户界面,在计算机中采用图形的方式显示用户界面 java的GUI开发 AWT:java最早推出的GUI编程开发包,界面风格跟随操作系统SWT:eclipse就是java使用SWT开发的Swing:在AWT的基础上扩充了功能…...
@Autowired和@Resource和getBean()区别
今天遇到一个对我来说很奇葩的错误,我想在Service中注入bean,我这里使用了Autowired和Resource都不能注入,导致初始化失败,使用了getBean()方法就可以注入。从来没有遇到过这个问题。后来我查询了一下,才明白了原理。我…...
Merlion笔记(四):添加一个新的预测模型
文章目录 1 模型配置类2 模型类3 运行模型:一个简单的例子4 可视化5 定量评估6 定义一个基于预测器的异常检测器 本文提供了一个示例,展示如何向 Merlion 添加一个新的预测模型,遵循 CONTRIBUTING.md 中的说明。建议在阅读本篇文章之前,先查…...
【论文阅读】ESRGAN
学习资料 论文题目:增强型超分辨率生成对抗网络(ESRGAN: Enhanced Super-Resolution Generative Adversarial Networks)论文地址:[1809.00219] ESRGAN:增强型超分辨率生成对抗网络代码:xinntao / ESRGAN&am…...
电脑异常情况总结
文章目录 笔记本无症状息屏黑屏 笔记本无症状息屏黑屏 🍎 问题描述: 息屏导致黑屏;依次操作计算机--》右键--》管理--》事件查看器--》Windows日志--》系统;从息屏到异常黑屏之间出现了很多错误,如下:事件…...
[项目详解][boost搜索引擎#1] 概述 | 去标签 | 数据清洗 | scp
目录 一、前言 二、项目的相关背景 三、搜索引擎的宏观原理 四、搜索引擎技术栈和项目环境 五、正排索引 VS 倒排索引--原理 正排索引 分词 倒排索引 六、编写数据去除标签和数据清洗模块 Parser 1.数据准备 parser 编码 1.枚举文件 EnumFile 2.去标签ParseHtml(…...
PL/I语言的起源?有C语言,有B语言和A语言吗?为什么shell脚本最开始可能有#!/bin/bash字样?为什么不支持嵌套注释?
PL/I语言的起源 在20世纪50~60年代,当时主流的编程语言是COBOL/FORTRAN/ALGOL等,IBM想要设计一门通用的编程语言,已有的编程语言无法实现此要求,故想要设计一门新语言,即是PL/I. PL/I是Programming Language/One的缩写…...
gin入门教程(3):创建第一个 HTTP 服务器
首先设置golang github代理,可解决拉取git包的时候,无法拉取的问题: export GOPROXYhttps://goproxy.io再查看自己的go版本: go version我这里的版本是:go1.23.2 linux/arm64 准备工作做好之后就可以进行开发了 3.…...
Vue+ECharts+iView实现大数据可视化大屏模板
Vue数据可视化 三个大屏模板 样式还是比较全的 包括世界地图、中国地图、canvas转盘等 项目演示: 视频: vue大数据可视化大屏模板...
el-table 表格设置必填项
el-table 表格设置必填项 要在 el-table 中集成 el-form 来设置必填项,并进行表单验证,可以使用 Element UI 提供的表单验证功能。下面是一个详细的示例,展示了如何在 el-table 中使用 el-form 来设置必填项,并进行验证。 示例代…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
华为OD机考-机房布局
import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...
宇树科技,改名了!
提到国内具身智能和机器人领域的代表企业,那宇树科技(Unitree)必须名列其榜。 最近,宇树科技的一项新变动消息在业界引发了不少关注和讨论,即: 宇树向其合作伙伴发布了一封公司名称变更函称,因…...
MyBatis中关于缓存的理解
MyBatis缓存 MyBatis系统当中默认定义两级缓存:一级缓存、二级缓存 默认情况下,只有一级缓存开启(sqlSession级别的缓存)二级缓存需要手动开启配置,需要局域namespace级别的缓存 一级缓存(本地缓存&#…...
面试高频问题
文章目录 🚀 消息队列核心技术揭秘:从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"?性能背后的秘密1.1 顺序写入与零拷贝:性能的双引擎1.2 分区并行:数据的"八车道高速公路"1.3 页缓存与批量处理…...
