讨论/技术交流/🏆 第 231 场力扣周赛/
🏆 第 231 场力扣周赛
2
共 79 个回复

Leetcode 第231场周赛题解

Problem A - 检查二进制字符串字段

一次遍历即可。

  • 时间复杂度O(∣S∣)\mathcal{O}(|S|)。
  • 空间复杂度O(1)\mathcal{O}(1)。
class Solution {
public:
    bool checkOnesSegment(string s) {
        int ans = 0;
        char last = '0';
        for (char c : s) {
            if (c == '1' && last == '0') {
                ans++;
            }
            last = c;
        }
        return ans <= 1;
    }
};

Problem B - 构成特定和需要添加的最少元素

计算出差值的绝对值Δ=∣goal−∑nums∣\Delta=|goal-\sum nums|,则最后的答案为⌈Δlimit⌉\left\lceil\frac{\Delta}{limit}\right\rceil。实际实现时需要注意除法中包含负数时的结果可能与预期不符,最好的办法是单独处理Δ=0\Delta=0的情形。

  • 时间复杂度O(N)\mathcal{O}(N)。
  • 空间复杂度O(1)\mathcal{O}(1)。
typedef long long ll;

class Solution {
public:
    int minElements(vector<int>& nums, int limit, int goal) {
        ll sum = 0;
        for (int num : nums)
            sum += num;
        ll delta = abs(sum - goal);
        if (delta == 0)
            return 0;
        return (delta - 1) / limit + 1;
    }
};

Problem C - 从第一个节点出发到最后一个节点的受限路径数

从NN开始跑一次单源Dijkstra,之后按照distdist升序进行动态规划求解。

  • 时间复杂度O(Elog⁡V)\mathcal{O}(E\log V)。
  • 空间复杂度O(E+V)\mathcal{O}(E+V)。
typedef long long ll;
const ll MOD = 1e9 + 7;

class Solution {
public:
    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        vector<vector<pair<int, int>>> adj(n + 1);
        for (auto &edge : edges) {
            int u = edge[0], v = edge[1], d = edge[2];
            adj[u].emplace_back(v, d);
            adj[v].emplace_back(u, d);
        }
        vector<int> dist(n + 1, INT_MAX);
        dist[n] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        pq.emplace(0, n);
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > dist[u])
                continue;
            for (auto [v, c] : adj[u]) {
                if (d + c < dist[v]) {
                    dist[v] = d + c;
                    pq.emplace(dist[v], v);
                }
            }
        }
        vector<int> order(n);
        for (int i = 0; i < n; ++i)
            order[i] = i + 1;
        sort(order.begin(), order.end(), [&](int u, int v) {
            return dist[u] < dist[v]; 
        });
        vector<ll> ans(n + 1);
        ans[n] = 1;
        for (int u : order) {
            for (auto [v, c] : adj[u]) {
                if (dist[v] > dist[u]) {
                    ans[v] = (ans[v] + ans[u]) % MOD;
                }
            }
        }
        return ans[1];
    }
};

Problem D - 使所有区间的异或结果为零

容易发现,最后得到的数组一定满足:

  • a1=ak+1=a2k+1=…a_1=a_{k+1}=a_{2k+1}=\dots
  • a2=ak+2=a2k+2=…a_2=a_{k+2}=a_{2k+2}=\dots
  • …\dots

因此可以考虑将同一组中的数放在一起进行考虑。

首先,我们对每一组分别进行计数。

接下来,我们用动态规划求解。dp[val]dp[val]表示处理到当前组时,异或值为valval的最小修改次数。显然初值(考虑第一组之前)为:

  • dp[0]=0dp[0]=0
  • dp[val]=∞ (val≠0)dp[val]=\infty\ (val\neq0)

在转移时,我们有两种选择:

  1. 将当前组的数全都改为同一个值,此时不管我们之前如何选择,都可以利用这一个值的选择得到任何一个异或值,那么我们自然应该选择之前的代价中最小的那个,此时的代价为size[i]+min⁡dp[val]size[i]+\min{dp[val]},新状态的异或值可以为[0,2D)[0,2^D)中的任意一个值。这一转移需要进行KK次。
  2. 使用当前组中的某一个值val′val'。此时我们需要枚举之前的异或值valval(或枚举达到的目标值,二者是等价的),此时的代价为size[i]−cnt[i][val′]+dp[val]size[i]-cnt[i][val']+dp[val],新状态的异或值为val⊕val′val\oplus val'。这一转移最多需要进行NN次。
  • 时间复杂度O(2D⋅(K+N))\mathcal{O}(2^D\cdot(K+N))。其中D=10D=10。
  • 空间复杂度O(N+2D)\mathcal{O}(N + 2^D)。
const int INF = 0x3f3f3f3f;

class Solution {
public:
    int minChanges(vector<int>& nums, int k) {
        int n = nums.size();
        vector<unordered_map<int, int>> groups(k);
        vector<int> size(k);
        for (int i = 0; i < k; ++i) {
            for (int j = i; j < n; j += k) {
                groups[i][nums[j]]++;
                size[i]++;
            }
        }
        
        vector<int> dp(1 << 10, INF);
        dp[0] = 0;
        for (int i = 0; i < k; ++i) {
            int lo = *min_element(dp.begin(), dp.end());
            vector<int> ndp(1 << 10, lo + size[i]);
            for (int j = 0; j < (1 << 10); ++j) {
                if (dp[j] == INF)
                    continue;
                for (auto [p, freq] : groups[i]) {
                    int nxt = p ^ j;
                    ndp[nxt] = min(ndp[nxt], dp[j] + size[i] - freq);
                }
            }
            dp = move(ndp);
        }
        
        return dp[0];
    }
};
31

前两道题20mins做完了,后面的题打扰了。

菜鸡痛哭。

15

Leetcode刷题两极分化严重难得太难,简单的太简单

10

读懂题目的时间超过大佬完成所有题目的时间

8

题意看不懂。

4

看到图论,就知道今天的竞赛对我来说已经结束了

4

第三题好不容易写出来 超时了 Orz

3

第三题看麻了

3

为啥还没加分嘞

2

有人一起打周赛刷题吗

2