【算法训练 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
新人硬件工程师能够通过面试,已经证明是能够胜任硬件工程师职责,当然胜任的时间会延迟,而不是当下,为什么呢?因为学校学习和公司做产品,两者之间有差异,会需要适应期。今天来看看新人硬件工程师…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
深入理解Optional:处理空指针异常
1. 使用Optional处理可能为空的集合 在Java开发中,集合判空是一个常见但容易出错的场景。传统方式虽然可行,但存在一些潜在问题: // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...
永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器
一、原理介绍 传统滑模观测器采用如下结构: 传统SMO中LPF会带来相位延迟和幅值衰减,并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF),可以去除高次谐波,并且不用相位补偿就可以获得一个误差较小的转子位…...
作为点的对象CenterNet论文阅读
摘要 检测器将图像中的物体表示为轴对齐的边界框。大多数成功的目标检测方法都会枚举几乎完整的潜在目标位置列表,并对每一个位置进行分类。这种做法既浪费又低效,并且需要额外的后处理。在本文中,我们采取了不同的方法。我们将物体建模为单…...
android计算器代码
本次作业要求实现一个计算器应用的基础框架。以下是布局文件的核心代码: <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"andr…...
SpringBoot+MySQL家政服务平台 设计开发
概述 基于SpringBootMySQL开发的家政服务平台完整项目,该系统实现了用户预约、服务管理、订单统计等核心功能,采用主流技术栈开发,代码规范且易于二次开发。 主要内容 系统功能架构 本系统采用前后端分离架构,前端提供用户交互…...
