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

相关文章

哈希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 &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

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

题目: 题解: 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 & MASK1) == 0) {return

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划