leetcode解题思路分析(一百五十五)1352 - 1358 题
- 最后 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);*/
- 最多可以参加的会议数目
给你一个数组 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;}
};
- 多次求和构造目标数组
给你一个整数数组 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 的数目排序
给你一个整数数组 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;}
};
- 每隔 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;}
};
- 包含所有三种字符的子字符串数目
给你一个字符串 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 题
最后 K 个数的乘积 请你实现一个「数字乘积类」ProductOfNumbers,要求支持下述两种方法: add(int num) 将数字 num 添加到当前数字列表的最后面。 getProduct(int k) 返回当前数字列表中,最后 k 个数字的乘积。 你可以假设当前列表中始终 至少…...

如何将普通maven项目转为maven-web项目
文件-项目结构(File-->Project Structure ) 模块-->learn(moudle-->learn) 选中需要添加web的moudle,点击加号,我得是learn,单击选中后进行下如图操作: 编辑路径 结果如下…...

LeetCode 226. 翻转二叉树
给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。 示例 1: 输入:root [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1] 示例 2: 输入:root [2,1,3] 输出:[2,3,1] 示例…...
【ArcGIS Pro二次开发】(85):Aspose.Cells中的Excel操作
Aspose.Cells是一款功能强大的Excel文档处理和转换控件,开发人员和客户电脑无需安装Microsoft Excel也能在应用程序中实现类似Excel的强大数据管理功能。 1、获取工作薄Workbook string excelFile "C:\Users\Administrator\Desktop\FE.xlsx"; Workbook …...

基于java+springboot+vue实现的兴顺物流管理系统(文末源码+Lw)23-287
摘 要 传统信息的管理大部分依赖于管理人员的手工登记与管理,然而,随着近些年信息技术的迅猛发展,让许多比较老套的信息管理模式进行了更新迭代,货运信息因为其管理内容繁杂,管理数量繁多导致手工进行处理不能满足广…...
pytorch view、expand、transpose、permute、reshape、repeat、repeat_interleave
非contiguous操作 There are a few operations on Tensors in PyTorch that do not change the contents of a tensor, but change the way the data is organized. These operations include: narrow(), view(), expand() and transpose() permute() This is where the con…...

uni-app实现下拉刷新
业务逻辑如下: 1.在滚动容器中加入refresher-enabled属性,表示为开启下拉刷新 2.监听事件,添加refresherrefresh事件 3.在事件监听函数中加载数据 4.关闭动画,添加refresher-triggered属性,在数据请求前开启刷新动画…...

vue ts 应用梳理
文章目录 前言一、页面传值1.1 [props](https://cn.vuejs.org/guide/components/props.html)1.2 [emit](https://cn.vuejs.org/guide/components/events.html)1.3 [store](https://pinia.vuejs.org/zh/getting-started.html) 二、实时计算2.1 [watch](https://cn.vuejs.org/gui…...

CUDA12.4文档-全文翻译
本博客参考官方文档进行介绍,全网仅此一家进行中文翻译,走过路过不要错过。 官方网址:https://docs.nvidia.com/cuda/cuda-c-programming-guide/ 本文档分成多个博客进行介绍,在本人专栏中含有所有内容: https://blog.csdn.net/qq_33345365/category_12610860.html CU…...

【C 数据结构】循环链表
文章目录 【 1. 基本原理 】【 2. 循环链表的创建 】2.1 循环链表结点设计2.2 循环单链表初始化 【 3. 循环链表的 插入 】【 4. 循环单链表的 删除操作 】【 5. 循环单链表的遍历 】【 6. 实例 - 循环链表的 增删查改 】【 7. 双向循环链表 】 【 1. 基本原理 】 对于单链表以…...
Python列表
使用场景:列表是用来存储多组数据的 列表是可变类型 列表支持切片 1.基本规则 1.列表使用[]来表示 2.初始化列表:list [] 3.列表可以一次性存储多个数据:[数据1,数据2,数据3,…] 4.列表中的每一项&#…...
谈谈系列之金融直播展业畅想
近些年直播异常火热,对于各大中小型基金证券公司,也纷纷引入直播作为新型展业渠道。在这其中有一部分直接采用第三方云平台,也有少部分选择自建直播平台。当然自建直播平台也不是纯自研,大抵都是外购第三方厂商整体解决方案&#…...

【C 数据结构】双向链表
文章目录 【 1. 基本原理 】【 2. 双向链表的 创建 】实例 - 输出双向链表 【 3. 双向链表 添加节点 】【 4. 双向链表 删除节点 】【 5. 双向链表查找节点 】【 7. 双向链表更改节点 】【 8. 实例 - 双向链表的 增删查改 】 【 1. 基本原理 】 表中各节点中都只包含一个指针&…...

Leetcode刷题之消失的数字(C语言版)
Leetcode刷题之消失的数字(C语言版) 一、题目描述二、题目解析 一、题目描述 数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗? 注意:本题相对书上原题稍作…...

LeetCode654:最大二叉树
题目描述 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 创建一个根节点,其值为 nums 中的最大值。 递归地在最大值 左边 的 子数组前缀上 构建左子树。 递归地在最大值 右边 的 子数组后缀上 构建右子树。 返回 nums 构建的 …...

AI禁区徘徊监测识别摄像机
AI禁区徘徊监测识别摄像机是一种基于人工智能技术的智能监控设备,用于监测禁止进入或逗留的区域。这种摄像机通过高清摄像头实时捕捉场景图像,利用AI算法对人员徘徊行为进行识别和监测,有助于提高安全防范水平,减少潜在的安全风险…...

【学习】什么是信创适配性测试?信创适配性测试的重要性有哪些?
随着信息技术的快速发展和广泛应用,信息技术应用创新(信创)已成为推动我国产业升级和经济发展的重要力量。在信创领域,适配性测试至关重要,它不仅关系到信创产品的质量和性能,还直接影响到用户的使用体验和…...
linux 配置服务开机启动
一、Centos 中配置进程开启启动 1、使用 systemd 服务: (1)创建一个名为 myapp.service 的服务文件: [Unit] DescriptionMyApp #描述 After #描述服务类别 [Service] Typefork…...
React中State管理的4 个关键解决方案
在 React 应用开发中,状态(state)管理是非常重要的一部分。合理地管理状态可以确保组件的行为正确,提高应用的可维护性和性能。然而,在实际使用 React 的 state 时,开发者常常会遇到一些常见的问题和陷阱。 本文将从解决问题的角度,总结 React 中 state 管理的4个关键技巧: 使…...

Testng测试框架(6)--@Factory动态地创建测试类的实例
工厂允许您动态地创建测试。例如,假设您想创建一个测试方法,该方法将多次访问网站上的某个页面,并且您希望使用不同的值来调用它。 public class TestWebServer {Test(parameters { "number-of-times" })public void accessPage(…...

深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...

UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...

HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...