LeetCode(48) -- 1005, 1009,

P1005. Maximize Sum Of Array After K Negations (Easy)

一个整数数组，可以选择其中任何一个数进行变号，可以变号k次（每次都可以选择任何一个数）。问最终得到的数组的和最大是多少。

我的思路

分情况讨论，如果负数的数量多于k,那么就找绝对值最大的k的负数进行变号，如果最后k还有剩余，则说明可能要变正数。如果有0就直接返回了。正数的话，如果k剩下的次数为偶数，那也直接返回了，如果是奇数，则找一个最小的正数进行变号，得到结果。

我的代码

class Solution {
    public int largestSumAfterKNegations(int[] A, int K) {
        Arrays.sort(A);
        int i = 0;
        while (A[i] < 0 && K > 0) {
            A[i] = -A[i];
            i++;
            K--;
        }
        if (A[i] <= 0 || (K & 1) == 0) {
            return sum(A);
        }
        if (i >= 1 && A[i] > A[i - 1]) {
            A[i - 1] = -A[i - 1];
        } else {
            A[i] = -A[i];
        }
        return sum(A);
    }

    private int sum (int[] A) {
        int sum = 0;
        for (int i : A) {
            sum += i;
        }
        return sum;
    }
}

88%

最优解

class Solution {
    public int largestSumAfterKNegations(int[] A, int K) {
        for(int i=0; i<K; i++){
            modifiyArray(A);
        }
        int sum = 0;
        for(int i=0; i<A.length; i++){
            sum += A[i];
        }
        return sum;
    }

    public void modifiyArray(int[] A){
        int minIndex = 0;
        int min = Integer.MAX_VALUE;

        for(int i=0; i < A.length; i++){
            if(A[i] < min){
                minIndex = i;
                min = A[i];
            }
        }

        A[minIndex] = A[minIndex] * -1;
    }
}

其实不用排序，每次都去改最小值，一定是最优的结果。不过这样做理论上的时间复杂度其实是高于排序的

P1009. Complement of Base 10 Integer (Easy)

整数的二进制表示，取反（0变1，1变0），找到那个新的整数。

我的思路

有多少位，就弄多少个1，最后跟原数做异或运算，就是结果。

我的代码

class Solution {
    public int bitwiseComplement(int N) {
        int temp = N >> 1;
        int ones = 1;
        while (temp != 0) {
            ones = (ones << 1) + 1;
            temp = (temp >> 1);
        }
        return N ^ ones;
    }
}

100%

最优解

class Solution {
    public int bitwiseComplement(int N) {
        int X = 1;
        while (N > X) X = X * 2 + 1;
        return X - N;
    }
}

P1010. Pairs of Songs With Total Durations Divisible by 60 (Easy)

在一个数组中，找出有多少两个数的和能被60整除的pair

我的思路

一开始暴力求解，超时了。然后用hashmap,也很慢，但过了。

我的代码

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int count = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < time.length; i++) {
            Integer value = map.getOrDefault((60 - time[i] % 60) % 60, 0);
            count += value;
            map.put(time[i] % 60, map.getOrDefault(time[i] % 60, 0) + 1);
        }
        return count;
    }
}

38%

最优解

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] arr = new int[501];

        for (int i : time)
            arr[i]++;

        for (int i = 60; i <= 500; i++)
            arr[i % 60] += arr[i];

        int result = ((arr[0] - 1) * arr[0] + (arr[30] - 1) * arr[30]) / 2;

        for (int i = 1; i < 30; i++)
            result += arr[i] * arr[60 - i];

        return result;
    }
}

time[i]是小于500的，这点很重要。