零基础代码随想录【Day42】|| 1049. 最后一块石头的重量 II,494. 目标和,474.一和零

2024-05-25 00:20

本文主要是介绍零基础代码随想录【Day42】|| 1049. 最后一块石头的重量 II,494. 目标和,474.一和零,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

DAY42

1049.最后一块石头的重量II

解题思路&代码

494.目标和

解题思路&代码

474.一和零

解题思路&代码


DAY42

1049.最后一块石头的重量II

力扣题目链接(opens new window)

题目难度:中等

有一堆石头,每块石头的重量都是正整数。

每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

如果 x == y,那么两块石头都会被完全粉碎;

如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。

最后,最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下,就返回 0。

示例:

  • 输入:[2,7,4,1,8,1]
  • 输出:1

解释:

  • 组合 2 和 4,得到 2,所以数组转化为 [2,7,1,8,1],
  • 组合 7 和 8,得到 1,所以数组转化为 [2,1,1,1],
  • 组合 2 和 1,得到 1,所以数组转化为 [1,1,1],
  • 组合 1 和 1,得到 0,所以数组转化为 [1],这就是最优值。

本题就和 昨天的 416. 分割等和子集 很像了,可以尝试先自己思考做一做。

视频讲解:动态规划之背包问题,这个背包最多能装多少?LeetCode:1049.最后一块石头的重量II_哔哩哔哩_bilibili

代码随想录

解题思路&代码

思路:

关键点:认识到什么是应用类背包问题,此处如何联系到背包?尽量把容器分成大小相等的两堆,则另一堆是否能用数组元素填满多少则是涉及到了背包最多能装多少的问题

本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了

是不是感觉和昨天讲解的416. 分割等和子集 (opens new window)非常像了。

本题物品的重量为stones[i],物品的价值也为stones[i]。

对应着01背包里的物品重量weight[i]和 物品价值value[i]。

1.确定dp数组以及下标的含义

dp[j]表示容量(这里说容量更形象,其实就是重量)为j的背包,最多可以背最大重量为dp[j]

可以回忆一下01背包中,dp[j]的含义,容量为j的背包,最多可以装的价值为 dp[j]。

2.确定递推公式

01背包的递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题则是:dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

3.dp数组如何初始化

既然 dp[j]中的j表示容量,那么最大容量(重量)是多少呢,就是所有石头的重量和。

因为提示中给出1 <= stones.length <= 30,1 <= stones[i] <= 1000,所以最大重量就是30 * 1000 。

而我们要求的target其实只是最大重量的一半,所以dp数组开到15000大小就可以了

4.确定遍历顺序

在动态规划:关于01背包问题,你该了解这些!(滚动数组) (opens new window)中就已经说明:如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历!

  • 时间复杂度:O(m × n) , m是石头总重量(准确的说是总重量的一半),n为石头块数
  • 空间复杂度:O(m)
class Solution {public int lastStoneWeightII(int[] stones) {int sum = 0;for (int i : stones) {sum += i;}int target = sum >> 1;//初始化dp数组int[] dp = new int[target + 1];//为什么要+1,因为涉及到背包重量为0的情况,要初始化,但是实际上数组元素是不包括这个的for (int i = 0; i < stones.length; i++) {//采用倒序for (int j = target; j >= stones[i]; j--) {//两种情况,要么放,要么不放dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - 2 * dp[target];}
}

494.目标和

力扣题目链接(opens new window)

难度:中等

给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例:

  • 输入:nums: [1, 1, 1, 1, 1], S: 3
  • 输出:5

解释:

