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

Leetcode 2902. Count of Sub-Multisets With Bounded Sum

  • Leetcode 2902. Count of Sub-Multisets With Bounded Sum
    • 1. 解题思路
    • 2. 代码实现
    • 3. 算法优化
  • 题目链接:2902. Count of Sub-Multisets With Bounded Sum

1. 解题思路

这一题有点惭愧,因为没有搞定,遇上了超时问题……

我的思路其实还是挺直接的,就是直接使用动态规划,首先将元素按照unique number进行分组,然后分别考察其取用各个数目的情况下的可能情况。

由此,基本我们就转换成一个元素取用的动态规划问题,剩下的我们就只需要进行剪枝优化即可。

2. 代码实现

给出python代码实现如下:

class Solution:def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:MOD = 10**9+7cnt = Counter(nums)nums = sorted(cnt.items(), reverse=True)n = len(nums)accums = [0 for _ in range(n+1)]for i in range(n-1, -1, -1):accums[i] = accums[i+1] + nums[i][0] * nums[i][1]@lru_cache(None)def dp(idx, prev):if idx >= n:return 1 if l <= prev <= r else 0if prev > r:return 0if prev + accums[idx] < l:return 0num, m = nums[idx]return sum(dp(idx+1, prev + i*num) for i in range(m+1)) % MODreturn dp(0, 0)

不过很不幸的是,上述算法一直遇到超时问题,最后也没有优化掉这个问题……

3. 算法优化

看了一下大佬们的解答,整体依然还是动态规划的思路,而且也是需要先将数据按照unique number进行分组。

不过,大佬们的解法是直接按照所有的值进行动态规划,考察得到某个具体的值的情况下可能的选择方法。

给出大佬们的python代码实现如下:

class Solution:def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:MOD = 10**9+7cnt = Counter(nums)dup = cnt[0] + 1nums = [(k, v) for k, v in cnt.items() if k != 0]dp = [0 for _ in range(r+1)]dp[0] = 1for num, k in nums:dp_acc = [0] * (num + r + 1)for i in range(r + 1):dp_acc[num+i] = dp_acc[i] + dp[i]new_dp = [0 for _ in range(r+1)]for i in range(r, -1, -1):new_dp[i] = (dp_acc[i + num] - dp_acc[max(0, i - k * num)]) % MODdp = new_dpreturn (sum(dp[l:]) * dup) % MOD

提交代码评测得到:耗时4445ms,占用内存20.4MB。

相关文章:

Leetcode 2902. Count of Sub-Multisets With Bounded Sum

Leetcode 2902. Count of Sub-Multisets With Bounded Sum 1. 解题思路2. 代码实现3. 算法优化 题目链接&#xff1a;2902. Count of Sub-Multisets With Bounded Sum 1. 解题思路 这一题有点惭愧&#xff0c;因为没有搞定&#xff0c;遇上了超时问题…… 我的思路其实还是…...

ARP协议(地址解析协议) 的作用和操作过程

目录 1.问题: &#xff08;在同一个LAN局域网内&#xff09;如何在已知目的接口的IP地址前提下确定其MAC地址&#xff1f;2.问题&#xff1a;现在假设主机A要向目的主机B发送一个数据报&#xff0c;怎么发送呢&#xff1f;2.1在一个局域网内时2.1.1情况一&#xff1a;2.1.2情况…...

轻游戏风格虚拟资源付费下载模板Discuz论坛模板

轻游戏风格虚拟资源付费下载模板Discuz论坛模板&#xff0c;游戏资讯付费VIP源码模板。 模板说明&#xff1a; 1、模板名称&#xff1a;"qing游戏风格"&#xff0c;版本支持&#xff1a;discuzx3.0版本&#xff0c;discuzx3.1版本&#xff0c;discuzx3.2版本&#…...

MongoDB索引操作

1、创建索引 语句&#xff1a; db.collection.createIndex(keys, options, commitQuorum) 选项参数名类型描述keys 包含排序字段和排序方式的对象&#xff0c; 值&#xff1a; 1为升序索引 -1为降序索引 options参数控制对象backgroundboolean 可选&#xff0…...

AMEYA360:君正低功耗AIoT图像识别处理器—X1600/X1600E

