tags: BiWeekly Contest

BiWeekly Contest 137

3254. Find the Power of K-Size Subarrays I (Easy)

限制 :

• 1 <= n == nums.length <= 500
• 1 <= nums[i] <= 105
• 1 <= k <= n

時間複雜度:

$O(n\ast k)$

空間複雜度:

$O(n)$

程式碼:

class Solution {
public:
    bool isOK(vector<int>& nums) {
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] - nums[i - 1] != 1) {
                return false;
            }
        }
        return true;
    }
    vector<int> resultsArray(vector<int>& nums, int k) {
        vector<int> record;
        vector<int> result;
        int i = 0;
        for (; i < k - 1; i++) {
            record.push_back(nums[i]);
        }
        for (; i < nums.size(); i++) {
            record.push_back(nums[i]);
            if (isOK(record) == true) {
                result.push_back(nums[i]);
            } else {
                result.push_back(-1);
            }
            record.erase(record.begin() + 0, record.begin() + 1);
        }
        return result;
    }
};

3255. Find the Power of K-Size Subarrays II (Medium)

限制 :

• 1 <= n == nums.length <= 105
• 1 <= nums[i] <= 105
• 1 <= k <= n

時間複雜度:

$O(n)$

空間複雜度:

$O(n)$

程式碼:

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        if(nums.size() == 1 ) return nums;
        vector<bool> isValid;
        for (int i = 1; i < nums.size(); i++) {
            isValid.push_back(nums[i] - nums[i - 1] == 1);
        }
        vector<int> result;
        int left = 0, right = k - 1, sum = 0;
        for (int i = left; i < right; i++) {
            sum += isValid[i];
        }
        while (right <= isValid.size()) {
            if (sum == (k - 1)) {
                result.push_back(nums[right]);
            } else {
                result.push_back(-1);
            }
            sum -= isValid[left++];
            sum += isValid[right++];
        }

        return result;
    }
};

3(Medium)

限制 :

• 104

時間複雜度:

$O()$

空間複雜度:

$O()$

程式碼:

4(Hard)

限制 :

• 104

時間複雜度:

$O()$

空間複雜度:

$O()$

程式碼: