leetcode解题思路分析（一百五十五）1352 - 1358 题

1352. 最后 K 个数的乘积
      请你实现一个「数字乘积类」ProductOfNumbers，要求支持下述两种方法：
      add(int num)
      将数字 num 添加到当前数字列表的最后面。
      getProduct(int k)
      返回当前数字列表中，最后 k 个数字的乘积。
      你可以假设当前列表中始终 至少 包含 k 个数字。
      题目数据保证：任何时候，任一连续数字序列的乘积都在 32-bit 整数范围内，不会溢出。

本体比较麻烦的就是数字可能为0，不然直接前缀积搞定。所以这里做一个调整：如果遇到0，则前面都不计了，重新开始计算，然后取乘积，取到超过计数那说明有0，直接返回0即可。

class ProductOfNumbers {
public:
    #define N 40010
    int len,pre[N];
    ProductOfNumbers() {
        pre[0]=1;
        len=0;
    }
    
    void add(int num) {
        if (!num) len=0;
        else{
            pre[++len]=num;
            pre[len]*=pre[len-1];
        }
    }
    
    int getProduct(int k) {
        if (len<k) return 0;
        return pre[len]/pre[len-k];
    }
};

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
 */

1353. 最多可以参加的会议数目
      给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。请你返回你可以参加的 最大 会议数目。

class Solution {
public:
    static int cmp(const vector<int>& x, const vector<int>& y)
    {
        return x[0] < y[0];
    }
    
    int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(),events.end(),cmp);
         int n = events.size();
        // 小顶堆：用于高效的维护最小的 endDay
        priority_queue<int,vector<int>, greater<int>> pq;
        int res = 0;
        int curDay = 1;
        int i = 0;
        while (i < n || !pq.empty()) {
            // 将所有开始时间等于 currDay 的会议的结束时间放到小顶堆
            while (i < n && events[i][0] == curDay) {
                pq.push(events[i][1]);
                i++;
            }

            // 将已经结束的会议弹出堆中，即堆顶的结束时间小于 currDay 的
            while (!pq.empty() && pq.top() < curDay) {
                pq.pop();
            }

            // 贪心的选择结束时间最小的会议参加
            if (!pq.empty()) {
                // 参加的会议，就从堆中删除
                pq.pop();
                res++;
            }

            // 当前的天往前走一天，开始看下下一天能不能参加会议
            curDay++;
        }

        return res;
    }
};

1354. 多次求和构造目标数组
      给你一个整数数组 target 。一开始，你有一个数组 A ，它的所有元素均为 1 ，你可以执行以下操作：
      令 x 为你数组里所有元素的和
      选择满足 0 <= i < target.size 的任意下标 i ，并让 A 数组里下标为 i 处的值为 x 。
      你可以重复该过程任意次
      如果能从 A 开始构造出目标数组 target ，请你返回 True ，否则返回 False 。

从终点往起点推，每次把最大数减去剩余数的和，如果最后得到的不是1而是0或者负数则false。这里做了一些剪枝优化：对于减去后仍然是最大的数，则可能会减很多次，因此直接取模完事。

class Solution {
public:
    bool isPossible(vector<int>& target) {
        long long sum = 0;
        priority_queue<long long> q;
        for(int ev: target){
            sum += ev;
            q.push(ev);
        }
        while(q.top() != 1){
            long long curMax = q.top(); q.pop();
            long long otherSum = sum - curMax;
            if(curMax - otherSum < 1 || otherSum == 0) return false;
            long long temp = curMax % otherSum;
            if(temp == 0) temp = otherSum;
            q.push(temp);
            sum = sum - curMax + temp;
        }
        return true;
    }
};

1356. 根据数字二进制下 1 的数目排序
      给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。请你返回排序后的数组。

直接预处理算出每个数字的1的个数，然后排序比较即可。

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        vector<int> bit(10001, 0);
        for (int i = 1; i <= 10000; ++i) {
            bit[i] = bit[i >> 1] + (i & 1);
        }
        sort(arr.begin(), arr.end(), [&](int x, int y){
            if (bit[x] < bit[y]) {
                return true;
            }
            if (bit[x] > bit[y]) {
                return false;
            }
            return x < y;
        });
        return arr;
    }
};

1357. 每隔 n 个顾客打折
      超市里正在举行打折活动，每隔 n 个顾客会得到 discount 的折扣。超市里有一些商品，第 i 种商品为 products[i] 且每件单品的价格为 prices[i] 。结账系统会统计顾客的数目，每隔 n 个顾客结账时，该顾客的账单都会打折，折扣为 discount （也就是如果原本账单为 x ，那么实际金额会变成 x - (discount * x) / 100 ），然后系统会重新开始计数。顾客会购买一些商品， product[i] 是顾客购买的第 i 种商品， amount[i] 是对应的购买该种商品的数目。
      请你实现 Cashier 类：
      Cashier(int n, int discount, int[] products, int[] prices) 初始化实例对象，参数分别为打折频率 n ，折扣大小 discount ，超市里的商品列表 products 和它们的价格 prices 。
      double getBill(int[] product, int[] amount) 返回账单的实际金额（如果有打折，请返回打折后的结果）。返回结果与标准答案误差在 10^-5 以内都视为正确结果。

简单到无聊的题目。

class Cashier {
private:
    unordered_map<int, int> price;
    int n, discount;
    int custom_id;
    
public:
    Cashier(int _n, int _d, vector<int>& products, vector<int>& prices): n(_n), discount(_d), custom_id(0) {
        for (int i = 0; i < products.size(); ++i) {
            price[products[i]] = prices[i];
        }
    }
    
    double getBill(vector<int> product, vector<int> amount) {
        ++custom_id;
        double payment = 0;
        for (int i = 0; i < product.size(); ++i) {
            payment += price[product[i]] * amount[i];
        }
        if (custom_id % n == 0) {
            payment -= payment * discount / 100;
        }
        return payment;
    }
};

1358. 包含所有三种字符的子字符串数目
      给你一个字符串 s ，它只包含三种字符 a, b 和 c 。请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。

双指针滑动，用set保存种类，数组保存数量，然后每次不是++而是+所有可能出现的后缀子数组数量，因为左指针移动后不会再统计到了，所以一次性计数统计完。

class Solution {
public:
    int numberOfSubstrings(string s) 
    {
        int nRet = 0;
        set<char> CharSet;
        int NumCnt[3] = {0, 0, 0};
        int nSize = s.size();
        int nLeft = 0;

        for (int i = 0; i < nSize; ++i)
        {
            char c = s[i];
            CharSet.insert(c);
            NumCnt[c - 'a']++;
            while (CharSet.size() == 3)
            {
                nRet += nSize - i;
                NumCnt[s[nLeft] - 'a']--;
                if (NumCnt[s[nLeft] - 'a'] == 0)
                    CharSet.erase(s[nLeft]);
                nLeft++;
            }
        }

        return nRet;
    }
};