又是不升不降的场，第三题做的蛮快但是居然被第二题卡了，最后发现是中位数的应用，着实是好久没碰到中位数的题了，上次碰到中位数的题还是在上次……

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

题目

给你三个整数数组 nums1、nums2 和 nums3 ，请你构造并返回一个不同数组，且由至少在两个数组中出现的所有值组成。数组中的元素可以按任意顺序排列。

示例 1：

输入：nums1 = [1,1,3,2], nums2 = [2,3], nums3 = [3]
输出：[3,2]
解释：至少在两个数组中出现的所有值为：

- 3 ，在全部三个数组中都出现过。
- 2 ，在数组 nums1 和 nums2 中出现过。

示例 2：

输入：nums1 = [3,1], nums2 = [2,3], nums3 = [1,2]
输出：[2,3,1]
解释：至少在两个数组中出现的所有值为：

- 2 ，在数组 nums2 和 nums3 中出现过。
- 3 ，在数组 nums1 和 nums2 中出现过。
- 1 ，在数组 nums1 和 nums3 中出现过。

示例 3：

1
2
3

输入：nums1 = [1,2,2], nums2 = [4,3,3], nums3 = [5]
输出：[]
解释：不存在至少在两个数组中出现的值。

提示：

1 2	1 <= nums1.length, nums2.length, nums3.length <= 100 1 <= nums1[i], nums2[j], nums3[k] <= 100

题解

签到题还是简单的，我直接拿三个set去重，然后开一个哈希表计数就可以了。

class Solution {
public:
    vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) {
        int s[110];
        unordered_set<int> s1,s2,s3;
        for(auto& x:nums1) s1.insert(x);
        for(auto& x:nums2) s2.insert(x);
        for(auto& x:nums3) s3.insert(x);
        memset(s,0,sizeof s);
        for(auto& x:s1) s[x]++;
        for(auto& x:s2) s[x]++;
        for(auto& x:s3) s[x]++;
        vector<int> ans;
        for(int i=1;i<=100;i++)
            if(s[i]>=2) ans.push_back(i);
        return ans;
    }
};

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

题目

给你一个大小为 m x n 的二维整数网格 grid 和一个整数 x 。每一次操作，你可以对 grid 中的任一元素加 x 或减 x 。

单值网格是全部元素都相等的网格。

返回使网格化为单值网格所需的最小操作数。如果不能，返回 -1 。

示例 1：

输入：grid = [[2,4],[6,8]], x = 2
输出：4
解释：可以执行下述操作使所有元素都等于 4 ： 

- 2 加 x 一次。
- 6 减 x 一次。
- 8 减 x 两次。
  共计 4 次操作。

示例 2：

1
2
3

输入：grid = [[1,5],[2,3]], x = 1
输出：5
解释：可以使所有元素都等于 3 。

示例 3：

1
2
3

输入：grid = [[1,2],[3,4]], x = 2
输出：-1
解释：无法使所有元素相等。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 10^5
1 <= m * n <= 10^5
1 <= x, grid[i][j] <= 10^4

题解

首先二维数组显然是一个障眼法，这道题跟二维数组基本上就是没什么关系，所以先将这个二维数组摊平成一个一维数组。

那么就转换成了一个经典的数轴问题，即如果有一个数轴，数轴上有若干个点。要在数轴上找一点，使得它到各个点的距离之和最短。

答案就是中位数这个点，其实这道题就是考一个中位数定理：

所有数与中位数的绝对差之和最小

找到中位数再去判断每个点是否可以到达中位数，如果有一个点不行那答案就是-1。

可能会有一个疑问就是，这里只判断了所有数能不能变成中位数，那我不变成中位数变成别的数字不是也行？大不了步骤多一点嘛！

其实也是不行的，我们观察一下其实不是-1的那些网格里的数字，其实都是可以两两相互到达的（通过若干步可以把任意一个数字变成网格里的另一个数字），只有两两相互可到达的棋盘才不会是-1，当中位数的判断失败后，因为中位数本身就是这网格中的一个数字，所以已经打破了这个两两可相互到达的条件，所以答案一定是-1。下面是具体的证明：

class Solution {
public:
    int ans;
    bool cal(vector<int>& v,int k,int x) {
        int res=0;
        for(auto& it:v){
            if(abs(it-k)%x!=0) return false;
            else res+=abs(it-k)/x;
        }
        ans=min(res,ans);
        return true;
    }
    int minOperations(vector<vector<int>>& g, int x) {
        int n=g.size(),m=g[0].size();
        ans=INT_MAX;
        vector<int> v;
        int sum=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                v.push_back(g[i][j]);
        sort(v.begin(),v.end());
        int mid=v[v.size()/2];
        cal(v,mid,x);
        if(ans==INT_MAX) return -1;
        else return ans;
    }
};

股票价格波动

