建站网站和维护需要会什么办公室装修设计怎么收费

建站网站和维护需要会什么,办公室装修设计怎么收费,佛山小程序开发制作,wordpress php那个版本号二进制表示中质数个计算置位 问题描述 给你两个整数 left 和 right#xff0c;请你找到在 [left, right] 范围内#xff0c;计算置位位数为质数的整数个数。 计算置位#xff1a;指二进制表示中 1 的个数。质数#xff1a;大于 1 且只能被 1 和自身整除的数。 注意请你找到在[left, right]范围内计算置位位数为质数的整数个数。计算置位指二进制表示中 1 的个数。质数大于 1 且只能被 1 和自身整除的数。注意1 不是质数。示例输入: left 6, right 10 输出: 4 解释: 6 - 110 (2 个计算置位2 是质数) 7 - 111 (3 个计算置位3 是质数) 8 - 1000 (1 个计算置位1 不是质数) 9 - 1001 (2 个计算置位2 是质数) 10- 1010 (2 个计算置位2 是质数) 共计 4 个整数拥有质数个计算置位。算法思路关键范围限制约束1 left right 10^6最大位数10^6 2^20所以任何数字的二进制表示最多有 20 位质数范围计算置位的个数范围是 [1, 20]所以只需要判断 1-20 中的质数预处理优化在 [1, 20] 范围内的质数只有2, 3, 5, 7, 11, 13, 17, 19可以预先将这些质数存储在 Set 中避免重复的质数判断代码实现方法一预处理质数 位运算计数importjava.util.*;classSolution{/** * 计算在[left, right]范围内计算置位位数为质数的整数个数 * * param left 范围左边界包含 * param right 范围右边界包含 * return 满足条件的整数个数 */publicintcountPrimeSetBits(intleft,intright){// 预处理[1, 20]范围内的质数// 由于10^6 2^20所以最多有20个1SetIntegerprimesnewHashSet(Arrays.asList(2,3,5,7,11,13,17,19));intcount0;// 遍历范围内的每个数字for(intnumleft;numright;num){// 计算二进制表示中1的个数intsetBitscountSetBits(num);// 检查1的个数是否为质数if(primes.contains(setBits)){count;}}returncount;}/** * 计算整数二进制表示中1的个数计算置位 * * param n 待计算的整数 * return 二进制中1的个数 */privateintcountSetBits(intn){intcount0;// 使用位运算每次清除最低位的1while(n!0){nn(n-1);// 清除最低位的1count;}returncount;}}方法二使用内置函数importjava.util.*;classSolution{/** * 使用Java内置函数 * * param left 范围左边界 * param right 范围右边界 * return 满足条件的整数个数 */publicintcountPrimeSetBits(intleft,intright){// 预处理质数集合SetIntegerprimesSet.of(2,3,5,7,11,13,17,19);intcount0;for(intnumleft;numright;num){// 使用Integer.bitCount()计算1的个数if(primes.contains(Integer.bitCount(num))){count;}}returncount;}}方法三手动质数判断classSolution{/** * 不使用预处理每次动态判断质数 * * param left 范围左边界 * param right 范围右边界 * return 满足条件的整数个数 */publicintcountPrimeSetBits(intleft,intright){intcount0;for(intnumleft;numright;num){intsetBitsInteger.bitCount(num);if(isPrime(setBits)){count;}}returncount;}/** * 判断一个数是否为质数 * * param n 待判断的数 * return true表示是质数false表示不是 */privatebooleanisPrime(intn){// 1不是质数小于1的数也不是质数if(n2){returnfalse;}// 2是质数if(n2){returntrue;}// 偶数不是质数if(n%20){returnfalse;}// 只需检查到sqrt(n)for(inti3;i*in;i2){if(n%i0){returnfalse;}}returntrue;}}算法分析时间复杂度O(n × log m)n right - left 1范围内的数字个数log m 计算每个数字1的个数的时间m为数字大小方法一和二由于预处理质数质数判断为O(1)方法三的质数判断为O(√k)k≤20也是O(1)空间复杂度方法一、二O(1) - 质数集合大小固定8个元素方法三O(1) - 无额外空间算法过程输入left 6, right 10逐个分析num 6二进制1101的个数22是质数num 7二进制1111的个数33是质数num 8二进制10001的个数11不是质数num 9二进制10011的个数22是质数num 10二进制10101的个数22是质数总计4个满足条件的数字测试用例publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1标准示例System.out.println(Test 1: solution.countPrimeSetBits(6,10));// 4// 测试用例2包含1的情况System.out.println(Test 2: solution.countPrimeSetBits(1,5));// 2// 1-1(1个1,非质数), 2-10(1个1,非质数), 3-11(2个1,质数), 4-100(1个1,非质数), 5-101(2个1,质数)// 测试用例3较大范围System.out.println(Test 3: solution.countPrimeSetBits(10,15));// 5// 10-1010(2), 11-1011(3), 12-1100(2), 13-1101(3), 14-1110(3), 15-1111(4非质数)// 测试用例4边界情况System.out.println(Test 4: solution.countPrimeSetBits(1,1));// 0// 测试用例5全范围System.out.println(Test 5: solution.countPrimeSetBits(1,1000000));// 大数值测试// 测试用例6包含最大1个数的情况System.out.println(Test 6: solution.countPrimeSetBits(1048575,1048575));// 1048575 2^20-1 (20个1,非质数) - 0// 测试用例7验证质数边界System.out.println(Test 7: solution.countPrimeSetBits(2097151,2097151));// 2097151 2^21-1 (21个1,非质数) - 0// 测试用例8刚好20个1的数inttwentyOnes(120)-1;// 1048575System.out.println(Test 8: solution.countPrimeSetBits(twentyOnes,twentyOnes));// 0 (20不是质数)// 测试用例919个1的数intnineteenOnes(119)-1;// 524287System.out.println(Test 9: solution.countPrimeSetBits(nineteenOnes,nineteenOnes));// 1 (19是质数)}关键点范围10^6 2^20 1,048,576任何输入数字最多有20个1质数判断只需考虑1-20的范围质数集合[1, 20]内的质数2, 3, 5, 7, 11, 13, 17, 19共8个质数位计数n (n-1)清除最低位的1高效计数Integer.bitCount()Java内置函数底层优化质数定义1不是质数质数必须大于1且只有1和自身两个正因数常见问题为什么1不是质数质数定义要求大于1且只有两个正因数1只有1个正因数就是1本身为什么可以预处理质数由于输入范围限制1的个数最多为20位计数逐位检查while(n 0) {count n 1; n 1;}内置函数Integer.bitCount(n)查表法预先计算0-255的位数