LeetCode(6) -- 342, 349, 350, 367, 371

P342. Power of Four (Easy)

给一个整数，判断它是否是4的幂。

我的思路

首先必须是2的幂，同时二进制里的那个1，必须在奇数位上，比如4是100，16是10000。。。

0x55555555 = 0101 0101 0101 0101 0101 0101 0101 0101 奇数位全是1。 用它跟自己做“和”运算，还应该等于它本身。

我的代码

public class E_342_PowerOfFour {
    public boolean isPowerOfFour(int num) {
        if (num <= 0) return false;
        return (num & (num - 1)) == 0 && (0x55555555 & num) == num;
    }
}

超过100%

最优解

class Solution {
    public boolean isPowerOfFour(int num) {
        if(num < 1){
            return false;
        }

        while(num % 4 == 0){
            num = num / 4;
        }

        if(num == 1){
            return true;
        }

        return false;
    }
}

这个估计还是因为测试次数不够。如果测试数量足够大时，应该还是数学方法最快。

P349. Intersection of Two Arrays (Easy)

给两个数组，把它们看作集合，求交集。

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

我的思路

把这两个数组都放在HashSet里，然后求HashSet的交集。

我的代码

public class E_349_IntersectionOfTwoArrays {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set1 = new HashSet<>();
        HashSet<Integer> set2 = new HashSet<>();
        for (int i : nums1) {
            set1.add(i);
        }
        for (int i : nums2) {
            set2.add(i);
        }
        set1.retainAll(set2);
        int[] arr = new int[set1.size()];
        int i = 0;
        for (Integer integer : set1) {
            arr[i++] = integer;
        }
        return arr;
    }
}

超过37%

最优解

import java.util.Arrays;
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for(int i :nums1){
            if(i < min) min = i;
            if(i > max) max = i;
        }

        boolean[] table = new boolean[max - min + 1];
        for(int s : nums1) table[s - min] = true;
        int[] temp = new int[table.length];
        int size = 0;
        for(int j :nums2){
            if(j <= max && j >= min && table[j - min]){
                temp[size++] = j;
                table[j - min] = false;
            }
        }
        int[] res = new int[size];
        for(int m =0 ; m < size; m++)  res[m] = temp[m];

        return res;
    }
}

先算出第一个数组的最大值和最小值，然后做了一个手工的哈希表，布尔型。

答案

方法一：

class Solution {
  public int[] set_intersection(HashSet<Integer> set1, HashSet<Integer> set2) {
    int [] output = new int[set1.size()];
    int idx = 0;
    for (Integer s : set1)
      if (set2.contains(s)) output[idx++] = s;

    return Arrays.copyOf(output, idx);
  }

  public int[] intersection(int[] nums1, int[] nums2) {
    HashSet<Integer> set1 = new HashSet<Integer>();
    for (Integer n : nums1) set1.add(n);
    HashSet<Integer> set2 = new HashSet<Integer>();
    for (Integer n : nums2) set2.add(n);

    if (set1.size() < set2.size()) return set_intersection(set1, set2);
    else return set_intersection(set2, set1);
  }
}

方法二：

class Solution {
  public int[] intersection(int[] nums1, int[] nums2) {
    HashSet<Integer> set1 = new HashSet<Integer>();
    for (Integer n : nums1) set1.add(n);
    HashSet<Integer> set2 = new HashSet<Integer>();
    for (Integer n : nums2) set2.add(n);

    set1.retainAll(set2);

    int [] output = new int[set1.size()];
    int idx = 0;
    for (int s : set1) output[idx++] = s;
    return output;
  }
}

P350. Intersection of Two Arrays II (Easy)

两个数组找交集，有多少次重复的，就要显示多少次。

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

我的思路

可以用hashmap存出现的次数。或者，先把两个数组排序，然后依次找到相同的数，数重叠的次数。

我的代码

