2023‐07‐16 第 354 场周赛

特殊元素平方和

• 第一题挺简单的
• 正常模拟就能 AC

class Solution {
public:
    int sumOfSquares(vector<int>& nums) {
        int res = 0;
        
        int n = nums.size();
        
        for (int i = 0; i < n; i ++) {
            if (n % (i + 1) == 0) res += nums[i] * nums[i];
        }
        
        return res;
    }
};

数组的最大美丽值

• 第二题还是比较考验思路的
• 罚了两次时 第一次是超时 第二次是没考虑到 res 的最小值应该是 1
• 主要是优化思路

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        int res = 1;
        
        int n = nums.size();
                
        int l = 0, r = l + 1;
        
        sort(nums.begin(), nums.end());
     
        while (l < n - 1 && r < n) {
            
            if (nums[l] + k < nums[r] - k) {
                l ++;
                
                continue;
            }
            
            while (r < n) {
                
                if (nums[l] + k >= nums[r] - k) r ++;
            
                else break;
            }
            
            res = max(r - l, res);
            
            l ++;
        }
        
        return res;
    }
};

合法分割最小下标

• 没想到第三题 AC 了
• 思路还是挺好想的
• 但是排名还是差点

class Solution {
public:
    int minimumIndex(vector<int>& nums) {
        // 支配元素一定是数组出现次数最多的
        // 关键是保证在分割的过程中 原数组中的支配元素在分割之后任然还是当前数组的支配元素
        // 在保证前半部的前提下 再考虑后半部分
        
        int res = -1;
        
        int n = nums.size();
        
        unordered_map<int, int> cnt;
        
        for (int i = 0; i < n; i ++) cnt[nums[i]] ++;
        
        int idx = 0, tem = 0;
        for (auto &[k, v] : cnt) { // 找出支配元素
            if (v > tem) idx = k, tem = v;
        }
        
        vector<int> cor; // 统计支配元素出现的位置
        
        for (int i = 0; i < n; i ++) if (nums[i] == idx) cor.emplace_back(i);
        
        // 支配元素的个数 大于 数组长度的一半 ---> 一定是数组中的最大
        int s = 0;
        for (int i = 0; i < cor.size(); i ++) {
            int l = cor[i];
            s ++;
            
            if ((l + 1) < s * 2 && (tem - s) * 2 > (n - l - 1)) {
                return l;
            }
        }
        
        return -1;
    }
};