LeetCode(13) -- 476, 482, 496

P476. Number Complement (Easy)

给一个正整数，求它的二进制的“补”

Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

我的思路

直接给这个数用位运算 “~”取个补。但问题是给定的要求前面的0不要取反。做题的时候发现，二进制我只会从右往左一位一位读，如果想把读到的数copy到另一个变量中，就不知道怎么办了。

讨论区

class Solution {
    public int findComplement(int num) {
        int powerOf2 = 1;
        while (num > powerOf2) {
            powerOf2 <<= 1;
            powerOf2++;
        }
        return num ^ powerOf2;
    }
}

有几位就生成几个1，最后把这些1跟原数做异或运算。

最优解

class Solution {
    public int findComplement(int num) {
        long i = 2;
        while (i < num) {
            i *= 2;
        }

        if (i == (long)num) return (int) (i-1);

        return (int) (i-1-num);
    }
}

把i初始化为二进制“10”，然后不断把1向左移，直到不小于原数为止。比如原数如果是5，也就是“101”，那就把1移动成“1000”。

接下来会有两种可能，一种是等于原数，另一种是大于原数。

如果等于原数，取反其实就是-1。如果大于原数，取反就是-1再减去原数。这就类似用“9999”减去某个四位数比如“6542”，得到的结果就是它的“补”。

P482. License Key Formatting (Easy)

字母加数字的授权码，用N个“-”分隔。给一个整数K，比如4。重新格式化这个授权码，使之变成K个字母为一组。

Input: S = "5F3Z-2e-9-w", K = 4

Output: "5F3Z-2E9W"

Explanation: The string S has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.

我的思路

简单的字符串拼接。

我的代码

public class E_482_LicenseKeyFormatting {
    public String licenseKeyFormatting(String S, int K) {
        String s = S.replaceAll("-", "");
        StringBuilder sb = new StringBuilder();
        int remainder = s.length() >= K ? s.length() % K : 0;
        int index = 0;
        for (int i = 0; i < remainder; i++) {
            sb.append(s.charAt(index));
            index++;
        }
        if (remainder != 0) {
            sb.append("-");
        }
        for (int i = 0; i < s.length() - remainder; i++) {
            sb.append(s.charAt(index));
            if ((i + 1) % K == 0 && (i + 1) != s.length() - remainder) {
                sb.append("-");
            }
            index++;
        }
        return sb.toString().toUpperCase();
    }

    public static void main(String[] args) {
        new E_482_LicenseKeyFormatting().licenseKeyFormatting("2-5g-3-J",2);
    }
}

51%

最优解

class Solution {
    public String licenseKeyFormatting(String S, int K) {
		if(S == null ||S.length() == 0) return S;
        int len = S.length() / K + S.length();
        if(S.length() % K == 0) len--;
        char[] array = new char[len];
        int j = len - 1;
        int counter = 0;
        for(int i = S.length() - 1; i >= 0; i--) {
            char c = S.charAt(i);
            if(c != '-') {
                if(c >= 'a') c = (char) ('A' + c - 'a');
                array[j--] = c;
                counter++;
                if(counter == K && i != 0) {
                    array[j--] = '-';
                    counter = 0;
                }
            }
        }
        if(j + 1 < len && array[j + 1] == '-') j++;
        return new String(array, j + 1, len - j - 1);
    }
}

先创建了一个字符型的数组，用来存最后的结果。那么首先第一个问题就是这个数组应该有多长。如果先把字符串中的“-”去除，那当然很容易算出这个数组有多长。但他为了性能，并没有去除“-”，而是算了一下这个数组最多可能有多长。也就是算出了长度的上限。怎么算呢？原始字符串如果不包含任何“-”，那它的长度至少也是它本身。后期我们往中间插入几个“-”呢？可以分成几组，就插入几个。根据是否能整除再做一下调整。

然后开始从右向左遍历原始字符串。只有在不是“-”时才进行操作。用j来记录结果集的index，一般情况下就直接赋值即可。当然如果是小写字母，要转化成大写字母。又用一个counter来记录是否是k的整数倍，决定是否要额外添加一个“-”。

最后如果第一个字符得到的是“-”，就把j向右移回去一位（因为刚才j一直是从左往右移动的）。最后返回数组中从j+1开始，一直到最右边所构成的字符串。

P496. Next Greater Element I (Easy)

给两个数组，第一个数组是第二个数组的子集。数组中的数都不重复。求第一个数组中的每个数，对应到第二个数组后，下一个比它大的数。

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
    For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
    For number 1 in the first array, the next greater number for it in the second array is 3.
    For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
    For number 2 in the first array, the next greater number for it in the second array is 3.
    For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

我的思路

做出来不难，主要是怎么降低时间复杂度。我想用HashMap存下第二个数组中每个数的index，再从第一个数组中遍历就可以很快找到了，然后再往后推，找一个比它大的数即可。

我的代码

public class E_496_NextGreaterElementI {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) {
            map.put(nums2[i], i);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            int current = nums1[i];
            Integer index = map.get(current);
            while (index + 1 < nums2.length) {
                if (nums2[index + 1] > current) {
                    res[i] = nums2[index + 1];
                    break;
                }
                index++;
            }
            if (index + 1 == nums2.length) {
                res[i] = -1;
            }
        }
        return res;
    }
}

80%

最优解

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int l1 = nums1.length, l2 = nums2.length;
        int[] res = new int[l1];
        if (l1 > l2 || l1 == 0 || l2 == 0){
            return res;
        }
        int maxNum = nums2[0];
        for(int k = 1; k < l2; k++){
            if (nums2[k] > maxNum){
                maxNum = nums2[k];
            }
        }
        int[] hashNums = new int[maxNum+1];
        int i, j;

        for(i=0; i<l2-1; i++){
            for(j=i+1; j<l2; j++){
                if(nums2[j]>nums2[i]){
                    hashNums[nums2[i]] = nums2[j];
                    break;
                }
            }
            if (j==l2){
                hashNums[nums2[i]] = -1;
            }
        }
        hashNums[nums2[l2-1]] = -1;
        for(i=0; i<l1; i++){
            res[i] = hashNums[nums1[i]];
        }
        return res;
    }
}

先找出第二个数组里的最大值，然后以这个最大值+1作为长度，新建一个数组。这是要自制HashMap。

然后第二个数组开始loop，找每一个数的下一个大于它的数，找到后存到HashMap里。最后一个不可以有更大的数，直接返回-1。

最后loop一遍nums1，每个数去HashMap里直接找到对应的值即可。