Algorithm

leetcode

twoSum

• Demo

/**
 * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
 * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
 * 示例：
 * 给定aums=[2，7，11，15]，target=9
 * 因为nums[0]+nums[1]=2+7=9
 * 所以返回[0，1]
 */
public class TwoSum {
    public static void main(String[] args) {
        int[] nums = new int[]{2,7,11,15};
        int target = 9;
        System.out.println(Arrays.toString(m1(nums, target)));
        System.out.println(Arrays.toString(m2(nums, target)));
    }
    public static int[] m1(int[] nums,int target){
        for(int i = 0; i < nums.length; i++){
            for(int j = i + 1; j < nums.length; j++){
                if(nums[i] + nums[j] == target){
                    return new int[]{i,j};
                }
            }
        }
        return null;
    }
    public static int[] m2(int[] nums,int target){
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int partnerNumber = target - nums[i];
            if(map.containsKey(partnerNumber)){
                return new int[]{map.get(partnerNumber),i};
            }
            map.put(nums[i],i);
        }
        return null;
    }
}

other

MTwoN

• Demo

/**
 * 给定一个数m求大于该数的最小2的n次幂，返回n
 */
public class MTwoN {
    public static void main(String[] args) {
        System.out.println(mTwoN1(34));
        System.out.println(mTwoN2(34));
    }
    public static int mTwoN1(int m){
        int i = 1;
        int temp = 1;
        while(m >= (temp = temp * 2)){
            ++i;
        }
        return i;
    }
    //这个问题就是把最高位的1后面的都变为1，然后 + 1得到结果。
    //就好比细胞分裂，最高位1是一个不断分裂的细胞，第一次1变2，然后两个细胞一起分裂；
    // 2变4(右移两位)；之后4个继续分裂为8(右移4位)，这就是为什么不是每次右移1位。
    // (假设每次进行一次右移，那么相当于每次只有一个细胞在分裂)
    //https://my.oschina.net/u/3870422/blog/3213854
    public static int mTwoN2(int m){
        int n = m - 1;//因为n可能已经是2的幂。先减去1
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (int)(Math.log(n + 1) / Math.log(2));//因为要求出大于>=n的2的幂。加1正好可以求出。
    }
}