当前位置: 首页 > news >正文

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 题

最后 K 个数的乘积 请你实现一个「数字乘积类」ProductOfNumbers&#xff0c;要求支持下述两种方法&#xff1a; add(int num) 将数字 num 添加到当前数字列表的最后面。 getProduct(int k) 返回当前数字列表中&#xff0c;最后 k 个数字的乘积。 你可以假设当前列表中始终 至少…...

如何将普通maven项目转为maven-web项目

文件-项目结构&#xff08;File-->Project Structure &#xff09; 模块-->learn&#xff08;moudle-->learn&#xff09; 选中需要添加web的moudle&#xff0c;点击加号&#xff0c;我得是learn&#xff0c;单击选中后进行下如图操作&#xff1a; 编辑路径 结果如下…...

LeetCode 226. 翻转二叉树

给你一棵二叉树的根节点 root &#xff0c;翻转这棵二叉树&#xff0c;并返回其根节点。 示例 1&#xff1a; 输入&#xff1a;root [4,2,7,1,3,6,9] 输出&#xff1a;[4,7,2,9,6,3,1] 示例 2&#xff1a; 输入&#xff1a;root [2,1,3] 输出&#xff1a;[2,3,1] 示例…...

【ArcGIS Pro二次开发】(85):Aspose.Cells中的Excel操作

Aspose.Cells是一款功能强大的Excel文档处理和转换控件&#xff0c;开发人员和客户电脑无需安装Microsoft Excel也能在应用程序中实现类似Excel的强大数据管理功能。 1、获取工作薄Workbook string excelFile "C:\Users\Administrator\Desktop\FE.xlsx"; Workbook …...

基于java+springboot+vue实现的兴顺物流管理系统(文末源码+Lw)23-287

摘 要 传统信息的管理大部分依赖于管理人员的手工登记与管理&#xff0c;然而&#xff0c;随着近些年信息技术的迅猛发展&#xff0c;让许多比较老套的信息管理模式进行了更新迭代&#xff0c;货运信息因为其管理内容繁杂&#xff0c;管理数量繁多导致手工进行处理不能满足广…...

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实现下拉刷新

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

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列表

使用场景&#xff1a;列表是用来存储多组数据的 列表是可变类型 列表支持切片 1.基本规则 1.列表使用[]来表示 2.初始化列表&#xff1a;list [] 3.列表可以一次性存储多个数据&#xff1a;[数据1&#xff0c;数据2&#xff0c;数据3&#xff0c;…] 4.列表中的每一项&#…...

谈谈系列之金融直播展业畅想

近些年直播异常火热&#xff0c;对于各大中小型基金证券公司&#xff0c;也纷纷引入直播作为新型展业渠道。在这其中有一部分直接采用第三方云平台&#xff0c;也有少部分选择自建直播平台。当然自建直播平台也不是纯自研&#xff0c;大抵都是外购第三方厂商整体解决方案&#…...

【C 数据结构】双向链表

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

Leetcode刷题之消失的数字(C语言版)

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

LeetCode654:最大二叉树

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

AI禁区徘徊监测识别摄像机

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

【学习】什么是信创适配性测试?信创适配性测试的重要性有哪些?

随着信息技术的快速发展和广泛应用&#xff0c;信息技术应用创新&#xff08;信创&#xff09;已成为推动我国产业升级和经济发展的重要力量。在信创领域&#xff0c;适配性测试至关重要&#xff0c;它不仅关系到信创产品的质量和性能&#xff0c;还直接影响到用户的使用体验和…...

linux 配置服务开机启动

一、Centos 中配置进程开启启动 1、使用 systemd 服务&#xff1a; &#xff08;1&#xff09;创建一个名为 myapp.service 的服务文件&#xff1a; [Unit] DescriptionMyApp #描述 After #描述服务类别 [Service] Typefork…...

React中State管理的4 个关键解决方案

在 React 应用开发中,状态(state)管理是非常重要的一部分。合理地管理状态可以确保组件的行为正确,提高应用的可维护性和性能。然而,在实际使用 React 的 state 时,开发者常常会遇到一些常见的问题和陷阱。 本文将从解决问题的角度,总结 React 中 state 管理的4个关键技巧: 使…...

Testng测试框架(6)--@Factory动态地创建测试类的实例

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

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)

在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...

es6+和css3新增的特性有哪些

一&#xff1a;ECMAScript 新特性&#xff08;ES6&#xff09; ES6 (2015) - 革命性更新 1&#xff0c;记住的方法&#xff0c;从一个方法里面用到了哪些技术 1&#xff0c;let /const块级作用域声明2&#xff0c;**默认参数**&#xff1a;函数参数可以设置默认值。3&#x…...

[拓扑优化] 1.概述

常见的拓扑优化方法有&#xff1a;均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有&#xff1a;有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...

HTTPS证书一年多少钱?

HTTPS证书作为保障网站数据传输安全的重要工具&#xff0c;成为众多网站运营者的必备选择。然而&#xff0c;面对市场上种类繁多的HTTPS证书&#xff0c;其一年费用究竟是多少&#xff0c;又受哪些因素影响呢&#xff1f; 首先&#xff0c;HTTPS证书通常在PinTrust这样的专业平…...

js 设置3秒后执行

如何在JavaScript中延迟3秒执行操作 在JavaScript中&#xff0c;要设置一个操作在指定延迟后&#xff08;例如3秒&#xff09;执行&#xff0c;可以使用 setTimeout 函数。setTimeout 是JavaScript的核心计时器方法&#xff0c;它接受两个参数&#xff1a; 要执行的函数&…...