【算法训练 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
新人硬件工程师能够通过面试,已经证明是能够胜任硬件工程师职责,当然胜任的时间会延迟,而不是当下,为什么呢?因为学校学习和公司做产品,两者之间有差异,会需要适应期。今天来看看新人硬件工程师…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...

在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...

以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...
Vue 模板语句的数据来源
🧩 Vue 模板语句的数据来源:全方位解析 Vue 模板(<template> 部分)中的表达式、指令绑定(如 v-bind, v-on)和插值({{ }})都在一个特定的作用域内求值。这个作用域由当前 组件…...