Weekly Contest 404

日期 2024/06/30

第二題與第三題只差在餘數 k 而已，使得第二題可以用簡單的解法，結果我反而卡在第二題，超過中午才解出來。
第三題是 Dynamic Programming 題目，就是很普通的題目。解題的時候 DP table 初始條件設錯導致除錯很久。

• Maximum Height of a Triangle
• Find the Maximum Length of Valid Subsequence I
• Find the Maximum Length of Valid Subsequence II
• Find Minimum Diameter After Merging Two Trees

第一題

int maxHeightOfTriangle(int red, int blue) {
    int ret = 1;
    while(true) {
        // 1 + 3 + 5 + 7 ...
        int a = 0;
        for(int i = 1; i <= ret; i += 2) {
            a += i;
        }

        int b = 0;
        for(int i = 2; i <= ret; i += 2) {
            b += i;
        }
        bool c1 = red >= a && blue >= b;
        bool c2 = blue >= a && red >= b;
        if(!c1 && !c2)
            break;
        ret++;
    }
    return ret- 1;
}

第二題

int maximumLength(vector<int>& nums) {
    const int n = nums.size();
    int r1 = 0;
    int r2 = 0;
    for(int x: nums) {
        r1 += x % 2 == 0;
        r2 += x % 2 == 1;
    }

    int r3 = 0;
    int odd = 1;
    int even = 0;
    int r4 = 0;
    for(int i = 0; i < n; i++) {
        int x = nums[i] + odd;
        if(x % 2 == 1) {
            r3++;
            odd = !odd;
        }

        int y = nums[i] + even;
        if(y % 2 == 1) {
            r4++;
            even = !even;
        }
    }

    int ret = 0;
    ret = max(r1, ret);
    ret = max(r2, ret);
    ret = max(r3, ret);
    ret = max(r4, ret);
    return ret;
}

第三題

int maximumLength(vector<int> &nums, int k)
{
    const int n = nums.size();
    vector<vector<int>> dp(n + 1, vector<int>(k, 1));
    /*
    dp[i][0]: 以第 i 個元素為結尾，且餘數為 0 的最大子陣列
    dp[i][1]: 以第 i 個元素為結尾，且餘數為 1 的最大子陣列
    */

    int ret = 1;
    for (int i = 1; i < n; i++) {
        for (int j = i - 1; j >= 0; j--) {
            int x = (nums[i] + nums[j]) % k;
            dp[i][x] = max(dp[i][x], dp[j][x] + 1);
            ret = max(ret, dp[i][x]);
        }
    }
    return ret;
}

第四題