2021.10.10第262场周赛

2032. 至少在两个数组中出现的值

思路

用哈希表记录每个数出现的次数，将所有至少出现在两个数组的数返回
一个数在一个数组中最多出现一次，故先去重

代码

class Solution {
public:
    vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) {
        unordered_map<int, int> mp;
        sort(nums1.begin(), nums1.end());
        nums1.erase(unique(nums1.begin(), nums1.end()), nums1.end());
        sort(nums2.begin(), nums2.end());
        nums2.erase(unique(nums2.begin(), nums2.end()), nums2.end());
        sort(nums3.begin(), nums3.end());
        nums3.erase(unique(nums3.begin(), nums3.end()), nums3.end());
        for (int i : nums1)
            mp[i] ++ ;
        for (int i : nums2)
            mp[i] ++ ;
        for (int i : nums3)
            mp[i] ++ ;
        
        vector<int> ans;
        for (auto i : mp)
            if (i.second > 1)
                ans.push_back(i.first);
        return ans;
    }
};

2033. 获取单值网格的最小操作数

思路

将所有值排序后一字排列，即转换为货仓选址问题，选择中位数即可，最后计算距离
若无法形成单值网格，则存在某两数之差不能整除x

代码

class Solution {
public:
    int minOperations(vector<vector<int>>& grid, int x) {
        int n = grid.size(), m = grid[0].size();
        vector<int> a;
        int ming = 1e9;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                ming = min(ming, grid[i][j]);
        
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ ) {
                if ((grid[i][j] - ming) % x != 0)
                    return -1;
                a.push_back(grid[i][j] - ming);
            }      
        sort(a.begin(), a.end());
        int si = a.size();
        int mid = a[si / 2], ans = 0;
        for (int i : a)
            ans += abs(mid - i) / x;
        
        return ans;
    }
};

2034. 股票价格波动

思路

使用两个堆记录最大值和最小值
mp记录某时刻最新的价格
cnt记录某个价格出现的次数
若某个价格被覆盖，将次数减一
每次查询最大值和最小值时需判断次数是否足够

代码

class StockPrice {
public:
    int curtime;
    unordered_map<int, int> mp;
    priority_queue<int, vector<int>, less<int>> q1; //大根堆
    priority_queue<int, vector<int>, greater<int>> q2; //小根堆
    unordered_map<int, int> cnt;
    
    StockPrice() {
        curtime = 0;
    }
    
    void update(int timestamp, int price) {
        curtime = max(curtime, timestamp);
        if (mp.count(timestamp)) {
            cnt[mp[timestamp]] -- ;
        }
        mp[timestamp] = price;
        cnt[price] ++ ;
        q1.push(price);        
        q2.push(price);
    }
    
    int current() {
        return mp[curtime];
    }
    
    int maximum() {
        while (cnt[q1.top()] == 0)
            q1.pop();
        return q1.top();
    }
    
    int minimum() {
        while (cnt[q2.top()] == 0)
            q2.pop();
        return q2.top();
    }
};

/**
 * Your StockPrice object will be instantiated and called as such:
 * StockPrice* obj = new StockPrice();
 * obj->update(timestamp,price);
 * int param_2 = obj->current();
 * int param_3 = obj->maximum();
 * int param_4 = obj->minimum();
 */

2035. 将数组分成两个数组并最小化数组和的差

思路

暴力算法是从n个数中选出一半，计算两组和之差，由于n最大为30，超时
使用优化枚举的方法
先预处理一半的元素中，所有可能出现的和的情况
再枚举另一半，二分查找和相近的值，最后取最小

选取一半的数为一组可以看做将一半的数前面添加正号，另一半添加负号，求总和绝对值最小

代码

class Solution {
public:
    int minimumDifference(vector<int>& nums) {
        unordered_map<int, vector<int>> mp; //记录前一半元素所有可能的和，key为正号的个数
        int n = nums.size() / 2;
        for (int i = 0; i < (1 << n); i ++ ) {
            int z_cnt = 0; //正号个数
            int sum = 0;
            for (int j = 0; j < n; j ++ )
                if (i >> j & 1) {
                    sum += nums[j];
                    z_cnt ++ ;
                }
                else
                    sum -= nums[j];
            mp[z_cnt].push_back(sum);
        }
        for (int i = 0; i <= n; i ++ )
            sort(mp[i].begin(), mp[i].end());
        int ans = 1e9;
        for (int i = 0; i < (1 << n); i ++ ) {
            int z_cnt = 0; //正号个数
            int sum = 0;
            for (int j = 0; j < n; j ++ ) {
                if (i >> j & 1) {
                    sum += nums[n + j];
                    z_cnt ++ ;
                }
                else
                    sum -= nums[n + j];
            }
            //后一半正号个数为z_cnt，则前一半正号个数必须为n - z_cnt，在此数组中二分查找
            vector<int>& t = mp[n - z_cnt]; 
            int pos = lower_bound(t.begin(), t.end(), -sum) - t.begin();
            if (pos < t.size())
                ans = min(ans, abs(t[pos] + sum));
            if (pos > 0)
                ans = min(ans, abs(t[pos - 1] + sum));
        }
        return ans;
    }
};