• 高性能 XBurst 1 CPU&#xff0c;主频1.0GHz • 超低功耗 • 内置LPDDR2(X1600&#xff1a;32MB&#xff0c;X1600E&#xff1a;64MB) • 实时控制核XBurst 0&#xff0c;面向安全管理和实时控制 • 丰富的外设接口 应用领域 • 基于二维码的智能商业 • 智能物联网 • 高端…...

EM@圆和圆锥曲线的参数方程

文章目录 abstract圆的参数方程匀速圆周运动的轨迹从普通方程直接转化为参数方程 任意位置圆心的方程参数方程一般方程例 交点问题的参数方程法 圆锥曲线的参数方程椭圆参数方程例椭圆内接矩形的最大面积问题 抛物线参数方程一般位置的抛物线例 双曲线的参数方程点到双曲线的最…...

uniapp 微信小程序 vue3.0+TS手写自定义封装步骤条(setup)

uniapp手写自定义步骤条&#xff08;setup&#xff09; 话不多说 先上效果图&#xff1a; setup.vue组件代码&#xff1a; <template><view class"stepBox"><viewclass"stepitem"v-for"(item, index) in stepList":key"i…...

Python 金融大数据分析

第一章 为什么将python用于金融 python编程语言 python是一种高级的多用途编程语言&#xff0c;广泛用于各种非技术和技术领域。 python是一种具备动态语义、面向对象的解释型高级编程语言。它的高级内建数据结构与动态类型及动态绑定相结合&#xff0c;使其在快速应用开发上…...

初识C++入门(1)

为什么会衍生出C&#xff1f; C语言是结构化和模块化的语言&#xff0c;适合处理较小规模的程序。对于复杂的问题&#xff0c;规模较大的程序&#xff0c;需要高度的抽象和建模时&#xff0c;C语言则不合适。为了解决软件危机&#xff0c;20世纪80年代&#xff0c;计算机界提出…...

使用Selenium的WebDriver进行长截图

from selenium import webdriver from PIL import Image from io import BytesIO # 创建浏览器驱动 driver webdriver.Chrome()# 打开网页 driver.get("https://www.douban.com/") # 替换为您要截图的网页URL def get_long_shot(driver,table_element):# 获取页面的…...

python+大数据校园卡数据分析 计算机竞赛

0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 基于yolov5的深度学习车牌识别系统实现 &#x1f947;学长这里给一个题目综合评分(每项满分5分) 难度系数&#xff1a;4分工作量&#xff1a;4分创新点&#xff1a;3分 该项目较为新颖&am…...

【机器学习】sklearn降维算法PCA

文章目录 降维PCAsklearn中的PCA代码实践 PCA对手写数字数据集的降维 降维 如何实现降维&#xff1f;【即减少特征的数量&#xff0c;又保留大部分有效信息】 将那些带有重复信息的特征合并&#xff0c;并删除那些带无效信息的特征等等&#xff0c;逐渐创造出能够代表原特征矩…...

华为云云耀云服务器L实例评测|企业项目最佳实践之评测用例(五)

华为云云耀云服务器L实例评测&#xff5c;企业项目最佳实践系列&#xff1a; 华为云云耀云服务器L实例评测&#xff5c;企业项目最佳实践之云服务器介绍(一) 华为云云耀云服务器L实例评测&#xff5c;企业项目最佳实践之华为云介绍(二) 华为云云耀云服务器L实例评测&#xff5…...

Xcode升级到15.0 解决DT_TOOLCHAIN_DIR问题

根据个人开发遇到的问题做的总结&#xff0c;公司要求Xcode 14.2 &#xff0c;Swift 5.7开发&#xff0c;由于升级了Mac 14.0系统后&#xff0c;Xcode 14.2不能使用&#xff0c;解决方案目前有2个 一、在原来Xcode 14.2 的显示包内容&#xff0c;如图 二、升级到Xcode的15.0后…...

小谈设计模式(29)—访问者模式

小谈设计模式&#xff08;29&#xff09;—访问者模式 专栏介绍专栏地址专栏介绍 访问者模式角色分析访问者被访问者 优缺点分析优点将数据结构与算法分离增加新的操作很容易增加新的数据结构很困难4 缺点增加新的数据结构比较困难增加新的操作会导致访问者类的数量增加34 总结…...

【25】c++设计模式——>责任链模式

责任链模式定义 C中的责任链模式&#xff08;Chain of Responsibility Pattern&#xff09;是一种行为型设计模式&#xff0c;它通过将请求沿着处理对象的链传递来避免把请求发送者与接收者耦合在一起。 责任链模式的主要思想是&#xff0c;通过将多个处理对象组成一条链&…...

