力扣题解(组合总和IV)
377. 组合总和 Ⅳ
给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
思路:
本题实质上是给一些数字,让他们在满足和是target的情况下随机排列组合,然后返回所有的排列数目。注意,本题和完全背包问题有所不同,完全背包问题不要求有先后顺序的区别,比如先放第i个物品再放第一个物品和先放第一个物品再放第二个物品没有区别,但是本题例如1+3=4和3+1=4就是不一样,因此dp数组的含义,具体做法有所不同。
dp[i]表示和是i的所有组合数目。dp[i]+=dp[i-nums[i]]。(对于可以视为在和是i-nums[i]的所有排列方法后面加一个nums[i],注意我的说法,是在所有组合的后面,是后面而不是任意位置,这一点接下来会用到!)
对于循环,本题外层循环是i从0到target,内层循环是对nums数组的遍历。本题外层循环个人理解方式是规定目前最后进入的元素该是那个,然后内存循环表示要进nums[i],这样就可以实现每次遍历都在对应的上一个外层循环排序后加一个元素,保证了没有重复。这里不太好说明,就比如假如有数字1,2,3,第一次会有三个式子1=1,2=2,3=3.然后第二次大循环会有1+1=2,1+2=3,1+3=4,2+1=3,2+2=4,2+3=5,3+1=4,3+2=5,3+3=6,可以很明显看出除了最后一个元素外的前面那一串式子就是上一次外层循环得到的所有式子。(即1,2,3)
初始化:
dp[0]=1,因为一个元素都没有才能使得和为0,只有一种组合。
注意:本题所有排列组合数目可能会非常大,因此通过模运算来保证不会超出int存储范围。
class Solution {
public:int combinationSum4(vector<int>& nums, int target) {const int mod=1e10;int n=nums.size();vector<long long>dp(target+1,0);dp[0]=1;for(int j=0;j<=target;j++){for(int i=0;i<n;i++){ if(j-nums[i]>=0)dp[j]+=dp[j-nums[i]];dp[j]%=mod;}}return dp[target];}
};
相关文章:
力扣题解(组合总和IV)
377. 组合总和 Ⅳ 给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 题目数据保证答案符合 32 位整数范围。 思路: 本题实质上是给一些数字,让他们在满足和是targ…...
Postgresql主键自增的方法
Postgresql主键自增的方法 一.方法(一) 使用 serial PRIMARY KEY 插入数据 二.方法(二) 🎈边走、边悟🎈迟早会好 一.方法(一) 使用 serial PRIMARY KEY 建表语句如下…...
【源码阅读】Sony的go breaker熔断器源码探究
文章目录 背景源码分析总结 背景 在微服务时代,服务和服务之间调用、跨部门调用都是很常见的事,但这些调用都存在很多不确定因素,如核心服务A依赖的部门B服务挂掉了,那么A本身的功能将会受到直接的影响,而这些都会影响…...
LeetCode题(66,69,35,88)--《c++》
66.加一 // // Created by wxj05 on 2024/7/20. // //法一 class Solution { public:vector<int> plusOne(vector<int>& digits) {bool carry true; // 进位标志for (int i digits.size() - 1; i > 0 && carry; --i) {digits[i] 1;carry digit…...
来参与“向日葵杯”全国教育仿真技术大赛~
可点击进行了解:“向日葵杯”全国教育仿真技术大赛 (sunmooc.cn) 本次大赛共分为四个赛道:自主命题赛道、教育知识图谱设计赛道、FPGA硬件扑克牌对抗赛道、EasyAR元宇宙空间设计赛道。 参赛对象 : 具有正式学籍的在校研究生,本科…...
SQL每日一题:删除重复电子邮箱
题干 表: Person -------------------- | Column Name | Type | -------------------- | id | int | | email | varchar | -------------------- id 是该表的主键列(具有唯一值的列)。 该表的每一行包含一封电子邮件。电子邮件将不包含大写字母。 编写解决方案 删除 所有重复…...
3、宠物商店智能合约实战(truffle智能合约项目实战)
3、宠物商店智能合约实战(truffle智能合约项目实战) 1-宠物商店环境搭建、运行2-webjs与宠物逻辑实现3-领养智能合约初始化4-宠物领养实现5-更新宠物领养状态 1-宠物商店环境搭建、运行 https://www.trufflesuite.com/boxes/pet-shop 这个还是不行 或者…...
数据库系列
目录 一、数据库的概念和作用 1.数据库的特点 2.数据模型 二、数据库系统 1.数据库管理系统 2.数据库的基本操作 一、数据库的概念和作用 数据库是指长期存储在计算机内,有组织的、可共享的数据集合。它可视为一个电子化的文件柜,用来存储电子文件…...
极狐GitLab如何启用和配置PlantUML?
GitLab 是一个全球知名的一体化 DevOps 平台,很多人都通过私有化部署 GitLab 来进行源代码托管。极狐GitLab :https://gitlab.cn/install?channelcontent&utm_sourcecsdn 是 GitLab 在中国的发行版,专门为中国程序员服务。可以一键式部署…...
Shell 构建flutter + Android 生成Apk
具体步骤 #shell 具体实现和说明如下: echo "build_start_apk!" echo "编译此脚本的前提条件如下:" #在Android 项目的主工程下,进入主工程文件夹,创建build-android 文件夹,在其文件夹下有build-android.sh文件,此文件就是整个文章的脚本内容(…...
如何用手机压缩视频?手机压缩视频方法来了
高清视频的大文件大小常常成为分享和存储的障碍,尤其是在数据流量有限或存储空间紧张的情况下。幸运的是,无论是智能手机还是个人电脑,都有多种方法可以帮助我们轻松压缩视频文件,以适应不同的需求和情境。本文将介绍如何在手机上…...
Linux下如何安装配置Elastic Stack日志收集系统
安装和配置Elastic Stack日志收集系统,包括Elasticsearch、Logstash和Kibana,是一个相对复杂的过程。本篇文章将逐步引导您完成整个过程。 安装Java Elasticsearch、Logstash和Kibana都需要Java运行环境。首先,您需要在Linux系统上安装Java…...
【深入C++】map和set的使用
文章目录 C 中的容器分类1. 顺序容器2. 关联容器3. 无序容器4. 容器适配器5. 字符串容器6. 特殊容器 set1.构造函数2.迭代器3.容量相关的成员函数4.修改器类的成员函数5.容器相关操作的成员函数 multiset1.equal_range map1.初始化相关的函数2.迭代器3.容量相关的成员函数4.访问…...
跟代码执行流程,读Megatron源码(二)训练入口pretrain_gpt.py
Megatron-LM默认支持GPT、T5、BERT等多个常见模型的预训练,当下大模型流行,故以pretrain_gpt.py为例做源码的走读。 一. 启动pretrain_gpt.py pretrain_gpt.py为GPT类模型的训练入口,它通过命令行形式被调用,其精确执行路径位于M…...
MATLAB练习题——矩阵(2)
逻辑运算 a [5 0.2 0 -8 -0.7 ],在进行逻辑运算时,a 相当于什么样的逻辑量。 相当于 a[1 1 0 1 1] 角度运算 在 sin(x)运算中,x 是角度还是弧度? 在 sin(x)运算中,x 是弧度,MATLAB 规定所有…...
arm、AArch64、x86、amd64、x86_64 的区别
arm vs AArch64 vs amd64 vs x86_64 vs x86 的区别 当涉及到 CPU 的时候,有许多术语:AArch64、x86_64、amd64、arm 等等。了解它们是什么以及它们之间的区别。 当你查看数据表或软件下载页面时是否被 ARM、AArch64、x86_64、i386 等术语混淆?…...
【SpringBoot】 jasypt配置文件密码加解密
目前我们对yml配置文件中的密码都是明文显示,显然这不安全,有的程序员离职了以后可能会做一些非法骚操作,所以我们最好要做一个加密,只能让领导架构师或者技术经理知道这个密码。所以这节课就需要来实现一下。 我们可以使用jasypt…...
复杂网络的任意子节点的网络最短距离
复杂网络的任意子节点的网络最短距离 题目要求介绍 本文算法测试用的数据集为空手道俱乐部,其中空手道俱乐部的数据集可通过这个链接进行下载•http://vlado.fmf.uni-lj.si/pub/networks/data/Ucinet/UciData.htm#zachary 摘要 本文旨在解决复杂网络中任意子节点…...
(Qt) 文件读写基础
文章目录 🗂️前言📄ref📄访问标记🗃️enum 标记 🗂️Code📄demo📄分点讲解🗃️继承体系🗃️打开/关闭🗃️写🗃️读 🗂️END…...
全产业布局对穿戴甲品牌连锁店的意义
对于美甲行业来说,穿戴甲虽然不是什么新生事物,但也就是近两年才流行开来。面对井喷的市场需求,相应的从业者,不管是品牌连锁店,还是做批发、外贸,美甲周边、亦或是OEM的,大家都忙得不亦乐乎&am…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...
消息队列系统设计与实践全解析
文章目录 🚀 消息队列系统设计与实践全解析🔍 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡💡 权衡决策框架 1.3 运维复杂度评估🔧 运维成本降低策略 🏗️ 二、典型架构设计2.1 分布式事务最终一致…...
MeshGPT 笔记
[2311.15475] MeshGPT: Generating Triangle Meshes with Decoder-Only Transformers https://library.scholarcy.com/try 真正意义上的AI生成三维模型MESHGPT来袭!_哔哩哔哩_bilibili GitHub - lucidrains/meshgpt-pytorch: Implementation of MeshGPT, SOTA Me…...
【Java】Ajax 技术详解
文章目录 1. Filter 过滤器1.1 Filter 概述1.2 Filter 快速入门开发步骤:1.3 Filter 执行流程1.4 Filter 拦截路径配置1.5 过滤器链2. Listener 监听器2.1 Listener 概述2.2 ServletContextListener3. Ajax 技术3.1 Ajax 概述3.2 Ajax 快速入门服务端实现:客户端实现:4. Axi…...
