力扣416. 分割等和子集

2024-05-15 14:44
文章标签 力扣 分割 416 子集

本文主要是介绍力扣416. 分割等和子集,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Problem: 416. 分割等和子集

文章目录

  • 题目描述
  • 思路
  • 解题方法
  • 复杂度
  • Code

题目描述

在这里插入图片描述

思路

该题目可以归类为0-1背包问题,具体到细节可以再归纳为背包是否装满问题

1.首先判断数组元素和的奇偶性(奇数则不能划分)
2.我们定义一个二维布尔类型数组,用于记录每一阶段的可选状态
3.针对于动态转移方程:我们要判断最终是否可以选取一些数使其和为原来数组元素和的一半,即通过一层一层的选择数(状态转移),判断最终状态是否可达(能否有一组数使得其和为原来数组元素和的一半)每一个位置都会有选与不选两种状态,若选取则dp[i][j] == dp[i - 1][j - nums[i]],若不选取则dp[i][j] == dp[i - 1][j];则我们可以知道每一个位置的状态只取决于上一层的两个位置的状态即 dp[i][j] == dp[i - 1][j] || dp[i - 1][j - numsi

解题方法

1.获取数组的长度(假设为 n n n),统计数组所有元素的和(假设为 s u m sum sum)并判断若 s u m sum sum为奇数则直接返回false,否则将 s u m sum sum除以2;
2.定义一个Boolean类型的二维数组dp(行数为 n n n,列数为 s u m + 1 sum + 1 sum+1),用于记录每个状态,初始化(将dp[0][0]位置设置为true),并判断若*nums[0]位置值小于sum(注意sum已经除等于2了)*则将dp[0][nums[0]]位置设为true,这样就将第0层的所有状态设置完毕
3.我们从dp数组的第一层开始遍历,并完成动态转移,在没有越界(此处笔者感觉也不能就叫做越界,但是思想和上述思路中的动态转移是一致的。执行该if判断只是为了更好契合该dp数组。读者可以尝试画一画dp数组演示一边便可理解)的情况下(if (j - nums[i] >= 0))则dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];否则dp[i][j] = dp[i - 1][j];
4.返回最终位置的状态即**dp[n - 1][sum]**位置的状态

复杂度

时间复杂度:

O ( M N ) O(MN) O(MN);其中 M M M为数组长度, N N N为数组元素和的一半

空间复杂度:

O ( M N ) O(MN) O(MN);其中 M M M为数组长度, N N N为数组元素和的一半

Code

class Solution {/*** Similar to the 0-1 knapsack problem (can the knapsack be filled?)** @param nums Given arrays* @return boolean*/public boolean canPartition(int[] nums) {int n = nums.length;int sum = 0;for (int i = 0; i < n; ++i) {sum += nums[i];}//Indivisible if oddif (sum % 2 == 1) {return false;}sum /= 2;//Records whether each node is reachableboolean[][] dp = new boolean[n][sum + 1];dp[0][0] = true;if (nums[0] <= sum) {dp[0][nums[0]] = true;}//State transition equationfor (int i = 1; i < n; ++i) {for (int j = 0; j <= sum; ++j) {//Determine whether the line has been crossedif (j - nums[i] >= 0) {dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];} else {dp[i][j] = dp[i - 1][j];}}}return dp[n - 1][sum];}
}

这篇关于力扣416. 分割等和子集的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/992104

相关文章

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

SAM2POINT:以zero-shot且快速的方式将任何 3D 视频分割为视频

摘要 我们介绍 SAM2POINT,这是一种采用 Segment Anything Model 2 (SAM 2) 进行零样本和快速 3D 分割的初步探索。 SAM2POINT 将任何 3D 数据解释为一系列多向视频,并利用 SAM 2 进行 3D 空间分割,无需进一步训练或 2D-3D 投影。 我们的框架支持各种提示类型,包括 3D 点、框和掩模,并且可以泛化到不同的场景,例如 3D 对象、室

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82, 237

总结,删除链表节点问题使用到列表,哈希表,递归比较容易超时,我觉得使用计数排序比较稳,处理起来也不是很难。 1. 力扣3217:从链表中移除在数组中的节点 1.1 题目: 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后,返回修改后的链表的头节点。 示例 1: 输入: nums = [1,2,3], head = [1,2,3,

基于YOLO8的图片实例分割系统

文章目录 在线体验快速开始一、项目介绍篇1.1 YOLO81.2 ultralytics1.3 模块介绍1.3.1 scan_task1.3.2 scan_taskflow.py1.3.3 segment_app.py 二、核心代码介绍篇2.1 segment_app.py2.2 scan_taskflow.py 三、结语 代码资源:计算机视觉领域YOLO8技术的图片实例分割实

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调

力扣接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]输出:6解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 示例 2: 输入:height

每日一题,力扣leetcode Hot100之238.除自身以外数组的乘积

乍一看这个题很简单,但是不能用除法,并且在O(N)时间复杂度完成或许有点难度。 考虑到不能用除法,如果我们要计算输出结果位置i的值,我们就要获取这个位置左边的乘积和右边的乘积,那么我新设立两个数组L和R。 对于L来说,由于表达的是位置i左边的数的乘积,那么L[0]=1,因为第一个数字左边没数那么为了不影响乘积初始值就设置为1,那么L[1]=L[0]*nums[0],那么L[i]=L[i-1

如何将卷积神经网络(CNN)应用于医学图像分析:从分类到分割和检测的实用指南

引言 在现代医疗领域,医学图像已经成为疾病诊断和治疗规划的重要工具。医学图像的类型繁多,包括但不限于X射线、CT(计算机断层扫描)、MRI(磁共振成像)和超声图像。这些图像提供了对身体内部结构的详细视图,有助于医生在进行准确诊断和制定个性化治疗方案时获取关键的信息。 1. 医学图像分析的挑战 医学图像分析面临诸多挑战,其中包括: 图像数据的复杂性:医学图像通常具有高维度和复杂的结构

代码随想录刷题day24丨93.复原IP地址 ,78.子集 , 90.子集II

代码随想录刷题day24丨93.复原IP地址 ,78.子集 , 90.子集II 1.题目 1.1复原IP地址 题目链接:93. 复原 IP 地址 - 力扣(LeetCode) 视频讲解:回溯算法如何分割字符串并判断是合法IP?| LeetCode:93.复原IP地址_哔哩哔哩_bilibili 文档讲解:https://programmercarl.com/0093.%E5%A4%8