LeetCode题解201.bitwise-and-of-numbers-range

题目地址

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
 *
 */
/**
 * @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;
};

LeetCode题解200.number-of-islands

题目地址 https://leetcode.com/problems/number-of-islands/description/ 题目描述 Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by …

LeetCode题解1218.longest-arithmetic-subsequence-of-given-difference

题目地址 https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/ 题目描述 给你一个整数数组 arr 和一个整数 difference，请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列，并返回其中最长的等差子序…

LeetCode题解1020.number-of-enclaves

题目地址 https://leetcode-cn.com/problems/number-of-enclaves/ 题目描述 给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。 移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。 返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。   示例 1： 输入…

LeetCode题解104.maximum-depth-of-binary-tree

题目地址 https://leetcode.com/problems/maximum-depth-of-binary-tree/description/ 题目描述 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the lo…

LeetCode题解1297.maximum-number-of-occurrences-of-a-substring

题目地址（1297. 子串的最大出现次数） https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring 题目描述 给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数： 子串中不同字母的数目必须小于等于 maxLetters 。 子串的…