聊城高端网站建设,杭州网站前端建设,做微商网站,北京关键词排名推广最后 K 个数的乘积 请你实现一个「数字乘积类」ProductOfNumbers#xff0c;要求支持下述两种方法#xff1a; add(int num) 将数字 num 添加到当前数字列表的最后面。 getProduct(int k) 返回当前数字列表中#xff0c;最后 k 个数字的乘积。 你可以假设当前列表中始终 至少…最后 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;len0;}void add(int num) {if (!num) len0;else{pre[len]num;pre[len]*pre[len-1];}}int getProduct(int k) {if (lenk) 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);*/
最多可以参加的会议数目 给你一个数组 events其中 events[i] [startDayi, endDayi] 表示会议 i 开始于 startDayi 结束于 endDayi 。你可以在满足 startDayi d endDayi 中的任意一天 d 参加会议 i 。注意一天只能参加一个会议。请你返回你可以参加的 最大 会议数目。
class Solution {
public:static int cmp(const vectorint x, const vectorint y){return x[0] y[0];}int maxEvents(vectorvectorint events) {sort(events.begin(),events.end(),cmp);int n events.size();// 小顶堆用于高效的维护最小的 endDaypriority_queueint,vectorint, greaterint 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;}
};多次求和构造目标数组 给你一个整数数组 target 。一开始你有一个数组 A 它的所有元素均为 1 你可以执行以下操作 令 x 为你数组里所有元素的和 选择满足 0 i target.size 的任意下标 i 并让 A 数组里下标为 i 处的值为 x 。 你可以重复该过程任意次 如果能从 A 开始构造出目标数组 target 请你返回 True 否则返回 False 。
从终点往起点推每次把最大数减去剩余数的和如果最后得到的不是1而是0或者负数则false。这里做了一些剪枝优化对于减去后仍然是最大的数则可能会减很多次因此直接取模完事。
class Solution {
public:bool isPossible(vectorint target) {long long sum 0;priority_queuelong 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;}
};
根据数字二进制下 1 的数目排序 给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。如果存在多个数字二进制中 1 的数目相同则必须将它们按照数值大小升序排列。请你返回排序后的数组。
直接预处理算出每个数字的1的个数然后排序比较即可。
class Solution {
public:vectorint sortByBits(vectorint arr) {vectorint 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;}
};
每隔 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_mapint, int price;int n, discount;int custom_id;public:Cashier(int _n, int _d, vectorint products, vectorint prices): n(_n), discount(_d), custom_id(0) {for (int i 0; i products.size(); i) {price[products[i]] prices[i];}}double getBill(vectorint product, vectorint 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;}
};
包含所有三种字符的子字符串数目 给你一个字符串 s 它只包含三种字符 a, b 和 c 。请你返回 ab 和 c 都 至少 出现过一次的子字符串数目。
双指针滑动用set保存种类数组保存数量然后每次不是而是所有可能出现的后缀子数组数量因为左指针移动后不会再统计到了所以一次性计数统计完。
class Solution {
public:int numberOfSubstrings(string s) {int nRet 0;setchar 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;}
};
