【LeetCode - 每日一题】2240. 买钢笔和铅笔的方案数(23.09.1)
2240. 买钢笔和铅笔的方案数
题意
- 两种价格的笔
- 返回所有可以买的方案数
- 可以为 0
解法
注意这道题的复杂度比较高,O(N2) 是过不了的。一开始是这样写的:
// tle 代码
class Solution {
public:long long waysToBuyPensPencils(int total, int cost1, int cost2) {int max1 = total / cost1;int max2 = total / cost2;long long ans = 0;for(int i = 0; i <= max1; i++){for(int j = 0; j <= max2; j++){if(i * cost1 + j * cost2 <= total)ans++;}}return ans;}
};
但是在极端情况,比如 cost1 = cost2 = 1 的时候,两重 for 循环的复杂度会达到O(N2),因此直接在每次拿取若干支钢笔时计算可以拿的铅笔的方案数(注意可以拿 0 只 铅笔)。
class Solution {
public:long long waysToBuyPensPencils(int total, int cost1, int cost2) {int max1 = total / cost1;int max2 = total / cost2;long long ans = 0;for(int i = 0; i <= max1; i++){int retain = total - i * cost1;ans += (retain / cost2 + 1);}return ans;}};
复杂度
时间复杂度:O( ⌈ t o t a l c o s t 1 ⌉ \lceil \frac{total}{cost1}\rceil ⌈cost1total⌉),可以优化为 O( m a x ( ⌈ t o t a l c o s t 1 ⌉ , ⌈ t o t a l c o s t 2 ⌉ ) max(\lceil \frac{total}{cost1}\rceil, \lceil \frac{total}{cost2}\rceil) max(⌈cost1total⌉,⌈cost2total⌉))。
空间复杂度:O(1)。
相关文章:
【LeetCode - 每日一题】2240. 买钢笔和铅笔的方案数(23.09.1)
2240. 买钢笔和铅笔的方案数 题意 两种价格的笔返回所有可以买的方案数可以为 0 解法 注意这道题的复杂度比较高,O(N2) 是过不了的。一开始是这样写的: // tle 代码 class Solution { public:long long waysToBuyPensPencils(int total, int cost1,…...
SQL Server如何新建作业
作业: 在 SQL Server 中,作业(Job)是一组可以在预定时间自动执行的任务。可以将作业看作是一个可以在后台运行的程序或脚本。作业由一系列步骤组成,每个步骤都是一个独立的任务,可以执行诸如执行 SQL 查询…...
【计算机网络】CDN 内容分发
CDN(Content Delivery Network)是一种用于加速网站内容传输的分布式网络架构。它的目标是通过在全球多个位置分布服务器来存储和分发网站的静态资源,从而减少用户访问这些资源的延迟,提高网站的加载速度和性能。以下是CDN内容分发…...
Yjs + Quill 实现文档多人协同编辑器开发(基础+实战)
前言 多人协同开发确实是比较难的知识点,在技术实现上有一定挑战,但随着各种技术库的发展,目前已经有了比较成熟的解决方案。今介绍 Yjs 基于CRDT算法,用于构建自动同步的协作应用程序,与Quill富文本编辑器,…...
个性化定制界面还是极简版原装界面?我的选择是……
个性化定制界面和极简版原装界面,哪一个你用起来更加顺手呢,相比之下你更喜欢哪一个?来聊一聊原因吧! 一、我的观点和选择 个性化定制界面和极简版原装界面,二者各有优缺点。 (一)极简版原装…...
C++ STL list容器使用教程
文章目录 引用头文件初始化赋值遍历 list 容器迭代器list 常用方法删除元素插入元素 合并列表 list 翻译为列表,列表容器被实现为双向链表,因此它提供了对其数据的双向顺序访问。 List 不提供快速随机访问,它只支持双向顺序访问。 List 允许…...
go web之一:hello world快速上手+handle(http.Handle和http.HandleFunc的区别与联系)
前情提要: 需要安装好go的环境和VSCode的go插件。 hello world快速上手 1、创建go.mod 在项目根目录下打开命令行,或者直接用VSCode中的终端。输入命令 go mod init github.com/solenovex/web-tutorial 然后就能看到项目结构中多了一个go.mod 2、…...
【Postman】postman生成测试报告完整步骤(包含命令与newman安装教程链接)
文章目录 一、前提二、导出Postman脚本三、生成测试报告 一、前提 前提准备: 已安装好Newman 指引文章:Newman安装与环境配置完整版文章 Newman是一款基于nodejs开发的可以运行Postman脚本的工具,并可以生成测试报告。 二、导出Postman脚本…...
一、C#—概述环境安装(1)
🌻🌻 目录 一、 C#概述1.1 为啥学习C#1.2 TIBOE编程语言排行榜1.3 IEEE编程语言排行榜1.4 什么是C#1.5 C#创始人1.6 C#发展历史1.7 C#特点1.8 C#与Java1.9 .NET Framework1.10 C# 与 .NET Framework1.11 C#得应用领域1.12 C#能做什么 二、开发环境得安装…...
C# 实现ComboBox下拉框控件
using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System...
leetcode做题笔记119. 杨辉三角 II
给定一个非负索引 rowIndex,返回「杨辉三角」的第 rowIndex 行。 在「杨辉三角」中,每个数是它左上方和右上方的数的和。 思路一:模拟题意 int* getRow(int rowIndex, int* returnSize){int* ret malloc(sizeof(int)*(rowIndex1));ret[0]…...
Dolphin for Mac(Wii游戏模拟器)配置指南
Wii模拟器Dolphin Mac是款适合Mac电脑中的游戏玩家们使用的模拟器工具。Wii模拟器Dolphin Mac官方版支持直接运行游戏镜像文件,玩家可以将游戏ISO拷贝到某一个文件夹中统一进行管理。Wii模拟器Dolphin Mac除了键盘和鼠标外,还支持配合原版的Wii遥控器操作…...
Java,Linux,Mysql小白入门
Java入门 java后端__阿伟_的博客-CSDN博客 Linux与Git入门 Linux与Git入门教程__阿伟_的博客-CSDN博客 Mysql入门 Linux与Git入门教程__阿伟_的博客-CSDN博客...
代码随想录算法训练营第二十四天|理论基础 77. 组合
理论基础 其实在讲解二叉树的时候,就给大家介绍过回溯,这次正式开启回溯算法,大家可以先看视频,对回溯算法有一个整体的了解。 题目链接/文章讲解:代码随想录 视频讲解:带你学透回溯算法(理论篇…...
macos安装zsh
https://www.cnblogs.com/xuLessReigns/p/11005435.html mac下安装autojump brew install autojump 1,安装zsh,执行 sh -c "$(curl -fsSL https://raw.github.com/robbyrussell/oh-my-zsh/master/tools/install.sh)" 2,将zsh设置…...
【Unity】预制体材质变(Clone)克隆体问题
1、排查代码是否存在直接修改预制体的材质为克隆体。 解决:删了这段代码。 2、双击Prefab文件进入预制体编辑模式时,会执行预制体身上的脚本方法Awake、Start等(生命周期方法),所以要排查这些方法里是否有克隆…...
python“魂牵”京东商品历史价格数据接口(含代码示例)
要通过京东的API获取商品详情历史价格数据,您可以使用京东开放平台提供的接口来实现。以下是一种使用Java编程语言实现的示例,展示如何通过京东开放平台API获取商品详情历史价格数据: 首先,确保您已注册成为京东开放平台的开发者…...
密码算法、密钥体系---安全行业基础篇1
一、密码算法 密码算法是一种数学和计算方法,用于保护数据的机密性和安全性。不同的密码算法使用不同的数学原理和技术来加密和解密数据。以下是一些常见的密码算法类型: 1. **对称密码算法:** 特点:相同的密钥用于加密和解密数…...
Java工具类记录
HTML转word 相关依赖 <dependency><groupId>org.apache.poi</groupId><artifactId>poi</artifactId><version>4.1.2</version></dependency>import org.apache.poi.poifs.filesystem.DirectoryEntry; import org.apache.poi…...
DVWA靶场搭建
目录 配置环境: 1、将下载好的压缩包放置php的WWW根目录下 2、改文件配置 3、查看mysql用户名和密码,将其修改值靶场配置文件中 4、完成后我们就可以在浏览器输入127.0.0.1/dvwa进入靶场 测试XSS注入: 配置环境: githhub下…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
