C++实现LeetCode(201.数字范围位相与)

[LeetCode] 201.Bitwise AND of Numbers Range 数字范围位相与

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

Credits:
Special thanks to @amrsaqr for adding this problem and creating all test cases.

又是一道考察位操作Bit Operation的题，相似的题目在LeetCode中还真不少，比如Repeated DNA Sequences 求重复的DNA序列， Single Number 单独的数字,   Single Number II 单独的数字之二 ， Grey Code 格雷码，和 Reverse Bits 翻转位 等等，那么这道题其实并不难，我们先从题目中给的例子来分析，[5, 7]里共有三个数字，分别写出它们的二进制为：

101　　110　　111

相与后的结果为100，仔细观察我们可以得出，最后的数是该数字范围内所有的数的左边共同的部分，如果上面那个例子不太明显，我们再来看一个范围[26, 30]，它们的二进制如下：

11010　　11011　　11100　　11101　　11110

发现了规律后，我们只要写代码找到左边公共的部分即可，我们可以从建立一个32位都是1的mask，然后每次向左移一位，比较m和n是否相同，不同再继续左移一位，直至相同，然后把m和mask相与就是最终结果，代码如下：

解法一：

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int d = INT_MAX;
        while ((m & d) != (n & d)) {
            d <<= 1;
        }
        return m & d;
    }
};

此题还有另一种解法，不需要用mask，直接平移m和n，每次向右移一位，直到m和n相等，记录下所有平移的次数i，然后再把m左移i位即为最终结果，代码如下：

解法二：

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int i = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            ++i;
        }
        return (m << i);
    }
};

下面这种方法有点叼，就一行搞定了，通过递归来做的，如果n大于m，那么就对m和n分别除以2，并且调用递归函数，对结果再乘以2，一定要乘回来，不然就不对了，就举一个最简单的例子，m = 10, n = 11，注意这里是二进制表示的，然后各自除以2，都变成了1，调用递归返回1，这时候要乘以2，才能变回10，参见代码如下：

解法三：

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        return (n > m) ? (rangeBitwiseAnd(m / 2, n / 2) << 1) : m;
    }
};

下面这种方法也不错，也很简单，如果m小于n就进行循环，n与上n-1，那么为什么要这样与呢，举个简单的例子呗，110与上(110-1)，得到100，这不就相当于去掉最低位的1么，n就这样每次去掉最低位的1，如果小于等于m了，返回此时的n即可，参见代码如下：

解法四：

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        while (m < n) n &= (n - 1);
        return n;
    }
};

参考资料：

https://discuss.leetcode.com/topic/13508/one-line-c-solution

https://discuss.leetcode.com/topic/12133/bit-operation-solution-java

https://discuss.leetcode.com/topic/20176/2-line-solution-with-detailed-explanation

到此这篇关于C++实现LeetCode(201.数字范围位相与)的文章就介绍到这了,更多相关C++实现数字范围位相与内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(190.颠倒二进制位)

    [LeetCode] 190. Reverse Bits 颠倒二进制位 Reverse bits of a given 32 bits unsigned integer. Example 1: Input: 00000010100101000001111010011100 Output: 00111001011110000010100101000000 Explanation: The input binary string 00000010100101000001111010011100 re

  • C++实现LeetCode(198.打家劫舍)

    [LeetCode] 198. House Robber 打家劫舍 You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security

  • C++实现LeetCode(309.买股票的最佳时间含冷冻期)

    [LeetCode] 309.Best Time to Buy and Sell Stock with Cooldown 买股票的最佳时间含冷冻期 Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as

  • C++实现LeetCode(191.位1的个数)

    [LeetCode] 191.Number of 1 Bits 位1的个数 Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight). For example, the 32-bit integer '11' has binary representation 00000000000000000000000

  • C++实现LeetCode(199.二叉树的右侧视图)

    [LeetCode] 199.Binary Tree Right Side View 二叉树的右侧视图 Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. For example: Given the following binary tree,    1     

  • C++实现LeetCode(203.移除链表元素)

    [LeetCode] 203.Remove Linked List Elements 移除链表元素 Remove all elements from a linked list of integers that have value val. Example Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6 Return: 1 --> 2 --> 3 --> 4 --> 5 Credits

  • C++实现LeetCode(188.买卖股票的最佳时间之四)

    [LeetCode] 188.Best Time to Buy and Sell Stock IV 买卖股票的最佳时间之四 Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most k transactions. Note: You m

  • C++实现LeetCode(202.快乐数)

    [LeetCode] 202.Happy Number 快乐数 Write an algorithm to determine if a number is "happy". A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits,

  • C++实现LeetCode(201.数字范围位相与)

    [LeetCode] 201.Bitwise AND of Numbers Range 数字范围位相与 Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. For example, given the range [5, 7], you should return 4. Credits: Special t

  • C++实现LeetCode(验证数字)

    [LeetCode] Valid Number 验证数字 Validate if a given string can be interpreted as a decimal number. Some examples: "0" => true " 0.1 " => true "abc" => false "1 a" => false "2e10" => true "

  • C++实现LeetCode(2.两个数字相加)

    [LeetCode] 2. Add Two Numbers 两个数字相加 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked

  • C++实现LeetCode(9.验证回文数字)

    [LeetCode] 9. Palindrome Number 验证回文数字 Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward. Example 1: Input: 121 Output: true Example 2: Input: -121 Output: false Explanation: From left

  • C++实现LeetCode(137.单独的数字之二)

    [LeetCode] 137. Single Number II 单独的数字之二 Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you

  • C++实现LeetCode(136.单独的数字)

    [LeetCode] 136.Single Number 单独的数字 Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

  • C++实现LeetCode(129.求根到叶节点数字之和)

    [LeetCode] 129. Sum Root to Leaf Numbers 求根到叶节点数字之和 Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum

  • SQL实现LeetCode(180.连续的数字)

    [LeetCode] 180.Consecutive Numbers 连续的数字 Write a SQL query to find all numbers that appear at least three times consecutively. +----+-----+ | Id | Num | +----+-----+ | 1  |  1  | | 2  |  1  | | 3  |  1  | | 4  |  2  | | 5  |  1  | | 6  |  2  | | 7  |

  • C++ Leetcode实现从英文中重建数字

    C++ Leetcode实现从英文中重建数字

    目录 题目 分析 代码 题目 分析 首先我们先分析每个字母的组成,然后发现一些字符只在一个单词中出现,我们先去统计一下这些单词个数. z,w,u,x,g都只出现在一个数字中,也就是0,2,4,6,8,我们用哈希表统计一下s字符串中各个字符的数量,就可以知道0,2,4,6,8的数量,然后我们注意一下只在两个数字中出现的字符. h 只在 3,8 中出现.由于我们已经知道了 8 出现的次数,因此可以计算出 3 出现的次数. f 只在 4,5 中出现.由于我们已经知道了 4 出现的次数,因此可以计算出

  • Java C++题解leetcode消失的两个数字实例

    Java C++题解leetcode消失的两个数字实例

    目录 题目要求 思路:数学推导 Java C++ Rust 总结 题目要求 思路:数学推导 不重复的数组序列可以根据高斯公式计算所有元素的总和: 用当前数组长度加上两个缺失的数字可以得到所有数字长度,即可应用公式. 减去当前数组和即可得到缺失数字和sumsumsum: 两个缺失的数字分别位于m=sum2m=\frac{sum}{2}m=2sum两边: 遍历当前数组中所有小于(或大于)mmm的值,找到缺失的一个: 同样利用两个“和”的差值得到: 利用sumsumsum即可得到另一个. Java c

随机推荐