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

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

目录

  • 1049. 最后一块石头的重量 II
    • 1、题目描述
    • 2、思路
    • 3、code
    • 4、复杂度分析
  • 494. 目标和
    • 1、题目描述
    • 2、思路
    • 3、code
    • 4、复杂度分析
  • 474. 一和零
    • 1、题目描述
    • 2、思路
    • 3、code
    • 4、复杂度分析

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

题目链接:link

1、题目描述

有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:
如果 x == y,那么两块石头都会被完全粉碎;
如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下,就返回 0。
示例 1:
输入:stones = [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],这就是最优值。

2、思路

3、code

class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:# 把石头分成两堆质量相差不多的==分隔等和子集sum_weight = sum(stones)target = sum_weight // 2  # case1:23//2 = 11+1 = 12# 物品重量就是石头的重量,物品价值就是石头的重量# 背包容量就是target# 背包放进去的石头的最大重量?# dp[j]:背包容量为j,能够放进去的最大石头重量dp = [0] * (target+1) # dp = [0] * 12for i in range(0,len(stones)):#石头编号从0,1,2,3,4,5for j in range(target,stones[i]-1,-1):# 容量从target,target-1,....,stone[i]dp[j] = max(dp[j],dp[j-stones[i]]+stones[i])# dp[target]就是分成一堆的最大重量res = abs(sum_weight - 2*dp[target])return res

4、复杂度分析

1️⃣ 时间复杂度: O ( N 2 ) O(N^2) O(N2)
2️⃣ 空间复杂度: O ( N ) O(N) O(N)

494. 目标和

题目链接:link

1、题目描述

给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ,然后串联起所有整数,可以构造一个 表达式 :
例如,nums = [2, 1] ,可以在 2 之前添加 ‘+’ ,在 1 之前添加 ‘-’ ,然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1:
输入:nums = [1,1,1,1,1], target = 3
输出:5
解释:一共有 5 种方法让最终目标和为 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
+1 + 1 + 1 + 1 - 1 = 3

2、思路

在这里插入图片描述

3、code

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:# left + right = sum# left - right = targetsum_nums = sum(nums)if (sum_nums + target) % 2 == 1:return 0left = int((sum_nums + target) / 2 )# 4if left < 0:return 0dp = [0] * (left+1) # dp[0],,,,dp[4]dp[0] = 1for i in range(len(nums)): # 0,1,2,3,4for j in range(left,nums[i]-1,-1): # 4,...,nums[i]dp[j] += dp[j-nums[i]]return dp[-1]

4、复杂度分析

1️⃣ 时间复杂度: O ( N 2 ) O(N^2) O(N2)
2️⃣ 空间复杂度: O ( N ) O(N) O(N)

474. 一和零

题目链接:link

1、题目描述

给你一个二进制字符串数组 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 。

2、思路

物品 :每个字符串,重量为两个值分别是0的数量和1的数量,价值就是1
背包容量 :两个,0的容量为m,1的容量为n
dp[i][j]代表0的容量为i,1的容量为j的背包能更装的字符串的个数

经典01问题,只不过dp是二维滚动数组

3、code

class Solution:def find01(self,str):list_str = list(str)num_0 = 0num_1 = 0for x in list_str:if x == '0':num_0 += 1else:num_1 += 1return num_0,num_1def findMaxForm(self, strs: List[str], m: int, n: int) -> int:# 物品是每个字符串,重量为两个值分别是0的数量和1的数量,价值就是1# 背包容量有两个,0的容量为m,1的容量为n# dp[i][j]代表0的容量为i,1的容量为j的背包能更装的字符串的个数dp = [[0 for _ in range(0,n+1)] for _ in range(m+1)]dp[0][0] = 0for x in strs: # 遍历物品num_0,num_1 = self.find01(x)for i in range(m,num_0-1,-1):for j in range(n,num_1-1,-1):dp[i][j] = max(dp[i][j],dp[i-num_0][j-num_1]+1)return dp[-1][-1]

4、复杂度分析

1️⃣ 时间复杂度: O ( N ∗ M ∗ K ) O(N*M*K) O(NMK)
2️⃣ 空间复杂度: O ( N ∗ M ) O(N*M) O(NM)

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



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

相关文章

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Java实现自定义table宽高的示例代码

《Java实现自定义table宽高的示例代码》在桌面应用、管理系统乃至报表工具中,表格(JTable)作为最常用的数据展示组件,不仅承载对数据的增删改查,还需要配合布局与视觉需求,而JavaSwing... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)

HTML5实现的移动端购物车自动结算功能示例代码

《HTML5实现的移动端购物车自动结算功能示例代码》本文介绍HTML5实现移动端购物车自动结算,通过WebStorage、事件监听、DOM操作等技术,确保实时更新与数据同步,优化性能及无障碍性,提升用... 目录1. 移动端购物车自动结算概述2. 数据存储与状态保存机制2.1 浏览器端的数据存储方式2.1.

基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

《基于HTML5Canvas实现图片旋转与下载功能(完整代码展示)》本文将深入剖析一段基于HTML5Canvas的代码,该代码实现了图片的旋转(90度和180度)以及旋转后图片的下载... 目录一、引言二、html 结构分析三、css 样式分析四、JavaScript 功能实现一、引言在 Web 开发中,

Python如何去除图片干扰代码示例

《Python如何去除图片干扰代码示例》图片降噪是一个广泛应用于图像处理的技术,可以提高图像质量和相关应用的效果,:本文主要介绍Python如何去除图片干扰的相关资料,文中通过代码介绍的非常详细,... 目录一、噪声去除1. 高斯噪声(像素值正态分布扰动)2. 椒盐噪声(随机黑白像素点)3. 复杂噪声(如伪

Java Spring ApplicationEvent 代码示例解析

《JavaSpringApplicationEvent代码示例解析》本文解析了Spring事件机制,涵盖核心概念(发布-订阅/观察者模式)、代码实现(事件定义、发布、监听)及高级应用(异步处理、... 目录一、Spring 事件机制核心概念1. 事件驱动架构模型2. 核心组件二、代码示例解析1. 事件定义