2023‐07‐02 第 352 场周赛

最长奇偶子数组

• 太久没打了
• 失误有点多 罚了两次时

class Solution {
public:
    int longestAlternatingSubarray(vector<int>& nums, int threshold) {
        // 以 偶数 开头
        // 余数互相不相等
        
        vector<int> idx; // 偶数的下标
        
        int n = nums.size();
        
        for (int i = 0; i < n; i ++) {
            if (nums[i] % 2 == 0) idx.emplace_back(i);   
        }
        
        int res = 0;
        
        for (int i = 0; i < idx.size(); i ++) {
            int k = idx[i];
            int l = 0;
            
            for (; k < n; k ++) {
                if (nums[k] > threshold) break;
                
                l ++;
                
                if (k < n - 1 && nums[k] % 2 == nums[k + 1] % 2) break;
            }
            
            
            res = max(res, l);
        }
        
        return res;
    }
};

---

和等于目标值的质数对

• 主要是超时
• 罚时 6 次
• 优化部分是在质数的判断部分 以及查数过程
• 注意判断是否质数的函数

class Solution {
public:
    bool func(int n) {
        if(n <= 3){
            return n > 1;
        }
 
        if(n % 6 != 1 && n % 6 != 5){
            return false;   
        }
    
        int s = (int)sqrt(n);
        
        for(int i = 5; i <= s; i += 6){
            if(n % i == 0 || n % (i + 2) == 0){
                return false;
            }
        }
 
        return true;
    }
    
   
    vector<vector<int>> findPrimePairs(int n) {
        vector<vector<int>> res;
        
        vector<bool> f(n + 1, 0);
        
        for (int i = 1; i < f.size() / 2 + 1; i ++) {
            f[i] = func(i);
            
            if (f[i]) f[n - i] = func(n - i);
        }
        
        for (int i = 1; i <= n / 2; i ++) {
            int l = i, r = n - l;
            
            if (f[l] && f[r]) res.push_back({l, r});
        }
    
        return res;
    }
};

不间断子数组

• 尝试了一下 最后是超时了
• 优化的方法没有想到

class Solution {
public:
    long long max(long long x1, long long x2) {
        return x1 > x2 ? x1 : x2;
    }
    
    long long min(long long x1, long long x2) {
        return x1 < x2 ? x1 : x2;
    }
    
    long long continuousSubarrays(vector<int>& nums) {
        // 最大的值 和 当前值的差值
        
        long long res = 0;
        
        long long idx = 0; // 当前最大值
        
        long long n = nums.size();
        
        for (int i = 0; i < n; i ++) {
            res ++;
            
            long long f1 = nums[i];
            long long f2 = nums[i];
            
            for (int k = i + 1; k < n; k ++) {
                f1 = max(f1, nums[k]);
                f2 = min(f2, nums[k]);
                
                if (abs(f1 - f2) > 2) break;
                
                res ++;
            }
        }
        
        return res;
    }
};

• 滑动窗口

class Solution {
public:
    long long continuousSubarrays(vector<int> &nums) {
        long long ans = 0;
        multiset<int> s;
        int left = 0, n = nums.size();
        for (int right = 0; right < n; right++) {
            s.insert(nums[right]);
            while (*s.rbegin() - *s.begin() > 2)
                s.erase(s.find(nums[left++]));
            ans += right - left + 1;
        }
        return ans;
    }
};