【笔试常见编程题06】最近公共祖先、求最大连续bit数、二进制插入、查找组成一个偶数最接近的两个素数

1. 最近公共祖先

将一棵无穷大满二叉树的结点按根结点一层一层地从左往右编号，根结点编号为1。现给定a，b为两个结点。设计一个算法，返回a、b最近的公共祖先的编号。注意其祖先也可能是结点本身。
测试样例：
2，3
返回：1
示例 1
输入
输出

思路1:
节点除2就是parent
大的先除直到两个数相等

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

2. 求最大连续bit数

求一个int类型数字对应的二进制数字中1的最大连续数，例如3的二进制为00000011，最大连续2个1
数据范围：数据组数：1 ≤ t ≤ 5, 1 ≤ n ≤ 500000
进阶：时间复杂度：O(logn)空间复杂度：O(1)
输入描述
输入一个int类型数字
输出描述
输出转成二进制之后连续1的个数
示例 1
输入
200
输出
2
说明
200的二进制表示是11001000，最多有2个连续的1

思路1:
从右往左找连续的1
更新计数器，直到找到最长的连续的1

int main() {
    int a = 0, count = 0;
    while (cin >> a) {
        int temp = 0;
        for (int i = 0; i < 32; i++) {
            if (1 << i & a)
                temp++;
            if ((1 << i & a) == 0 || i == 31) { //如果a=-1,二进制全是1,需要加一个条件i == 31就进来
                count = max(temp, count);  
                temp = 0;
            }     
        }
        cout << count << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

思路2:
求二进制数有几个1，n & n-1
求二进制数最长连续的1，n & (n << 1)

int main() 
{
    int n;
    while (cin >> n) {
        int count = 0;
        while (n) {
            n = n & (n << 1);
            count++;
        }
        cout << count << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3. 二进制插入

给定两个32位整数n和m，同时给定i和j，将m的二进制数位插入到n的二进制的第j到第i位,保证n的第j到第i位均为零，且m的二进制位数小于等于i-j+1，其中二进制的位数从0开始由低到高。
测试样例：
1024，19，2，6
返回：1100
示例 1
输入
输出

思路1:

class BinInsert {
public:
    int binInsert(int n, int m, int j, int i) {
        m <<= j;
        return n + m;
    }
};
1
2
3
4
5
6
7

class BinInsert {
public:
    int binInsert(int n, int m, int j, int i) {
        while(j) {
            m *= 2;
            j--;
        }
        return n + m;
    }
};
1
2
3
4
5
6
7
8
9
10

4. 查找组成一个偶数最接近的两个素数

任意一个偶数（大于2）都可以由2个素数组成，组成偶数的2个素数有很多种情况，本题目要求输出组成指定偶数的两个素数差值最小的素数对。
数据范围：输入的数据满足
输入描述
输入一个大于2的偶数
输出描述
从小到大输出两个素数
示例 1
输入
20
输出
7
13
示例 2
输入
4
输出
2
2

思路1:
中间组成偶数的两个素数差值最小
从中间往两边找差值最小素数

#include <iostream>
using namespace std;

// 质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数
bool isPrime(int n) { // 经常用到的功能封装成函数会更方便
    for (int i = 2; i <= n / 2; i++) {
        if (n % i == 0)
            return false;
    }
    return true; // 遍历完都没有就是素数
}

int main() { 
    int n;
    while (cin >> n) {
        for (int i = n/2; i > 0; i--) 
            if (isPrime(i) && isPrime(n - i)) {
                cout << i << '\n' << n - i << endl;
                break;
            }
    }
    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