java面试总结-20250616
题目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的全部组合，相同的组合只能出现一次。
输入：target=8，nums=[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 List<List<Integer>> getCombineSum(int target, int[] nums) {Arrays.sort(nums);List<List<Integer>> res= new ArrayList<>(16);List<Integer> path = new ArrayList<>(16);hsSum(res, path, target, nums, 0);return res;}public static void hsSum(List<List<Integer>> res, List<Integer> 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);}}