lcp338

K 件物品的最大和

方法一：模拟

class Solution {
    public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        if (k <= numOnes)
            return k;
        else if (k > numOnes && k <= numOnes + numZeros)
            return numOnes;
        else
            return numOnes - (k - numOnes - numZeros);
    }
}

质数减法运算

　

方法一：TreeSet

class Solution {
    static public int MAX = 1000;
    static public TreeSet<Integer> set = new TreeSet<>();

    static {
        boolean[] notPrime = new boolean[MAX + 1];
        for (int i = 2; i < MAX; ++i) {
            if (!notPrime[i]) {
                set.add(i);
                if ((long) i * i < MAX) {
                    for (int j = i * i; j < MAX; j+=i)
                        notPrime[j] = true;
                }
            }
        }
    }

    public boolean primeSubOperation(int[] nums) {
        int n = nums.length;
        for (int i = n - 1; i >= 1; --i) {
            int pre = nums[i - 1], next = nums[i];
            if (pre >= next) {
                int diff = pre - next;
                Integer higher = set.higher(diff);
                if (higher == null || higher >= pre)
                    return false;
                nums[i - 1] -= higher;
            }
        }
        return true;
    }
}

使数组元素全部相等的最少操作次数

方法一：排序 + 前缀和 + 二分

long long long!!!!!

class Solution {
    public List<Long> minOperations(int[] nums, int[] queries) {
        Arrays.sort(nums);
        List<Long> res = new ArrayList<>();
        long[] preSum = new long[nums.length + 1];
        for (int i = 0; i < nums.length; ++i)
            preSum[i + 1] = preSum[i] + nums[i];
        for (int q : queries) {
            int index = lower(q, nums);
            long left = index * (long) q - preSum[index];
            long right = preSum[nums.length] - preSum[index] - (long) q * (nums.length - index);
            res.add(left + right);
        }
        return res;
    }

    private int lower(int q, int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= q)
                r = mid - 1;
            else
                l = mid + 1;
        }
        return l;
    }
}

方法二：和lcp339那题类似的做法

class Solution {
    public List<Long> minOperations(int[] nums, int[] queries) {
        Arrays.sort(nums);
        List<Long> res = new ArrayList<>();
        long s = 0, q1 = queries[0];
        long[] preSum = new long[nums.length + 1];
        int index = 1;
        for (int x : nums) {
            s += Math.abs(x - q1);
            preSum[index] = preSum[index++ - 1] + x;
        }
        res.add(s);
        for (int j = 1; j < queries.length; ++j) {
            // 找到 >= q的nums下标
            int i = findIndex2(queries[j - 1], nums);
            int k = findIndex(queries[j], nums);
            long middleSum = preSum[k] - preSum[i + 1];
            int size = k - i - 1;
            long diff =  ((long) queries[j] * size - middleSum) - (middleSum - (long) queries[j - 1] * size);
            int left = i + 1;
            int right = nums.length - k;
            s += (left - right) * ((long) queries[j] - queries[j - 1]) + diff;
            res.add(s);
        }
        return res;
    }

    private int findIndex(int q, int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= q)
                r = mid - 1;
            else
                l = mid + 1;
        }
        return l;
    }

    private int findIndex2(int q, int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] > q)
                r = mid - 1;
            else
                l = mid + 1;
        }
        return r;
    }
}

2603. 收集树中金币

方法一：两次拓扑排序

class Solution {
    public int collectTheCoins(int[] coins, int[][] edges) {
        int n = edges.length + 1;
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        int[] degree = new int[n];
        for (int[] edge : edges) {
            int from = edge[0], to = edge[1];
            g[from].add(to);
            g[to].add(from);
            ++degree[from];
            ++degree[to];
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; ++i)
            if (degree[i] == 1 && coins[i] == 0)
                queue.offer(i);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int next : g[node])
                if (--degree[next] == 1 && coins[next] == 0)
                    queue.offer(next);
        }
        for (int i = 0; i < n; ++i)
            if (degree[i] == 1 && coins[i] == 1)
                queue.offer(i);
        int[] times = new int[n];
        int t = 1;
        while (!queue.isEmpty()) {
            int size= queue.size();
            for (int i = 0; i < size; ++i) {
                int node = queue.poll();
                for (int next : g[node]) {
                    if (--degree[next] == 1) {
                        queue.offer(next);
                        times[next] = t;
                    }
                }
            }
            ++t;
        }
        int res = 0;
        for (int[] edge : edges)
            if (times[edge[0]] >= 2 && times[edge[1]] >= 2)
                res += 2;
        return res;
    }
}