leetcode第273周赛补题

因为上午有实验，只能下午再来补题了，顺带记录下，前两题太简单就不赘述了

竞赛链接

T3: 5965. 相同元素的间隔之和

---

思路

哈希表+前缀和统计（这个知识点我印象中以前出现过，不过却把公式忘记了，麻了

Code

class Solution {
public:
    vector<long long> getDistances(vector<int>& arr) {
        // mark.first 表示arr中出现的数字
        // mark.second.first 表示位置之和
        // mark.second.second 表示出现次数

        unordered_map<int, pair<int64_t, int64_t >> mark;
        // anw 用于存储答案
        vector<long long> anw(arr.size());

        // 开始正序遍历
        for (int i = 0; i < arr.size(); i++) {
            auto &data = mark[arr[i]];
            // 从 mark 中取出 sum_{i,0} 和 cnt_{i,0}，更新 anw[i]
            anw[i] += data.second * 1L * i - data.first;
            // 更新 sum_{i,0} 和 cnt_{i,0}
            data.second ++;
            data.first += i;
        }
        // 重置  mark，以便在逆序遍历中使用
        mark.clear();
        // 开始逆序遍历
        for (int i = arr.size()-1; i >= 0; --i) {
            auto &data = mark[arr[i]];
            // 从 mark 中取出 sum_{i,1} 和 cnt_{i,1}，更新 anw[i]
            anw[i] += data.first - data.second * 1L * i;
            // 更新 sum_{i,1} 和 cnt_{i,1}
            data.second ++;
            data.first += i;
        }
        return anw;
    }
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

T4: 5966. 还原原数组

---

思路

做的时候没想出来，后来看完题解后我直呼妙

                                                枚举k

Code

class Solution {
public:
    vector<int> recoverArray(vector<int>& nums) {
        // 寻找 k 的候选值，并存储到 cand 中。
        sort(nums.begin(), nums.end());
        unordered_set<int> cand;
        for (int i = 1; i < nums.size(); i++) {
            if (((nums[i] - nums[0])&1) == 0 && nums[i] != nums[0]) {
                cand.insert((nums[i]-nums[0])/2);
            }
        }
        // anw 用于存储答案
        vector<int> anw;
        // 构造哈希表，以便实现 O(n) 构造过程。
        unordered_multiset<int> mark1;
        for (auto num : nums) {
            mark1.insert(num);
        }
        // 枚举 k
        for (auto k : cand) {
            // 初始化 anw 和 mark，用于一次构造过程
            unordered_multiset<int> mark = mark1;
            anw.resize(0);
            anw.reserve(nums.size()/2);
            // 从小到大枚举 nums
            for (int i = 0; i < nums.size(); i++) {
                int num = nums[i];
                auto fit = mark.find(num);
                // 如果 num 不在 mark 中，说明已经被删除了，继续下一个。
                if (fit == mark.end()) { continue; }
                // num 在 mark 中，则 num+2k 必须在 mark 中。即 num 属于 lower，num+2k 属于 higher
                auto sit = mark.find(num + 2*k);
                if (sit == mark.end()) {
                    break;
                }
                // 删除 num 和 num+2k，并将 num+k 放入 anw 中。
                anw.push_back(num + k);
                mark.erase(fit);
                mark.erase(sit);
            }
            // 构造成功，返回答案。否则继续处理下一个候选值
            if (anw.size() == nums.size()/2) {
                return anw;
            }
        }
        // 题目保证了一定有答案，因此不会执行到这。加这个只是为了消除编译报警。
        return vector<int>{};
    }
};

复杂度分析

• 时间复杂度：O(n^2)
• 空间复杂度：O(n)

个人总结

t3和t4都是很不错的题目，考察的细节还是蛮多的，虽然不涉及到太复杂的算法，但比较考验🧠和经验（一定要常复习