public class E_350_IntersectionOfTwoArraysII {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums1.length; i++) {
            if (map.get(nums1[i]) == null) {
                map.put(nums1[i],1);
            } else {
                map.put(nums1[i], map.get(nums1[i]) + 1);
            }
        }
        for (int i = 0; i < nums2.length; i++) {
            if (map.containsKey(nums2[i])) {
                result.add(nums2[i]);
                int value = map.get(nums2[i]);
                if ( value > 1) {
                    map.put(nums2[i], value - 1);
                } else {
                    map.remove(nums2[i]);
                }
            }
        }
        int[] arr = new int[result.size()];
        int i = 0;
        for (Integer integer : result) {
            arr[i++] = integer;
        }
        return arr;
    }
}

超过54%

最优解

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int[] ret;
        int i, j, k;
        i = 0; j = 0; k = 0;
        while(i < nums1.length && j < nums2.length){
            if(nums1[i] == nums2[j]){
                nums1[k] = nums1[i];
                k++;
                i++;
                j++;
            }
            else if(nums1[i] < nums2[j])    i++;
            else    j++;
        }
        return Arrays.copyOfRange(nums1, 0, k);
    }

}

用了先排序的方法, 一开始两个数组齐头并进，谁小谁往前走，直到走到一样大，然后把一样大的这个数覆盖掉nums1，k++。最后把0到k作为有效的结果copy出来即可。

P367. Valid Perfect Square (Easy)

给一个正整数，判断它是否是完全平方数。不许用sqrt

我的思路

能想到的就是挨个数试了。。。1的平方，2的平方，3的平方。。。

看了答案，其实还是自己做了简易版的sqrt，还是用的牛顿开平方的方法。

讨论区

public class E_367_ValidPerfectSquare {
    public boolean isPerfectSquare(int num) {
        long r = num;
        while (r * r > num) {
            r = (r + num / r) / 2;
        }
        return r * r == num;
    }
}

要求一个数的开方，就反复猜，先猜它本身（肯定不对啊），只要猜的数的平方大于这个数，就用这个数除以猜的数，再跟猜的数r取平均值。这样就会一点一点接近真实的开方。

P371. Sum of Two Integers (Easy)

求两个整数的和，但不许用加号、减号。。。

我的思路

这个很明显是要用位运算啊。可以把它先转成二进制的字符串，再从个位数字开始一个一个做“与”运算。感觉又有点麻烦。。。不知道有没有更好的办法。

我的代码

public class E_371_SumOfTwoIntegers {
    public int getSum(int a, int b) {
//        String aString = Integer.toBinaryString(a);
//        String bString = Integer.toBinaryString(b);
//        for (int i = aString.length() - 1; i >= 0; i--) {
//            aString.charAt(i);
//        }

        int sum = Integer.sum(a, b);
        return sum;
    }
}

这大概算作弊。。。

最优解

class Solution {
    public int getSum(int a, int b) {
        int carry, sum;
        sum = a ^ b;
        carry = (a & b) << 1;
        while (carry != 0) {
            a = (sum ^ carry);
            b = (sum & carry) << 1;
            sum = a;
            carry = b;
        }
        return sum;
    }
}

第一行sum = a ^ b的意思是，把这两个整数的二进制做“XOR”运算，这样只有在一个0一个1的情况下结果才是1；如果是两个0或两个1，当前位结果都是0，这样就正好跟加法的法则相吻合。但是有一个遗留问题就是进位，carry。如果是一个0一个1，或者两个0，其结果都是正确的，没问题；但如果两个1呢？加起来当前结果虽然是0，但是需要进一位。

手工计算加法的时候，进位的问题一般是从右往左依次进位的。每一位是否有进位，都取决于右边的一位是否要进位。但我们做位运算的时候，其实可以把所有的数位是否需要进位同时算出来。这也就是第二行carry = (a & b) « 1的含义。它算的不是某一位是否要进位，而是所有的位置上是否要进位。

接下来通过while循环，不断地把a更新成异或运算， 把b更新成所有位置上的进位情况。进位本质上就是要向高一位加1，所以其实还是加法。不断地循环这一操作，最终肯定能把进位全部消除掉。最终得到的sum当然就是实际加法的结果。