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

【LeetCode】416.分割等和子集

题目

给你一个 只包含正整数 的 非空 数组 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 {public boolean canPartition(int[] nums) {if (nums.length < 2) {return false;}int sum = 0, max = 0;for (int num : nums) {sum += num;max = Math.max(max, num);}if (sum % 2 == 1) {return false;}if (max > sum / 2) {return false;}boolean[][] dp = new boolean[nums.length][sum / 2 + 1];dp[0][nums[0]] = true;for (int i = 0; i < nums.length; i++) {dp[i][0] = true;}for (int i = 1; i < nums.length; i++) {for (int j = 1; j <= sum / 2; j++) {if (nums[i] > j) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i]];}}}return dp[nums.length - 1][sum / 2];}
}

总结

实际上是求能否从背包里选取元素,使这些元素之和等于数组所有元素之和的一半。dp[i][j]表示数组{0,…,i}中能否选出和为j的元素。

优化空间复杂度的算法也看了,勉强理解了,但是自己写应该还想不到这样优化。

相关文章:

【LeetCode】416.分割等和子集

题目 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集&#xff0c;使得两个子集的元素和相等。 示例 1&#xff1a; 输入&#xff1a;nums [1,5,11,5] 输出&#xff1a;true 解释&#xff1a;数组可以分割成 [1, 5, 5] 和 [11] 。 示…...

go vet中的那些检测项

go vet 是 Go 语言自带的一个工具&#xff0c;用于分析 Go 代码中的常见错误和潜在问题。它可以检查代码中可能存在的各种问题&#xff0c;例如&#xff1a; 未使用的变量、函数或包 可疑的函数调用 错误的函数签名 程序中的竞态条件 错误的类型转换等 本文意图指令当前go vet所…...

Qt 自定义菜单、右键菜单

在接触Qt这段时间以来&#xff0c;经常遇到菜单项的问题&#xff08;右键菜单、托盘菜单、按钮菜单等&#xff09;&#xff0c;QMenu用于菜单栏,上下文菜单,弹出菜单等&#xff0c;利用QMenuQAction就可以达到效果&#xff01; 右键菜单实现&#xff1a;通过重写contextMenuEv…...

VScode 编辑器报错: ‘HelloWorld‘ is declared but its value is never read.

.vue文件被标识红色波浪线&#xff1b;提示&#xff1a; HelloWorld is declared but its value is never read. 问题原因&#xff1a; 因为vue3已经不支持vetur插件。 1、在扩展里面进行搜索Vetur插件&#xff0c;进行禁用或卸载&#xff1b; 2、在 VScode扩展里面搜索并下载…...

如何使用LLM实现文本自动生成视频

推荐&#xff1a;使用 NSDT场景编辑器 助你快速搭建可二次编辑的3D应用场景 介绍 基于扩散的图像生成模型代表了计算机视觉领域的革命性突破。这些进步由Imagen&#xff0c;DallE和MidJourney等模型开创&#xff0c;展示了文本条件图像生成的卓越功能。有关这些模型内部工作的…...

Rust处理JSON

基本操作 Cargo.toml: [package]name "json"version "0.1.0"edition "2021"# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html[dependencies]serde { version "1", features …...

Python如何操作网络爬虫

Python是一种非常强大的编程语言&#xff0c;用于网络爬虫操作也非常方便。Python提供了许多用于构建和操作网络爬虫的库和工具&#xff0c;如BeautifulSoup、Scrapy、Requests等。本文将详细介绍Python如何操作网络爬虫。 一、安装相关库 首先&#xff0c;我们需要安装Python…...

linux文件复制覆盖命令

目录 cp 命令参数2.cp -rf 出现复制不覆盖文件问题3.解决文件复制覆盖提示操作问题&#xff0c;以下四种方式&#xff0c;供大家参考使用。方法1&#xff1a;编写带cp的路径复制覆盖文件方法2&#xff1a;在CP命令前面加一个斜杠\&#xff0c;实现强制覆盖文件方法3&#xff1a…...

modbus概览

modbus Modbus是Modicon&#xff08;施耐德&#xff09;公司于1979年开发的串行通信协议。它最初设计用于公司的可编程逻辑控制器&#xff08;PLC&#xff09;。 Modbus是一种开放式协议&#xff0c;支持使用RS232/RS485/RS422协议的串行设备&#xff0c;同时还支持调制解调器…...

