【题解】Bitwise AND of Numbers Range

矫情吗；* 2022-08-07 14:56 118阅读 0赞

这道题是leetcode上新出的题目，有兴趣做了一下，轻松通过，具体代码如下所示

  1. class Solution {
  2. public:
  3.     int rangeBitwiseAnd(int m, int n) {
  4.         stack<int> m_stack, n_stack;
  5.         int one_num = 0;
  6.         int answer = 0;
  8.         if (m == n)
  9.         {
  10.             return m;
  11.         }
  12.         if (0 == m)
  13.         {
  14.             return 0;
  15.         }
  16.         while (0 != m)
  17.         {
  18.             one_num = m&(m^(m-1));
  19.             m_stack.push(one_num);
  20.             m -= one_num;
  21.         }
  22.         while (0 != n)
  23.         {
  24.             one_num = n&(n^(n-1));
  25.             n_stack.push(one_num);
  26.             n -= one_num;
  27.         }
  28.         while (!m_stack.empty() && !n_stack.empty())
  29.         {
  30.             if (m_stack.top() == n_stack.top())
  31.             {
  32.                 answer += m_stack.top();
  33.                 m_stack.pop();
  34.                 n_stack.pop();
  35.             }
  36.             else
  37.             {
  38.                 break;
  39.             }
  40.         }
  41.         return answer;
  42.     }
  43. };

思路如下，首先判断输入的合法性，然后去求m的二进制表述中为1的那些位代表的数字，并将其放入堆栈中，如m=3时，堆栈中有（1,2）这两个元素，同理将n进行类似的操作，如n=4时，堆栈中有（4）这一个元素，然后对m和n的堆栈同时进行弹栈，当栈顶元素相同的时候，将栈顶元素加入结果中，不同的时候退出循环。

通过这样的处理，就可以避免去一个个计算每隔元素的1的位置，然后进行与运算。

发表评论

表情：
评论列表 （有 0 条评论，118人围观）

还没有评论，来说两句吧...

相关阅读