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 40010int 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();// 小顶堆：用于高效的维护最小的 endDaypriority_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;}
};