【LeetCode】416. 分割等和子集(中等)——代码随想录算法训练营Day41
题目链接:416. 分割等和子集
题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例 1:
输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2:
输入:nums = [1,2,3,5] 输出:false 解释:数组不能分割成两个元素和相等的子集。
提示:
1 <= nums.length <= 2001 <= nums[i] <= 100
文章讲解:代码随想录
视频讲解:动态规划之背包问题,这个包能装满吗?| LeetCode:416.分割等和子集_哔哩哔哩_bilibili
题解1:回溯法(超时)
思路:使用回溯法遍历数组中每个元素是否加入到第1组中,其他元素加入到第二组,遍历所有情况看看相不相等。
/*** @param {number[]} nums* @return {boolean}*/
var canPartition = function(nums) {const path = new Array(nums.length);const backtracking = function (start) {for (let i = start; i < nums.length; i++) {path[i] = true;let sum1 = sum2 = 0;nums.forEach((num, index) => path[index] ? sum1 += num : sum2 += num);if (sum1 === sum2 || backtracking(i + 1)) {return true;}path[i] = false;}return false;};return backtracking(0);
};
分析:时间复杂度为 O(n * 2 ^ n),空间复杂度为 O(n)。
题解2:动态规划
思路:取数组元素和的一半,记为 target。以 target 为背包容量,数组的元素作为物品质量和价值,每个元素只能取1次,若能装满背包,则说明可以分割。这是一个01背包问题。
动态规划分析:
- dp 数组以及下标的含义:dp[j] 代表容量为 j 的背包最多能装下多少价值的物品。
- 递推公式:dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i])。
- dp 数组初始化:全部初始化成0。
- 遍历顺序:先遍历物品,再倒序遍历背包。
- 打印 dp 数组:输入为 [1,5,11,5] 时,dp 数组为 [ 0, 1, 1, 1, 1, 5, 6, 6, 6, 6, 10, 11 ]。
/*** @param {number[]} nums* @return {boolean}*/
var canPartition = function(nums) {const target = nums.reduce((a, b) => a + b) / 2; // 背包容量为数组元素和的一半if (Math.floor(target) !== target) {return false;}const dp = new Array(target + 1).fill(0);for (let i = 0; i < nums.length; i++) {for (let j = target; j >= nums[i]; j--) {dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}}return dp[target] === target; // 装满背包则返回 true
};
分析:时间复杂度为 O(n²),空间复杂度为 O(n)。
收获
练习动态规划法求解01背包问题。
相关文章:
【LeetCode】416. 分割等和子集(中等)——代码随想录算法训练营Day41
题目链接:416. 分割等和子集 题目描述 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums [1,5,11,5] 输出:true 解释&#x…...
51单片机学习(4)-----独立按键进一步控制LED灯
前言:感谢您的关注哦,我会持续更新编程相关知识,愿您在这里有所收获。如果有任何问题,欢迎沟通交流!期待与您在学习编程的道路上共同进步。 目录 一. 独立按键灵活控制LED 程序一:单个独立按键控制多个…...
Redis 学习笔记 3:黑马点评
Redis 学习笔记 3:黑马点评 准备工作 需要先导入项目相关资源: 数据库文件 hmdp.sql后端代码 hm-dianping.zip包括前端代码的 Nginx 启动后端代码和 Nginx。 短信登录 发送验证码 PostMapping("code") public Result sendCode(RequestP…...
电脑恢复删除数据的原理和方法
在恢复数据的时候,很多人都会问,为什么删除的数据还能恢复?本篇和大家一起了解下硬盘上数据的存储方式,文件被删除的时候具体发生了什么,帮助大家理解数据恢复的基本原理。最后还会分享一个好用的数据恢复工具并附上图…...
SpringBoot和SpringCloud的区别,使用微服务的好处和缺点
SpringBoot是一个用于快速开发单个Spring应用程序的框架,通过提供默认配置和约定大于配置的方式,快速搭建基于Spring的应用。让程序员更专注于业务逻辑的编写,不需要过多关注配置细节。可以看成是一种快速搭建房子的工具包,不用从…...
32单片机基础:GPIO输出
目录 简介: GPIO输出的八种模式 STM32的GPIO工作方式 GPIO支持4种输入模式: GPIO支持4种输出模式: 浮空输入模式 上拉输入模式 下拉输入模式 模拟输入模式: 开漏输出模式:(PMOS无效,就…...
【linux】查看openssl程序的安装情况
【linux】查看openssl程序的安装情况 1、查看安装包信息 $ rpm -qa |grep openssl 2、安装路径 $ rpm -ql openssl $ rpm -ql openssl-libs $ rpm -ql openssl-devel 3、相关文件和目录 /usr/bin/openssl /usr/include/openssl /usr/lib64/libssl.so.* /usr/lib64/libcrypto…...
高防服务器主要运用在哪些场景?
高防服务器主要是用来防御DDOS攻击的服务器,能够为客户提供安全维护,高防服务器能够帮助网站拒绝服务攻击,定时扫描网络主节点,进行查找可能会出现的安全漏洞的服务类型,高防服务器也会根据不同的IDC机房环境来提供硬防…...
Eureka:微服务中的服务注册与发现机制
引言 在微服务架构中,由于服务数量巨大并且各个服务的实例可能会频繁上下线,因此服务注册和发现机制至关重要。 那么,有什么工具或技术可以帮助我们解决这个问题呢? 答案就是Eureka。 一、Eureka简介 Eureka是Netflix公司开源的…...
python程序设计基础:字符串与正则表达式
第四章:字符串与正则表达式 4.1字符串 最早的字符串编码是美国标准信息交换码ASCII,仅对10个数字、26个大写英文字母、26个小写英文字母及一些其他符号进行了编码。ASCII码采用1个字节来对字符进行编码,最多只能表示256个符号。 随着信息技…...
华为配置WDS手拉手业务示例
配置WDS手拉手业务示例 组网图形 图1 配置WDS手拉手业务示例组网图 业务需求组网需求数据规划配置思路配置注意事项操作步骤配置文件 业务需求 企业用户通过WLAN接入网络,以满足移动办公的最基本需求。但企业考虑到AP通过有线部署的成本较高,所以通过建立…...
Apache celeborn 安装及使用教程
1.下载安装包 https://celeborn.apache.org/download/ 测0.4.0时出现https://github.com/apache/incubator-celeborn/issues/835 2.解压 tar -xzvf apache-celeborn-0.3.2-incubating-bin.tgz 3.修改配置文件 cp celeborn-env.sh.template celeborn-env.shcp log4j2.xml.…...
数据保护:如何有效应对.BecSec-P-XXXXXXXX勒索病毒的威胁
导言: 随着网络安全威胁的不断增加,勒索软件成为了网络犯罪分子的一种常见手段之一。.BecSec-P-XXXXXXXX勒索病毒(简称.BecSec勒索病毒)作为其中之一,对用户的数据安全构成了严重威胁。本文91数据恢复将介绍.BecSec勒…...
流畅的Python(十二)-继承的优缺点
一、核心要义 1. 子类化内置类型的缺点 2.多重继承和方法解析顺序 二、代码示例 1. 子类化内置类型的缺点 #!/usr/bin/env python # -*- coding: utf-8 -*- # Time : 2024/2/24 7:29 # Author : Maple # File : 01-子类化内置类型的问题.py # Software: PyCharm fr…...
机器学习基础(三)监督学习的进阶探索
导语:上一节我们深入地探讨监督学习和非监督学习的知识,重点关注它们的理论基础、常用算法及实际应用场景,详情可见: 机器学习基础(二)监督与非监督学习-CSDN博客文章浏览阅读769次,点赞15次&a…...
avidemux-一个免费的视频编辑器,用于剪切、过滤和编码项目
avidemux-一个免费的视频编辑器,用于剪切、过滤和编码项目 avidemux-一个免费的视频编辑器,用于剪切、过滤和编码项目avidemux下载avidemux源代码参考资料 avidemux-一个免费的视频编辑器,用于剪切、过滤和编码项目 avidemux下载 avidemux …...
RisingWave最佳实践-利用Dynamic filters 和 Temporal filters 实现监控告警
心得的体会 刚过了年刚开工,闲暇之余调研了分布式SQL流处理数据库–RisingWave,本人是Flink(包括FlinkSQL和Flink DataStream API)的资深用户,但接触到RisingWave令我眼前一亮,并且拿我们生产上的监控告警…...
【Qt学习】QRadioButton 的介绍与使用(性别选择、模拟点餐)
文章目录 介绍实例使用实例1(性别选择 - 单选 隐藏)实例2(模拟点餐,多组单选) 相关资源文件 介绍 这里简单对QRadioButton类 进行介绍: QRadioButton 继承自 QAbstractButton ,用于创建单选按…...
基于java springboot的图书管理系统设计和实现
基于java springboot的图书管理系统设计和实现 博主介绍:5年java开发经验,专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐留言 文末获取源码联…...
自定义类型:联合和枚举
目录 1. 联合体 1.1 联合体类型的声明及特点 1.2 相同成员的结构体和联合体对比 1.3 联合体大小的计算 1.4 联合体的应用举例 2. 枚举类型 2.1 枚举类型的声明 2.2 枚举类型的优点 1. 联合体 1.1 联合体类型的声明及特点 像结构体一样,联合体也是由一个或…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...
MySQL JOIN 表过多的优化思路
当 MySQL 查询涉及大量表 JOIN 时,性能会显著下降。以下是优化思路和简易实现方法: 一、核心优化思路 减少 JOIN 数量 数据冗余:添加必要的冗余字段(如订单表直接存储用户名)合并表:将频繁关联的小表合并成…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...
协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...
