LC Weekly Context 430

https://leetcode.com/contest/weekly-contest-430/

3402. Minimum Operations to Make Columns Strictly Increasing

class Solution {
public:
    int minimumOperations(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans += max(0, grid[i - 1][j] + 1 - grid[i][j]);
                grid[i][j] = max(grid[i][j], grid[i - 1][j] + 1);
            }
        }
        return ans;
    }
};

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

普通的 Greedy 題目，使用 Greedy 想法就可以通過了。

3403. Find the Lexicographically Largest String From the Box I

class Solution {
public:
    string answerString(string word, int numFriends) {
        if (numFriends == 1) return word;
        int n = word.size();
        int maxLen = n - numFriends + 1;
        string ans = "";
        for (int i = 0; i < n; i++) {
            int len = min(maxLen, n - i);
            string cur = word.substr(i, len);
            if (ans == "") ans = cur;
            else if (ans.compare(cur) < 0) ans = cur;
        }
        return ans;
    }
};

Time Complexity: O(n^2)
Space: O(n)

這題的關鍵在於發現答案的長度會在 n - numFriends + 1 ，這個條件但是比較沒有這麼好的地方在 Time Complexity 會到 O(n^2)。

3404. Count Special Subsequences

本題的核心關鍵在轉換 nums[p] * nums[r] == nums[q] * nums[s] 這個式子變成，
nums[p] / nums[q] == nums[q] / nums[r] ，這樣就會簡單許多了。

typedef long long ll;
class Solution {
public:
    long long numberOfSubsequences(vector<int>& nums) {
        int n = nums.size();
        ll ans = 0;
        unordered_map<double, ll> f;
        vector<ll> cnt(1001, 0);
        for (int i = n - 1; i >= 6; i--) cnt[nums[i]] += 1;
        f[1.0 * nums[0] / nums[2]] += 1;
        for (int i = 4; i < n; i++) {
            for (int j = 1; j <= 1000; j++) {
                if (cnt[j] == 0) continue;
                double target = 1.0 * j / nums[i];
                ans += f[target] * cnt[j];
            }
            for (int j = i - 3; j >= 0; j--) {
                f[1.0 * nums[j] / nums[i - 1]] += 1;
            }
            if (i + 2 < n) cnt[nums[i + 2]] -= 1;
        }
        return ans;
    }
};

第一種解法是透過 double 作為 Map 的 key 保存，透過找尋是否存在這樣的數字來達成，但是這樣會有精度的問題，不過本題不會發生，所以這樣也是會通過的。

typedef long long ll;
class Solution {
public:
    string trans(int a, int b) {
        int c = gcd(a, b);
        a /= c;
        b /= c;
        return to_string(a) + "/" + to_string(b);
    }
    long long numberOfSubsequences(vector<int>& nums) {
        int n = nums.size();
        ll ans = 0;
        unordered_map<string, ll> f;
        vector<ll> cnt(1001, 0);
        for (int i = n - 1; i >= 6; i--) cnt[nums[i]] += 1;
        f[trans(nums[0], nums[2])] += 1;
        for (int i = 4; i < n; i++) {
            for (int j = 1; j <= 1000; j++) {
                if (cnt[j] == 0) continue;
                string target = trans(j, nums[i]);
                ans += f[target] * cnt[j];
            }
            for (int j = i - 3; j >= 0; j--) {
                f[trans(nums[j], nums[i - 1])] += 1;
            }
            if (i + 2 < n) cnt[nums[i + 2]] -= 1;
        }
        return ans;
    }
};

在第二種解法我們透過分數的方式來表達 key ，使用分數就可以避免掉經度上面的問題，但是由於我們只能透過字串的方式來儲存，所以會導致在比對上花費比較多的時間。

Time Complexity: O(n^2)
Space: O(n^2)

3405. Count the Number of Arrays with K Matching Adjacent Elements

typedef long long ll;
class Solution {
public:
    ll mod = 1e9 + 7;   
    ll myPow(ll a, ll b) {
        ll res = 1;
        while (b) {
            if (b & 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }
    long long computeInv(int x) {
        ll s = 1;
        for (; x > 1; x = mod % x)
        s = s * (mod - mod / x) % mod;
        return s;
    }
    int countGoodArrays(int n, int m, int k) {
        n -= k;
        vector<ll> f(k + n);
        f[0] = 1;
        for (int i = 1; i < f.size(); i++) f[i] = f[i - 1] * i % mod;
        ll comb = (f[k + n - 1] * computeInv(f[n - 1]) % mod) * computeInv(f[k + n - 1 - n + 1]) % mod;
        return (m * myPow(m - 1, n - 1) % mod) * comb % mod;
    }
};

純粹的數學題目，但是需要使用到 inverse ，所以也沒有很建議現在寫。

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