最小好进制

题面

leetcode题目

对于给定的整数 \(n\), 如果\(n\)的\(k\) （ \(k\geq 2\)）进制数的所有数位全为\(1\)，则称 \(k\) （ \(k\geq 2\)）是 n 的一个好进制。

以字符串的形式给出 \(n\), 以字符串的形式返回 \(n\) 的最小好进制。

example

输入："13"
输出："3"
解释：13 的 \(3\) 进制是 \(111\)。

数位成本和为目标值的最大数字

题面

leetcode题目

给你一个整数数组 \(cost\) 和一个整数 \(target\) 。请你返回满足如下规则可以得到的 最大 整数：

• 给当前结果添加一个数位\(（i + 1）\)的成本为 \(cost[i]\) （\(cost\) 数组下标从 \(0\) 开始）。
• 总成本必须恰好等于 \(target\) 。
• 添加的数位中没有数字 \(0\) 。

由于答案可能会很大，请你以字符串形式返回。

如果按照上述要求无法得到任何整数，请你返回 "0" 。

example

输入：\(cost = [4,3,2,5,6,7,2,5,5]\), \(target = 9\)
输出："7772"
解释：添加数位 '7' 的成本为 \(2\) ，添加数位 '2' 的成本为 \(3\) 。所以 "7772" 的代价为 \(2\times 3+ 3\times 1 = 9\) 。 "977" 也是满足要求的数字，但 "7772" 是较大的数字。
数字 成本
1 -> 4
2 -> 3
3 -> 2
4 -> 5
5 -> 6
6 -> 7
7 -> 2
8 -> 5
9 -> 5

零钱兑换 II

题面

leetcode题目

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

example

输入: \(amount = 5\), \(coins = [1, 2, 5]\)
输出: \(4\)
解释: 有四种方式可以凑成总金额:

• \(5=5\)
• \(5=2+2+1\)
• \(5=2+1+1+1\)
• \(5=1+1+1+1+1\)

盈利计划

题面

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\) 。