【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下…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
