当前位置: 首页 > news >正文

3007. 价值和小于等于 K 的最大数字(24.8.21)

前言

感谢皇家笨阿宝的指导

题目

给你一个整数 k 和一个整数 x 。整数 num 的价值是它的二进制表示中在 x,2x,3x 等位置处设置位的数目(从最低有效位开始)。下面的表格包含了如何计算价值的例子。

XnumBinary RepresentationPrice
1130000011013
2130000011011
22330111010013
3130000011011
33621011010102

num 的 累加价值 是从 1 到 num 的数字的 总 价值。如果 num 的累加价值小于或等于 k 则被认为是 廉价的。

请你返回 最大 的廉价数字。

示例 1:

输入:k = 9, x = 1
输出:6
解释:由下表所示,6 是最大的廉价数字。

XnumBinary RepresentationPriceAccumulated Price
1100111
1201012
1301124
1410015
1510127
1611029
17111312

示例 2:

输入:k = 7, x = 2
输出:9
解释:由下表所示,9 是最大的廉价数字。

XnumBinary RepresentationPriceAccumulated Price
21000100
22001011
23001112
24010002
25010102
26011013
27011114
28100015
29100116
210101028

提示:

1 <= k <= 1015
1 <= x <= 8

解题思路

见代码内

代码

class Solution {
public:long long findMaximumNumber(long long k, int x) {//二分查找的过程long long left=1,right=(k+1)<<x;while(left<right){long long mid=(left+right+1)/2;if(Sum(x,mid)>k){//如果比 k 大 说明答案在mid左边right=mid-1;}else{//如果比 k 小 说明在mid右边left=mid;}}return left;}
//求解从 1 到 num 所有整数在二进制表示下在 i 位置处设置位的数字之和
/*
规律:1 2 3 4 5 6
0:         0 0 0 0 0 0
1:         0 0 0 0 0 1
2:         0 0 0 0 1 0
3:         0 0 0 0 1 1
4:         0 0 0 1 0 0
5:         0 0 0 1 0 1
6:         0 0 0 1 1 0
7:         0 0 0 1 1 1
8:         0 0 1 0 0 0
9:         0 0 1 0 0 1此处从 0 开始列举,由于 0 的贡献值为 0 ,因此对本题无影响
数学规律:第 i 位的 0 ,1 存在周期性变化对于 i 位置 先是 2^(i-1) 个 0 后是 2^(i-1) 个 1得出周期为 2^(i-1)+2^(i-1) 即 2^i*/
//先得到二进制有几位(per):1LL<<x
//对于在一个完整周期( T )内的贡献值是: T/2
//对于在一个不完整周期( T )内的贡献值是: 
//           -不超过 T/2 ,贡献值为 0 ;
//           -超过 T/2 ,则是超过部分个 1 ,即最后一个不完整周期到 T/2 的距离    long long Sum_per(int x,long long num){long long per=1LL<<x;long long ans=per/2*(num/per);if(num%per>=per/2){ans+=num%per-(per/2-1);}return ans;}
//是 num 的累加价值long long Sum(int x,long long num){long long ans=0;int l=64-__builtin_clzll(num);//求出数的二进制的位数(除去前导 0 )//位数不可能超过num的最高位://假设位数为:x 2x 3x 4x ...nx//则 nx<= lfor(int i=x;i<=l;i+=x){//搜索在第 i 位的累加之和ans+=Sum_per(i,num);}return ans;}
};

相关文章:

3007. 价值和小于等于 K 的最大数字(24.8.21)

前言 感谢皇家笨阿宝的指导 题目 给你一个整数 k 和一个整数 x 。整数 num 的价值是它的二进制表示中在 x&#xff0c;2x&#xff0c;3x 等位置处设置位的数目&#xff08;从最低有效位开始&#xff09;。下面的表格包含了如何计算价值的例子。 XnumBinary RepresentationPri…...

微服务 - 分布式锁的实现与处理策略

作者&#xff1a;逍遥Sean 简介&#xff1a;一个主修Java的Web网站\游戏服务器后端开发者 主页&#xff1a;https://blog.csdn.net/Ureliable 觉得博主文章不错的话&#xff0c;可以三连支持一下~ 如有疑问和建议&#xff0c;请私信或评论留言&#xff01; 分布式锁的实现与处理…...

Catf1ag CTF Web(九)

前言 Catf1agCTF 是一个面向所有CTF&#xff08;Capture The Flag&#xff09;爱好者的综合训练平台&#xff0c;尤其适合新手学习和提升技能 。该平台由catf1ag团队打造&#xff0c;拥有超过200个原创题目&#xff0c;题目设计注重知识点的掌握&#xff0c;旨在帮助新手掌握C…...

QT QFileDialog 类

QFileDialog 类 QFileDialog 类 QFileDialog 是 Qt 库中的一个类&#xff0c;用于提供文件选择对话框&#xff0c; 允许用户选择文件或目录。QFileDialog 提供了多种静态方法和实例方法&#xff0c; 用于创建和配置文件对话框&#xff0c;并获取用户选择的文件或目录。 QObje…...

了解 K-Means 聚类的工作原理(详细指南)

一、说明 K-means 的目标是将一组观测值划分为 k 个聚类&#xff0c;每个观测值分配给均值&#xff08;聚类中心或质心&#xff09;最接近的聚类&#xff0c;从而充当该聚类的代表。 在本文中&#xff0c;我们将全面介绍 k 均值聚类&#xff08;最常用的聚类方法之一&#xff0…...

预警先行,弯道哨兵让行车更安全

预警先行&#xff0c;弯道哨兵让行车更安全”这句话深刻体现了现代交通安全理念中预防为主、科技赋能的重要性。在道路交通中&#xff0c;尤其是复杂多变的弯道区域&#xff0c;交通事故的发生率往往较高&#xff0c;因此&#xff0c;采取有效的预警措施和引入先进的交通辅助设…...

预约咨询小程序搭建开发,uniapp前端,PHP语言开发

目录 前言&#xff1a; 一、预约小程序搭建功能介绍 二、示例代码片段 前言&#xff1a; 预约咨询小程序适合需付费咨询和交流的场景&#xff1a;比如讲师,摄影,婚庆&#xff0c;美发,律师,心理等等支持商家入驻支持视频、图文、线下、电话等方式在线支付咨询。 一、预约小程…...

极速文件预览!轻松部署 kkFileView 于 Docker 中!

大家好&#xff0c;这几天闲的难受&#xff0c;决定给自己找点事做。博主的项目中有个文件预览的小需求&#xff0c;原有方案是想将文件转换成 PDF 进行预览。本着能借鉴就绝对不自己写的原则。今天就让我们简单试用一下 kkFileView 文件预览服务&#xff0c;一起探索它的强大功…...

某验九宫格分类识别

注意,本文只提供学习的思路,严禁违反法律以及破坏信息系统等行为,本文只提供思路 如有侵犯,请联系作者下架 九宫格分类如下 这种就是最简单的分类识别了,用迁移学习resnet训练即可,下面来看成品 训练代码查看往期文章中就有,部分代码如下: DEVICE = torch.device(…...

未来展望:观测云技术的发展与企业业务的融合

随着技术的不断进步&#xff0c;观测云作为企业数据监控和分析的关键工具&#xff0c;其发展与企业业务的融合趋势显得尤为重要。在未来&#xff0c;观测云技术将如何演进&#xff0c;以及它将如何更深层次地与企业业务相融合&#xff0c;是值得我们深入探讨的问题。 首先&…...

day6JS-DOM(文档对象模型)

DOM树 DOM 操作 1. 获取元素 1.1 根据id名获取元素 document.getElementById("id名"); 案例&#xff1a; <body><div id"box">div盒子</div><h1>一级标题</h1><script>console.log(document.getElementById(&quo…...

MySQL列表分区分区表

什么是列表分区分区表&#xff1f; 列表分区是一种根据某个列的离散值将表数据分割成多个分区的分区方式。在列表分区中&#xff0c;每个分区都有自己的离散值集合&#xff0c;当插入数据时&#xff0c;MySQL会根据指定的列值将数据分配到相应的分区中。这种分区方式可以使得表…...

qt打包程序方法(非常好用)

1.下载 Index of /official_releases/qt-installer-framework/4.6.1 bi...

IP地址管理:优化网络布局与提升效率

在日益复杂的网络环境中&#xff0c;IP地址管理成为了网络管理员日常工作中不可或缺的一部分。有效的IP地址管理不仅能够优化网络布局&#xff0c;提升网络运行效率&#xff0c;还能确保网络安全和稳定性。本文将探讨IP地址管理的重要性、实施策略以及最佳实践。 一、IP地址管…...

老古董Lisp实用主义入门教程(5):好奇先生用Lisp探索Lisp

鲁莽先生什么都不管 鲁莽先生打开电脑&#xff0c;安装一堆东西&#xff0c;噼里啪啦敲了一堆代码&#xff0c;叽里呱啦说了一堆话&#xff0c;然后累了就回家睡觉了。 这可把好奇先生的兴趣勾起来&#xff0c;他怎么也睡不着。好奇先生打开电脑&#xff0c;看了看鲁莽先生留…...

linux文件——用户缓冲区——概念深度理解、IO模拟实现

前言&#xff1a;本篇文章主要讲解文件缓冲区。 讲解的方式是通过抛出问题&#xff0c; 然后通过分析问题&#xff0c; 将缓冲区的概念与原理一步一步地讲解。同时&#xff0c; 本节内容在最后一部分还会带友友们模拟实现一下c语言的printf&#xff0c; fprintf接口&#xff0c…...

Selenium模拟鼠标滚动页面:实现自动化测试中的页面交互

Selenium模拟鼠标滚动页面&#xff1a;实现自动化测试中的页面交互 在进行网页自动化测试时&#xff0c;经常需要模拟用户的滚动行为来加载更多内容或触发页面上的某些交互。Selenium WebDriver提供了强大的工具来模拟这些用户行为&#xff0c;包括鼠标滚动。本文将介绍如何使…...

Eureka原理与实践:构建高效的微服务架构

Eureka原理与实践&#xff1a;构建高效的微服务架构 Eureka的核心原理Eureka Server&#xff1a;服务注册中心Eureka Client&#xff1a;服务提供者与服务消费者 Eureka的实践应用集成Eureka到Spring Cloud项目中创建Eureka Server创建Eureka Client&#xff08;服务提供者&…...

OpenJDK 和 OracleJDK 的区别、下载方式

OpenJDK 和 OracleJDK 都是 Java 开发套件 (JDK)&#xff0c;用于开发和运行 Java 应用程序。它们之间的主要区别如下&#xff1a; 许可证和使用限制&#xff1a; OpenJDK&#xff1a;由 OpenJDK 社区开发和维护&#xff0c;基于 GPL v2 with Classpath Exception 许可证&#…...

arthas源码刨析:arthas-core (2)

文章目录 attach JVMagent**ArthasBootstrap** arthas-core的启动可以从上一篇做参考 参考 pom&#xff0c;即启动是调用的 Arthas 的 main 方法 attach JVM JVM提供了 Java Attach 功能&#xff0c;能够让客户端与目标JVM进行通讯从而获取JVM运行时的数据&#xff0c;甚至可以…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...