KMP算法开荒

文章目录 一 、前言二、 暴力解法三、KMP算法原理3.1 自动子串的指针3.2 跳过多少个字符3.3 next数组 - 暴力3.4 next数组 - 求解 四 KMP实现 一 、前言 字符串匹配 import re print(re.search(www, www.runoob.com).span()) # 在起始位置匹配 print(re.search(com, www.run…...

XXL-JOB(2)

Glue模式 任务以源码的形式去维护调度中心&#xff0c;支持实时编译&#xff0c;无需指定JobHandler。 实际上是继承自JobHandler的java类代码&#xff0c;在执行器中运行&#xff0c;可以使用Resource/Autowire注入执行器里中的其他服务. 在执行器中添加service Service p…...

Linux常用命令_网络命令、关机重启命令

文章目录 1. 网络命令1.1 网络命令: write1.2 网络命令: wall1.3 网络命令: ping1.4 网络命令: ifconfig1.5 网络命令: mail1.6 网络命令: last1.7 网络命令: lastlog1.8 网络命令: traceroute1.9 网络命令: netstat1.10 网络命令: setup1.11 挂载命令 2. 关机重启命令2.1 shut…...

用Cmake build OpenCV后,在VS中查看OpenCV源码的方法(环境VS2022+openCV4.8.0) Part I

用Cmake build OpenCV后&#xff0c;在VS中查看OpenCV源码的方法 Part I 写在最前面&#xff0c;最近这段时间的工作需要用opencv&#xff0c;不仅是调包&#xff0c;还要能够看到opencv的源码。然后就跟着网上的教程实现了一遍&#xff0c;在实现过程中&#xff0c;遇到了不少…...

如何使用Docker搭建ZooKeepe集群

1、拉取镜像 # docker pull zookeeper:3.7.12、创建网络 Docker创建容器时默认采用bridge网络&#xff0c;自行分配ip&#xff0c;不允许自己指定。在实际部署中&#xff0c;需要指定容器ip&#xff0c;不允许其自行分配ip&#xff0c;尤其在搭建集群时。可以通过docker netw…...

【javaweb】学习日记Day3 - Ajax 前后端分离开发 入门

目录 一、Ajax 1、简介 2、Axios &#xff08;没懂 暂留&#xff09; &#xff08;1&#xff09;请求方式别名 &#xff08;2&#xff09;发送get请求 &#xff08;3&#xff09;发送post请求 &#xff08;4&#xff09;案例 二、前端工程化 1、Vue项目-目录结构 2、…...

SQL注入漏洞复现:探索不同类型的注入攻击方法

这篇文章旨在用于网络安全学习&#xff0c;请勿进行任何非法行为&#xff0c;否则后果自负。 准备环境 sqlilabs靶场 安装&#xff1a;详细安装sqlmap详细教程_sqlmap安装教程_mingzhi61的博客-CSDN博客 一、基于错误的注入 注入讲解 介绍 基于错误的注入&#xff08;Err…...

大彩串口屏使用记录

写在最前面 屏幕型号 DC10600M070 IDE VisualTFT&#xff08;官方&#xff09; VSCode&#xff08;lua编程&#xff09; 用之前看一下官方那个1小时的视频教程就大概懂控件怎么用了&#xff0c;用官方的软件VisualTFT很简单 本文只是简单记录遇到的一些坑 lua编辑器 VisualTF…...

Qt http 的认证方式以及简单实现

http 的认证方式 基本认证&#xff08;Basic Authentication&#xff09;: 基本认证是最简单的HTTP认证方式。客户端在请求头中使用Base64编码的用户名和密码进行身份验证由于仅使用Base64编码&#xff0c;基本认证并不安全&#xff0c;因此建议与HTTPS一起使用&#xff0c;以…...

【图像分割】实现snake模型的活动轮廓模型以进行图像分割研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

【MongoDB系列】1.MongoDB 6.x 在 Windows 和 Linux 下的安装教程(详细)

本文主要介绍 MongoDB 最新版本 6.x 在Windows 和 Linux 操作系统下的安装方式&#xff0c;和过去 4.x 、5.x 有些许不同之处&#xff0c;供大家参考。 Windows 安装 进入官网下载 Mongodb 安装包&#xff0c;点此跳转&#xff0c;网站会自动检测当前操作系统提供最新的版本&…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...