【算法训练 day44 分割等和子集】
目录
- 一、分割等和子集-LeetCode 416
- 思路
- 实现代码
- 1.二维dp代码
- 2.一维dp代码
- 问题
- 总结
一、分割等和子集-LeetCode 416
Leecode链接: leetcode 416
文章链接: 代码随想录
视频链接: B站
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例1:
输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。
思路
本体可以看作一个背包模型,将数组总和除2,将总和一半定义为背包的容量,数组元素为可选的物品。本题既可以定义一个一维dp数组,也可以定义一个二维dp数组,但二维便于理解与讲解并且一维只是二维的精简版,思想基本一致,所以主要写一下二维的思路。数组形式为dp[i][j],i为可选的物品范围,例如当i为3时,表示可选的物品范围为0到3下标的物品任意物品;j表示当前背包的容量大小。dp数组含义为,在j容量下,物品0到i范围可以获得的最大和。递推公式为dp[i][j] = dp[i-1][j]或dp[i][j] = max(dp[i-1][j] , dp[i-1][j-nums[i]] + nums[i])。前者表示不放的情况,后者表示物品放入后可能的情况。不放的条件就是背包容量不足以放下物品,放物品的条件就是当前背包的容量大于或等于当前物品的重量。
实现代码
1.二维dp代码
//cpp
class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;int len = nums.size();//物品的数量for(int a:nums){sum += a;} if(sum%2 == 1) return false;int target = sum/2;//既是物品的价值也是物品的重量vector<vector<int>>dp(len,vector<int>(target+1,0));for(int j = nums[0];j<=target;j++){dp[0][j] = nums[0];}for(int i = 1;i<len;i++){for(int j = 0;j<=target;j++){if(j<nums[i]){dp[i][j] = dp[i-1][j];}else {dp[i][j] = max(dp[i-1][j],dp[i-1][j - nums[i]]+nums[i]);}}}if(dp[len-1][target] == target) return true;return false;}
};
2.一维dp代码
//cpp
class Solution {
public:bool canPartition(vector<int>& nums) {//vector<int> dp(10001, 0);int sum = 0;for(int a:nums){sum += a;} if(sum%2 == 1) return false;int t = sum/2;vector<int>dp(t+1,0);for(int i = 0;i<nums.size();i++){for(int j = t;j>=nums[i];j--){dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);}}if(dp[t] == t) return true;return false;}
};
问题
代码实现细节不熟练,比如初始化时,怎么将第一行的哪些数初始化为恒定值。
总结
一维与二维的区别在于:省去了多余空间的使用,并且改变了遍历顺序,这是因为如果跟二维数组一样从前往后遍历,就会导致重复选择同一个物品。比如,当i = 1时,dp[1] = 1、dp[2] = 1;当i = 2时,dp[1] = 1、dp[2] = 2,显然是不对的因为一件物品只能选一次。虽然一维省去了空间,但时间复杂很高,leetcode上一维dp的执行用时为300ms左右,空间占用达到了10MB左右;二维dp为100ms左右,同样的二维空间占用达到了98MB左右。
相关文章:
【算法训练 day44 分割等和子集】
目录 一、分割等和子集-LeetCode 416思路实现代码1.二维dp代码2.一维dp代码 问题总结 一、分割等和子集-LeetCode 416 Leecode链接: leetcode 416 文章链接: 代码随想录 视频链接: B站 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集&…...

前端实习记录——git篇(一些问题与相关命令)
1、版本控制 (1)版本回滚 git log // 查看版本git reset --mixed HEAD^ // 回滚到修改状态,文件内容没有变化git reset --soft HEAD^ // 回滚暂存区,^的个数代表几个版本git reset --hard HEAD^ // 回滚到修改状态ÿ…...
XML Web 服务技术解析:WSDL 与 SOAP 原理、应用案例一览
XML Web服务是一种用于在网络上发布、发现和使用应用程序组件的技术。它基于一系列标准和协议,如WSDL、SOAP、RDF和RSS。下面是一些相关的内容: WSDL(Web服务描述语言):用于描述Web服务的基于XML的语言,定义…...
解析Java中1000个常用类:FunctionalInterface类,你学会了吗?
Java 8 引入了一系列新的特性和改进,其中之一便是函数式编程。函数式接口(Functional Interface)是函数式编程的核心概念之一。本文将深入探讨 FunctionalInterface 注解,介绍其用法、重要性,并通过示例展示如何在实际开发中应用函数式接口。 什么是函数式接口? 函数式…...

Kafka自定义分区器编写教程
1.创建java类MyPartitioner并实现Partitioner接口 点击灯泡选择实现方法,导入需要实现的抽象方法 2.实现方法 3.自定义分区器的使用 在自定义生产者消息发送时,属性配置上加入自定义分区器 properties.put(ProducerConfig.PARTITIONER_CLASS_CONFIG,&q…...

python移动文件
测试1(直接把B文件夹移动到了A里,成为了A的子文件夹) import os import shutil# 移动文件夹,B文件夹在当前目录没有了,跑到了A的子文件里 ## shutil.move(./example1/B/, ./example1/A/)测试2(B文件不动,将B文件里的所有的子文件夹移动到A内…...

eNSP学习——OSPF的DR与BDR
目录 相关命令 原理概述 实验内容 实验目的 实验拓扑 实验编址 实验步骤 1、基本配置 2、搭建基本的OSPF网络 3、查看默认情况下的DR/BDR状态 4、根据现网需求影响DR/BDR选举 相关命令 [R4]int g0/0/0 [R4-GigabitEthernet0/0/0]ospf network-type p2mp //在接…...

【文献阅读】应用人工智能在Simulink中开发软件
参考文献:《AI用于Simulink模型的降阶方法和应用场景》Mathworks在2024年MATLAB XEPO大会的演讲 文章目录: 1、模型框架 2、数据准备 3、AI建模 4、仿真和测试 5、部署应用 Tips:降阶模型(Reduced Order Modeling࿰…...

【计算机毕设】基于SpringBoot的房产销售系统设计与实现 - 源码免费(私信领取)
免费领取源码 | 项目完整可运行 | v:chengn7890 诚招源码校园代理! 1. 研究目的 随着房地产市场的发展和互联网技术的进步,传统的房产销售模式逐渐向线上转移。设计并实现一个基于Spring Boot的房产销售系统࿰…...

Docker 私有仓库部署和管理
目录 一、案例一 概述 二、案例一 前置知识点 2.1、什么是 Docker Compose 2.2、什么是 Consul 三、案例一 使用 docker Compose 搭建 Consul 集群环境 3.1、案例实验环境 3.2、案例需求 四、案例实施 4.1、Docker 网络通信 1)端口映射 2…...

大模型时代的具身智能系列专题(六)
UCSD 王小龙组 王小龙是UCSD电子与计算机工程系的助理教授。他曾在加州大学伯克利分校与Alexei Efros和Trevor Darrell一起担任博士后研究员,在CMU RI获得了机器人学博士学位,师从Abhinav Gupta。他的研究重点是通过视频和物理机器人交互数据来学习3D和…...

Pytorch入门需要达到的效果
会搭建深度学习环境和依赖包安装 使用Anaconda创建环境、在pytorch官网安装pytorch、安装依赖包 会使用常见操作,例如matmul,sigmoid,softmax,relu,linear matmul操作见文章torch.matmul()的用法 sigmoid࿰…...

数据结构的快速排序(c语言版)
一.快速排序的概念 1.快排的基本概念 快速排序是一种常用的排序算法,它是基于分治策略的一种高效排序算法。它的基本思想如下: 从数列中挑出一个元素作为基准(pivot)。将所有小于基准值的元素放在基准前面,所有大于基准值的元素放在基准后面。这个过程称为分区(partition)操作…...
数据结构基础篇(4)
十六.循环链表 概念 循环链表是一种头尾相接的链表(最后一个结点的指针域指向头结点,整个链表形成一个环)优点 从表任一结点出发均可找到表中其他结点判断终止 由于循环链表中没有NULL指针,所以涉及遍历操作时,终止条…...

使用cad绘制一个螺旋输送机
1、第一步,绘制一个矩形 2、使用绘图中的样条线拟合曲线,绘制螺旋线。 绘制时使用上下辅助线、阵列工具绘制多个竖线保证样条线顶点在同一高度。 3、调整矩形右侧的两个顶点,使其变形。 矩形1和矩形2连接时,使用blend命令&#…...

迭代器模式(行为型)
目录 一、前言 二、迭代器模式 三、总结 一、前言 迭代器模式(Iterator Pattern)是一种行为型设计模式,提供一种方法顺序访问一个聚合对象中各个元素,而又不暴露该对象的内部表示。总的来说就是分离了集合对象的遍历行为,抽象出…...

Django——Admin站点(Python)
#前言: 该博客为小编Django基础知识操作博客的最后一篇,主要讲解了关于Admin站点的一些基本操作,小编会继续尽力更新一些优质文章,同时欢迎大家点赞和收藏,也欢迎大家关注等待后续文章。 一、简介: Djan…...
React 组件通信
1.从父组件向子组件传递参数: 父组件可以通过props将数据传递给子组件。子组件通过接收props来获取这些数据。 // 父组件 const ParentComponent () > {const data Hello, Child!;return <ChildComponent childData{data} />; }; // 子组件 const ChildCompone…...

【再探】设计模式—访问者模式、策略模式及状态模式
访问者模式是用于访问复杂数据结构的元素,对不同的元素执行不同的操作。策略模式是对于具有多种实现的算法,在运行过程中可动态选择使用哪种具体的实现。状态模式是用于具有不同状态的对象,状态之间可以转换,且不同状态下对象的行…...
新人硬件工程师,工作中遇到的问题list
新人硬件工程师能够通过面试,已经证明是能够胜任硬件工程师职责,当然胜任的时间会延迟,而不是当下,为什么呢?因为学校学习和公司做产品,两者之间有差异,会需要适应期。今天来看看新人硬件工程师…...

学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...

基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
Webpack性能优化:构建速度与体积优化策略
一、构建速度优化 1、升级Webpack和Node.js 优化效果:Webpack 4比Webpack 3构建时间降低60%-98%。原因: V8引擎优化(for of替代forEach、Map/Set替代Object)。默认使用更快的md4哈希算法。AST直接从Loa…...