news 2026/4/17 22:18:45

记力扣LCP28.采购方案 练习理解

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
记力扣LCP28.采购方案 练习理解

小力将 N 个零件的报价存于数组nums。小力预算为target,假定小力仅购买两个零件,要求购买零件的花费不超过预算,请问他有多少种采购方案。

注意:答案需要以1e9 + 7 (1000000007)为底取模,如:计算初始结果为:1000000008,请返回1

思路:
因为只需要买两个零件考虑到只需要计算两个数值的和是否在预算以内即可,故而采用双指针的办法,依次判断之和是否满足条件即可。最后结果对1000000007取余即可(因为可能零件和预算变大之后方法也会变多)。主要难理解的可能是其中判断依据排序后为什么是right-left是一个数学问题,他如果最小的和最大的和满足题意,等价于一个搭配问题,两个两个取能取几次,是个排列问题,他的次数为最右边的序数减去最左边的序数就是次数。

class Solution: def purchasePlans(self,nums:List[int],target:int)->int: left,right=0,len(nums)-1 count=0 nums.sort() while left<right: if nums[left]+nums[right]<=target: count+=right-left left+=1 else: right-=1 return count%1000000007

难点分析:

  1. 排序保证了 “单调性”:左指针固定时,右指针往左的所有数都更小,因此和左指针的和也更小;
  2. 双指针的 “贪心”:找到最大的合法右指针,就能覆盖所有更小的右指针的合法情况;
  3. 计数的 “数学本质”:left+1right的元素个数 = 终止索引 - 起始索引 =right - left(起始索引是 left+1,终止索引是 right → 个数 = right - (left+1) + 1 = right - left)。
版权声明: 本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
网站建设 2026/4/15 20:06:31

Proton-GE完整Wayland支持指南:原生游戏体验的终极解决方案

Proton-GE完整Wayland支持指南&#xff1a;原生游戏体验的终极解决方案 【免费下载链接】proton-ge-custom 项目地址: https://gitcode.com/gh_mirrors/pr/proton-ge-custom 想要在Linux系统上彻底告别X11/XWayland的传统限制&#xff0c;享受真正的原生Wayland游戏环境…

作者头像 李华
网站建设 2026/4/3 14:32:50

Kanata键盘定制工具:释放你的键盘无限潜力

Kanata键盘定制工具&#xff1a;释放你的键盘无限潜力 【免费下载链接】kanata Improve keyboard comfort and usability with advanced customization 项目地址: https://gitcode.com/GitHub_Trending/ka/kanata 你是否曾经因为标准键盘布局的限制而感到束缚&#xff1…

作者头像 李华
网站建设 2026/4/17 12:58:04

终极Oh-My-Bash配置指南:打造个性化终端体验

终极Oh-My-Bash配置指南&#xff1a;打造个性化终端体验 【免费下载链接】oh-my-bash A delightful community-driven framework for managing your bash configuration, and an auto-update tool so that makes it easy to keep up with the latest updates from the communit…

作者头像 李华
网站建设 2026/4/16 22:32:24

前端webpack面试题,零基础入门到精通,收藏这篇就够了

1、webpack的作用是什么&#xff0c;谈谈你对它的理解&#xff1f; 现在的前端网页功能丰富&#xff0c;特别是SPA&#xff08;single page web application 单页应用&#xff09;技术流行后&#xff0c;JavaScript的复杂度增加和需要一大堆依赖包&#xff0c;还需要解决Scss&…

作者头像 李华
网站建设 2026/4/15 15:01:25

5分钟掌握Sway:现代Wayland窗口管理器的终极指南

5分钟掌握Sway&#xff1a;现代Wayland窗口管理器的终极指南 【免费下载链接】sway i3-compatible Wayland compositor 项目地址: https://gitcode.com/GitHub_Trending/swa/sway 在Linux桌面环境中&#xff0c;窗口管理器一直是提升工作效率的关键工具。Sway作为i3兼容…

作者头像 李华
网站建设 2026/4/16 20:36:48

FaceFusion如何避免“恐怖谷效应”?自然度调参指南

FaceFusion如何避免“恐怖谷效应”&#xff1f;自然度调参指南 在AI生成内容&#xff08;AIGC&#xff09;迅速普及的今天&#xff0c;人脸替换技术已不再是实验室里的概念。从短视频平台上的趣味换脸滤镜&#xff0c;到影视工业中用于修复或替代表演的高级工具&#xff0c;深度…

作者头像 李华