【Leetcode周赛】contest-262 (2021年10月11日)

链接：https://leetcode.com/contest/weekly-contest-262

T1: 2032. Two Out of Three

https://leetcode.com/problems/two-out-of-three/

思路：无

T2: 2033. Minimum Operations to Make a Uni-Value Grid

https://leetcode.com/problems/minimum-operations-to-make-a-uni-value-grid/

思路：排序找中位数。（为啥能行，其实我也不知道。。）

 1 class Solution {
 2 public:
 3     int minOperations(vector<vector<int>>& grid, int x) {
 4         int m = grid.size(), n = grid[0].size();
 5         vector<int> nums(m * n);
 6         for (int i = 0; i < m; ++i) {
 7             for (int j = 0; j < n; ++j) {
 8                 nums[j + i * n] = grid[i][j];
 9             }
10         }
11         sort(nums.begin(), nums.end());
12         int median = nums[(m*n-1)/2];
13         int res = 0;
14         for (int i = 0; i < nums.size(); ++i) {
15             if (abs(nums[i] - median) % x) {
16                 return -1;
17             }
18             int times = abs(nums[i] - median) / x;
19             res += times;
20         } 
21         return res;
22     }
23 };

T3: 2034. Stock Price Fluctuation

https://leetcode.com/problems/stock-price-fluctuation/Design an algorithm that:

Updates the price of the stock at a particular timestamp, correcting the price from any previous records at the timestamp.
Finds the latest price of the stock based on the current records. The latest price is the price at the latest timestamp recorded.
Finds the maximum price the stock has been based on the current records.
Finds the minimum price the stock has been based on the current records.

Implement the StockPrice class:

StockPrice() Initializes the object with no price records.
void update(int timestamp, int price) Updates the price of the stock at the given timestamp.
int current() Returns the latest price of the stock.
int maximum() Returns the maximum price of the stock.
int minimum() Returns the minimum price of the stock.

思路：我用了两个 map，做了一个类似倒排索引的结构。

 1 class StockPrice {
 2 public:
 3     map<int, int> tsToPriceMap;
 4     map<int, unordered_set<int>> priceToTsMap;
 5     StockPrice() {
 6         
 7     }
 8     
 9     void update(int timestamp, int price) {
10         if (tsToPriceMap.count(timestamp)) {
11             int orignalPrice = tsToPriceMap[timestamp];
12             priceToTsMap[orignalPrice].erase(timestamp);
13             if (priceToTsMap[orignalPrice].empty()) {
14                 priceToTsMap.erase(orignalPrice);
15             }
16         } 
17         tsToPriceMap[timestamp] = price;
18         priceToTsMap[price].insert(timestamp);
19     }
20     
21     int current() {
22         return prev(tsToPriceMap.end())->second;
23     }
24     
25     int maximum() {
26         return prev(priceToTsMap.end())->first;
27     }
28     
29     int minimum() {
30         return (priceToTsMap.begin())->first;
31     }
32 };
33 
34 /**
35  * Your StockPrice object will be instantiated and called as such:
36  * StockPrice* obj = new StockPrice();
37  * obj->update(timestamp,price);
38  * int param_2 = obj->current();
39  * int param_3 = obj->maximum();
40  * int param_4 = obj->minimum();
41  */

T4: 2035. Partition Array Into Two Arrays to Minimize Sum Difference

https://leetcode.com/problems/partition-array-into-two-arrays-to-minimize-sum-difference/

思路：没有 --- 大坑未补。