lcp340

对角线上的质数

方法一：埃氏筛

class Solution {
    static int n = 4 * (int) 1e6 + 1;
    static boolean[] notPrime = new boolean[n];
    static {
        notPrime[0] = true;
        notPrime[1] = true;
        for (int i = 2; i < n; ++i) {
            if (!notPrime[i]) {
                if ((long) i * i < n) {
                    for (int j = i * i; j < n; j+=i) {
                        notPrime[j] = true;
                    }
                }
            }
        }
    }

    public int diagonalPrime(int[][] nums) {
        int res = 0, m = nums.length, n = nums[0].length;
        for (int i = 0; i < m; ++i) {
            if (!notPrime[nums[i][m - 1 - i]])
                res = Math.max(res, nums[i][m - 1 - i]);
            if (!notPrime[nums[i][i]])
                res = Math.max(res, nums[i][i]);
        }
        return res;
    }

}

等值距离和

方法一：相同元素分组+考虑增量

如下图

左边距离增加了的个数，右边距离减少了的个数

long size = (j - 1) - (list.size() - 1 - j)= j * 2 - list.size();

class Solution {
    public long[] distance(int[] nums) {
        int n = nums.length;
        long[] res = new long[n];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int num = nums[i];
            if (!map.containsKey(num))
                map.putIfAbsent(num, new ArrayList<>());
            map.get(num).add(i);
        }
        for (List<Integer> list : map.values()) {
            long first = 0;
            for (int x : list) 
                first += x - list.get(0);
            
            res[list.get(0)] = first;
            for (int j = 1; j < list.size(); ++j) {
                long diff = list.get(j) - list.get(j - 1);
                long size = (long) (j * 2 - list.size());
                res[list.get(j)] = res[list.get(j - 1)] + diff * size;
            }
        }
        return res;
    }
}

2616. 最小化数对的最大差值

方法一：贪心 + 二分

class Solution {
    public int minimizeMax(int[] nums, int p) {
        int n = nums.length;
        Arrays.sort(nums);
        int l = 0, r = nums[n - 1] - nums[0];
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(nums, mid, p))
                r = mid - 1;
            else 
                l = mid + 1;
        }
        return l;
    }

    private boolean check(int[] nums, int limit, int p) {
        int cnt = 0;
        for (int i = 0; i < nums.length - 1; ++i) {
            if (Math.abs(nums[i] - nums[i + 1]) <= limit) {
                ++cnt;
                i++;
            }
        }
        return cnt >= p;
    }
}