[100天算法】-分割等和子集(day 78)

news/2024/4/19 20:13:37/

题目描述

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。注意:每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:输入: [1, 5, 11, 5]输出: true解释: 数组可以分割成 [1, 5, 5] 和 [11].示例 2:输入: [1, 2, 3, 5]输出: false解释: 数组不能分割成两个元素和相等的子集.来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路 1: DP

题目理解

一开始看到题目提到两个子数组,还有点不知道怎么跟 DP 扯上关系。

但其实题目可以换一个说法:给定数组 nums,是否存在一个子数组,该子数组的和等于 nums 元素和的一半

这样就清晰多了。

解题

我们还是用一个一维数组 dp 来记录题目的解,dp[i] 表示是否存在元素和为 i 的子数组

对于 nums 中的每个数字 n 来说,都有不选两种选择,选的话问题变成 dp[i - n],不选的话问题还是 dp[i],所以:

dp[i] = dp[i - n] or dp[i]

复杂度

  • 时间复杂度:$O(len*target)$, len 是 nums 的长度,target 是 nums 元素和的一半。
  • 空间复杂度:$O(target)$, target 是 nums 数组元素和的一半。

代码

JavaScript Code

/*** @param {number[]} nums* @return {boolean}*/
var canPartition = function (nums) {const target = nums.reduce((a, b) => a + b) / 2;if (target % 1 !== 0) return false; // nums 和为奇数const dp = Array(target + 1).fill(false);dp[0] = true;for (const n of nums) {for (let i = target; i >= n; i--) {// 逆向填充if (dp[target]) return true; // 提前返回结果dp[i] = dp[i] || dp[i - n];}}return dp[target];
};

思路 2: DFS

将两个子数组 a 和 b 分别初始化为 nums 和 [],然后不断从 a 中取出数字放到 b 中,当两个子数组的和相等时,返回 true。

对于 a 中的每个数字,都有不选两种选择。

p.s. 要使用记忆化递归才不会超时

复杂度

  • 时间复杂度:$O(2^n)$,n 为数组 nums 长度,可以看成是二叉树的遍历。
  • 空间复杂度:$O(logn)$,n 为数组 nums 长度,递归栈消耗的空间。

代码

Python Code

class Solution(object):def canPartition(self, nums):""":type nums: List[int]:rtype: bool"""@lru_cachedef dfs(i, sum1, sum2):if sum1 == sum2: return Trueif sum2 > sum1 or i >= len(nums): return Falsereturn dfs(i + 1, sum1 - nums[i], sum2 + nums[i]) or dfs(i + 1, sum1, sum2)total = sum(nums)if total % 2 == 1: return Falsereturn dfs(0, total, 0)

http://www.ppmy.cn/news/1217989.html

相关文章

python语言的由来与发展历程

Python语言的由来可以追溯到1989年,由Guido van Rossum(吉多范罗苏姆)创造。在他的业余时间里,Guido van Rossum为了打发时间,决定创造一种新的编程语言。他受到了ABC语言的启发,ABC语言是一种过程式编程语…

[sd_scripts]之train

https://github.com/kohya-ss/sd-scripts/blob/main/docs/train_README-zh.mdhttps://github.com/kohya-ss/sd-scripts/blob/main/docs/train_README-zh.md 支持模型fine-tune,dreambooth,lora,textual inversion。 1.数据准备 在任意多个…

记录pytorch实现自定义算子并转onnx文件输出

概览:记录了如何自定义一个算子,实现pytorch注册,通过C编译为库文件供python端调用,并转为onnx文件输出 整体大概流程: 定义算子实现为torch的C版本文件注册算子编译算子生成库文件调用自定义算子 一、编译环境准备…

诚迈科技旗下智达诚远亮相2023世界新汽车技术合作生态展

11月10日-12日,2023世界新汽车技术合作生态展在昆山盛大举行,这是中国汽车产业史上首次真正以零部件为主体的新汽车供应链展。诚迈科技子公司智达诚远作为智能汽车操作系统领军企业,携引领跨域融合时代的峰昇操作系统FusionOS亮相大会&#x…

Pytorch自动混合精度的计算:torch.cuda.amp.autocast

1 autocast介绍 1.1 什么是AMP? 默认情况下,大多数深度学习框架都采用32位浮点算法进行训练。2017年,NVIDIA研究了一种用于混合精度训练的方法,该方法在训练网络时将单精度(FP32)与半精度(FP16)结合在一起&#xff…

基于非对称纳什谈判的多微网电能共享运行优化策略(附带MATLAB程序)

基于非对称纳什谈判的多微网电能共享运行优化策略MATLAB程序 参考文献: 《基于非对称纳什谈判的多微网电能共享运行优化策略》——吴锦领 资源地址: 基于非对称纳什谈判的多微网电能共享运行优化策略MATLAB程序 MATLAB代码:基于非对称纳什…

固定式液压破碎工作臂系统柱塞液压泵站系统比例阀控制器

固定式液压破碎工作臂系统柱塞液压泵站系统比例阀控制器主要用于:矿山、矿井、采石场,砂石骨料场、冶金冶炼厂、铸造厂、水泥厂、钢包炉渣厂、电厂、港口和码头、辅助翻车机翻卸铁路敞车散料、建材、公路、铁路、水利和化学工业等众多液压控制部门。通过…

docker-compose 部署 MySQL 8

前言 Windows 系统通过 docker-compose 部署 MySQL8.0。 MySQL 配置文件(my.cnf) # 服务端参数配置 [mysqld] usermysql # MySQL启动用户 default-storage-engineINNODB # 创建新表时将使用的默认存储引擎 character-set-serverutf8mb4 # 设置mysql服…

pycharm/vscode 配置black和isort

Pycharm blackd Pycharm中有插件可以实现后台服务运行black:BlackConnect 安装 配置 Pycharm isort pycharm中,isort没有插件,暂使用外部工具实现,外部工具也可添加快捷键实现快捷对文件、文件夹进行format import&#xff1…

Clickhouse学习笔记

学习内容参考:一套上手ClickHouse-OLAP分析引擎,囊括Prometheus与Grafana_哔哩哔哩_bilibili 下为笔记链接,以及全套笔记pdf版本 Clickhouse学习笔记(1)—— ClickHouse的安装启动_clickhouse后台启动_THE WHY的博客-C…

8.指令格式,指令的寻址方式

目录 一. 指令格式 二. 扩展操作码 三. 指令寻址 (1)指令寻址 (2)数据寻址 1.直接寻址 2.间接寻址 3.寄存器寻址 4.寄存器间接寻址 5.隐含寻址 6.立即寻址 7.基址寻址 8.变址寻址 9.相对寻址 10.堆栈寻址 一. 指令…

【python】爬取酷狗音乐Top500排行榜【附源码】

一、导入必要的模块: 这篇博客将介绍如何使用Python编写一个爬虫程序,从斗鱼直播网站上获取图片信息并保存到本地。我们将使用requests模块发送HTTP请求和接收响应,以及os模块处理文件和目录操作。 如果出现模块报错 进入控制台输入&#xff…

Linux下mysql安装配置教程

MySQL是一种常用的关系型数据库管理系统,安装配置MySQL需经历以下步骤: 1.下载MySQL 首先,你需要从MySQL官网下载MySQL的压缩包。在下载页面中,你需要选择正确的系统和版本(例如Windows或Linux,32位或64位…

Ubuntu openssh-server 离线安装

经常用到ubunutu 20.04容器,但是没有ssh比较难调试代码,离线环境下安装方法: 安装以下三个软件包,点击openssh下载链接可下载: 1、openssh-client_8.2p1-4_amd64.deb 2、openssh-sftp-server_8.2p1-4_amd64.deb 3、…

Jenkins中强制停止停不下来的job

# Script console 执行脚本 Jenkins 的提供了 script console 的功能,允许你写一些脚本,来调度 Jenkins 执行一些任务。 我们就可以利用 script console 来强制停止 job 执行。 首先进入 Jenkins 的 script console 页面: script console 路…

Uniapp开发 购物商城源码 在线电商商城源码 适配移动终端项目及各小程序

lilishop电商商城系统 商城移动端,使用Uniapp开发,可编译为所有移动终端项目及各小程序 源码下载:https://download.csdn.net/download/m0_66047725/88487579 源码下载2:关注我留言

深入理解强化学习——马尔可夫决策过程:马尔可夫奖励过程-[回报]

分类目录:《深入理解强化学习》总目录 在马尔可夫过程的基础上加入奖励函数和折扣因子,就可以得到马尔可夫奖励过程(Markov Reward Process)。一个马尔可夫奖励过程由 ( S , P , r , γ ) (S, P, r, \gamma) (S,P,r,γ)构成&#…

kali命令行下python多版本切换

kali命令行下python多版本切换 适用情景:需要用特有的版本安装 库 1 先列举出系统可用python版本: update-alternatives --list python2 查看当前所有可用python版本,同时可以设置当前使用版本 sudo update-alternatives --config python…

SQL之回炉重造

重新学sql,整个知识框架出来,之前学的太烂了 SQL是什么: SQL 是一种操作数据库的语言,包括创建数据库、删除数据库、查询记录、修改记录、添加字段等。SQL 虽然是一种被 ANSI 标准化的语言,但是它有很多不同的实现版…

【左程云算法全讲10】打表技巧和矩阵处理技巧

系列综述: 💞目的:本系列是个人整理为了秋招面试的,整理期间苛求每个知识点,平衡理解简易度与深入程度。 🥰来源:材料主要源于左程云算法课程进行的,每个知识点的修正和深入主要参考…