Leetcode 第425场周赛分析总结

Leetcode 第425场周赛

Q1. 最小正和子数组

AC代码

class Solution {
public:
    int minimumSumSubarray(vector<int>& nums, int l, int r) {
        int n = nums.size();
        vector<int> sum(n + 1);
        for (int i = 0; i < n; ++i) {
            sum[i + 1] = sum[i] + nums[i];
        }
        int ans = -1;
        bool flag = false;
        for (int len = l; len <= r; ++len) {
            for (int i = 0, j = len - 1; j < n; ++i, ++j) {
                int tmp_sum = sum[j + 1] - sum[i];
                if (tmp_sum <= 0) continue;
                if (flag == false) {
                    ans = tmp_sum;
                    flag = true;
                } else {
                    ans = min(ans, tmp_sum);
                }
            }
        }
        return ans;
    }
};

分析总结

题目描述看完发现不是非常trivial，看了一眼数据范围，觉得不要多想直接暴力好了。闪过念头不会把数据范围变成1e5就是第三题吧，AC之后去看了一眼发现不是松了一口气。简单想了一下感觉可能和滑动窗口有关，但是却没有发现单调性，没有什么思路。

下来认真看了灵神的视频，发现果真复杂。发现自己目前存在一个问题，对于不能一眼看出思路的算法题会产生抗拒，不愿意静下心认真思考解决的方案，似乎遇到困难就会缩起来。这可能是之前刷题的时候总是苛求自己，导致闪回，遇到自己能力的边界不是一件可耻的事情。

认真分析后发现，我们要求的区间$[i,j)$和要满足下面的条件：
$$\begin{gathered} sum[j]-sum[i]>0 \\ l\le j-i\le r \end{gathered}$$
对于这种有两个变量的问题，我们可以先固定一个变量，考虑另一个变量进行简化，例如我们这里固定j（枚举右、维护左）
$$\begin{gathered} sum[i]<sum[j] \\ j-r\le i\le j-l \end{gathered}$$
即我们要在区间$[j-r,j-l]$中找到比$sum[j]$小的最大的$sum[i]$，为了得到这个信息，我们可以维护一个有序区间，在里面进行二分查找，而随着$j$的遍历，我们也要动态更新这个有序区间的值，我们可以用红黑树数据结构来维护。

class Solution {
public:
    int minimumSumSubarray(vector<int>& nums, int l, int r) {
        int n = nums.size();
        vector<int> sum(n + 1);
        for (int i = 0; i < n; ++i) {
            sum[i + 1] = sum[i] + nums[i];
        }
        int ans = -1;
        bool flag = false;
        multiset<int> segment;
        for (int j = l; j <= n; ++j) {
            segment.insert(sum[j - l]);
            auto iter = segment.lower_bound(sum[j]);
            if (iter != segment.begin()) {
                iter--; // < sum[j]
                if (!flag) {
                    flag = true;
                    ans = sum[j] - *iter;
                } else {
                    ans = min(ans, sum[j] - *iter);
                }
            }
            if (j >= r) {
                segment.erase(segment.find(sum[j - r]));
            }
        }
        return ans;
    }
};

思路清晰以后我尝试实现了一下，发现存在错误，经过仔细的分析都没有找出来问题在哪里。去研究了一下灵神的代码，发现我基本上写的和他一样，就是有一个小的地方，在erase的时候他是先find一下，再erase，而我是直接erase对应的值。刚开始我还没有注意这个问题，过了一会才想到可能是multiset在erase对应key的时候会删除所有的key，而我们正确的是只删除一个。由于之前没有怎么使用过multiset，所以忽略了这个问题。

“纸上得来终觉浅，绝知此事要躬行”。

Q2. 重排子字符串以形成目标字符串

AC代码

class Solution {
public:
    bool isPossibleToRearrange(string s, string t, int k) {
        map<string, int> cnt_s, cnt_t;
        int step = s.size() / k;
        for (int i = 0, j = 0; j < k; i += step, j++) {
            cnt_s[s.substr(i, step)]++;
            cnt_t[t.substr(i, step)]++;
        }
        return cnt_s == cnt_t;
    }
};

分析总结

觉得这个题更适合放到第一题，很快注意到分块的方式是固定的，那么我们只需要统计两个字符串中每个块出现的次数即可。注意C++中unordered_map不支持==运算符（很合理）。

看了一下灵神的代码，他是先放到vector里面再进行排序，时间复杂度和map是一样的，可能常数更小一些。

Q3. 最小数组和

