共计 1385 个字符,预计需要花费 4 分钟才能阅读完成。
原文归档:「烤冷面讲算法,每周一讲」
原文链接:「动静布局」LeetCode 416(宰割等和子集)
LeetCode 416
上一周讲了 01 背包问题,这周咱们趁热打铁,用 01 背包问题的思路来解决 LeetCode 416 题。
题干简述
给定:一个只蕴含正整数的非空数组 nums。
要求:判断 nums 是否能够被宰割成 元素和相等
的两个子集。
题目详情:416. 宰割等和子集
解题思路
- 解题的关键在于咱们是否从
nums
中找出一些元素,「元素的和」等于「总和」的一半,如果找失去,答案即为 true,否则就是 false。 - 依据第 1 点,咱们能够把这道题转化为 01 背包问题,
背包容量 =nums 元素和 /2
,物品就是nums 数组
中的每个元素,物品的分量和价值相等,等于元素的值(也就是 nums[i])。
除此之外还有一些边界条件:
- 首先,
nums 中所有元素的和
必须为偶数
,否则不可能被宰割成元素和相等
的两个子整数集。 - 其次,若 nums 中某个元素的值 >
总元素和 /2
,间接 return false。
图解算法
官网案例:
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
就像「01 背包问题」这篇文章提到的那样,咱们能够画出这样一个矩阵:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
---|---|---|---|---|---|---|---|---|---|---|---|
nums[0]=1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
nums[1]=5 | 1 | 1 | 1 | 1 | 5 | 6 | 6 | 6 | 6 | 6 | 6 |
nums[2]=11 | 1 | 1 | 1 | 1 | 5 | 6 | 6 | 6 | 6 | 6 | 11 |
nums[3]=5 | 1 | 1 | 1 | 1 | 5 | 6 | 6 | 6 | 6 | 10 | 11 |
代码实现
class Solution:
def canPartition(self, nums: List[int]) -> bool:
s = sum(nums)
target = s // 2
# 边界值检测
if s % 2 == 1:
return False
# 边界值检测
maxNum = 0
for num in (nums):
maxNum = max(num, maxNum)
if maxNum > target:
return False
dp = [([0] * target) for p in range(len(nums))]
# 填充矩阵第一行
for j in range(0, target):
subTarget = j + 1
if subTarget >= nums[0]:
dp[0][j] = nums[0]
# 填充矩阵残余所有行
for i in range(1, len(nums)):
num = nums[i]
for j in range(0, target):
subTarget = j + 1
if subTarget > num:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-num]+num)
elif subTarget == num:
dp[i][j] = num
else:
dp[i][j] = dp[i - 1][j]
if dp[i][target-1] == target:
return True
return False
复杂度
工夫复杂度 O(n^2),空间复杂度 O(n^2),在 LeetCode 下面的体现并不现实:
网上还是有不少优化计划的,比方将二维数组优化为一维数组,空间复杂度从 O(n^2)降到 O(n)。
不过这篇文章的本意在于利用上一篇「01 背包问题」学到的货色来解决 LeetCode 中相干的题目,所以先不开展讲了,当前有机会再探讨这个话题。
最初分享一个不止聊算法的圈子:「Script Run 技术社群」
正文完