leetcode 201. Bitwise AND of Numbers Range | 201. 数字范围按位与(Java) 偏执的太偏执、 2022-10-05 08:57 155阅读 0赞 ## 题目 ## [https://leetcode.com/problems/bitwise-and-of-numbers-range/][https_leetcode.com_problems_bitwise-and-of-numbers-range] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70] ## 题解 ## (这题暴力法超时了,最后还是参考了答案的思路) 最直观的解决方案就是:迭代范围内的每个数字,依次执行按位与运算,得到结果,但此方法在 \[m,n\] 范围较大的测试用例中超时。 正解如下: ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3] class Solution { public int rangeBitwiseAnd(int left, int right) { int shift = 0; // 同时右移 shift 位后,两数第一次相等 while (left >> shift != right >> shift) { if (left >> shift == 0 && right >> shift != 0) return 0; // 如果最高位不能对齐的话,则必无公共前缀 shift++; } return left >> shift << shift; // 见图1,目标是将虚线后面的位置0 } } 图1: ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 4] ##### 方法二:Brian Kernighan 算法 ##### ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 5] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 6] -------------------- ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 7] [https_leetcode.com_problems_bitwise-and-of-numbers-range]: https://leetcode.com/problems/bitwise-and-of-numbers-range/ [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/fd56981d206548ef8ad696b2c5f8cf02.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221005/0d803eac33f84928bdf2a34e8e09c8eb.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20221005/c028830af6964563bb6438b8a579802c.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]: /images/20221005/99f09d59029d4caa9dffa80eca2fc021.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 4]: /images/20221005/d2aeb2e853e54eff9b4907e9639eb830.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 5]: /images/20221005/f93983556db34ac6935c20354abfce64.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 6]: /images/20221005/fda7636e1c48429f9ee42e46c9bcae83.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 7]: /images/20221005/39cd34af215648bc89d976b67ec076e6.png
相关 leetcode 201. Bitwise AND of Numbers Range | 201. 数字范围按位与(Java) 题目 [https://leetcode.com/problems/bitwise-and-of-numbers-range/][https_leetcode.com_p 偏执的太偏执、/ 2022年10月05日 08:57/ 0 赞/ 156 阅读
相关 Bitwise AND of Numbers Range(C++数字范围按位与) (1)性质 class Solution { public: int rangeBitwiseAnd(int left, int ゞ 浴缸里的玫瑰/ 2022年08月31日 02:29/ 0 赞/ 134 阅读
相关 leetcode 201. Bitwise AND of Numbers Range Given a range \[m, n\] where 0 <= m <= n <= 2147483647, return the bitwise AND of all nu 我就是我/ 2022年07月27日 13:38/ 0 赞/ 160 阅读
相关 leetcode 201. Bitwise AND of Numbers Range 最长公共前缀问题 + 位操作 Given a range \[m, n\] where 0 <= m <= n <= 2147483647, return the bitwise AND of all nu Dear 丶/ 2022年06月08日 09:12/ 0 赞/ 128 阅读
相关 【LeetCode】201. Bitwise AND of Numbers Range > Given a range \[m, n\] where 0 <= m <= n <= 2147483647, return the bitwise AND of all 爱被打了一巴掌/ 2022年05月21日 10:05/ 0 赞/ 131 阅读
相关 LeetCode 201.Bitwise AND of Numbers Range (数字范围按位与) 给定范围 \[m, n\],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。 示例 1: 输入: 谁借莪1个温暖的怀抱¢/ 2022年04月15日 01:11/ 0 赞/ 140 阅读
相关 【Leetcode】201. Bitwise AND of Numbers Range(区间二进制数或运算) Given a range \[m, n\] where 0 <= m <= n <= 2147483647, return the bitwise AND of all nu 深藏阁楼爱情的钟/ 2022年01月30日 02:57/ 0 赞/ 148 阅读
相关 LeetCode 201. 数字范围按位与(Bitwise AND of Numbers Range) 201. 数字范围按位与 201. Bitwise AND of Numbers Range 题目描述 给定范围 \[m, n\],其中 0 <= m <= n <= 客官°小女子只卖身不卖艺/ 2021年11月22日 06:02/ 0 赞/ 147 阅读
还没有评论,来说两句吧...