LeetCode] 第 340 期每周问题解决者第 340 期每周问题解决者

6361. 对角线上的质数

给你一个下标从 0 开始的二维整数数组 nums 。 返回位于 nums 至少一条 对角线 上的最大 质数 。如果任一对角线上均不存在质数，返回 0 。 注意：

• 如果某个整数大于 1 ，且不存在除 1 和自身之外的正整数因子，则认为该整数是一个质数。
• 如果存在整数 i ，使得 nums[i][i] = val 或者 nums[i][nums.length - i - 1]= val ，则认为整数 val 位于 nums 的一条对角线上。

在上图中，一条对角线是  [1,5,9]  ，而另一条对角线是 [3,5,7]  。

示例 1：

输入： nums = [[1,2,3],[5,6,7],[9,10,11]]
输出： 11
解释： 数字 1、3、6、9 和 11 是所有 "位于至少一条对角线上" 的数字。由于 11 是最大的质数，故返回 11 。

示例 2：

输入： nums = [[1,2,3],[5,17,7],[9,11,10]]
输出： 17
解释： 数字 1、3、9、10 和 17 是所有满足"位于至少一条对角线上"的数字。由于 17 是最大的质数，故返回 17 。

提示：

• 1 <= nums.length <= 300
• nums.length == numsi.length
• 1 <= nums[i][j] <= 4*106

题解：求质数

class Solution {
public:
    int diagonalPrime(vector<vector<int>>& nums) {
        int n = nums.size();
        int res = 0;
        for(int i=0; i<n; i++){
            if(isPrime(nums[i][i])){
                res = max(res, nums[i][i]);
            }
            if(isPrime(nums[i][n-i-1])){
                res = max(res, nums[i][n-i-1]);
            }
        }
        return res;
    }
    
    bool isPrime(int num){
        if(num == 1) return false;
        for(int i=2; i*i<=num; i++){
            if(num%i == 0){
                return false;
            }
        }
        return true;
    }
};

6360. 等值距离和

给你一个下标从 0 开始的整数数组 nums 。现有一个长度等于 nums.length 的数组 arr 。对于满足 nums[j] == nums[i] 且 j != i 的所有 j ，arr[i] 等于所有 |i - j| 之和。如果不存在这样的 j ，则令 arr[i] 等于 0 。

返回数组 **arr 。

示例 1：

输入： nums = [1,3,1,1,2]
输出： [5,0,3,4,0]
解释：
i = 0 ，nums[0] == nums[2] 且 nums[0] == nums[3] 。因此，arr[0] = |0 - 2| + |0 - 3| = 5 。 
i = 1 ，arr[1] = 0 因为不存在值等于 3 的其他下标。
i = 2 ，nums[2] == nums[0] 且 nums[2] == nums[3] 。因此，arr[2] = |2 - 0| + |2 - 3| = 3 。
i = 3 ，nums[3] == nums[0] 且 nums[3] == nums[2] 。因此，arr[3] = |3 - 0| + |3 - 2| = 4 。 
i = 4 ，arr[4] = 0 因为不存在值等于 2 的其他下标。

示例 2：

输入： nums = [0,5,3]
输出： [0,0,0]
解释： 因为 nums 中的元素互不相同，对于所有 i ，都有 arr[i] = 0 。

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

题解：前后缀和

class Solution {
public:
    vector<long long> distance(vector<int>& nums) {
        int n = nums.size();
        vector<long long> f(n+1);
        vector<long long> g(n+1);
        unordered_map<long long, int> pos;
        unordered_map<int, int> cnt;
        for(int i=1; i<=n; i++){
           f[i] = abs(i-pos[nums[i-1]]) * cnt[nums[i-1]] + f[pos[nums[i-1]]];
           pos[nums[i-1]] = i;
           cnt[nums[i-1]]++;
        }
        pos.clear();
        cnt.clear();
        for(int i=n; i>=1; i--){
           g[i] = abs(i-pos[nums[i-1]]) * cnt[nums[i-1]] + g[pos[nums[i-1]]];
           pos[nums[i-1]] = i;
           cnt[nums[i-1]]++;
        }
        vector<long long> res;
        for(int i=1; i<=n; i++){
           res.push_back(f[i]+g[i]);
        }
        return res;
    }
};

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

给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，每个下标对对应数值取差值，你需要使得这 p 个差值的 最大值 最小。同时，你需要确保每个下标在这 p 个下标对中最多出现一次。

对于一个下标对 i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的 绝对值 。

请你返回 p 个下标对对应数值 最大差值 的 最小值 。

示例 1：

输入： nums = [10,1,2,7,1,3], p = 2
输出： 1
解释： 第一个下标对选择 1 和 4 ，第二个下标对选择 2 和 5 。
最大差值为 max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1 。所以我们返回 1 。

示例 2：

输入： nums = [4,2,1,2], p = 1
输出： 0
解释： 选择下标 1 和 3 构成下标对。差值为 |2 - 2| = 0 ，这是最大差值的最小值。

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109
• 0 <= p <= (nums.length)/2

题解：二分+贪心

class Solution {
public:
    int minimizeMax(vector<int>& nums, int p) {
       sort(nums.begin(), nums.end());
        int n = nums.size();
        long long l = 0, r = nums[n-1] - nums[0];
        while(l < r){
            long mid = (l+r)/2;
            if(check(nums, mid, p)){
                r = mid;
            }else{
                l = mid+1;
            }
        }
        return l;
    }
    
    bool check(vector<int> nums, int mid, int p){
        int sum = 0;
        for(int i=1; i<nums.size();){
            if(nums[i] - nums[i-1] <= mid){
                sum++;
                i+=2;
            }else{
                i++;
            }
        }
        return sum >= p;
    }
};