Skip to content

Latest commit

 

History

History
124 lines (90 loc) · 2.28 KB

201.bitwise-and-of-numbers-range.md

File metadata and controls

124 lines (90 loc) · 2.28 KB

题目地址

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依次进行求与的操作。

    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 运算

代码:

(n > m) ? (rangeBitwiseAnd(m/2, n/2) << 1) : m;

每次问题规模缩小一半, 这是二分法吗?

代码

/*
 * @lc app=leetcode id=201 lang=javascript
 *
 * [201] Bitwise AND of Numbers Range
 *
 * https://leetcode.com/problems/bitwise-and-of-numbers-range/description/
 *
 * algorithms
 * Medium (35.58%)
 * Total Accepted:    78.9K
 * Total Submissions: 221.3K
 * Testcase Example:  '5\n7'
 *
 * 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
 */
/**
 * @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;
};