../ Competitive Programming

-rw-r--r--aguang5.5 KiB2021-10-114 min read

Leet Code Weekly Contest 262

1. Two Out of Three

Naive. Just do it as described.

c++

class Solution {
public:
    vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) {
        
      set<int> any, s[3];

      for (int i = 0; i < nums1.size(); i++)
      {
          any.insert(nums1[i]);
          s[0].insert(nums1[i]);
      }

      for (int i = 0; i < nums2.size(); i++)
      {
          any.insert(nums2[i]);
          s[1].insert(nums2[i]);
      }

      for (int i = 0; i < nums3.size(); i++)
      {
          any.insert(nums3[i]);
          s[2].insert(nums3[i]);
      }

      vector<int> result;

      for (auto i = any.begin(); i != any.end(); i++)
      {
          int cnt = 0;
          
          for (int j = 0; j < 3; j++)
          {
              if (s[j].find(*i) != s[j].end())
              {
                  cnt++;
              }
          }
          
          if (cnt >= 2)
          {
              result.push_back(*i);
          }
      }

      return result;
    }
};

2. Minimum Operations to Make a Uni-Value Grid

Given any two numbers $a$ and $b$ , if $(a - b) \mod x \neq 0$ , then there will be no solution.
Median number is the optimal uni-value.

c++

class Solution {
public:
    int minOperations(vector<vector<int>>& grid, int x) {
        
        vector<int> nums;
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[i].size(); j++)
            {
                nums.push_back(grid[i][j]);
            }
        }
        
        sort(nums.begin(), nums.end());
        
        int target = nums[nums.size() / 2], ans = 0;
        
        for (int i = 0; i < nums.size(); i++)
        {
            int diff = abs(nums[i] - target);
            
            if (diff % x != 0)
            {
                return -1;
            }
            
            ans += diff / x;
        }        
        
        return ans;
    }
};

3. Stock Price Fluctuation

Put all versions of records into a priority queue.
Ignore out-dated versions.

c++

struct record
{
  int timestamp, price; 
};

class cmp_max {
  public:
  bool operator() (record x, record y) {
    return x.price < y.price;
  }
};

class cmp_min {
  public:
  bool operator() (record x, record y) {
    return x.price > y.price;
  }
};

class StockPrice {

private:
    int last_timestamp;
    map<int, int> prices;
    priority_queue<record, vector<record>, cmp_max> q_max;
    priority_queue<record, vector<record>, cmp_min> q_min;

public:
    
    StockPrice() {
        
    }
    
    void update(int timestamp, int price) {

      last_timestamp = max(timestamp, last_timestamp);

      prices[timestamp] = price;

      auto r = record();
      r.timestamp = timestamp;
      r.price = price;

      q_max.push(r);
      q_min.push(r);
    }
    
    int current() {
      return prices[last_timestamp];
    }
    
    int maximum() {
       while (!q_max.empty())
       {
         auto r = q_max.top();

         if (prices[r.timestamp] != r.price)
         {
           q_max.pop();
         }
         else
         {
           return r.price;
         }
       }

       return -1;
    }
    
    int minimum() {
      while (!q_min.empty())
      {
        auto r = q_min.top();

        if (prices[r.timestamp] != r.price)
        {
          q_min.pop();
        }
        else
        {
          return r.price;
        }
      }

      return -1;
    }
};

4. Partition Array Into Two Arrays to Minimize Sum Difference

Divide the numbers into two parts (left and right) of which the length is $N$ .
Given each part, we can enumerate all subsets $(size, sum)$ .
Iterate each $(size, sum)$ from left part, we can do a binary search to find best right subset.

c++

class Solution {
public:
    
    int minimumDifference(vector<int>& nums) {

      int n = nums.size() / 2;
      int sum = accumulate(nums.begin(), nums.end(), 0);

      vector<int> left[16], right[16];

      for (int bit = 0; bit < (2 << n); bit++)
      {
        int size = 0, l_sum = 0, r_sum = 0;

        for (int i = 0; i < n; i++)
        {
          if (bit & (1 << i))
          {
            size++;
            l_sum += nums[i];
            r_sum += nums[n + i];
          }
        }

        left[size].push_back(l_sum);
        right[size].push_back(r_sum);
      }

      for (int i = 1; i < n; i++)
      {
        sort(right[i].begin(), right[i].end());
      }

      int best_ans = min(abs(sum - 2 * (*left[n].begin())), abs(sum - 2 * (*right[n].begin())));

      for (int i = 1; i < n && best_ans > 0; i++)
      {
        for (auto &l_sum : left[i])
        {
          int r_sum = (sum / 2 ) - l_sum;

          auto q = lower_bound(right[n - i].begin(), right[n - i].end(), r_sum);

          if (q != right[n - i].end())
          {
            best_ans = min(best_ans, abs(sum - 2 * (l_sum + *q)));

            if (q != right[n - i].begin())
            {
              auto r = --q;
              best_ans = min(best_ans, abs(sum - 2 * (l_sum + *r)));
            }
          }
        }
      }
      
      return best_ans;
    }
};

press any key / click to skip