127 lines
2.5 KiB
Markdown
127 lines
2.5 KiB
Markdown
|
|
|||
|
|
## 题目地址
|
|||
|
|
https://leetcode.com/problems/bitwise-and-of-numbers-range/description/
|
|||
|
|
|
|||
|
|
## 题目描述
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
|
|||
|
|
|
|||
|
|
Example 1:
|
|||
|
|
|
|||
|
|
Input: [5,7]
|
|||
|
|
Output: 4
|
|||
|
|
Example 2:
|
|||
|
|
|
|||
|
|
Input: [0,1]
|
|||
|
|
Output: 0
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
## 思路
|
|||
|
|
|
|||
|
|
一个显而易见的解法是， 从m到n依次进行`求与`的操作。
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
|
|||
|
|
let res = m;
|
|||
|
|
for (let i = m + 1; i <= n; i++) {
|
|||
|
|
res = res & i;
|
|||
|
|
}
|
|||
|
|
return res;
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
但是， 如果你把这个solution提交的话，很显然不会通过， 会超时。
|
|||
|
|
|
|||
|
|
我们依旧还是用trick来简化操作。 我们利用的性质是， n个连续数字求与的时候，前m位都是1.
|
|||
|
|
|
|||
|
|
举题目给的例子：[5,7] 共 5， 6，7三个数字， 用二进制表示 101, 110,111,
|
|||
|
|
这三个数字特点是第一位都是1，后面几位求与一定是0.
|
|||
|
|
|
|||
|
|
再来一个明显的例子：[20, 24], 共 20， 21， 22， 23，24五个数字，二进制表示就是
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
0001 0100
|
|||
|
|
0001 0101
|
|||
|
|
0001 0110
|
|||
|
|
0001 0111
|
|||
|
|
0001 1000
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
这五个数字特点是第四位都是1，后面几位求与一定是0.
|
|||
|
|
|
|||
|
|
因此我们的思路就是， 求出这个数字区间的数字前多少位都是1了，那么他们求与的结果一定是前几位数字，然后后面都是0.
|
|||
|
|
|
|||
|
|
|
|||
|
|
## 关键点解析
|
|||
|
|
|
|||
|
|
|
|||
|
|
- n个连续数字求与的时候，前m位都是1
|
|||
|
|
|
|||
|
|
- 可以用递归实现， 个人认为比较难想到
|
|||
|
|
|
|||
|
|
- bit 运算
|
|||
|
|
|
|||
|
|
代码：
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
|
|||
|
|
(n > m) ? (rangeBitwiseAnd(m/2, n/2) << 1) : m;
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
> 每次问题规模缩小一半， 这是二分法吗？
|
|||
|
|
|
|||
|
|
## 代码
|
|||
|
|
|
|||
|
|
语言支持：JavaSCript，Python3
|
|||
|
|
|
|||
|
|
JavaScript Code:
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
/*
|
|||
|
|
* @lc app=leetcode id=201 lang=javascript
|
|||
|
|
*
|
|||
|
|
* [201] Bitwise AND of Numbers Range
|
|||
|
|
*
|
|||
|
|
*/
|
|||
|
|
/**
|
|||
|
|
* @param {number} m
|
|||
|
|
* @param {number} n
|
|||
|
|
* @return {number}
|
|||
|
|
*/
|
|||
|
|
var rangeBitwiseAnd = function(m, n) {
|
|||
|
|
let count = 0;
|
|||
|
|
while (m !== n) {
|
|||
|
|
m = m >> 1;
|
|||
|
|
n = n >> 1;
|
|||
|
|
count++;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
return n << count;
|
|||
|
|
};
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
Python Code:
|
|||
|
|
|
|||
|
|
```python
|
|||
|
|
class Solution:
|
|||
|
|
def rangeBitwiseAnd(self, m: int, n: int) -> int:
|
|||
|
|
cnt = 0
|
|||
|
|
while m != n:
|
|||
|
|
m >>= 1
|
|||
|
|
n >>= 1
|
|||
|
|
cnt += 1
|
|||
|
|
|
|||
|
|
return m << cnt
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**复杂度分析**
|
|||
|
|
|
|||
|
|
- 时间复杂度：最坏的情况我们需要循环N次，最好的情况是一次都不需要， 因此时间复杂度取决于我们移动的位数，具体移动的次数取决于我们的输入，平均来说时间复杂度为 $O(N)$，其中N为M和N的二进制表示的位数。
|
|||
|
|
- 空间复杂度：$O(1)$
|
|||
|
|
|
|||
|
|
|