盈利计划

题面

leetcode题目

集团里有 \(n\) 名员工，他们可以完成各种各样的工作创造利润。

第 \(i\) 种工作会产生 \(profit[i]\) 的利润，它要求 \(group[i]\) 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。

工作的任何至少产生 \(minProfit\) 利润的子集称为 盈利计划 。并且工作的成员总数最多为 \(n\) 。

有多少种计划可以选择？因为答案很大，所以 返回结果模 \(10^9 + 7\) 的值。

example

输入：\(n = 5\), \(minProfit = 3\), \(group = [2,2]\), \(profit = [2,3]\)
输出：\(2\)
解释：至少产生 \(3\) 的利润，该集团可以完成工作 \(0\) 和工作 \(1\) ，或仅完成工作 \(1\) 。 总的来说，有两种计划。

最后一块石头的重量 II

题面

leetcode题目

有一堆石头，用整数数组 \(stones\) 表示。其中 \(stones[i]\) 表示第 \(i\) 块石头的重量。

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

• 如果 \(x = y\)，那么两块石头都会被完全粉碎；
• 如果 \(x\neq y\)，那么重量为 \(x\) 的石头将会完全粉碎，而重量为 \(y\) 的石头新重量为 \(y-x\)。
• 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 \(0\)。

example

输入：\(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]\)，这就是最优值。

目标和

题面

leetcode题目

给你一个整数数组 \(nums\) 和一个整数 \(target\) 。

向数组中的每个整数前添加 \(+\) 或 \(-\) ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，\(nums = [2, 1]\) ，可以在 \(2\) 之前添加 \(+\) ，在 \(1\) 之前添加 \(-\) ，然后串联起来得到表达式 \(+2-1\) 。

返回可以通过上述方法构造的、运算结果等于 \(target\) 的不同 表达式 的数目。

example

输入：\(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\)

一和零

题面

leetcode题目

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

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

如果 \(x\) 的所有元素也是 \(y\) 的元素，集合 \(x\) 是集合 \(y\) 的子集。

example

输入：\(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\) 。