class Solution {
public:
    int minArraySum(vector<int>& nums, int k, int op1, int op2) {
        int n = nums.size();

        vector memo(n, vector(op1 + 1, vector<int>(op2 + 1, -1)));
        function<int(int, int, int)> dfs;
        dfs = [&](int idx, int op1, int op2) -> int {
            if (idx == n) {
                return 0;
            }
            int& ret = memo[idx][op1][op2];
            if (ret != -1) return ret;
            ret = nums[idx] + dfs(idx + 1, op1, op2);
            if (op1 > 0) {
                int x = nums[idx];
                x = (x + 1) / 2;
                ret = min(ret, x + dfs(idx + 1, op1 - 1, op2));
                if (op2 > 0 && x >= k) {
                    ret = min(ret, x - k + dfs(idx + 1, op1 - 1, op2 - 1));
                }
            }
            if (op2 > 0 && nums[idx] >= k) {
                int x = nums[idx] - k;
                ret = min(ret, x + dfs(idx + 1, op1, op2 - 1));
                if (op1 > 0) {
                    ret = min(ret, (x + 1) / 2 + dfs(idx + 1, op1 -1, op2 - 1));
                }
            }
            return ret;
        };
        return dfs(0, op1, op2);
    }
};

Q4. 移除边之后的权重最大和

2611. 老鼠和奶酪

class Solution {
public:
    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
        for (int i = 0; i < reward1.size(); ++i) reward1[i] -= reward2[i];
        ranges::nth_element(reward1, reward1.end() - k);
        return reduce(reward2.begin(), reward2.end()) + reduce(reward1.end() - k, reward1.end());
    }
};

class Solution {
public:
    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
        int n = reward1.size();
        vector memo(n, vector(k + 1, -1));
        function<int(int, int)> dfs;
        dfs = [&](int idx, int k) -> int {
            if (idx == n) {
                return k == 0 ? 0 : numeric_limits<int>::min();
            }
            int &ret = memo[idx][k];
            if (~ret) {
                return ret;
            }
            ret = reward2[idx] + dfs(idx + 1, k);
            if (k) {
                ret = max(ret, reward1[idx] + dfs(idx + 1, k - 1));
            }
            return ret;
        };
        return dfs(0, k);
    }
};

分析总结

第四题当时没有来得及看，不过我觉得即使当时有时间应该也很难做出来，这道题在我的能力的边界。

首先最重要的应该是熟悉树形搜索的框架，对于树形搜索，我们从任意一个节点出发，在不访问父节点的情况下，不用担心节点的重复访问，因为没有环。

接下来就是思考我们希望从子树中获取什么信息，这应该是树形搜索的关键。对于这道题，我们可以对每一条边去判断删除和不删除两种情况，那么我们可以获取子树根节点：

• 最大连接边是k时子树最大权重（对应删除从当前节点到子树根节点连边）
• 最大连接数是k-1时子树最大权重（对应不删除）

两种信息。

另一个关键的点是，我们获取了所有子树的信息后，如何向上返回这两种信息。这就要用到类似上面老鼠和奶酪的思想。我们可以先选择删除所有和子树的连边，然后再贪心的选择不删除情况下增量最大的最多k（-1）条边

class Solution {
public:
    long long maximizeSumOfWeights(vector<vector<int>>& edges, int k) {
        using ll = long long;
        int n = edges.size() + 1;

        //build graph
        vector graph(n, vector<pair<int, ll>>());
        for (auto &&edge : edges) {
            int u = edge[0], v = edge[1];
            ll w = edge[2];
            graph[u].emplace_back(v, w);
            graph[v].emplace_back(u, w);
        }

        using RetType = pair<ll, ll>;   //<connect, disconnect>
        //vector memo(n, RetType{-1, -1});
        function<RetType(int, int)> dfs;
        
        dfs = [&](int u, int father) -> RetType {
            vector<ll> diff;
            ll sum = 0;
            for (auto [v, w] : graph[u]) {
                if (v == father) continue;
                auto [con, discon] = dfs(v, u);
                sum += discon;
                auto d = con - discon + w;
                if (d > 0) {
                    diff.push_back(d);
                }
            }
            //most choose k edge connect
            ranges::sort(diff, greater());
            int n = min((int)diff.size(), k - 1);
            for (int i = 0; i < n; ++i) {
                sum += diff[i];
            }
            return RetType{sum, diff.size() >= k ? sum + diff[k - 1] : sum};
        };
        auto [r0, r1] = dfs(0, -1);
        return r1;
    }
};

整个代码还是相对比较直观的，在听了灵神的思路后我自己实现了一下。结果在返回的时候遇到了bug，我想着先获取n=min(n, k)，然后再遍历累加前n-1个，最后再判断加上最后一个元素。可是实际的逻辑应该是先选前k-1个，再判断能不能选第k个。这其中细微的差异在于当n < k的时候，第n个元素仍然属于前k-1个，应该属于连接数不超过k-1的情况。

这告诫我在实现代码的时候应该遵守KISS的原则，按照逻辑用代码去描述，然后再考虑是否能够优化。一上来就使用比较trick的写法可能在逻辑上隐藏不容易发现的bug。

虽然他们把这种题目叫做树形DP，可是我并没有看到DP的影子。DP的最核心的点应该是有重复的子问题，我们通过记忆化去加速搜索，而对树进行搜索的时候并不会有重复访问同一个节点的情况，我认为叫树形搜索更加合适。

周赛总结

我认为我目前的能力应该足够应付绝大多数的周赛题目，因此应该更加自信大胆的去思考，而不是稍微卡壳就想要放弃。下次周赛加油~