代码随想录算法训练营Day42|1049.最后一块石头的重量II、494.目标和、474.一和零

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

最后一块石头的重量II

1049. 最后一块石头的重量 II - 力扣(LeetCode)

考虑昨天的能否将一个数组分为两个和相等的子集,本题有类似的思路,即将左右分为左右两个和相近的子集,然后返回其差值,这里使用动态规划的话。

DP数组含义,dp[j]表示能够达到的总重量为j的石头的最大重量

背包容量从0到1501(根据题目要求变化)

dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]),j为重量,i为石头的选择与否。

遍历顺序同样物品遍历在外,背包遍历在内层,且内层倒序遍历。

最后考虑对最后一块石头重量的返回。考虑到dp[j]为其中一个子集所能抵达的最大重量,则另外一个子集的重量为总重量减去子集1的重量,要得到最后一块石头的重量,为两个子集和的相减值,最后的结果可以表示为sum -= 2*dp[j]。

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {// 创建一个长度为1501,全0的数组dp,用于动态规划// dp[j]表示能够达到的总重量为j的石头的最大重量vector<int> dp(1501, 0);int sum = 0;// 计算stones数组中所有石头的总重量for (auto x : stones) {sum += x;}// 计算目标和,即分割后两堆石头的总重量应该接近sum/2const int target = sum / 2;for (int i = 0; i < stones.size(); i++) {// 从大到小遍历目标和及其以下的值for (int j = target; j >= stones[i]; j--) {// 更新dp[j],选取当前石头和不选取当前石头,取两种情况的最大值dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}// 最终结果为sum - dp[target]的两倍,因为dp[target]是接近sum/2的最大重量// 所以sum - dp[target]是另一堆石头的重量,两堆石头碰撞后剩下的最小重量就是它们的差return sum - 2 * dp[target];}
};

算法的时间复杂度为O(n^2),空间复杂度为O(n)。

目标和

494. 目标和 - 力扣(LeetCode)

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

得到目标和,需要在数字前面添加加号和减号,即存在两个数组我们假定为left数组和right数组,left数组中元素前全为加号,right数组中元素前全为减号。目标和为target,元素的所有和为sum。

sum_left + sum_right = target;

sum_left - sum_right = sum;

sum_left = (target + sum)/2,即我们能够得到left数组的和为target和元素和sum的一半。

使用动态规划算法来解决这个问题。

此时的dp[j]表示的是要装满容量为j的背包共有dp[j]种方式。

dp[j]:装满容量为j的背包有dp[j]种方式。

dp[j]的推导公式,这里需要牢记 dp[j]表示的是装满容量为j的背包的所有方式数量,所以dp[j]与dp[j-nums[j]]相关。即总容量为5,我们有一个质量为1的物品,则应该有dp[4]种方法能够得到5(1+4 = 5),若我们有一个质量为2的物品,应该有dp[3]种方法能够得到5(2+3 = 5 考虑之前的爬楼梯的题目),依次向下推,则dp[5] = dp[4] + dp[3] + dp[2] + dp[1] + dp[0]。

dp[j] += dp[j-nums[i]],此处为累加

dp[0]本应为0,但这里若初始为0,则所有dp均为0,所以初始化为1,非0下标初始化为0。

遍历顺序物品遍历在外,背包遍历在内层,且内层倒序遍历。

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;// 计算数组nums中所有数字的和for (auto x : nums) {sum += x;}// 如果(target + sum)是奇数,那么不可能通过添加+或-得到target,因为每添加一个-,总和就会减少两倍if ((target + sum) % 2 == 1) {return 0;}// 如果target的绝对值大于sum,那么也不可能得到target,leetcode有反例[100] target -200if (abs(target) > sum) {return 0;}// 计算我们需要的正数总和leftconst int left = (sum + target) / 2;// 初始化动态规划数组dp,大小为left+1,初值都为0,dp[j]表示总和为j的方法数vector<int> dp(left + 1, 0);// 总和为0的方法只有1种,即不选择任何数字dp[0] = 1;// 遍历数组nums中的每个数字for (int i = 0; i < nums.size(); i++) {// 从大到小遍历left及其以下的值for (int j = left; j >= nums[i]; j--) {// 更新dp[j],考虑选择当前数字和不选择当前数字的情况dp[j] += dp[j - nums[i]];}}// 返回总和为left的方法数,即dp[left]return dp[left];}
};

算法的时间复杂度为O(n^2),空间复杂度为O(n)。

一和零

474. 一和零 - 力扣(LeetCode)

本题还是一个01背包问题,虽然有两个维度。具体参考如下网站

代码随想录 (programmercarl.com)

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

我们需要装满m个0,n个1的背包,共2个维度,需要一个二维的dp数组,背包中最多有多少个物品,dp[i][j]即表示最多背的物品个数,即最后返回值为dp[m][n]。

dp[i][j] = max(dp[i][j-1],dp[i][j]) x和y分别表示物品i中有x个0,y个1,此处max中的dp[i][j]参考之前背包问题的滚动数组,做了压缩。

对dp数组进行初始化,dp[0][0] = 0,其余值也全赋值为0。同样参考之前背包问题的滚动数组,dp[i][j]的值在每次遍历过程中会被覆盖。

遍历顺序,先遍历物品,再遍历背包,且背包要倒序遍历。

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {// 初始化动态规划数组dp,大小为(m+1) x (n+1),初值都为0// dp[i][j]表示最多能组成多少个只包含0和1的字符串,且0的数量不超过i,1的数量不超过jvector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));// 遍历数组strs中的每个字符串for (string str : strs) {int zero_count = 0; // 记录当前字符串中0的数量int one_count = 0;  // 记录当前字符串中1的数量// 遍历当前字符串中的每个字符for (auto c : str) {if (c == '0') {zero_count++;} else {one_count++;}}// 从大到小遍历m和n,更新dp数组for (int i = m; i >= zero_count; i--) {for (int j = n; j >= one_count; j--) {// 更新dp[i][j],考虑选择当前字符串和不选择当前字符串的情况dp[i][j] = max(dp[i - zero_count][j - one_count] + 1, dp[i][j]);}}}// 返回最多能组成只包含0和1的字符串的数量,即dp[m][n]return dp[m][n];}
};

算法的时间复杂度为O(m*n*k),k为strs的长度,外层遍历str数组中的每个字符串,共有strs.size()次迭代,k为strs数组的总长度,为strs.size()*每个数组中元素的平均长度L。

空间复杂度考虑需要维护一个二维dp数组,为O(m*n)。

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



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

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

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

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

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

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

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费