  • -1+1+1+1+1 = 3
  • +1-1+1+1+1 = 3
  • +1+1-1+1+1 = 3
  • +1+1+1-1+1 = 3
  • +1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

大家重点理解 递推公式:dp[j] += dp[j - nums[i]],这个公式后面的提问 我们还会用到。

视频讲解:动态规划之背包问题,装满背包有多少种方法?| LeetCode:494.目标和_哔哩哔哩_bilibili

代码随想录

 

解题思路&代码

思路:

本题要如何使表达式结果为target,

既然为target,那么就一定有 left组合 - right组合 = target。

left + right = sum,而sum是固定的。right = sum - left

公式来了, left - (sum - left) = target 推导出 left = (target + sum)/2 。

target是固定的,sum是固定的,left就可以求出来。

此时问题就是在集合nums中找出和为left的组合

再回归到01背包问题,为什么是01背包呢?

因为每个物品(题目中的1)只用一次!

这次和之前遇到的背包问题不一样了,之前都是求容量为j的背包,最多能装多少。

本题则是装满有几种方法。其实这就是一个组合问题了。

1.确定dp数组以及下标的含义

dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法

其实也可以使用二维dp数组来求解本题,dp[i][j]:使用 下标为[0, i]的nums[i]能够凑满j(包括j)这么大容量的包,有dp[i][j]种方法。

2.确定递推公式

有哪些来源可以推出dp[j]呢?

只要搞到nums[i],凑成dp[j]就有dp[j - nums[i]] 种方法。

例如:dp[j],j 为5,

  • 已经有一个1(nums[i]) 的话,有 dp[4]种方法 凑成 容量为5的背包。
  • 已经有一个2(nums[i]) 的话,有 dp[3]种方法 凑成 容量为5的背包。
  • 已经有一个3(nums[i]) 的话,有 dp[2]中方法 凑成 容量为5的背包
  • 已经有一个4(nums[i]) 的话,有 dp[1]中方法 凑成 容量为5的背包
  • 已经有一个5 (nums[i])的话,有 dp[0]中方法 凑成 容量为5的背包

那么凑整dp[5]有多少方法呢,也就是把 所有的 dp[j - nums[i]] 累加起来。

所以求组合类问题的公式,都是类似这种:

dp[j] += dp[j - nums[i]]

3.dp数组如何初始化

从递推公式可以看出,在初始化的时候dp[0] 一定要初始化为1,因为dp[0]是在公式中一切递推结果的起源,如果dp[0]是0的话,递推结果将都是0。

如果数组[0] ,target = 0,那么 bagSize = (target + sum) / 2 = 0。 dp[0]也应该是1, 也就是说给数组里的元素 0 前面无论放加法还是减法,都是 1 种方法。

所以本题我们应该初始化 dp[0] 为 1。

4.确定遍历顺序

在动态规划:关于01背包问题,你该了解这些!(滚动数组) (opens new window)中,我们讲过对于01背包问题一维dp的遍历,nums放在外循环,target在内循环,且内循环倒序。

5.举例推导dp数组

输入:nums: [1, 1, 1, 1, 1], S: 3

bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4

dp数组状态变化如下:

  • 时间复杂度:O(n × m),n为正数个数,m为背包容量
  • 空间复杂度:O(m),m为背包容量
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int i = 0; i < nums.length; i++) sum += nums[i];//如果target的绝对值大于sum,那么是没有方案的if (Math.abs(target) > sum) return 0;//如果(target+sum)除以2的余数不为0,也是没有方案的if ((target + sum) % 2 == 1) return 0;int bagSize = (target + sum) / 2;int[] dp = new int[bagSize + 1];dp[0] = 1;for (int i = 0; i < nums.length; i++) {for (int j = bagSize; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[bagSize];}
}

474.一和零

力扣题目链接(opens new window)

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小,该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。

示例 1:

  • 输入:strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3

  • 输出:4

  • 解释:最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ,因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意,因为它含 4 个 1 ,大于 n 的值 3 。

通过这道题目,大家先粗略了解, 01背包,完全背包,多重背包的区别,不过不用细扣,因为后面 对于 完全背包,多重背包 还有单独讲解。

视频讲解:动态规划之背包问题,装满这个背包最多用多少个物品?| LeetCode:474.一和零_哔哩哔哩_bilibili

代码随想录

