leetcode解题思路分析(一百五十五)1352 - 1358 题

2024-04-11 21:36

本文主要是介绍leetcode解题思路分析(一百五十五)1352 - 1358 题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  1. 最后 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);*/
  1. 最多可以参加的会议数目
    给你一个数组 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;}
};
  1. 多次求和构造目标数组
    给你一个整数数组 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;}
};
  1. 根据数字二进制下 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;}
};
  1. 每隔 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;}
};
  1. 包含所有三种字符的子字符串数目
    给你一个字符串 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;}
};

这篇关于leetcode解题思路分析(一百五十五)1352 - 1358 题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/895244

相关文章

Python中的Walrus运算符分析示例详解

《Python中的Walrus运算符分析示例详解》Python中的Walrus运算符(:=)是Python3.8引入的一个新特性,允许在表达式中同时赋值和返回值,它的核心作用是减少重复计算,提升代码简... 目录1. 在循环中避免重复计算2. 在条件判断中同时赋值变量3. 在列表推导式或字典推导式中简化逻辑

Java程序进程起来了但是不打印日志的原因分析

《Java程序进程起来了但是不打印日志的原因分析》:本文主要介绍Java程序进程起来了但是不打印日志的原因分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java程序进程起来了但是不打印日志的原因1、日志配置问题2、日志文件权限问题3、日志文件路径问题4、程序

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

Python 迭代器和生成器概念及场景分析

《Python迭代器和生成器概念及场景分析》yield是Python中实现惰性计算和协程的核心工具,结合send()、throw()、close()等方法,能够构建高效、灵活的数据流和控制流模型,这... 目录迭代器的介绍自定义迭代器省略的迭代器生产器的介绍yield的普通用法yield的高级用法yidle

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串,目前我找到两种解决问题的思路,具体实现如下:

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

kotlin中const 和val的区别及使用场景分析

《kotlin中const和val的区别及使用场景分析》在Kotlin中,const和val都是用来声明常量的,但它们的使用场景和功能有所不同,下面给大家介绍kotlin中const和val的区别,... 目录kotlin中const 和val的区别1. val:2. const:二 代码示例1 Java

Go标准库常见错误分析和解决办法

《Go标准库常见错误分析和解决办法》Go语言的标准库为开发者提供了丰富且高效的工具,涵盖了从网络编程到文件操作等各个方面,然而,标准库虽好,使用不当却可能适得其反,正所谓工欲善其事,必先利其器,本文将... 目录1. 使用了错误的time.Duration2. time.After导致的内存泄漏3. jsO

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3

找不到Anaconda prompt终端的原因分析及解决方案

《找不到Anacondaprompt终端的原因分析及解决方案》因为anaconda还没有初始化,在安装anaconda的过程中,有一行是否要添加anaconda到菜单目录中,由于没有勾选,导致没有菜... 目录问题原因问http://www.chinasem.cn题解决安装了 Anaconda 却找不到 An