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

力扣2300.咒语和药水的成功对数(二分法)

 根据 灵茶山艾府 题解所写

题目描述:

给你两个正整数数组 spells 和 potions ,长度分别为 n 和 m ,其中 spells[i] 表示第 i 个咒语的能量强度,potions[j] 表示第 j 瓶药水的能量强度。

同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ,那么它们视为一对 成功 的组合。

请你返回一个长度为 n 的整数数组 pairs,其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。

示例 1:

输入:spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出:[4,0,3]
解释:
- 第 0 个咒语:5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
- 第 1 个咒语:1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
- 第 2 个咒语:3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
所以返回 [4,0,3] 。

示例 2:

输入:spells = [3,1,2], potions = [8,5,8], success = 16
输出:[2,0,2]
解释:
- 第 0 个咒语:3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
- 第 1 个咒语:1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
- 第 2 个咒语:2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
所以返回 [2,0,2] 。

解题思路:

 其中这部分是表示计算一个整数除法的向上取整操作

公式解释

加 b−1 的作用是确保当 a不是 b 的整数倍时,结果会向上取整。

代码实现

class Solution {public int[] successfulPairs(int[] spells, int[] potions, long success) {Arrays.sort(potions);for (int i = 0; i < spells.length; i++) {long target = (success - 1) / spells[i];if (target < potions[potions.length - 1]) { // 防止 long 转成 int 溢出spells[i] = potions.length - upperBound(potions, (int) target);} else {spells[i] = 0;}}return spells;}// 直接二分 long 是 28ms,改成 int 是 26msprivate int upperBound(int[] nums, int target) {int left = -1, right = nums.length; // 开区间 (left, right)while (left + 1 < right) { // 区间不为空// 循环不变量:// nums[left] <= target// nums[right] > target//无符号数右移int mid = (left + right) >>> 1;if (nums[mid] > target) {right = mid; // 二分范围缩小到 (left, mid)} else {left = mid; // 二分范围缩小到 (mid, right)}}return right;}
}

相关文章:

力扣2300.咒语和药水的成功对数(二分法)

根据 灵茶山艾府 题解所写 题目描述&#xff1a; 给你两个正整数数组 spells 和 potions &#xff0c;长度分别为 n 和 m &#xff0c;其中 spells[i] 表示第 i 个咒语的能量强度&#xff0c;potions[j] 表示第 j 瓶药水的能量强度。 同时给你一个整数 success 。一个咒语和药…...

WEB开发: 全栈工程师起步 - Python Flask +SQLite的管理系统实现

一、前言 罗马不是一天建成的。 每个全栈工程师都是从HELLO WORLD 起步的。 之前我们分别用NODE.JS 、ASP.NET Core 这两个框架实现过基于WebServer的全栈工程师入门教程。 今天我们用更简单的来实现&#xff1a; Python。 我们将用Python来实现一个学生管理应用&#xff0…...

云原生周刊:Kubernetes v1.32 正式发布

开源项目推荐 Helmper Helmper 简化了将 Helm Charts导入OCI&#xff08;开放容器倡议&#xff09;注册表的过程&#xff0c;并支持可选的漏洞修复功能。它确保您的 Helm Charts不仅安全存储&#xff0c;还能及时应用最新的安全修复。该工具完全兼容 OCI 标准&#xff0c;能够…...

京准电钟:电厂自控NTP时间同步服务器技术方案

京准电钟&#xff1a;电厂自控NTP时间同步服务器技术方案 京准电钟&#xff1a;电厂自控NTP时间同步服务器技术方案 随着计算机和网络通信技术的飞速发展&#xff0c;火电厂热工自动化系统数字化、网络化的时代已经到来。一方面它为控制和信息系统之间的数据交换、分析和应用…...

深入探索Flink的复杂事件处理CEP

深入探索Flink的复杂事件处理CEP 引言 在当今大数据时代&#xff0c;实时数据处理变得愈发关键。Apache Flink作为一款强大的流处理框架&#xff0c;其复杂事件处理&#xff08;CEP&#xff09;组件为我们从海量实时数据中提取有价值信息提供了有力支持。本文将详细介绍Flink…...

clickhouse-数据库引擎

1、数据库引擎和表引擎 数据库引擎默认是Ordinary&#xff0c;在这种数据库下面的表可以是任意类型引擎。 生产环境中常用的表引擎是MergeTree系列&#xff0c;也是官方主推的引擎。 MergeTree是基础引擎&#xff0c;有主键索引、数据分区、数据副本、数据采样、删除和修改等功…...

力扣hot100——哈希

1. 两数之和 class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> ans;map<int, int> mp;for (int i 0; i < nums.size(); i) {if (mp.count(target - nums[i])) {ans.push_back(mp[target - nums[i]])…...

少样本学习之CAML算法

上下文感知元学习&#xff08;Context-Aware Meta-Learning, CAML&#xff09; 概述 在机器学习和深度学习领域&#xff0c;元学习&#xff08;Meta-Learning&#xff09;旨在通过学习如何学习&#xff0c;使模型能够在面对新任务时快速适应。传统的元学习方法通常需要在特定…...

C# 中的闭包

文章目录 前言一、闭包的基本概念二、匿名函数中的闭包1、定义和使用匿名函数2、匿名函数捕获外部变量3、闭包的生命周期 三、Lambda 表达式中的闭包1、定义和使用 Lambda 表达式2、Lambda 表达式捕获外部变量3、闭包的作用域 四、闭包的应用场景1、事件处理2、异步编程3、迭代…...

网络编程 03:端口的定义、分类,端口映射,通过 Java 实现了 IP 和端口的信息获取

一、概述 记录时间 [2024-12-19] 前置文章&#xff1a; 网络编程 01&#xff1a;计算机网络概述&#xff0c;网络的作用&#xff0c;网络通信的要素&#xff0c;以及网络通信协议与分层模型 网络编程 02&#xff1a;IP 地址&#xff0c;IP 地址的作用、分类&#xff0c;通过 …...

制作项目之前的分析

对网页的分析可以从多个角度入手&#xff0c;具体包括内容分析、技术分析、用户体验分析。 以下是对网页分析的详细步骤&#xff0c;帮助你从不同维度评估一个网页的效果与质量&#xff1a; 1. 内容分析 内容是网页最核心的部分&#xff0c;确保其符合用户需求是网页设计的首…...

LeetCode 1925 统计平方和三元组的数目

探索平方和三元组&#xff1a;从问题到 Java 代码实现 在数学与编程的交叉领域&#xff0c;常常会遇到一些有趣且富有挑战性的问题。今天&#xff0c;就让我们深入探讨一下 “平方和三元组” 这个有趣的话题&#xff0c;并使用 Java 语言来实现计算满足特定条件的平方和三元组…...

java开发入门学习三-二进制与其他进制

常见的进制 常用的进制有二进制&#xff0c;八进制&#xff0c;十进制&#xff0c;十六进制。而我们最熟悉的是十进制&#xff0c;他们分别是怎么表达的呢&#xff1f; 定义不同的进制&#xff0c;写法不同 二进制&#xff08;Binary&#xff09;&#xff1a; 使用前缀 0b 或…...

C/S软件授权注册系统(Winform+WebApi+.NET8+EFCore版)

适用软件&#xff1a;C/S系统、Winform桌面应用软件。 运行平台&#xff1a;Windows .NETCore&#xff0c;.NET8 开发工具&#xff1a;Visual Studio 2022&#xff0c;C#语言 数据库&#xff1a;Microsoft SQLServer 2012&#xff0c;Oracle 21c&#xff0c;MySQL8&#xf…...

Linux —— 管理进程

一、查看进程 运行态&#xff08;Running&#xff09; 定义&#xff1a;处于运行态的进程正在 CPU 上执行指令。在单 CPU 系统中&#xff0c;同一时刻只有一个进程处于运行态&#xff1b;在多 CPU 或多核系统中&#xff0c;可能有多个进程同时处于运行态。示例&#xff1a; 当…...

Diffusino Policy学习note

Diffusion Policy—基于扩散模型的机器人动作生成策略 - 知乎 建议看看&#xff0c;感觉普通实验室复现不了这种工作。复现了也没有太大扩展的意义。 Diffusion Policy 是监督学习吗 Diffusion Policy 通常被视为一种基于监督学习的方法&#xff0c;但它的实际训练过程可能结…...

【Python】*args和**kwargs

【Python】*args和**kwargs 一、*args: 接收不定数量的位置参数示例1&#xff1a;简单的加法计算器示例2&#xff1a;转发参数给另一个函数 二、**kwargs: 接收不定数量的关键字参数示例3&#xff1a;创建用户配置文件示例4&#xff1a;合并多个字典 三、组合使用*args和**kwar…...

使用正则表达式提取PDF文件页数的实现方案

文章目录 背景介绍实现原理代码实现1. 基础函数结构2. 页数提取逻辑3. 使用示例 正则表达式解析优点与局限性优点局限性 错误处理建议性能优化建议最佳实践建议总结参考资源 背景介绍 在Web应用开发中,我们经常需要获取上传PDF文件的页数信息。虽然可以使用pdf.js等第三方库,但…...

Android实现RecyclerView边缘渐变效果

Android实现RecyclerView边缘渐变效果 1.前言&#xff1a; 是指在RecyclerView中实现淡入淡出效果的边缘效果。通过这种效果&#xff0c;可以使RecyclerView的边缘在滚动时逐渐淡出或淡入&#xff0c;以提升用户体验。 2.Recyclerview属性&#xff1a; 2.1、requiresFading…...

springboot443旅游管理系统(论文+源码)_kaic

摘 要 如今社会上各行各业&#xff0c;都喜欢用自己行业的专属软件工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。新技术的产生&#xff0c;往往能解决一些老技术的弊端问题。因为传统旅游管理系统信息管理难度大&#xff0c;容错率低&#…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...