解题思路&代码

思路:

本题并不是多重背包,再来看一下这个图,捋清几种背包的关系

416.分割等和子集1

多重背包是每个物品,数量不同的情况。

本题中strs 数组里的元素就是物品,每个物品都是一个!

而m 和 n相当于是一个背包,两个维度的背包

理解成多重背包的同学主要是把m和n混淆为物品了,感觉这是不同数量的物品,所以以为是多重背包。

但本题其实是01背包问题!

只不过这个背包有两个维度,一个是m 一个是n,而不同长度的字符串就是不同大小的待装物品。

1.确定dp数组(dp table)以及下标的含义

dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]

2.确定递推公式

dp[i][j] 可以由前一个strs里的字符串推导出来,strs里的字符串有zeroNum个0,oneNum个1。

dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。

然后我们在遍历的过程中,取dp[i][j]的最大值。

所以递推公式:dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

此时大家可以回想一下01背包的递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

对比一下就会发现,字符串的zeroNum和oneNum相当于物品的重量(weight[i]),字符串本身的个数相当于物品的价值(value[i])。

这就是一个典型的01背包! 只不过物品的重量有了两个维度而已。

3.dp数组如何初始化

在动态规划:关于01背包问题,你该了解这些!(滚动数组) (opens new window)中已经讲解了,01背包的dp数组初始化为0就可以。

因为物品价值不会是负数,初始为0,保证递推的时候dp[i][j]不会被初始值覆盖。

4.确定遍历顺序

在动态规划:关于01背包问题,你该了解这些!(滚动数组) (opens new window)中,我们讲到了01背包为什么一定是外层for循环遍历物品,内层for循环遍历背包容量且从后向前遍历!

那么本题也是,物品就是strs里的字符串,背包容量就是题目描述中的m和n。

  • 时间复杂度: O(kmn),k 为strs的长度
  • 空间复杂度: O(mn) 
class Solution {public int findMaxForm(String[] strs, int m, int n) {//dp[i][j]表示i个0和j个1时的最大子集int[][] dp = new int[m + 1][n + 1];int oneNum, zeroNum;for (String str : strs) {//正序遍历物品oneNum = 0;zeroNum = 0;for (char ch : str.toCharArray()) {if (ch == '0') {zeroNum++;} else {oneNum++;}}//倒序遍历背包容量for (int i = m; i >= zeroNum; i--) {for (int j = n; j >= oneNum; j--) {dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
}

这篇关于零基础代码随想录【Day42】|| 1049. 最后一块石头的重量 II,494. 目标和,474.一和零的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

烟火目标检测数据集 7800张 烟火检测 带标注 voc yolo

一个包含7800张带标注图像的数据集,专门用于烟火目标检测,是一个非常有价值的资源,尤其对于那些致力于公共安全、事件管理和烟花表演监控等领域的人士而言。下面是对此数据集的一个详细介绍: 数据集名称:烟火目标检测数据集 数据集规模: 图片数量:7800张类别:主要包含烟火类目标,可能还包括其他相关类别,如烟火发射装置、背景等。格式:图像文件通常为JPEG或PNG格式;标注文件可能为X

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

【Linux 从基础到进阶】Ansible自动化运维工具使用

Ansible自动化运维工具使用 Ansible 是一款开源的自动化运维工具,采用无代理架构(agentless),基于 SSH 连接进行管理,具有简单易用、灵活强大、可扩展性高等特点。它广泛用于服务器管理、应用部署、配置管理等任务。本文将介绍 Ansible 的安装、基本使用方法及一些实际运维场景中的应用,旨在帮助运维人员快速上手并熟练运用 Ansible。 1. Ansible的核心概念

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

D4代码AC集

贪心问题解决的步骤: (局部贪心能导致全局贪心)    1.确定贪心策略    2.验证贪心策略是否正确 排队接水 #include<bits/stdc++.h>using namespace std;int main(){int w,n,a[32000];cin>>w>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int i=1