每日一题 416 分割等和子集(01背包)
题目
分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例 1:
输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2:
输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。
提示:
1 <= nums.length <= 200
1 <= nums[i] <= 100
题解
记忆化搜索
class Solution {private int[] nums;//这里如果定义布尔数组的话将会无法存储已经遍历的路径private int[][] cache;public boolean canPartition(int[] nums) {int target = 0;for (int x : nums) {target += x;}if (target % 2 != 0 || target < 0) {return false;}target /= 2;this.nums = nums;int n = nums.length;cache = new int[n][target + 1];for (int i = 0; i < n; i++) {Arrays.fill(cache[i],-1);}return dfs(n - 1, target);}public boolean dfs (int i, int c) {if (i < 0) {return c == 0;}if (cache[i][c] != -1) {return cache[i][c] > 0 ? true : false;}if (c < nums[i]) {cache[i][c] = dfs(i - 1, c) ? 1 : 0;return dfs(i - 1, c);}cache[i][c] = (dfs(i - 1, c) || dfs(i - 1, c - nums[i])) ? 1 : 0; return dfs(i - 1, c) || dfs(i - 1, c - nums[i]);}
}
1:1递推
两个数组空间优化
class Solution {public boolean canPartition(int[] nums) {int target = 0;for (int x : nums) {target += x;}if (target % 2 != 0 || target < 0) {return false;}target /= 2;int n = nums.length;boolean[][] f = new boolean[2][target + 1];f[0][0] = true;for (int i = 0; i < n; i++) {for (int c = 0; c <= target; c++) {if (c < nums[i]) {f[(i + 1) % 2][c] = f[i % 2][c];} else {f[(i + 1) % 2][c] = f[i % 2][c] || f[i % 2][c - nums[i]];}}}return f[n % 2][target];}
}
一个数组空间优化
class Solution {public boolean canPartition(int[] nums) {int target = 0;for (int x : nums) {target += x;}if (target % 2 != 0 || target < 0) {return false;}target /= 2;int n = nums.length;boolean[] f = new boolean[target + 1];f[0] = true;for (int x : nums) {for (int c = target; c >= x; c--) {f[c] = f[c] || f[c - x];}}return f[target];}
}
相关文章:
每日一题 416 分割等和子集(01背包)
题目 分割等和子集 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] …...
U盘插上就显示让格式化是坏了吗?
U盘以其体积小巧、存储容量大、读写速度快的特点,在各种工作和个人使用场合中得到了广泛应用,因此深得用户好评。然而,在日常使用U盘的过程中,经常会遇到一些问题和挑战。今天,我将为大家详细解释U盘出现要求格式化的现…...
分布式应用程序协调服务 ZooKeeper 详解
目录 1、ZooKeeper简介 2、ZooKeeper的使用场景 3、ZooKeeper设计目的 4、ZooKeeper数据模型 5、ZooKeeper几个重要概念 5.1、ZooKeeper Session 5.2、ZooKeeper Watch 5.3、Consistency Guarantees 6、ZooKeeper的工作原理 6.1、Leader Election 6.2、Leader工作流…...
Anniversary party(树形dp 基础题)
1.题目大意 There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In …...
Junit的常用操作
注:本篇文章讲解的是junit5 目录 Juint是什么 Juint需要导入的依赖 Juint常用注解 Junit执行顺序 参数化 断言 测试套件 Juint是什么 Juint 是 Java 的一个单元测试框架. 也是回归测试框架. 使用 Junit 能让我们快速的完成单元测试。 注意:Junit 测试也是程序…...
Elasticsearch安装并使用Postman访问
Elasticsearch,一个强大的开源搜索和分析引擎,已经在全球范围内被广泛应用于各种场景,包括网站搜索、日志分析、实时应用等。由于其强大的功能和灵活性,Elasticsearch 已经成为大数据处理的重要工具。然而,对于许多初次…...
Pytorch深度学习训练模型保存问题,找不到保存路径
执行torch.save(net.state_dict(), save_path_pth)报错: RuntimeError: Parent directory D:\xxxxxxxxxxx\weights does not exist. 将文件路径的中文改成全英文就可以了。 注意:这个代码在torch1.7版本无报错,但是在1.13.1版本报错。在linu…...
数据结构与算法之堆: Leetcode 23. 合并 K 个升序链表 (Typescript版)
合并 K 个升序链表 https://leetcode.cn/problems/merge-k-sorted-lists/ 描述 给你一个链表数组,每个链表都已经按升序排列请你将所有链表合并到一个升序链表中,返回合并后的链表 示例 1 输入:lists [[1,4,5],[1,3,4],[2,6]] 输出&…...
代码随想录算法训练营第五十七天 | 392.判断子序列 115.不同的子序列
1. 判断子序列 392. 判断子序列 - 力扣(LeetCode) dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度。 class Solution {public boolean isSubsequence(String s, String t) {//dp[i][j] 表示…...
Kafka日志索引详解以及生产常见问题分析与总结
文章目录 1、Kafka的Log日志梳理1.1、Topic下的消息是如何存储的?1.1.1、 log文件追加记录所有消息1.1.2、 index和timeindex加速读取log消息日志。 1.2、文件清理机制1.2.1、如何判断哪些日志文件过期了1.2.2、过期的日志文件如何处理 1.3、Kafka的文件高效读写机制…...
vue中 css scoped原理
Vue中css的逻辑是先放子组件,然后放父组件,所以同样的css类名,子组件会被父组件覆盖 html 如下 子被父覆盖 scoped是通过给组件加hash值,锁定组件。 父子组件均scoped的情况下,子仍会覆盖 还是被覆盖了 如何避免被…...
tf.compat.v1.global_variables()
tf.global_variables tf.global_variables() 是 TensorFlow 1.x 中的一个函数,它返回图中所有的全局变量。在 TensorFlow 2.x 中,这个函数已经被移除了,取而代之的是 tf.compat.v1.global_variables()。 然而,在 TensorFlow 2.x …...
登录注册实现
一、前端页面注册到Vue 1.创建登录和注册组件 <template><div>login</div></template><script> export default {name: HomeView,data() {return {}},methods: {}, } </script><template><div>register</div></tem…...
Push rejected: Push to origin/master was rejected
Push rejected: Push to origin/master was rejected 原因:推拒绝:推送到起源/主人被拒绝 解决方案如下: 方案1: 1.在Idea打开终端 方案2: 1、在对应项目文件里打开 Git Bash 然后依次输入: git pull …...
在线OJ项目核心思路
文章目录 在线OJ项目核心思路1. 项目介绍2.预备知识理解多进程编程为啥采用多进程而不使用多线程?标准输入&标准输出&标准错误 3.项目实现题目API实现相关实体类定义新增/修改题目获取题目列表 编译运行编译运行流程 4.统一功能处理 在线OJ项目核心思路 1. 项目介绍 …...
Spring MVC:数据绑定
Spring MVC 数据绑定数据类型转换数据格式化数据校验 附 数据绑定 数据绑定,指 Web 页面上请求和响应的数据与 Controller 中对应处理方法上的对象绑定(即是将用户提交的表单数据绑定到 Java 对象中)。 过程如下: ServletRequest…...
STM32CubeMX学习笔记-USB接口使用(HID按键)
STM32CubeMX学习笔记-USB接口使用(HID按键) 一、USB简介1.1 USB HID简介 二、新建工程1. 打开 STM32CubeMX 软件,点击“新建工程”2. 选择 MCU 和封装3. 配置时钟4. 配置调试模式 三、USB3.1 参数配置3.2 引脚配置3.3 配置时钟3.4 USB Device…...
C#,数值计算——Ranq2的计算方法与源程序
1 文本格式 using System; namespace Legalsoft.Truffer { /// <summary> /// Backup generator if Ranq1 has too short a period and Ran is too slow.The /// period is 8.5E37. Calling conventions same as Ran, above. /// </summary> …...
C/C++ 数据结构 - 链表
1.单链表 https://blog.csdn.net/qq_36806987/article/details/79858957 1 #include<stdio.h>2 #include<stdlib.h>3 4 /*结构体部分*/5 typedef struct Node6 {7 int data; //数值域8 struct Node *next; //指针域9 }N;10 11 N *Init() //初始化单…...
【算法基础】一文掌握十大排序算法,冒泡排序、插入排序、选择排序、归并排序、计数排序、基数排序、希尔排序和堆排序
目录 1 冒泡排序(Bubble Sort) 2 插入排序(Insertion Sort) 3 选择排序(Selection Sort) 4. 快速排序(Quick Sort) 5. 归并排序(Merge Sort) 6 堆排序 …...
国产操作系统安全实战:用银河麒麟KYSEC防护关键文件的5种典型场景
国产操作系统安全实战:银河麒麟KYSEC防护关键文件的5种典型场景 在数字化转型浪潮中,企业核心数据资产的安全防护已成为技术团队的头等大事。想象一下:财务系统的敏感账目被误删、研发代码遭恶意篡改、数据库凭证意外泄露...这些场景轻则造成…...
抖音视频批量下载神器:3分钟搞定复杂内容管理的终极方案
抖音视频批量下载神器:3分钟搞定复杂内容管理的终极方案 【免费下载链接】douyin-downloader 项目地址: https://gitcode.com/GitHub_Trending/do/douyin-downloader 抖音作为全球最受欢迎的短视频平台,每天产生海量的精彩内容。然而,…...
3步解除音乐枷锁:QMCDecode全场景音频解密指南
3步解除音乐枷锁:QMCDecode全场景音频解密指南 【免费下载链接】QMCDecode QQ音乐QMC格式转换为普通格式(qmcflac转flac,qmc0,qmc3转mp3, mflac,mflac0等转flac),仅支持macOS,可自动识别到QQ音乐下载目录,默认转换结果…...
开源像素艺术工具推荐:Pixel Fashion Atelier vs Automatic1111定制化对比
开源像素艺术工具推荐:Pixel Fashion Atelier vs Automatic1111定制化对比 1. 工具概览 1.1 Pixel Fashion Atelier简介 Pixel Fashion Atelier是一款基于Stable Diffusion与Anything-v5的图像生成工作站。它采用独特的复古日系RPG界面设计,将AI图像生…...
手把手教你用YOLOv5训练自己的交通标志数据集(从LabelImg标注到模型部署)
从零构建YOLOv5交通标志检测器的实战指南 在自动驾驶和智能交通系统快速发展的今天,准确识别道路标志已成为计算机视觉领域的重要应用场景。不同于传统图像处理方法,基于深度学习的目标检测技术能够适应复杂环境变化,而YOLOv5以其卓越的速度-…...
HP-Socket技术演讲视频描述撰写指南:关键词与吸引力
HP-Socket技术演讲视频描述撰写指南:关键词与吸引力 【免费下载链接】HP-Socket High Performance TCP/UDP/HTTP Communication Component 项目地址: https://gitcode.com/gh_mirrors/hp/HP-Socket HP-Socket是一款高性能跨平台网络通信框架,专为…...
Wan2.1-umt5能力展示:模拟计算机组成原理教学问答
Wan2.1-umt5能力展示:模拟计算机组成原理教学问答 最近在尝试用大模型辅助教学,发现了一个挺有意思的镜像——Wan2.1-umt5。它不像常见的聊天模型,更像是一个专门为理解和生成专业内容设计的“专家”。我突发奇想,让它扮演了一回…...
Python边缘部署不是“复制粘贴”!12个生产环境真实报错日志溯源分析(附可复用诊断矩阵表)
第一章:Python边缘部署的本质认知与误区破除Python边缘部署不是将桌面或服务器环境简单“搬移”到嵌入式设备,而是面向资源受限、实时性敏感、网络不可靠、运维通道受限等物理约束下的系统性重构。其本质是**在算力、内存、存储、功耗与可靠性之间达成动…...
Linux服务器运维:5个最容易被忽略的故障排查技巧(附实战命令)
Linux服务器运维:5个最容易被忽略的故障排查技巧(附实战命令) 在Linux服务器运维的日常工作中,有些故障排查点往往被工程师们忽视,直到问题爆发才追悔莫及。本文将揭示五个最容易被忽略但至关重要的排查技巧ÿ…...
string字符串基础相关知识
课程要求1.string的三种创建方式2.string常用方法空格处理,空值判断,替换操作,字符串截取,字符串拆分,字符索引访问拼接与性能,删除操作3.理解 string 不可变性,能在循环拼接场景中使用 StringB…...
