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

【算法训练 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、版本控制 &#xff08;1&#xff09;版本回滚 git log // 查看版本git reset --mixed HEAD^ // 回滚到修改状态&#xff0c;文件内容没有变化git reset --soft HEAD^ // 回滚暂存区&#xff0c;^的个数代表几个版本git reset --hard HEAD^ // 回滚到修改状态&#xff…...

XML Web 服务技术解析:WSDL 与 SOAP 原理、应用案例一览

XML Web服务是一种用于在网络上发布、发现和使用应用程序组件的技术。它基于一系列标准和协议&#xff0c;如WSDL、SOAP、RDF和RSS。下面是一些相关的内容&#xff1a; WSDL&#xff08;Web服务描述语言&#xff09;&#xff1a;用于描述Web服务的基于XML的语言&#xff0c;定义…...

解析Java中1000个常用类:FunctionalInterface类,你学会了吗?

Java 8 引入了一系列新的特性和改进,其中之一便是函数式编程。函数式接口(Functional Interface)是函数式编程的核心概念之一。本文将深入探讨 FunctionalInterface 注解,介绍其用法、重要性,并通过示例展示如何在实际开发中应用函数式接口。 什么是函数式接口? 函数式…...

Kafka自定义分区器编写教程

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

python移动文件

测试1(直接把B文件夹移动到了A里&#xff0c;成为了A的子文件夹) import os import shutil# 移动文件夹,B文件夹在当前目录没有了&#xff0c;跑到了A的子文件里 ## shutil.move(./example1/B/, ./example1/A/)测试2(B文件不动&#xff0c;将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中开发软件

参考文献&#xff1a;《AI用于Simulink模型的降阶方法和应用场景》Mathworks在2024年MATLAB XEPO大会的演讲 文章目录&#xff1a; 1、模型框架 2、数据准备 3、AI建模 4、仿真和测试 5、部署应用 Tips&#xff1a;降阶模型&#xff08;Reduced Order Modeling&#xff0…...

【计算机毕设】基于SpringBoot的房产销售系统设计与实现 - 源码免费(私信领取)

免费领取源码 &#xff5c; 项目完整可运行 &#xff5c; v&#xff1a;chengn7890 诚招源码校园代理&#xff01; 1. 研究目的 随着房地产市场的发展和互联网技术的进步&#xff0c;传统的房产销售模式逐渐向线上转移。设计并实现一个基于Spring Boot的房产销售系统&#xff0…...

Docker 私有仓库部署和管理

目录 一、案例一 概述 二、案例一 前置知识点 2.1、什么是 Docker Compose 2.2、什么是 Consul 三、案例一 使用 docker Compose 搭建 Consul 集群环境 3.1、案例实验环境 3.2、案例需求 四、案例实施 4.1、Docker 网络通信 1&#xff09;端口映射 2&#xf…...

大模型时代的具身智能系列专题(六)

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

Pytorch入门需要达到的效果

会搭建深度学习环境和依赖包安装 使用Anaconda创建环境、在pytorch官网安装pytorch、安装依赖包 会使用常见操作&#xff0c;例如matmul&#xff0c;sigmoid&#xff0c;softmax&#xff0c;relu&#xff0c;linear matmul操作见文章torch.matmul()的用法 sigmoid&#xff0…...

数据结构的快速排序(c语言版)

一.快速排序的概念 1.快排的基本概念 快速排序是一种常用的排序算法,它是基于分治策略的一种高效排序算法。它的基本思想如下: 从数列中挑出一个元素作为基准(pivot)。将所有小于基准值的元素放在基准前面,所有大于基准值的元素放在基准后面。这个过程称为分区(partition)操作…...

数据结构基础篇(4)

十六.循环链表 概念 循环链表是一种头尾相接的链表&#xff08;最后一个结点的指针域指向头结点&#xff0c;整个链表形成一个环&#xff09;优点 从表任一结点出发均可找到表中其他结点判断终止 由于循环链表中没有NULL指针&#xff0c;所以涉及遍历操作时&#xff0c;终止条…...

使用cad绘制一个螺旋输送机

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

迭代器模式(行为型)

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

Django——Admin站点(Python)

#前言&#xff1a; 该博客为小编Django基础知识操作博客的最后一篇&#xff0c;主要讲解了关于Admin站点的一些基本操作&#xff0c;小编会继续尽力更新一些优质文章&#xff0c;同时欢迎大家点赞和收藏&#xff0c;也欢迎大家关注等待后续文章。 一、简介&#xff1a; Djan…...

React 组件通信

1.从父组件向子组件传递参数: 父组件可以通过props将数据传递给子组件。子组件通过接收props来获取这些数据。 // 父组件 const ParentComponent () > {const data Hello, Child!;return <ChildComponent childData{data} />; }; ​ // 子组件 const ChildCompone…...

【再探】设计模式—访问者模式、策略模式及状态模式

访问者模式是用于访问复杂数据结构的元素&#xff0c;对不同的元素执行不同的操作。策略模式是对于具有多种实现的算法&#xff0c;在运行过程中可动态选择使用哪种具体的实现。状态模式是用于具有不同状态的对象&#xff0c;状态之间可以转换&#xff0c;且不同状态下对象的行…...

新人硬件工程师,工作中遇到的问题list

新人硬件工程师能够通过面试&#xff0c;已经证明是能够胜任硬件工程师职责&#xff0c;当然胜任的时间会延迟&#xff0c;而不是当下&#xff0c;为什么呢&#xff1f;因为学校学习和公司做产品&#xff0c;两者之间有差异&#xff0c;会需要适应期。今天来看看新人硬件工程师…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; 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社区养老保险系统小程序

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

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...