网站建设平台软件,企业vi设计图片,百度应用app下载,电脑网页打不开是什么问题题目1: 求一个int类型正整数二进制中最高位1的位置#xff1f; 比如10#xff0c;二进制位1010#xff0c;最高位1所在位置位4。
解体思路#xff1a;
使用高位扩散#xff0c;将1010扩散位1111使用二分法#xff0c;计算32位二进制中1111前面0的位数n#xff1b;结果…题目1: 求一个int类型正整数二进制中最高位1的位置 比如10二进制位1010最高位1所在位置位4。
解体思路
使用高位扩散将1010扩散位1111使用二分法计算32位二进制中1111前面0的位数n结果为32-n
代码如下 public static int getMaxDigit(int num) {// 获取最高位为1的数例如8会得到8(1000)int highestOneBit Integer.highestOneBit(num);// 计算这个数的二进制位数return 32 - numberOfLeadingZeros2(highestOneBit);}public static int numberOfLeadingZeros2(int i) {int res 1;// 看条件A高16为是否都为0。// 如果是结果加16并且将低16位变成高16位这里是为了和条件A的反逻辑即高16位有不为0的情况进行统一if (i 16 0) {i 16;res 16;}// 看高8位是否都为0if( i 24 0) {res 8;i 8;}// 看高4位是否都为0if (i 28 0) {res 4;i 4;}// 看高2位是否都为0if (i 30 0) {res 2;i 2;}// 看高一位是否为0因为res的初始值为1return res - (i 31);}
highestOneBit、numberOfLeadingZeros 这两个方法都是Integer包装类中的。 highestOneBit求指定num的最高位为1其他位为0的数字。实现逻辑如下 public static int highestOneBit(int i) {// HD, Figure 3-1i | (i 1);i | (i 2);i | (i 4);i | (i 8);i | (i 16);return i - (i 1);}用位移和或运算实现。
题目2: 给一个数字target求数组和为target的全部组合相同的组合只能出现一次。 输入target8nums[2,1,5,1,6,7] 输出 [[1,1,6], [1,2,5], [1,7]]
思路 1.排序 2.回溯 3.去重
public static void main(String[] args) {System.out.println(Arrays.deepToString(getCombineSum(8, new int[]{2,1,5,1,6,7}).toArray()));}public static ListListInteger getCombineSum(int target, int[] nums) {Arrays.sort(nums);ListListInteger res new ArrayList(16);ListInteger path new ArrayList(16);hsSum(res, path, target, nums, 0);return res;}public static void hsSum(ListListInteger res, ListInteger path, int target, int[] nums, int begin) {if (target 0) {res.add(new ArrayList(path));return;} else if (target 0) {return;}for (int i begin; i nums.length; i) {if (i begin nums[i - 1] nums[i]) {continue;}path.add(nums[i]);hsSum(res, path, target - nums[i], nums,i 1);path.remove(path.size()-1);}}
