做计算机网站有哪些,作文素材,wordpress清理缓存,网站后台登陆图片1. 最近公共祖先 将一棵无穷大满二叉树的结点按根结点一层一层地从左往右编号#xff0c;根结点编号为1。现给定a#xff0c;b为两个结点。设计一个算法#xff0c;返回a、b最近的公共祖先的编号。注意其祖先也可能是结点本身。 测试样例#xff1a; 2#xff0c;3 返回根结点编号为1。现给定ab为两个结点。设计一个算法返回a、b最近的公共祖先的编号。注意其祖先也可能是结点本身。 测试样例 23 返回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;}
};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;
}思路2: 求二进制数有几个1n n-1 求二进制数最长连续的1n (n 1)
int main()
{int n;while (cin n) {int count 0;while (n) {n n (n 1);count;}cout count endl;}return 0;
}3. 二进制插入 给定两个32位整数n和m同时给定i和j将m的二进制数位插入到n的二进制的第j到第i位,保证n的第j到第i位均为零且m的二进制位数小于等于i-j1其中二进制的位数从0开始由低到高。 测试样例 10241926 返回1100 示例 1 输入 输出 思路1:
class BinInsert {
public:int binInsert(int n, int m, int j, int i) {m j;return n m;}
};class BinInsert {
public:int binInsert(int n, int m, int j, int i) {while(j) {m * 2;j--;}return n m;}
};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;
}
