【算法训练营】最近公共祖先+求最大连续bit数

1.最近公共祖先

题目链接

• 【题目解析】：
  最近公共祖先表示距离两个节点最近的公共父节点，这道题考察二叉树。
• 【解题思路】：
  题目所描述的满二叉树如下： 1 / \ 2 3 / \ / \ 4 5 6 7 上述树中子节点与父节点之间的关系为root = child / 2
  所以如果a ！= b，就让其中的较大数除以2， 如此循环直到a == b 即是原来两个数的最近公共祖先 比如： 2
  和7的最近公共祖先：7/2 = 3 —> 3/2 = 1， 2/2 = 1， 得到1为它们的公共祖先
  代码：

class LCA {
public:
int getLCA(int a, int b) {
 while (a != b)
  {
    if (a > b)
   a /= 2;
    else
    b /= 2;
  }
  return a;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13

求最大连续bit数

题目链接

【题目解析】：
这道题考察位运算

【解题思路】：
根据位运算，获取每一位的二进制值。获取第i位的值： (n >> i) & 1。如果1连续，则计数累加，如果不连
续，则从0开始计数。

代码

#include
#include
#include
using namespace std;
int main()
{
int n;
while (cin >> n)
{
int count = 0, maxCount = 0;
  // n右移32次就变为0
while (n)
{
    //获取当前位的二进制值
if (n & 1)
{
      //如果1的值连续，计数累加，并且跟新最大计数
++count;
maxCount = max(count, maxCount);
}
else
    {
      //如果1的值不连续，重新累加
count = 0;
    }
    //右移一次，为获取下一位二进制值做准备
n = n >> 1;
}
cout << maxCount << endl;
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32