Try   HackMD

Weekly Contest

日期 2024/11/10
LeetCode 出題模式有些改變,原本題目通常是 EMMH,現在會變成 E(M)MHH。

第一題

bool hasIncreasingSubarrays(vector<int>& nums, int k) {
    const int n = nums.size();
    for(int i = 0; i < n; i++) {
        int count = 0;
        int cur = -1001;
        int j = i;
        while(j < n && cur < nums[j] && count < k) {
            count++;
            cur = nums[j];
            j++;
        }

        int count2 = 0;
        cur = -1001;
        j = i + k;
        while(j < n && cur < nums[j] && count2 < k) {
            count2++;
            cur = nums[j];
            j++;
        }

        if(count == k && count2 == k)
            return true;
    }
    return false;
}

第二題

int maxIncreasingSubarrays(vector<int>& nums) {
    const int n = nums.size();
    // number of strictly increasing
    vector<int> prefix(n, 1);
    for (int i = 1; i < n; i++) {
        if (nums[i] > nums[i - 1])
            prefix[i] = prefix[i - 1] + 1;
    }

    int left = 0;
    int right = n / 2;
    int ret = 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (solve(prefix, mid)) {
            ret = max(ret, mid);
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return ret;
}

bool solve(vector<int>& prefix, int k) {
    const int n = prefix.size();
    if (k == 0)
        return true;
    for (int i = 0; i < n; i++) {
        int count = 0;
        int count2 = 0;
        int j = i + k + k - 1;
        if (i + k - 1 < n)
            count = prefix[i + k - 1];
        if (j < n)
            count2 = prefix[j];
        if (count >= k && count2 >= k)
            return true;
    }
    return false;
}

題目與第一題的差異是自己要找一個 k 數值。

第三題

第四題