鸭梨公共文档

主题

第 339 场周赛 ​

6362. 最长平衡子字符串 ​

遍历，当遇到 '0' 时清除计数，最后取最大值。

cpp
class Solution {
public:
    int findTheLongestBalancedSubstring(string s) {
        int n = s.size();
        int res = 0;
        int count0 = 0, count1 = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '0') {
                if (count1) count1 = count0 = 0;
                count0++;
            } else {
                count1++;
            }
            res = max(res, min(count0, count1) * 2);
        }
        return res;
    }
};

6363. 转换二维数组 ​

计数，使用哈希表储存计数即可。

cpp
class Solution {
public:
    vector<vector<int>> findMatrix(vector<int>& nums) {
        unordered_map<int, int> count;
        for (auto beg = nums.cbegin(); beg != nums.cend(); ++beg)
            count[*beg]++;
        vector<vector<int>> res;
        while (true) {
            bool is_finished = true;
            vector<int> temp;
            for (auto beg = count.begin(); beg != count.end(); ++beg) {
                if (beg->second >= 1) {
                    temp.push_back(beg->first);
                    is_finished = false;
                    beg->second -= 1;
                }
            }
            if (is_finished) break;
            res.push_back(temp);
        }
        return res;
    }
};

6364. 老鼠和奶酪 ​

贪心，假设全部被第一只老鼠吃掉，然后每次选择最大的差值，直到第二只吃掉 n−kn-k 个奶酪。

cpp
class Solution {
public:
    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
        int res = 0;
        for (int i = 0; i < reward1.size(); ++i) res += reward1[i];
        vector<int> minus;
        for (int i = 0; i < reward1.size(); ++i)
            minus.push_back(reward2[i] - reward1[i]);
        sort(minus.begin(), minus.end(), greater<int>());
        for (int i = 0; i < (int)reward1.size() - k; ++i) res += minus[i];
        return res;
    }
};

6365. 最少翻转操作数 ​

TODO 暂未通过，通过 BFS，双向查找。（696 / 710 个通过测试用例）

cpp
class Solution {
public:
    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
        if (k <= 1) {
            vector<int> res(n, -1);
            res[p] = 0;
            return res;
        }
        vector<int> res(n, 0);
        for (int v : banned) res[v] = -1;
        queue<pair<int, int>> q;
        q.push({p, 0});
        while (!q.empty()) {
            int pos = q.front().first;
            int step = q.front().second;
            q.pop();
            for (int s = k; s > 0; s -= 2) {
                int delta = (k - s) / 2;
                if (pos - delta >= 0 && pos + s - 1 + delta < n) {
                    int curr = res[pos + s - 1];
                    if (curr == -1) continue;
                    if (curr == 0) {
                        res[pos + s - 1] = step + 1;
                        q.push({pos + s - 1, step + 1});
                    } else if (curr > step + 1) {
                        res[pos + s - 1] = step + 1;
                        q.push({pos + s - 1, step + 1});
                    }
                }
            }
            for (int s = k; s > 0; s -= 2) {
                int delta = (k - s) / 2;
                if (pos - s + 1 - delta >= 0 && pos + delta < n) {
                    int curr = res[pos - s + 1];
                    if (curr == -1) continue;
                    if (curr == 0) {
                        res[pos - s + 1] = step + 1;
                        q.push({pos - s + 1, step + 1});
                    } else if (curr > step + 1) {
                        res[pos - s + 1] = step + 1;
                        q.push({pos - s + 1, step + 1});
                    }
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            if (res[i] == 0) res[i] = -1;
        }
        res[p] = 0;
        return res;
    }
};