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

LeetCode 3226. 使两个整数相等的位更改次数

. - 力扣(LeetCode)

题目

给你两个正整数 n 和 k。你可以选择 n 的 二进制表示 中任意一个值为 1 的位,并将其改为 0。

返回使得 n 等于 k 所需要的更改次数。如果无法实现,返回 -1。

  • 示例 1:
    • 输入: n = 13, k = 4
    • 输出: 2
    • 解释:最初,n 和 k 的二进制表示分别为 n = (1101)2 和 k = (0100)2,我们可以改变 n 的第一位和第四位。结果整数为 n = (0100)2 = k
  • 示例 2:
    • 输入: n = 21, k = 21
    • 输出: 0
    • 解释:n 和 k 已经相等,因此不需要更改。
  • 示例 3:
    • 输入: n = 14, k = 13
    • 输出: -1
    • 解释:无法使 n 等于 k

解题方案

1. 逐位遍历

依次取n和k最后一位,进行比较

  • 如果last_n == last_k, 则不需要修改,继续遍历
  • 如果lask_n != last_k:
    • 如果last_n == 1, last_k == 0, 则需要改变操作,操作数+1
    • 如果last_n == 0, last_k == 1, 则无法通过指定操作使n变成k, 直接返回-1

class Solution:def minChanges(self, n: int, k: int) -> int:if n < k:return -1if n == k:return 0mod = 0while k > 0 or n > 0:last_n = n & 1 # 取n的最后一位last_k = k & 1 # 取k的最后一位n = n >> 1k = k >> 1if last_n == last_k:print(last_n, last_k, n, k, mod)continueelif last_k == 1:return - 1else:mod += 1 print(last_n, last_k, n, k, mod)return mod

分析复杂度

  • 时间复杂度是n和k位数的最大值:O(log \ max(n, k)) 

  • 空间复杂度是O(1)

2. 位操作

如果把n和k的二进制为1的位分别看做一个集合,那么k应该是n的一个子集。

1. 按位或操作,如果操作结果等于k,则n可以通过修改某些位置上1为0得到k;反之则不能,直接返回-1.

2. 已知n可以通过修改某些位置上1为0得到k,接下来进行异或操作(n和k不同的位为1,即需要修改的位为1),统计操作结果中1的位数即可

class Solution:def minChanges(self, n: int, k: int) -> int:return (n ^ k).bit_count() if (n & k) == k else -1

分析复杂度

  • 时间复杂度 O(1)
  • 空间复杂度 O(1) 

 

 

相关文章:

LeetCode 3226. 使两个整数相等的位更改次数

. - 力扣&#xff08;LeetCode&#xff09; 题目 给你两个正整数 n 和 k。你可以选择 n 的 二进制表示 中任意一个值为 1 的位&#xff0c;并将其改为 0。 返回使得 n 等于 k 所需要的更改次数。如果无法实现&#xff0c;返回 -1。 示例 1&#xff1a; 输入&#xff1a; n …...

面试经典 150 题:189、383

