LC Biweekly Contest 146

https://leetcode.com/contest/biweekly-contest-146/

3392. Count Subarrays of Length Three With a Condition

Tag: Array

class Solution {
public:
    int countSubarrays(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        for (int i = 2; i < n; i++)
            ans += (nums[i - 2] + nums[i]) * 2 == nums[i - 1];
        return ans;
    }
};

Time Complexity: O(n)
Space: O(1)

3393. Count Paths With the Given XOR Value

Tag:DP

typedef long long ll;
class Solution {
public:
    ll mod = 1e9 + 7;
    int countPathsWithXorValue(vector<vector<int>>& grid, int target) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<vector<ll>>> f(m, vector<vector<ll>>(n, vector<ll>(16, 0)));
        f[0][0][grid[0][0]] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i - 1 >= 0) {
                    for (int k = 0; k < 16; k++)
                        f[i][j][grid[i][j] ^ k] += f[i - 1][j][k];
                }
                if (j - 1 >= 0) {
                    for (int k = 0; k < 16; k++)
                        f[i][j][grid[i][j] ^ k] += f[i][j - 1][k];
                }
                for (int k = 0; k < 16; k++) f[i][j][k] %= mod;
            }
        }
        return f[m - 1][n - 1][target];
    }
};

Time Complexity: O(m * n * 16)
Space: O(m * n * 16)

算是經典 DP 的稍微變形，需要注意一下他的數值限制就可以發現他希望你使用的做法，基本上看到他的數字都不大就知道可以暴力 DP 了。

再來就是如果 Bottom-up 的 DP 不知道怎麼做也可以考慮使用 Top-down的 DP 會比較好理解。

Top-down: 會把 DP 類型的題目使用遞迴的方式解出來，同時他會需要搭配 memory 的方式紀錄曾經算過的東西。
Bottom-up: 會把 DP 類型的題目使用迴圈的方式解出來。

3394. Check if Grid can be Cut into Sections

Tag: Sort

class Solution {
public:
    static const bool cmpY(vector<int> &a, vector<int> &b) {
        if (a[1] != b[1]) return a[1] < b[1];
        return a[3] < b[3];
    }
    static const bool cmpX(vector<int> &a, vector<int> &b) {
        if (a[0] != b[0]) return a[0] < b[0];
        return a[2] < b[2];
    }
    bool checkValidCuts(int sz, vector<vector<int>>& rectangles) {
        int n = rectangles.size();
        sort(rectangles.begin(), rectangles.end(), cmpY);
        int cnt = 0;
        int l = 0, r = 1;
        while (r < n) {
            while (rectangles[l][3] <= rectangles[r][1]) {
                l += 1;
            }
            cnt += l == r;
            if (cnt == 2) return true;
            r += 1;
        }

        sort(rectangles.begin(), rectangles.end(), cmpX);
        cnt = 0;
        l = 0, r = 1;
        while (r < n) {
            while (l < r && rectangles[l][0] < rectangles[r][0] && rectangles[l][2] <= rectangles[r][0]) {
                l += 1;
            }
            cnt += (l == r);
            if (cnt == 2) return true;
            r += 1;
        }
        return false;
    }
};

n = rectangles.size
Time Complexity: O(nlogn)
Space: O(1)

基本上我們可以把水平與垂直分開處理，只要你知道水平怎麼處理就會知道垂直怎麼解了。核心部分就在我們需要分別對起始的 x 或是 y 進行排序，然後使用雙指針就可以知道在哪個地方進行切割。