LeetCode LCP 28. 采购方案

server/2024/12/26 5:30:17/

LeetCode LCP 28. 采购方案

小力将 N 个零件的报价存于数组 nums。小力预算为 target,假定小力仅购买两个零件,要求购买零件的花费不超过预算,请问他有多少种采购方案。
注意:答案需要以 1e9 + 7 (1000000007) 为底取模,如:计算初始结果为:1000000008,请返回 1
示例 1:
输入:nums = [2,5,3,5], target = 6
输出:1
解释:预算内仅能购买 nums[0] 与 nums[2]。
示例 2:
输入:nums = [2,2,1,9], target = 10
输出:4
解释:符合预算的采购方案如下: nums[0] + nums[1] = 4 nums[0] + nums[2] = 3 nums[1] + nums[2] = 3 nums[2] + nums[3] = 10
提示:
2 <= nums.length <= 10^5
1 <= nums[i], target <= 10^5

双指针

  1. 本题的重点在于排序预处理,预先排序是对双指针使用的一个不错的小技巧,有时候不好解决的问题只要预先排序就变得十分好处理。
  2. 后面的主要思路就是选中第一个元素,找到最大的那个能满足预算的那个,那么中间的与第一个元素构成的方案都可以满足预算,所以假设满足预算的那个最大的序号为j,则整个方案数量就是j-0,依次类推,求出第二个元素的对应的j,直到求出第i个元素对应的j,注意由于需要保证方案不重复,i<j是一个限制条件,如此可以获得最终结果。
class Solution:def purchasePlans(self, nums: List[int], target: int) -> int:nums.sort()n = len(nums)j = n - 1res = 0for i in range(n):while nums[i] + nums[j] > target and i < j:j -= 1if i < j:res = (res + j - i) % int((1e9 + 7))else:breakreturn res

http://www.ppmy.cn/server/137304.html

相关文章

SQLite3库增删改查实现数据管理

1. SQLite3简介 SQLite3是一个轻量级的、嵌入式的关系型数据库管理系统&#xff0c;在保存测序数据或结果等时可使用&#xff0c;简单高效&#xff0c;并且有无需服务器、单文件存储数据、支持标准SQL、支持跨平台等优势。 本文以Sqlite3数据库为基础&#xff0c;创建代码示例…

17. 从尾到头打印链表

文章目录 QuestionIdeasCode Question 输入一个链表的头结点&#xff0c;按照 从尾到头 的顺序返回节点的值。 返回的结果用数组存储。 数据范围0≤链表长度 ≤1000。 样例 输入&#xff1a;[2, 3, 5] 返回&#xff1a;[5, 3, 2] Ideas 直接遍历链表&#xff0c;然后倒序…

STATCOM静止同步补偿器原理及MATLAB仿真模型

STATCOM原理简述 整个STATCOM 装置相当于一个电压大小可以控制的电压源。当控制 STATCOM 装置产生的电压小于系统电压即UI<US 时&#xff0c;STATCOM 装置向系统输出的无功功率Q<0&#xff0c;此时 STATCOM 装置相当于电感&#xff1b;当控制 STATCOM 装置产生的电压大于…

用QWebSocketServer写websocket服务端

1. 引入必要的头文件 #include <QCoreApplication> #include <QWebSocketServer> #include <QWebSocket> #include <QDebug> #include <QObject>QCoreApplication&#xff1a;用于创建控制台应用的事件循环。QWebSocketServer&#xff1a;提供 …

美团2025校招 广告算法工程师 面经

目录 一面/技术面 2024/09/05二面/技术面 2024/09/12三面/技术面 2024/09/19 一面/技术面 2024/09/05 拷打实习&#xff08;拷打了很长时间&#xff09;你做的这些实验里&#xff0c;模型规模是怎样的&#xff1f;有没有训练过更大的模型&#xff1f;给定一个pytorch的checkpo…

扫雷游戏(C语言详解)

扫雷游戏&#xff08;C语言详解&#xff09; 放在最前面的1、前言&#xff08;扫雷游戏的简介&#xff09;2、扫雷游戏的规则&#xff08;简易版&#xff09;3、代码实现&#xff08;3.1&#xff09;提醒一下&#xff1a;( i ) 提醒1&#xff1a;( ii ) 提醒2&#xff1a; &…

HarmonyOS NEXT应用元服务开发组合场景

在一些场景中&#xff0c;一个功能上完整的UI对象可能是由若干个更小的UI组件组合而成的。若每一个小的UI组件都可以获焦并朗读&#xff0c;则会造成信息冗余和效率降低。同时由于可聚焦的组件过多过细&#xff0c;也会影响触摸浏览时走焦的性能体验。在这种情况下&#xff0c;…

「C/C++」C++标准库之#include<fstream>文件流

✨博客主页何曾参静谧的博客&#x1f4cc;文章专栏「C/C」C/C程序设计&#x1f4da;全部专栏「VS」Visual Studio「C/C」C/C程序设计「UG/NX」BlockUI集合「Win」Windows程序设计「DSA」数据结构与算法「UG/NX」NX二次开发「QT」QT5程序设计「File」数据文件格式「PK」Parasoli…