郑州外语网站建站优化网站建设与维护 目录

郑州外语网站建站优化,网站建设与维护 目录,西宁网站推广,网页图片格式题目链接#xff1a;Bitwise AND of Numbers Rangeleetcode​ 题目与直觉理解 题目#xff1a;给定两个整数 left 和 right#xff0c;表示闭区间 [left, right]#xff0c;返回区间内所有整数的按位与结果。leetcode​ 约束#xff1a;0 left right 2^31…题目链接Bitwise AND of Numbers Rangeleetcode​题目与直觉理解题目给定两个整数 left 和 right表示闭区间 [left, right]返回区间内所有整数的按位与结果。leetcode​约束0 left right 2^31 - 1也就是 32 位非负整数范围。leetcode​直觉上如果区间很大比如从 1 到一个非常大的数那么某些二进制位在中间某个数上一定会变成 0最后按位与结果也会在这些位上变成 0。唯一可能保持为 1 的只能是整个区间里从头到尾都从未变化过的那部分高位前缀。初始错误思路只看最高位 1一开始容易想到的一个思路是把每个数都看成 32 位整数找最高位的 1 在哪一位。如果区间内所有数的最高位 1 都在同一位就认为结果是只有这一位是 1其余位为 0否则返回 0。这个思路抓住了高位这个感觉但有两个致命问题只看最高位是否一致忽略了更低位可能也一直为 1。例如区间 [6, 7]6 1107 111最高位 1 都在同一位但真实结果是 110 (6)而不是 100 (4)。没有真正找到公共前缀的全部部分等于只保留了最左边那一位。这说明我们需要的不是最高位而是 left 和 right 的完整二进制公共前缀。正确核心找二进制公共前缀这道题有一个非常典型的结论区间 [left, right] 所有数的按位与结果就是 left 和 right 在二进制下的 公共前缀其余低位全部变为 0。leetcode​原因可以这样理解从 left 增加到 right 的过程中只要某一位在这个过程中经历过从 0 变 1 或从 1 变 0 的变化那么这一位在某个数上必然是 0按位与之后这个位就会变 0。只有在 left 和 right 对应位完全一致、且在整个区间内不发生变化的那一段高位前缀才能在结果中保持为 1。所以问题变成如何高效地求出 left 和 right 的公共前缀经典解法不断右移直到相等一种常见且优雅的做法是用一个计数 shift 0 记录右移的次数。当 left right 时同时右移 left 和 right 一位left 1; right 1;并让 shift。循环直到 left right。此时的 left或 right就是它们的公共前缀。最后将这个公共前缀左移 shift 位把低位补回 0left shift即为答案。leetcode​示意伪代码C 风格cppint rangeBitwiseAnd(int left, int right) {int shift 0;while (left right) {left 1;right 1;shift;}return left shift;}这里用 while (left right) 和 while (left ! right) 在题目保证 left right 的前提下是等价的选择哪个更多是风格问题。为什么右移有效从丢掉一定为 0 的尾部看每次右移一位在本质上是在做丢掉当前的最低位。当某一位开始在 left 与 right 之间发生差异时说明在区间 [left, right] 内这一位必然经历了 0/1 的变化。因为按位与对所有数都要是 1 才能为 1一旦某一位在区间里出现过 0最终结果这位一定是 0。所以只要 left right说明仍有某些低位是不稳定的在中间会变化这些低位我们干脆整体右移扔掉。当右移到 left right 的那一刻说明剩下的所有位在整个区间内已经完全一致它们就是公共前缀。最后再通过左移 shift 位把这些高位放回原来的位置低位补 0得到最终按位与结果。细节问题while 条件与移位方向关于你在过程中的几个思考点顺便也整理一下left ! right 还是 left right题目保证 left right输入不会出现 left right。leetcode​又因为每一步都同时右移 left 和 right不会人为制造 left right 的情况。所以 while (left right) 和 while (left ! right) 在这题上效果等价用哪一个主要看你觉得哪一种更清晰。算术右移还是逻辑右移左移只有一个操作符 没有算术/逻辑之分。右移在 C/C/Java 中 对有符号整数通常是算术右移保留符号位Java 还有 是逻辑右移。本题保证 0 left, right 2^31 - 1全部是非负数即最高位为 0不会出现符号扩展问题所以用 即可算术右移和逻辑右移在这里表现一致。leetcode​left 0 需要特判吗不需要。left 0 时区间 [0, right] 一定包含 0整个区间按位与结果必然为 0。在上面的循环中left 右移始终为 0。right 不断右移直到也变为 0此时 left right 0。最终返回 0 shift仍然是 0符合预期无需额外分支。示例推演验证思路以几个典型例子推一遍这个过程可以更有信心left 6 (110)right 7 (111)第一次left 3 (11)right 3 (11)shift 1。循环结束返回 3 1 110 (6)与真实按位与结果一致。left 12 (1100)right 15 (1111)第一次1100 - 1101111 - 111shift 1。第二次110 - 11111 - 11shift 2。返回 3 2 1100 (12)与逐个按位与的结果一致。left 1right 2147483647不断右移后最终两者都会变成 0shift 为 31。返回 0 31 0符合题目示例。总结适合写成博客的结构建议如果写成一篇博客大致可以按下面结构组织题目描述与样例直观思路为什么要找公共前缀错误/不完整思路只看最高位 1 的陷阱正确解法一右移找公共前缀你现在实现的解法思路描述代码实现示例推演边界条件讨论left 0、移位类型等复杂度分析时间 O(logN)空间 O(1)小结这类题的共性——“范围按位运算往往等价于端点的公共前缀”https://leetcode.com/problems/bitwise-and-of-numbers-range/?envTypestudy-plan-v2envIdtop-interview-150https://leetcode.com/problems/bitwise-and-of-numbers-range/submissions/1876552823/?envTypestudy-plan-v2envIdtop-interview-150