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

每日一题 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 。请你判断是否可以将这个数组分割成两个子集&#xff0c;使得两个子集的元素和相等。 示例 1&#xff1a; 输入&#xff1a;nums [1,5,11,5] 输出&#xff1a;true 解释&#xff1a;数组可以分割成 [1, 5, 5] …...

U盘插上就显示让格式化是坏了吗?

U盘以其体积小巧、存储容量大、读写速度快的特点&#xff0c;在各种工作和个人使用场合中得到了广泛应用&#xff0c;因此深得用户好评。然而&#xff0c;在日常使用U盘的过程中&#xff0c;经常会遇到一些问题和挑战。今天&#xff0c;我将为大家详细解释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 能让我们快速的完成单元测试。 注意&#xff1a;Junit 测试也是程序…...

Elasticsearch安装并使用Postman访问

Elasticsearch&#xff0c;一个强大的开源搜索和分析引擎&#xff0c;已经在全球范围内被广泛应用于各种场景&#xff0c;包括网站搜索、日志分析、实时应用等。由于其强大的功能和灵活性&#xff0c;Elasticsearch 已经成为大数据处理的重要工具。然而&#xff0c;对于许多初次…...

Pytorch深度学习训练模型保存问题,找不到保存路径

执行torch.save(net.state_dict(), save_path_pth)报错&#xff1a; RuntimeError: Parent directory D:\xxxxxxxxxxx\weights does not exist. 将文件路径的中文改成全英文就可以了。 注意&#xff1a;这个代码在torch1.7版本无报错&#xff0c;但是在1.13.1版本报错。在linu…...

数据结构与算法之堆: Leetcode 23. 合并 K 个升序链表 (Typescript版)

合并 K 个升序链表 https://leetcode.cn/problems/merge-k-sorted-lists/ 描述 给你一个链表数组&#xff0c;每个链表都已经按升序排列请你将所有链表合并到一个升序链表中&#xff0c;返回合并后的链表 示例 1 输入&#xff1a;lists [[1,4,5],[1,3,4],[2,6]] 输出&…...

代码随想录算法训练营第五十七天 | 392.判断子序列 115.不同的子序列

1. 判断子序列 392. 判断子序列 - 力扣&#xff08;LeetCode&#xff09; dp[i][j] 表示以下标i-1为结尾的字符串s&#xff0c;和以下标j-1为结尾的字符串t&#xff0c;相同子序列的长度。 class Solution {public boolean isSubsequence(String s, String t) {//dp[i][j] 表示…...

Kafka日志索引详解以及生产常见问题分析与总结

文章目录 1、Kafka的Log日志梳理1.1、Topic下的消息是如何存储的&#xff1f;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的逻辑是先放子组件&#xff0c;然后放父组件&#xff0c;所以同样的css类名&#xff0c;子组件会被父组件覆盖 html 如下 子被父覆盖 scoped是通过给组件加hash值&#xff0c;锁定组件。 父子组件均scoped的情况下&#xff0c;子仍会覆盖 还是被覆盖了 如何避免被…...

tf.compat.v1.global_variables()

tf.global_variables tf.global_variables() 是 TensorFlow 1.x 中的一个函数&#xff0c;它返回图中所有的全局变量。在 TensorFlow 2.x 中&#xff0c;这个函数已经被移除了&#xff0c;取而代之的是 tf.compat.v1.global_variables()。 然而&#xff0c;在 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 原因&#xff1a;推拒绝&#xff1a;推送到起源/主人被拒绝 解决方案如下&#xff1a; 方案1&#xff1a; 1.在Idea打开终端 方案2&#xff1a; 1、在对应项目文件里打开 Git Bash 然后依次输入&#xff1a; git pull …...

在线OJ项目核心思路

文章目录 在线OJ项目核心思路1. 项目介绍2.预备知识理解多进程编程为啥采用多进程而不使用多线程?标准输入&标准输出&标准错误 3.项目实现题目API实现相关实体类定义新增/修改题目获取题目列表 编译运行编译运行流程 4.统一功能处理 在线OJ项目核心思路 1. 项目介绍 …...

Spring MVC:数据绑定

Spring MVC 数据绑定数据类型转换数据格式化数据校验 附 数据绑定 数据绑定&#xff0c;指 Web 页面上请求和响应的数据与 Controller 中对应处理方法上的对象绑定&#xff08;即是将用户提交的表单数据绑定到 Java 对象中&#xff09;。 过程如下&#xff1a; ServletRequest…...

STM32CubeMX学习笔记-USB接口使用(HID按键)

STM32CubeMX学习笔记-USB接口使用&#xff08;HID按键&#xff09; 一、USB简介1.1 USB HID简介 二、新建工程1. 打开 STM32CubeMX 软件&#xff0c;点击“新建工程”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 冒泡排序&#xff08;Bubble Sort&#xff09; 2 插入排序&#xff08;Insertion Sort&#xff09; 3 选择排序&#xff08;Selection Sort&#xff09; 4. 快速排序&#xff08;Quick Sort&#xff09; 5. 归并排序&#xff08;Merge Sort&#xff09; 6 堆排序 …...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

云安全与网络安全:核心区别与协同作用解析

在数字化转型的浪潮中&#xff0c;云安全与网络安全作为信息安全的两大支柱&#xff0c;常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异&#xff0c;并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全&#xff1a;聚焦于保…...