周赛第一次AK

2022-12-27

虽然全是水题,但是菜鸡第一次周赛四题全部AC还是好激动!

6020. 将数组划分成相等数对

给你一个整数数组 nums,它包含 2 \* n个整数。

你需要将 nums划分成 n 个数对,满足:

  1. 每个元素 只属于一个 数对。
  2. 同一数对中的元素 相等 。

如果可以将 nums划分成 n 个数对,请你返回 true,否则返回 false


class Solution {
public:
    bool divideArray(vector& nums) {
        if (nums.size() % 2) { return false; }

       unordered_map<int,int> map;

        for (int i : nums) {
            map[i]++;
        }

        for (auto &p : map) {
            if (p.second % 2) {
                return false;
            }
        }

        return true;
    }

};

6021.字符串中最多数目的子字符串

给你一个下标从 0 开始的字符串 text和另一个下标从 0 开始且长度为 2 的字符串 pattern,两者都只包含小写英文字母。

你可以在 text中任意位置插入 一个 字符,这个插入的字符必须是 pattern[0] 或者 pattern[1] 。注意,这个字符可以插入在 text开头或者结尾的位置。

请你返回插入一个字符后,text中最多包含多少个等于 pattern的 子序列 。

子序列 指的是将一个字符串删除若干个字符后(也可以不删除),剩余字符保持原本顺序得到的字符串。


class Solution {
public:
    long long maximumSubsequenceCount(string text, string pattern) {
        int m = text.length(), n = pattern.length(); long long origin = 0, max = 0;

        auto prev0 = vector<long long>(m + 1, 0);
        auto next1 = vector<long long>(m, 0);

        long long prev = 0, next = 0;
        for (int i = 0; i <= m; i++) {
            prev0[i] = prev;
            if (text[i] == pattern[0]) {
                prev++;
            }
        }

        for (int i = m - 1; i >= 0; i--) {
            if (text[i] == pattern[1]) {
                next++;
                origin += prev0[i];
            }
            next1[i] = next;
        }

        for (int i = 0; i < m; i++) {
            long long l0 = prev0[i], r1 = next1[i];
            max = std::max(max, std::max(l0, r1));
        }

        max = std::max(max, prev0.back());

        return max + origin;
    }
};

6022. 将数组和减半的最少操作次数

给你一个正整数数组 nums。每一次操作中,你可以从 nums中选择任意一个数并将它减小到恰好一半(注意,在后续操作中你可以对减半过的数继续执行操作)

请你返回将 nums数组和至少减少一半的最少操作数。


class Solution {
public:
    int halveArray(vector& nums) {
        double sum = 0;
        double half = 0;
        int step = 0;
        priority_queue pq;

        for (const int& i : nums) {
            sum += (double)i;
            pq.emplace((double)i);
        }

        half = sum / double(2);

        while (sum > half && !pq.empty()) {
            double t = pq.top();
            pq.pop();
            sum -= t / (double)2;
            pq.emplace(t - t / (double)2);
            step++;
        }

        return step;
    }
};

6023.用地毯覆盖后的最少白色砖块

给你一个下标从 0开始的二进制字符串 floor,它表示地板上砖块的颜色。

  1. floor[i] = \0\表示地板上第i块砖块的颜色是黑色 。
  2. floor[i] = \1\表示地板上第i块砖块的颜色是白色 。

同时给你 numCarpetscarpetLen。你有 numCarpets条黑色的地毯,每一条黑色的地毯长度都为 carpetLen块砖块。请你使用这些地毯去覆盖砖块,使得未被覆盖的剩余白色砖块的数目最小。地毯相互之间可以覆盖。

请你返回没被覆盖的白色砖块的最少数目。

 

class Solution {
public:
    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
        if (numCarpets * carpetLen >= floor.length()) {
            return 0;
        }

        while (numCarpets--) {
            int maxWhite = 0, maxPos = 0, white = 0;
            for (int i = 0; i < carpetLen; i++) {
                if (floor[i] == \1\) {
                    white++;
                    maxWhite++;
                }
            }

            for (int i = carpetLen; i < floor.length(); i++) {
                if (maxWhite == carpetLen) {
                    maxPos = i - carpetLen;
                    break;
                }
                if (floor[i - carpetLen] == \1\) {
                    white--;
                }
                if (floor[i] == \1\) {
                    white++;
                }
                if (white > maxWhite) {
                    maxWhite = white;
                    maxPos = i - carpetLen + 1;
                }
            }

            for (int i = 0; i < carpetLen; i++) {
                floor[maxPos + i] = \0\;
            }
    }

    int ans = 0;

    for (int i = 0; i < floor.length(); i++) {
        if (floor[i] == \1\) {
            ans++;
        }
    }

    return ans;
}

};