LeetCode --- 444 周赛

题目列表

3507. 移除最小数对使数组有序 I
3508. 设计路由器
3509. 最大化交错和为 K 的子序列乘积
3510. 移除最小数对使数组有序 II

一、移除最小数对使数组有序 I & II

由于数组是给定的，所以本题的操作步骤是固定的，我们只要能快速模拟操作的过程即可
设 $i、j$ 为当前进行了操作之后的一对相邻元素下标

• 如何快速找到 $nums[i]$ 左右两边相邻的 $nums[l]、nums[r]$

  • 思路一：维护下标的有序集合，当我们进行合并 $nums[i]、nums[j](i<j)$时 ，删除 $j$，保留 $i$，当我们要查找 $i$ 左右两边的相邻元素时，就去二分查找答案，可以用 $set$ 维护
  • 思路二：用数组模拟双向链表的增删查改操作，即维护数组 $left[i]、right[i]$，分别记录 $i$ 左右两边的元素下标

• 如何快速的找到和最小的 $nums[i]、nums[j]？$

  • 可以用最小堆记录 p a i r { n u m s [ i ] + n u m s [ j ] , i } pair\{nums[i]+nums[j],i\} pair{nums[i]+nums[j],i}，这里的 $i$ 为数对下标中较小的那个，即 $i<j$
  • 当我们将 $nums[i]、nums[j]$ 跟新为 $nums[i]+nums[j]$ (记为 $s$)时，不仅需要向堆中添加 { n u m s [ l ] + s , l } 、 { s + n u m s [ r ] , i } \{nums[l]+s,l\}、\{s+nums[r],i\} {nums[l]+s,l}、{s+nums[r],i}，还需要从堆中删除 { n u m s [ l ] + n u m s [ i ] , l } 、 { n u m s [ i + 1 ] + n u m s [ r ] , j } \{nums[l]+nums[i],l\}、\{nums[i+1]+nums[r],j\} {nums[l]+nums[i],l}、{nums[i+1]+nums[r],j}，需要用到懒删除的技巧
  • 如果不会懒删除技巧，可以用有序集合 $set$ 来模拟实现懒删除堆

代码如下

// C++
class Solution {
public:
    int minimumPairRemoval(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n, -1), right(n + 1, n); // 模拟双向链表
        priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
        int cnt = 0; //  记录 nums[i] > nums[i+1] 的个数，以此来判断数组是否是非递减的
        // 初始化
        for(int i = 0; i < n; i++){
            right[i] = i + 1;
            if(i + 1 < n) {
                left[i+1] = i;
                pq.emplace(nums[i] + nums[i+1], i);
                cnt += nums[i] > nums[i + 1];
            }
        }
        int step = 0;
        while(cnt > 0){
        	// 懒删除
        	// right[pq.top().second] >= n 表示当前 pq.top().second 已经被合并后删除
        	// pq.top().first != nums[pq.top().second] + nums[right[pq.top().second]] 表示 nums[right[pq.top().second]] 已经被合并过了
            while(right[pq.top().second] >= n || pq.top().first != nums[pq.top().second] + nums[right[pq.top().second]]){
                pq.pop();
            }
            auto [s, i] = pq.top(); pq.pop();
            int l = left[i], j = right[i], r = right[j]; // l,i,j,r 之间的大小关系发生变化
            // 由于 i、j 要合并，先去掉之前的大小关系
            if(nums[i] > nums[j]) cnt--;
            if(l != -1 && nums[l] > nums[i]) cnt--;
            if(r != n && nums[j] > nums[r]) cnt--;
			// 加入新的大小关系
            if(l != -1 && nums[l] > s) cnt++;
            if(r != n && s > nums[r]) cnt++;
			// 如果 i 的前面有数字，则将{nums[l]+s,l}加入堆中
            if(l != -1){
                pq.emplace(s + nums[l], l);
            }
            // 如果 i 的后面有数字，则将{nums[r]+s,r}加入堆中
            if(r != n){
                pq.emplace(s + nums[r], i);
            }
            // 删除 j 结点，保留 i 结点
            // 让 i -> r, r -> i
            // 同时让 j -> n 表示 结点 j 被删除
            if(j < n) right[i] = right[j], right[j] = n;
            if(r < n) left[r] = i;
            nums[i] = s; // 跟新当前合并之后的值
            step++;
        }
        return step;
    }
};

二、设计路由器

本题关键理解题意，抽象出我们需要使用的数据结构