189. 轮转数组 【参考代码】 class Solution { public:void rotate(vector<int>& nums, int k) {int size nums.size();if(1 size){return;}vector<int> temp(size);//k k % size;for(int i0; i<size; i){temp[(i k) % size] nums[i];}nums temp; }…...

Python模拟真人动态生成鼠标滑动路径

一.简介 鼠标轨迹算法是一种模拟人类鼠标操作的程序&#xff0c;它能够模拟出自然而真实的鼠标移动路径。 鼠标轨迹算法的底层实现采用C/C语言&#xff0c;原因在于C/C提供了高性能的执行能力和直接访问操作系统底层资源的能力。 鼠标轨迹算法具有以下优势&#xff1a; 模拟…...

如何压缩pdf文件的大小?5分钟压缩pdf的方法推荐

如何压缩pdf文件的大小&#xff1f;在现代办公和学习中&#xff0c;PDF文件因其稳定性和广泛的兼容性被广泛使用。然而&#xff0c;随着文件内容的增多&#xff0c;制作好的PDF文件常常变得过大&#xff0c;给使用带来了诸多不便。无论是电子邮件附件的发送&#xff0c;还是在线…...

【SQL】[2BP01] ERROR: cannot drop table course because other objects depend on it

问题描述 在尝试执行以下SQL语句时&#xff0c;发生错误。 DROP TABLE Course RESTRICT;执行以上语句后&#xff0c;系统返回了一个错误提示&#xff1a; [2BP01] ERROR: cannot drop table course because other objects depend on it 详细&#xff1a;constraint sc_cno_…...

gbase8s之spring框架用druid中间件报语法错误

spring框架 调用druid中间件 时报这个错&#xff1a; MetaDataAccessException: Could not get Connection for extracting meta-data; nested exception is org.springframework.jdbc.CannotGetJdbcConnectionException: Failed to obtain JDBC Connection; nested exception …...

【网络安全】|nessus使用

1、扫描结果分析&#xff1a; Sev&#xff1a;漏洞的严重性级别 CVSS&#xff1a;量化漏洞严重性的标准&#xff0c;通过计算得出一个分数&#xff0c;分数越高表示漏洞越严重。 VPR&#xff1a;基于风险的评分系统&#xff0c;帮助组织优先处理风险最高的漏洞。 EPSS&#xf…...

CSRA2的LINUX操作系统24年11月2日上午上课笔记

几个查找命令&#xff1a; .whereis:查看文件的路径,查看可执行文件的路径&#xff0c;一级相应文档路径。 .which:查看系统可执行的文件的路径&#xff0c;以及命令的别名等信息 .local&#xff1a;他会将linux中的所有文件的路径信息保存到数据库中&#xff0c;在数据库中查…...

通过分解质因数求若干个数的最小公倍数

求最小公倍数的常规方法回顾 暴力枚举法 long long work(long long a,long long b) {for(long long imax(a,b);;i)if(i%a0&&i%b0)return i; }大数翻倍法 long long work(long long a,long long b) {if(a<b) swap(a,b);for(long long ia;;ia) // i 是 a 的倍数&#…...

数据库三范式(1NF、2NF、3NF)

1NF&#xff08;第一范式&#xff09; 定义&#xff1a;确保每一列都是原子值&#xff0c;即是不可分割的基础数据项。 所谓第一范式&#xff08;1NF&#xff09;是指在关系模型中&#xff0c;对于添加列的一个规范要求&#xff0c;所有的列都 应该是原子性的&#xff0c;即数…...

C语言_数据结构_顺序表

1. 本章重点 顺序表初始化顺序表尾插顺序表尾删顺序表头插顺序表头删顺序表查找顺序表在pos位置插入x顺序表删除pos位置的值顺序表销毁顺序表打印 2. 顺序表的概念及结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构&#xff0c;一般情况下采用数组存储…...

Llama 3.2 Vision Molmo:多模态开源生态系统基础

编者按&#xff1a; 视觉功能的融入对模型能力和推理方式的影响如何&#xff1f;当我们需要一个既能看懂图像、又能生成文本的 AI 助手时&#xff0c;是否只能依赖于 GPT-4V 这样的闭源解决方案&#xff1f; 我们今天为大家分享的这篇文章&#xff0c;作者的核心观点是&#xf…...

【数据结构与算法】第6课—数据结构之栈

文章目录 1. 栈2. 栈的初始化和栈的销毁3. 入栈和出栈&#xff08;压栈&#xff09;4. 取栈顶元素并打印5. 栈的练习题5.1 有效的括号 1. 栈 栈&#xff1a;也是一种线性表&#xff0c;其数据结构与动态顺序表的数据结构类似栈分为栈顶和栈底&#xff0c;在栈中&#xff0c;插入…...

开源全站第一个Nextron(NextJS+electron)项目--NextTalk:一款集成chatgpt的实时聊天工具

NextTalk 简介 该项目是一个基于Nextron(NextJSElectron)的桌面端实时聊天工具。 但由于使用了NextJS中的ssr及api route功能&#xff0c;该程序只能在开发环境运行。 关于生产版本&#xff1a;我将其网页端部分分离&#xff0c;并用Pake将其打包成桌面端&#xff0c;生产体…...

多样化的编程模型:并发与并行策略

因为经常看着某些框架设计的编程模型很晕&#xff0c;所以自己梳理总结了一下编程模型的分类&#xff0c;总共六个大类&#xff0c;基本所有常见框架设计的编程模型都是基于这六个大类来实现的&#xff0c;如果有错误的地方&#xff0c;请见谅并不吝赐教&#xff0c;感谢&#…...

npm入门教程2:npm历史

一、起源与诞生 时间背景&#xff1a;npm的诞生与Node.js的兴起紧密相关。Node.js是一个基于Chrome V8引擎的JavaScript运行环境&#xff0c;它允许JavaScript代码在服务器端运行。随着Node.js的流行&#xff0c;开发者们对于包管理和依赖解决的需求日益增长。诞生&#xff1a…...

Cuebric:用AI重新定义3D创作的未来

一、简介 Cuebric 是一家成立于2022年夏天的好莱坞创新公司,致力于为电影、电视、游戏和时尚等行业提供先进的AI多模态SaaS平台。自2024年1月正式推出以来,Cuebric 已经在市场上获得了广泛的认可和积极的反馈。目前,该平台正处于1.0版本的beta测试阶段,已募集约50万美元的…...

前端react常见面试题目(basic)

1. 如果 React 组件的属性没有传值&#xff0c;它的默认值是什么? 如果一个 React 组件的属性&#xff08;props&#xff09;没有传值&#xff0c;那么它的默认值会是 undefined。你可以通过组件内部的逻辑来设置默认值&#xff0c;比如使用逻辑运算符或者 ES6 的默认参数。 …...

机器人技术基础(4章逆运动解算和雅克比矩阵)

逆运动解算&#xff1a; 雅克比矩阵&#xff1a; 将动力学分析转向运动的物体 下图中的 n o y 反映了机器人的姿态矩阵&#xff0c; 最后一列 p 反应了机器人在空间中的位置&#xff1a;...

OpenGL入门002——顶点着色器和片段着色器

文章目录 一些概念坐标转换阶段顶点着色器片段着色器VBOVAO 实战简介main.cppCMakeLists.txt最终效果 一些概念 坐标转换阶段 概述&#xff1a; 模型空间、世界空间、视图空间和裁剪空间是对象在3D场景中经历的不同坐标变换阶段。每个空间对应渲染管道的一个步骤&#xff0c;…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...