重庆高端网站设计,网站开发账务处理,中山市建设安全监督站网站,人才网站建设cms494. 目标和
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 或 - #xff0c;然后串联起所有整数#xff0c;可以构造一个 表达式 #xff1a;
例如#xff0c;nums [2, 1] #xff0c;可以在 2 之前添加 #xff0c;在 1 之前添加 - …494. 目标和
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 或 - 然后串联起所有整数可以构造一个 表达式
例如nums [2, 1] 可以在 2 之前添加 在 1 之前添加 - 然后串联起来得到表达式 2-1 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
思路
从数组里的元素-物品的价值target-背包的容量。因为有正负所以商品的价值可正客负。与昨天类似可以先将所有的数看成正数那么每将一个数的符号改为负数总数就减少到 totalsum - 2nums[i], 这道题目就转换成通过修改符号使得 totalsum变为target的选择数目。
既然如此就可以将这道题看作背包问题。totalsum - target// 2 就是背包的容量nums[i]就是物品的体积。求使用nums[i]填满背包的方法数。
那么dp[i]的定义就是 填满容量为i的背包的方法数转移方程为 dp[i] dp[i - nums[j]] , 先遍历 物品nums数组再倒序遍历容量dp数组最后返回dp[target].
根据题意当 totalsum 小于 target 时方法数一定为0当totalsum - target% 2 1时方法数一定为0因为2nums[i] 一定为偶数。当target为0且totalsum满足上列要求是一定可以找到且只能找到一个方法满足条件故dp[0]1
python:
class Solution:def findTargetSumWays(self, nums: List[int], target: int) - int:totalsum sum(nums)if totalsum target:return 0if (totalsum - target) % 2 1:return 0target_num (totalsum - target) // 2dp [0 for _ in range(target_num 1)]dp[0] 1for num in nums:for i in range(target_num, num-1, -1):dp[i] dp[i - num]return dp[target_num]
474. 一和零
给你一个二进制字符串数组 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
输入strs [10, 0, 1], m 1, n 1
输出2
解释最大的子集是 {0, 1} 所以答案是 2
思路可以把这道题看作是二维的01背包字符串数组的字符串的0和1的个数就是二维的空间。动态规划数组 dp[i][j] 表示 背包容量为 m in j 时的的最大子集长度转移方程为 dp max dp[i][j], dp[ i - 字符串0的个数, j - 字符串1的个数] 1
class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) - int:dp [[0] * (n 1) for _ in range(m 1)] # 遍历物品for s in strs:ones s.count(1) zeros s.count(0) # 遍历背包容量且从后向前遍历for i in range(m, zeros - 1, -1):for j in range(n, ones - 1, -1):dp[i][j] max(dp[i][j], dp[i - zeros][j - ones] 1) return dp[m][n]