• $int[]forwardPacket()$ 需要先进先出：需要有一个 $queue$
• $booladdPacket(intsource,intdestination,inttimestamp)$ 要求不能重复插入相同的数据包：需要一个哈希表 $unordered\_set$，记录插入过的数据包
• $intgetCount(intdestination,intstartTime,intendTime)$ 获取尚未转发的时间在 $[startTime,endTime]$ 中，且目标为 $destination$ 的数据包的个数：这里我们可以把 $destination$ 相同的数据包放在一个数组中，由于数据包是按照时间顺序插入的，我们可以用二分法，获取区间内的数据包个数，即额外维护一个 $unordered\_map<int,vector<int>>$

代码如下

class Router {
    unordered_map<int,vector<int>> d_t; // [d, vt]
    // 这里使用循环数组模拟队列
    vector<tuple<int,int,int>> v;
    int l = 0, r = 0;
    unordered_set<string> st;
public:
    Router(int memoryLimit) : v(memoryLimit + 1) {}
    
    bool addPacket(int s, int d, int t) {
        string mask = to_string(s) + '|' +  to_string(d) + '|' + to_string(t);
        if(st.count(mask)) return false;
        st.insert(mask);
        if((r + 1)%v.size() == l){ // 队列满
            auto [ss, dd, tt] = v[l++];
            l %= v.size();
            st.erase(to_string(ss) + '|' + to_string(dd) + '|' + to_string(tt));
            d_t[dd].erase(d_t[dd].begin());
        }
        d_t[d].push_back(t);
        v[r++] = {s, d, t};
        r %= v.size();
        return true;
    }
    
    vector<int> forwardPacket() {
        if(r == l) return {}; // 队列为空
        auto [s, d, t] = v[l++];
        l %= v.size();
        d_t[d].erase(d_t[d].begin());
        st.erase(to_string(s) + '|' + to_string(d) + '|' + to_string(t));
        return {s, d, t};
    }
    
    int getCount(int d, int startTime, int endTime) {
        auto& v = d_t[d];
        return ranges::upper_bound(v, endTime) - ranges::lower_bound(v, startTime);
    }
};

三、最大化交错和为 K 的子序列乘积

本题只需要暴搜即可，因为状态的个数并没有我们想象的那么多

• 状态定义为 $dfs(i,s,m,op,empty)$

  • $i$ 表示枚举的数字下标
  • $s$ 表示交错和
  • $m$ 表示子序列的元素乘积
  • $op$ 表示当前元素是取正，还是取负
  • $empty$ 表示子序列是否为空

• 有人可能觉得这个状态太多了，肯定会超时
  
  因为 $m$ 的取值范围是 $[1,5000]$，但实际上，在当前的数据范围内 $m$ 最多只有 $394+1$ 种可能取值($+1$ 表示当子序列中有 $0$ 时，乘积为 $0$)，可以通过如下代码进行验证

int init = [](){
    set<int> st{1};
    for(int i = 0; i < 150; i++){ // 150 个值
        auto tmp = st;
        for(auto x : st){
            for(int i = 1; i <= 12; i++){ // 每个值有可以取 1~12
                if(x * i <= 5000){
                    st.insert(x * i);
                }
            }
        }
    }
    cout << st.size() << endl;
    return 0;
}();

代码如下

class Solution {
public:
    int maxProduct(vector<int>& nums, int k, int limit) {
        int total = reduce(nums.begin(), nums.end());
        if (total < abs(k)) { // |k| 太大
            return -1;
        }

        int n = nums.size(), ans = -1;
        unordered_set<long long> vis;
        auto dfs = [&](this auto&& dfs, int i, int s, int m, bool op, bool empty) -> void {
            // 无法让 ans 变得更大
            // 注意：当 m > limit && ans < 0 时，如果在选择一个0，既能让 m < limt，ans = 0
            if (ans == limit || m > limit && ans >= 0) { 
                return;
            }

            if (i == n) {
                if (!empty && s == k && m <= limit) { // 合法子序列
                    ans = max(ans, m); // 更新答案的最大值
                }
                return;
            }

            long long mask = (long long) i << 32 | (s + total) << 15 | m << 2 | op << 1 | empty;
            if (!vis.insert(mask).second) {
                return;
            }

            // 不选 x
            dfs(i + 1, s, m, op, empty);

            // 选 x
            int x = nums[i];
            dfs(i + 1, s + (op ? -x : x), min(m * x, limit + 1), !op, false);
        };
        dfs(0, 0, 1, false, true);
        return ans;
    }
};