[leetcode] 周賽 211

2020 年 10 月 18 日
筆記
leetcode

🏆 比賽題目：//leetcode-cn.com/circle/discuss/luvHfG/

兩個相同字符之間的最長子字符串

開始理解錯題意了，結果提交了 2 次錯誤答案 🤒️ 。

用一個 map 記錄字符出現的第一次位置即可。時間 \(O(n)\)，空間 \(O(1)\) 。

class Solution {
public:
    int maxLengthBetweenEqualCharacters(string s) 
    {
        int maxval = -1;
        unordered_map<char, int> m;
        int len = s.length();
        for (int i=0; i<len; i++)
        {
            if (m.count(s[i]) == 1)
                maxval = max(maxval, i-m[s[i]]-1);
            else
                m[s[i]] = i;
        }
        return maxval;
    }
};

帶閾值的圖連通性

題目：5128. 帶閾值的圖連通性。

這題看出來是考察並查集的，但是第一次寫是通過窮舉圖中的任意 2 個點是否聯通實現的，時間複雜度是 \(O(N^2)\) ，超時了。

class Solution {
public:
    vector<int> root;
    vector<bool> res;
    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) 
    {
        root.resize(n + 1, -1);
        for (int i=1; i<=n; i++)
        {
            for (int j=i+1; j<=n; j++)
            {
                if (check(n, threshold, j, i))
                    merge(i,j);
            }
        }
        for (auto &v: queries)
            res.push_back(find(v[0]) == find(v[1]));
        return res;
    }
    void merge(int x, int y)
    {
        x = find(x), y = find(y);
        if (x != y) root[y] = x;
    }
    int find(int x)
    {
        return root[x] == -1 ? x : (root[x] = find(root[x]));
    }
    int gcd(int a, int b)  // require a >= b
    {
        return (b == 0) ? a : gcd(b, a % b);
    }
    bool check(int n, int threshold, int x, int y)
    {
        return gcd(x, y) > threshold;
    }
};

然後也考慮了一下怎麼優化，我的第一直覺是從「倍數」關係入手，對於 i 節點，我們只需要看它與 j=2*i, 3*i, 4*i, ... 是否聯通。但是仔細一想，不對勁 🤨 ，比如 threshold = 2 時，i=6, j=9 這 2 個節點也是聯通的，這麼做不就忽略這種情況嗎？

但其實並沒有。

因為 gcd(6, 9) = 3 ，所以其實 6 和 9 在並查集當中通過 3 連起來了。所以通過循環 i=3, j=6,9,... 時，我們已經把這種情況考慮了。

只需要改一下內層循環：

for (int i=1; i<=n; i++)
    for (int j=i+i; j<=n; j+=i)
        if (check(n, threshold, j, i))
            merge(i, j);

實際上 i 可以從 threshold 開始。

空間複雜度 \(O(n)\) 。下面看時間複雜度分析。

首先，雙重循環的複雜度是：

\[\sum_{i=1}^{n}\frac{n}{i} = n \sum_{i=1}^{n}\frac{1}{i}
\]

問題來了，這裡有一個調和級數（真忘記了當時上算法課有沒有學過 🤒️ ），但是高數裡邊判斷是否收斂有個叫積分判別法的東西。所以有（這裡的等號並不嚴謹）：

\[\sum_{i=1}^{n}\frac{1}{i} = \int_{1}^{n} \frac{1}{x}dx = \ln{n}
\]

所以雙重循壞複雜度是 \(O(n \log n)\)，此外，每次循環還包含一次並查集操作，所以總的時間複雜度是 \(O(n \log n \cdot \alpha(n))\) .

無矛盾的最佳球隊

題目：5545. 無矛盾的最佳球隊。

這 TM 應該是最難的一道題了，看完題解的我還是一臉懵逼。

首先排序，年齡小的在前，同年齡分數小的在前。

那麼對於 data[i] ，在其之前的人中（即下面的 data[j] ），跟他沒有矛盾的條件是：

同一年齡
分數小於等於 data[i] 的分數

定義 dp[i] 是在區間 [0, i] 上選取人員，且選中人員 i 時最大分數。

轉移方程：

\[dp[i] = max(score[i], score[i] + dp[j]), 0 \le j < i
\]

有點類似於 LIS ，即最長上升子序列。

class Node 
{
public:
    int score, age;
    Node(int s, int a): score(s), age(a){}
    bool operator < (const Node &n) const
    {
        return age < n.age || (age == n.age && score < n.score);
    }
};
class Solution {
public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) 
    {
        int n = scores.size();
        vector<Node> data;
        for (int i=0; i<n; i++)
            data.push_back(Node(scores[i], ages[i]));
        sort(data.begin(), data.end());
        vector<int> dp(n);
        int maxval = data[0].score;
        for (int i=0; i<n; i++)
        {
            dp[i] = data[i].score;
            for (int j=0; j<i; j++)
            {
                if (data[j].age == data[i].age || data[j].score <= data[i].score)
                    dp[i] = max(dp[i], dp[j] + data[i].score);
            }
            maxval = max(maxval, dp[i]);
        }
        return maxval;
    }
};

還有一題是：5544. 執行操作後字典序最小的字符串，都說窮舉（我也想到了），但就是寫不出來，我是傻逼。

就這樣吧，不要太難為自己 2333 。

Tags: leetcode