GlobalTransactional

seata-spring的maven坐标&#xff1a; <dependency><groupId>io.seata</groupId><artifactId>seata-spring</artifactId><version>1.6.1</version> </dependency>GlobalTransactional注解的位置&#xff1a; io.seata.sprin…...

Android Studio运行kotlin项目,一直Read timed out

Android Studio运行kotlin项目&#xff0c;一直Read timed out 下载别人的Kotlin项目&#xff0c;导入as后&#xff0c;运行app一直失败&#xff0c;提示Read timed out&#xff0c;有2种解决办法 第一种方式&#xff1a;gradle.properties 修改kotlin项目种的gradle.proper…...

Excel 的单元格内容和单元格格式

文章目录 单元格内容单元格格式常规格式数字格式 单元格内容 文本&#xff1a;只要不是纯数字&#xff0c;Excel 都默认是文本格式。 在 Excel 中&#xff0c;逻辑值只有两个&#xff1a;True 和 False。 全选一片区域&#xff0c;按 Delet 键删除内容时&#xff0c;确实可以删…...

4大软件测试策略的特点和区别(单元测试、集成测试、确认测试和系统测试)

四大软件测试策略分别是单元测试、集成测试、确认测试和系统测试。 一、单元测试 单元测试也称为模块测试&#xff0c;它针对软件中的最小单元&#xff08;如函数、方法、类、模块等&#xff09;进行测试&#xff0c;以验证其是否符合预期的行为和结果。单元测试通常由开发人…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

一些实用的chrome扩展0x01

简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序&#xff0c;无论是测试应用程序、搜寻漏洞还是收集情报&#xff0c;它们都能提升工作流程。 FoxyProxy 代理管理工具&#xff0c;此扩展简化了使用代理&#xff08;如 Burp…...

数据库正常,但后端收不到数据原因及解决

从代码和日志来看&#xff0c;后端SQL查询确实返回了数据&#xff0c;但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离&#xff0c;并且ai辅助开发的时候&#xff0c;很容易出现前后端变量名不一致情况&#xff0c;还不报错&#xff0c;只是单…...

FTXUI::Dom 模块

DOM 模块定义了分层的 FTXUI::Element 树&#xff0c;可用于构建复杂的终端界面&#xff0c;支持响应终端尺寸变化。 namespace ftxui {...// 定义文档 定义布局盒子 Element document vbox({// 设置文本 设置加粗 设置文本颜色text("The window") | bold | color(…...

AT模式下的全局锁冲突如何解决?

一、全局锁冲突解决方案 1. 业务层重试机制&#xff08;推荐方案&#xff09; Service public class OrderService {GlobalTransactionalRetryable(maxAttempts 3, backoff Backoff(delay 100))public void createOrder(OrderDTO order) {// 库存扣减&#xff08;自动加全…...

[QMT量化交易小白入门]-六十二、ETF轮动中简单的评分算法如何获取历史年化收益32.7%

本专栏主要是介绍QMT的基础用法,常见函数,写策略的方法,也会分享一些量化交易的思路,大概会写100篇左右。 QMT的相关资料较少,在使用过程中不断的摸索,遇到了一些问题,记录下来和大家一起沟通,共同进步。 文章目录 相关阅读1. 策略概述2. 趋势评分模块3 代码解析4 木头…...

项目进度管理软件是什么?项目进度管理软件有哪些核心功能?

无论是建筑施工、软件开发&#xff0c;还是市场营销活动&#xff0c;项目往往涉及多个团队、大量资源和严格的时间表。如果没有一个系统化的工具来跟踪和管理这些元素&#xff0c;项目很容易陷入混乱&#xff0c;导致进度延误、成本超支&#xff0c;甚至失败。 项目进度管理软…...

解决MybatisPlus使用Druid1.2.11连接池查询PG数据库报Merge sql error的一种办法

目录 前言 一、问题重现 1、环境说明 2、重现步骤 3、错误信息 二、关于LATERAL 1、Lateral作用场景 2、在四至场景中使用 三、问题解决之道 1、源码追踪 2、关闭sql合并 3、改写处理SQL 四、总结 前言 在博客&#xff1a;【写在创作纪念日】基于SpringBoot和PostG…...