【面试经典150 | 位运算】数字范围按位与
文章目录
- Tag
- 题目来源
- 题目解读
- 解题思路
- 方法一:公共前缀
- 方法二:n & (n-1)
- 写在最后
Tag
【位运算】
题目来源
201. 数字范围按位与
题目解读
计算给定区间内所有整数的按位与的结果。
解题思路
本题朴素的方法是直接将区间内的所有整数按位与,时间复杂度为 O ( n ) O(n) O(n),数据量已经达到 1 0 1 0 10^10 1010,必然超时。接下来介绍两种不会超时的方法。
方法一:公共前缀
先来说说什么是公共前缀,公共前缀指的是所有需要按位与计算的数对应的二进制数从高位到低位公共的二进制字符。比如 [9, 12] 的公共前缀为 0000 1,解释如图所示:
根据上图,我们发现连续数字按位与的值等于公共前缀后面再补上剩余的 0。 这个规律正确吗?我们来证明一下。假设对于连续区间内所有数的二进制数,前 i 位(从高位开始数)均相同,第 i+1 位开始不同,由于区间 [m, n] 连续,所以区间内从小到大先枚举出来的数的第 i+1 位为 0,枚举出来相对靠后数的第 i+1 位全部为 1。 并且一定存在连续的两个数 x 和 x+1 满足 x 的第 i+1 位为 0,后面全为 1,x+1 的第 i+1 位为 1,后面全为 0,对应上图中的例子即为 11 和 12。这种形如 0111… 和 1000… 的二进制串的按位与的结果一定为 0000…,因此第 i+1 位开始的剩余位均为 0,前 i 位由于均相同,因此按位与结果不变。最后的答案即为二进制字符串的公共前缀再用零补上后面的剩余位。
实现代码
class Solution {
public:int rangeBitwiseAnd(int left, int right) {int res = 0;for (int i = 0; i < 32; ++i) {for (int num = left; num <= right; ++num) {res |= num & 1;num >>= 1;}}return res;}
};
复杂度分析
时间复杂度: O ( l o g n ) O(logn) O(logn), n n n 为 right 的值、
空间复杂度: O ( 1 ) O(1) O(1)。
方法二:n & (n-1)
根据方法一,我们知道需要保留的是区间 [m, n] 中的公共前缀,也就是去掉非公共前缀的部分,我们可以使用 n & (n-1) 来去除,直到 m = n,最后返回 n 即可。于是有代码:
实现代码
class Solution {
public:int rangeBitwiseAnd(int m, int n) {while (m < n) {n &= (n-1);}return n;}
};
复杂度分析
时间复杂度: O ( l o g n ) O(logn) O(logn), n n n 为 right 的值、
空间复杂度: O ( 1 ) O(1) O(1)。
写在最后
如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。
最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。
相关文章:
【面试经典150 | 位运算】数字范围按位与
文章目录 Tag题目来源题目解读解题思路方法一:公共前缀方法二:n & (n-1) 写在最后 Tag 【位运算】 题目来源 201. 数字范围按位与 题目解读 计算给定区间内所有整数的按位与的结果。 解题思路 本题朴素的方法是直接将区间内的所有整数按位与&…...
推介会如何做好媒体宣传
传媒如春雨,润物细无声,大家好,我是51媒体网胡老师。 推介会是一种专为企业、社会组织和团体、政府等提供的展示自身特点、产品和政策的活动形式,旨在促进交流活动,形成合作,从而带来共同利益。推介会的本…...
【ROS导航Navigation】五 | 导航相关的消息 | 地图 | 里程计 | 坐标变换 | 定位 | 目标点和路径规划 | 激光雷达 | 相机
致谢:ROS赵虚左老师 Introduction Autolabor-ROS机器人入门课程《ROS理论与实践》零基础教程 参考赵虚左老师的实战教程 一、地图 nav_msgs/MapMetaData 地图元数据,包括地图的宽度、高度、分辨率等。 nav_msgs/OccupancyGrid 地图栅格数据&#…...
什么是脏读、不可重复读、幻读讲解
数据库隔离级别是数据库管理系统中一个重要的概念,它定义了事务之间的可见性和影响。在多用户并发访问数据库时,隔离级别能够确保事务之间的相互独立性,避免数据不一致的问题。本文将深入探讨三种常见的并发问题:脏读、不可重复读…...
2018年五一杯数学建模C题江苏省本科教育质量综合评价解题全过程文档及程序
2019年五一杯数学建模 C题 江苏省本科教育质量综合评价 原题再现 随着中国的改革开放,国家的综合实力不断增强,中国高等教育发展整体已进入世界中上水平。作为一个教育大省,江苏省的本科教育发展在全国名列前茅,而江苏省13个地级…...
第四代智能井盖传感器:万宾科技助力城市安全
在繁华喧嚣的城市里人来人往,井盖作为基础设施的一个组成部分在路面上分布范围广。然而这些看似普通的井盖却存在着位移、水浸的风险,可能给我们的生活带来诸多不便,更会威胁到我们的人身安全。如何有效监测和管理井盖的状态,成为…...
[Jenkins] Docker 安装Jenkins及迁移流程
系统要求 最低推荐配置: 256MB可用内存1GB可用磁盘空间(作为一个Docker容器运行jenkins的话推荐10GB) 为小团队推荐的硬件配置: 1GB可用内存50 GB 可用磁盘空间 软件配置: Java 8—无论是Java运行时环境(JRE)还是Java开发工具包(JDKÿ…...
第七篇 基于JSP 技术的网上购书系统——新品上架、推荐产品、在线留言、搜索功能实现(网上商城、仿淘宝、当当、亚马逊)
目录 1.新品上架 1.1功能说明 1.2界面设计 1.3处理流程 1.4数据来源和算法 1.4.1数据来源 1.4.2查询条件 1.4.3表间关系 1.4.4相关sql实例 2.推荐产品 2.1功能说明 2.2界面设计 2.3处理流程 2.4数据来源和算法 2.4.1数据来源 2.4.2查询条件 2.4.3表间关…...
IntelliJ IDE 插件开发 |(一)快速入门
前言 IntelliJ IDEA 作为 Java 开发的首选 IDE,其强大、方便之处不必多说。不过,由于个人或者团队的个性化需求,我们或多或少会想对其功能进行拓展,这时就需要开发插件(在 IntelliJ 平台下的所有 IDE 均可运行&#x…...
【Ubuntu】Windows远程Ubuntu系统
步骤 开启ssh服务并开放22端口关闭防火墙ufw或iptables ;或者将远程端口添加到入站与出站规则安装xrdp并将xrdp用户添加到ssl-cert用户组mstsc 远程,输入账号密码 1、开启ssh服务 1.1. 查看ssh是否已经开启 sudo ps -e | grep ssh如果最后返回是sshd…...
pipeline jenkins流水线
Pipeline 是 Jenkins 中一种灵活且强大的工作流机制,它允许您以代码的形式来定义和管理持续集成和持续交付的流程。 Pipeline 的作用主要体现在以下几个方面: 可编排的构建流程:使用 Pipeline,您可以将一个或多个阶段(…...
软件工程理论与实践 (吕云翔) 第六章 面向对象分析课后习题及其解析
第六章 面向对象分析 知识点: 一个典型的软件系统通常包括的内容为:它使用数据结构(对象模型),执行操作(动态模型),并且完成数据值的变化(功能模型)。 3种模型之间的关…...
langchain(1):使用LangChain 调用 openai 的 text/chat model
文章目录 重要参考OPENAI API调用 Text 模型调用 Chat 模型消息角色 Chat 模型 vs Text 模型 通过 LangChain 调用 Text 和 Chat 模型调用 text 模型调用 chat 模型 重要参考 langchain 中文网 langchain api openai api 文档 huggingface LangChain 是一个全方位的、基于大…...
rabbitMQ的扇出模式(fanout发布订阅)的生产者与消费者使用案例
扇出模式 fanout 发布订阅模式 生产者 生产者发送消息到交换机(logs),控制台输入消息作为生产者的消息发送 package com.esint.rabbitmq.work03;import com.esint.rabbitmq.RabbitMQUtils; import com.rabbitmq.client.Channel;import java.util.Scanne…...
VSCode打开Json 文件格式化
在VSCode中打开JSON文件时,你可以使用以下步骤来格式化JSON并显示为多行: 使用快捷键: 在打开的JSON文件中,使用快捷键格式化文档。 Windows/Linux:Shift Alt FmacOS:Shift Option F 右键菜单ÿ…...
【C++】:STL——标准模板库介绍 || string类
📚1.什么是STL STL(standard template libaray-标准模板库):是C标准库的重要组成部分,不仅是一个可复用的组件库,而且 是一个包罗数据结构与算法的软件框架 📚2.STL的版本 原始版本 Alexander Stepanov、Meng Lee 在…...
Python小白之PyCharm仍然显示“No module named ‘xlwings‘”
Python小白之“没有名称为xlwings‘的模块”-CSDN博客文章浏览阅读8次。cmd 打开命令行,输入python出现>>>的提示格,输入import xlwings 回车,正常报错:No module named xlwings。输入python 回车后,再输入im…...
在Uni-app中实现计时器效果
本文将介绍如何在Uni-app中使用Vue.js的计时器功能实现一个简单的计时器效果。 首先,我们需要创建一个包含计时器的组件。以下是一个基本的计时器组件示例: <template><div class"timer"><p>{{ formatTime }}</p><…...
Linux脚本shell中将Windos格式字符转换为unix
众所周知,windos的文档直接复制到linux服务器上去,是需要进行格式转换的,否则可能出现以下报错: 解决方法: vim 脚本 输入 :set ff ##会显示字符格式 :set ffunix ##转换为unix格式 :wq ##保存退出...
【分布式】MIT 6.824 Lab 2B实现细节分析
基于6.824 2020版 http://nil.csail.mit.edu/6.824/2020/schedule.html Lab 2A(选举)一天就完成了,主要是第一次开始写Raft需要稍微熟悉一下,但是几乎不用修改,很容易就通过了。不过到了Lab 2B就会发现2A能够通过纯属侥…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
