Weekly Contest 429

日期 2024/12/22

第三題沒時間想出來，討論區是使用 binary search 猜一個數字，並驗證這個數字是否可行。

• Minimum Number of Operations to Make Elements in Array Distinct
• Maximum Number of Distinct Elements After Operations
• Smallest Substring With Identical Characters I
• Smallest Substring With Identical Characters II

第一題

    int minimumOperations(vector<int>& nums) {
        unordered_map<int, int> freq;
        for(int x: nums)
            freq[x]++;

        int ret = 0;
        const int n = nums.size();
        int i = 0;

        auto check = [&freq]() {
            for(auto kv: freq) {
                if(kv.second > 1)
                    return false;
            }
            return true;
        };
        
        if(check())
            return 0;
        while(i < n) {
            if(i + 2 < n) {
                freq[nums[i]]--;
                freq[nums[i + 1]]--;
                freq[nums[i + 2]]--;
                ret++;
                i = i + 3;
            }else{
                for(int j = i; j < n; j++)
                    freq[nums[j]]--;
                ret++;
                i = n;
            }
            if(check())
                return ret;
        }

        return ret;
    }

第二題

mmin 用於記錄最小可使用數值，避免重複計算(不這樣做會 TLE)

    int maxDistinctElements(vector<int>& nums, int k) {
        const int n = nums.size();
        unordered_set<int> used;
        sort(nums.begin(), nums.end());

        int mmin = nums[0] - k;
        for (int i = 0; i < n;) {
            int count = 0;
            while(i + count < n && nums[i] == nums[i + count])
                count++;

            int x = nums[i];
            i += count;
            int start = max(x - k, mmin);
            while(count--) {
                while(start <= x + k) {
                    auto it = used.insert(start);
                    start++;
                    if(it.second) {
                        // cout << x + k << " ";
                        break;
                    }
                        
                }
            }
            mmin = max(mmin, start);
        }
        return used.size();
    }

第三題

https://leetcode.com/problems/smallest-substring-with-identical-characters-i/solutions/6172678/binary-search-with-special-case-for-mid-1

    bool check(string& s, int numOps, char startChar) {
        for (int i = 0; i < s.size(); i++) {
            if (startChar == s[i])
                numOps--;
            startChar = !(startChar - '0') + '0';
        }
        return numOps >= 0;
    }

    bool isValid(string& s, int numOps, int mid) {
        if (mid == 1)
            return check(s, numOps, '1') || check(s, numOps, '0');

        int count = 0;
        for (int i = 0, last = -1; i < s.size(); i++) {
            if (s[i] == last)
                count++;
            else {
                numOps -= count / (mid + 1);
                last = s[i];
                count = 1;
            }
        }
        if (count > mid)
            numOps -= count / (mid + 1);
        return numOps >= 0;
    }

    int minLength(string s, int numOps) {
        int start = 1;
        int end = s.size();
        int ret = s.size();
        while (start <= end) {
            int mid = (start + end) / 2;
            if (isValid(s, numOps, mid)) {
                ret = mid;
                end = mid - 1;
            } else
                start = mid + 1;
        }
        return ret;
    }

第四題

與第三題相同