每日一题 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 堆排序 …...
分支限界法 vs 回溯法:5个关键区别和实际应用场景对比
分支限界法与回溯法:核心差异与工程实践指南 在解决复杂组合优化问题时,算法选择往往决定了程序的执行效率。当面对NP难问题时,两种经典算法——分支限界法和回溯法——常被开发者拿来比较。本文将深入剖析这两种算法的本质区别,并…...
大多数加密API都不够用:量化团队真正需要的数据到底是什么?
如果你做过加密相关开发,无论是: 量化交易数据平台研究分析风控系统 你大概率都会经历一个阶段: 👉 API 接了一堆,但始终“不够用”。 常见的一个误区 很多人在刚开始做数据接入时,会觉得: …...
分享一份2026金三银四Java面试通关宝典!
金三银四快到了,不少人找LZ咨询,问我现在的面试需要提前准备什么?为了造福更多的开发者,也为了让更多的小伙伴通过面试;LZ近期也一直想着怎么才能帮到大家。所以近期在各大渠道整合大厂相关面试题,并结合了…...
PyTorch 2.8镜像部署教程:适配550.90.07驱动的GPU监控与显存优化技巧
PyTorch 2.8镜像部署教程:适配550.90.07驱动的GPU监控与显存优化技巧 1. 镜像概述与环境准备 PyTorch 2.8深度学习镜像专为RTX 4090D 24GB显卡和CUDA 12.4环境深度优化,预装了完整的深度学习工具链。这个镜像已经过严格测试,确保在550.90.0…...
基于光伏出力不确定性的梯级水光互补系统短期优化调度模型及Matlab代码复现研究报告
1023-(文章复现)梯级水光互补系统最大化可消纳电量期望短期优化调度模型matlab代码 参考资料《梯级水光互补系统最大化可消纳电量期望短期优化调度模型》 文中考虑光伏出力不确定性,以整体可消纳电量期望最大为目标,提出了梯级水光互补系统的短期优化调度…...
SecGPT-14B实战手册:Chainlit中集成Markdown渲染与代码块语法高亮
SecGPT-14B实战手册:Chainlit中集成Markdown渲染与代码块语法高亮 1. SecGPT-14B简介 SecGPT是由云起无垠推出的开源大语言模型,专门针对网络安全领域优化。该模型基于先进的自然语言处理技术,能够理解和生成与网络安全相关的专业内容。 S…...
Gemma-3 Pixel Studio镜像免配置:开箱即用的12B多模态推理工作站
Gemma-3 Pixel Studio镜像免配置:开箱即用的12B多模态推理工作站 1. 产品概览 Gemma-3 Pixel Studio是基于Google最新开源Gemma-3-12b-it模型构建的高性能多模态对话终端。这个预配置的Docker镜像消除了复杂的部署流程,让用户能够立即体验12B参数大模型…...
从逻辑门到CPU:计算机工作原理详解
戏说CPU的工作原理:从逻辑门到计算系统1. 计算系统的基本构建单元1.1 逻辑门的物理实现计算系统最基本的构建单元是逻辑门,它们可以通过简单的物理实体来演示。以三名士兵为例,我们可以构建最基本的逻辑运算单元:输入单元…...
三菱PLC与MCGS组态农田智能灌溉系统:后发送产品包括梯形图原理图、IO分配及组态画面解析
基于三菱PLC和MCGS组态农田智能灌溉系统 我们主要的后发送的产品有,带解释的梯形图接线图原理图图纸,io分配,组态画面上周刚把农田智能灌溉的项目收尾,把资料打包发给客户的时候,终于能瘫在椅子上喝杯冰可乐了。这个…...
当我谈 Rax 按端拆分代码的时候我谈些什么:代码规范相关
前言在跨端开发领域,Rax 作为一个备受关注的框架,凭借其“一次编写,多端运行”的理念,为开发者带来了巨大的效率提升。然而,随着业务规模的扩大和终端形态的多样化(Web、Weex、小程序、Node 等)…...