题目

给你一支股票价格的数据流。数据流中每一条记录包含一个时间戳和该时间点股票对应的价格。

不巧的是，由于股票市场内在的波动性，股票价格记录可能不是按时间顺序到来的。某些情况下，有的记录可能是错的。如果两个有相同时间戳的记录出现在数据流中，前一条记录视为错误记录，后出现的记录更正前一条错误的记录。

请你设计一个算法，实现：

更新股票在某一时间戳的股票价格，如果有之前同一时间戳的价格，这一操作将更正之前的错误价格。
找到当前记录里最新股票价格。最新股票价格定义为时间戳最晚的股票价格。
找到当前记录里股票的最高价格。
找到当前记录里股票的最低价格。
请你实现 StockPrice 类：

StockPrice() 初始化对象，当前无股票价格记录。
void update(int timestamp, int price) 在时间点 timestamp 更新股票价格为 price 。
int current() 返回股票最新价格。
int maximum() 返回股票最高价格。
int minimum() 返回股票最低价格。

示例 1：

输入：
["StockPrice", "update", "update", "current", "maximum", "update", "maximum", "update", "minimum"]
[[], [1, 10], [2, 5], [], [], [1, 3], [], [4, 2], []]
输出：
[null, null, null, 5, 10, null, 5, null, 2]

解释：
StockPrice stockPrice = new StockPrice();
stockPrice.update(1, 10); // 时间戳为 [1] ，对应的股票价格为 [10] 。
stockPrice.update(2, 5);  // 时间戳为 [1,2] ，对应的股票价格为 [10,5] 。
stockPrice.current();     // 返回 5 ，最新时间戳为 2 ，对应价格为 5 。
stockPrice.maximum();     // 返回 10 ，最高价格的时间戳为 1 ，价格为 10 。
stockPrice.update(1, 3);  // 之前时间戳为 1 的价格错误，价格更新为 3 。
                          // 时间戳为 [1,2] ，对应股票价格为 [3,5] 。
stockPrice.maximum();     // 返回 5 ，更正后最高价格为 5 。
stockPrice.update(4, 2);  // 时间戳为 [1,2,4] ，对应价格为 [3,5,2] 。
stockPrice.minimum();     // 返回 2 ，最低价格时间戳为 4 ，价格为 2 。

提示：

1
2
3

1 <= timestamp, price <= 10^9
update，current，maximum 和 minimum 总 调用次数不超过 10^5 。
current，maximum 和 minimum 被调用时，update 操作 至少 已经被调用过 一次 。

题解

一道考map的题目，两个map就可以解决，一个map的键值对是时间和价格，另一个map的键值对是价格和该价格出现的次数（当次数为0时将这个价格erase掉）。

由于C++的map内部使用平衡树，本身就是有序的，每次取最小和最大只需要访问begin()和rbegin()这两个迭代器就行，所以可以很方便的找到最大最小的价格。就是注意update的时候要同步添加和删除价格。

class StockPrice {
public:
    unordered_map<int,int> mp;
    map<int,int> m;
    int mx,mi,cnt;
    StockPrice() {
        cnt=-1;
    }
    void update(int timestamp, int price) {
        cnt=max(cnt,timestamp);
        if(mp.count(timestamp)){
            int t=mp[timestamp];
            m[t]--;
            if(m[t]==0) m.erase(t);
        }
        mp[timestamp]=price;
        m[price]++;
    }
    
    int current() {
        return mp[cnt];
    }
    
    int maximum() {
        auto it=m.end();
        it--;
        return it->first;
    }
    
    int minimum() {
        auto it=m.begin();
        return it->first;
    }
};

/**
 * 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();
 */

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

题目

给你一个长度为 2 * n 的整数数组。你需要将 nums 分成两个长度为 n 的数组，分别求出两个数组的和，并 最小化 两个数组和之 差的绝对值 。nums 中每个元素都需要放入两个数组之一。

请你返回最小的数组和之差。

示例 1：

输入：nums = [3,9,7,3]
输出：2
解释：最优分组方案是分成 [3,9] 和 [7,3] 。
数组和之差的绝对值为 abs((3 + 9) - (7 + 3)) = 2 。

示例 2：

输入：nums = [-36,36]
输出：72
解释：最优分组方案是分成 [-36] 和 [36] 。
数组和之差的绝对值为 abs((-36) - (36)) = 72 。

示例 3：

输入：nums = [2,-1,0,4,-2,-9]
输出：0
解释：最优分组方案是分成 [2,4,-9] 和 [-1,0,-2] 。
数组和之差的绝对值为 abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0 。

提示：

1 <= n <= 15
nums.length == 2 * n
-107 <= nums[i] <= 107

In The End

Leetcode周赛第262场题解

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

题目

题解

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

题目

题解

股票价格波动

题目

题解

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

题目

题解