leetcode-201. 数字范围按位与

2023-12-30 17:08

本文主要是介绍leetcode-201. 数字范围按位与,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。

示例 1:

输入: [5,7]
输出: 4

示例 2:

输入: [0,1]
输出: 0

解题思路

暴力版,从m到n一路按位与下去,会超时。

Period Rule

Note the 1s and 0s are changing following a rule: the number of 1s and 0s in digit i are 2^i, so for digit i, there will only be 2^i / 2 1s and 2^i / 2 0s. If the number between left and right is larger than 2^i / 2, then there must be 0s, so after AND the digit must be 0. If the number is smaller than 2^i / 2, then the result depends on left and right. If left and right at the current digit are both 0, then it must be 0. If one of them is 0, then the result is 0. Only when left and right both have 1 on the digit, will the result be 1.

Time complexity: o ( log ⁡ n ) o(\log n) o(logn)
Space complexity: o ( 1 ) o(1) o(1)

官方题解版

以计算[9, 12]为例,先写出来每个数字对应的二进制形式:

9: 	0 0 0 0 1 0 0 1
10: 0 0 0 0 1 0 1 0
11: 0 0 0 0 1 0 1 1
12: 0 0 0 0 1 1 0 0

因为是从mn的连续区间,所以必然有某个位x满足:该数字的x位为0,x后面的位都是1,下一个数字的x位是1,x后面的数字都是0
这样按位与之后,会导致x及x之后所有位都是0
因此最终的结果实际上是求区间开头和区间结尾的二进制表示中的共同前缀。

求二进制共同前缀的方法:
位移法
将两个数字同时向右移位,并记录移位的次数。当两个数字相等时,就得到了共同的前缀,再将这个共同前缀向左移位移回原先大小即可。

时间复杂度 o ( l o g 2 n ) o(log_2n) o(log2n),其中n是区间大小

Brian Kernighan 算法
背景知识:将一个数nn - 1按位与之后,可以去除n最右边的1

考虑对于区间右边界n,不断去除最右边的1,当n <= m时,非公共前缀的1就全部去掉了,此时的n就是答案

时间复杂度仍然是 o ( l o g 2 n ) o(log_2n) o(log2n)

代码

Period Rule

class Solution:def rangeBitwiseAnd(self, left: int, right: int) -> int:number_between = right - left + 1res = 0period_len = 1while period_len <= right:if number_between <= period_len:res += left & right & period_lenperiod_len *= 2return res

位移版

class Solution:def rangeBitwiseAnd(self, m: int, n: int) -> int:shift = 0while m < n:m >>= 1n >>= 1shift += 1return m << shift

Brian Kernighan 算法

class Solution:def rangeBitwiseAnd(self, m: int, n: int) -> int:while n > m:n &= (n - 1)return n

这篇关于leetcode-201. 数字范围按位与的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/553490

相关文章

使用PyTorch实现手写数字识别功能

《使用PyTorch实现手写数字识别功能》在人工智能的世界里,计算机视觉是最具魅力的领域之一,通过PyTorch这一强大的深度学习框架,我们将在经典的MNIST数据集上,见证一个神经网络从零开始学会识... 目录当计算机学会“看”数字搭建开发环境MNIST数据集解析1. 认识手写数字数据库2. 数据预处理的

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

Java数字转换工具类NumberUtil的使用

《Java数字转换工具类NumberUtil的使用》NumberUtil是一个功能强大的Java工具类,用于处理数字的各种操作,包括数值运算、格式化、随机数生成和数值判断,下面就来介绍一下Number... 目录一、NumberUtil类概述二、主要功能介绍1. 数值运算2. 格式化3. 数值判断4. 随机

使用Python合并 Excel单元格指定行列或单元格范围

《使用Python合并Excel单元格指定行列或单元格范围》合并Excel单元格是Excel数据处理和表格设计中的一项常用操作,本文将介绍如何通过Python合并Excel中的指定行列或单... 目录python Excel库安装Python合并Excel 中的指定行Python合并Excel 中的指定列P

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

从去中心化到智能化:Web3如何与AI共同塑造数字生态

在数字时代的演进中,Web3和人工智能(AI)正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术,正相互交织,共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界,并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &