fork()==0世界线变动

正在加载今日诗词....

0%

发表于 更新于 分类于

    2585. 获得分数的方法数

    考试中有 n 种类型的题目。给你一个整数 target 和一个下标从 0 开始的二维整数数组 types ，其中 types[i] = [counti, marksi] 表示第 i 种类型的题目有 counti 道，每道题目对应 marksi 分。

    返回你在考试中恰好得到 target 分的方法数。由于答案可能很大，结果需要对 10^9 +7 取余。

    注意，同类型题目无法区分。

    • 比如说，如果有 3 道同类型题目，那么解答第 1 和第 2 道题目与解答第 1 和第 3 道题目或者第 2 和第 3 道题目是相同的。

    示例 1：

    ```txt

    输入：target = 6, types = [[6,1],[3,2],[2,3]]

    输出：7

    解释：要获得 6 分，你可以选择以下七种方法之一：

    • 解决 6 道第 0 种类型的题目：1 + 1 + 1 + 1 + 1 + 1 = 6

    • 解决 4 道第 0 种类型的题目和 1 道第 1 种类型的题目：1 + 1 + 1 + 1 + 2 = 6

    • 解决 2 道第 0 种类型的题目和 2 道第 1 种类型的题目：1 + 1 + 2 + 2 = 6

    • 解决 3 道第 0 种类型的题目和 1 道第 2 种类型的题目：1 + 1 + 1 + 3 = 6

    • 解决 1 道第 0 种类型的题目、1 道第 1 种类型的题目和 1 道第 2 种类型的题目：1 + 2 + 3 = 6

    • 解决 3 道第 1 种类型的题目：2 + 2 + 2 = 6

    • 解决 2 道第 2 种类型的题目：3 + 3 = 6

    ```

    示例 2：

    ```txt

    输入：target = 5, types = [[50,1],[50,2],[50,5]]

    输出：4

    解释：要获得 5 分，你可以选择以下四种方法之一：

    • 解决 5 道第 0 种类型的题目：1 + 1 + 1 + 1 + 1 = 5

    • 解决 3 道第 0 种类型的题目和 1 道第 1 种类型的题目：1 + 1 + 1 + 2 = 5

    • 解决 1 道第 0 种类型的题目和 2 道第 1 种类型的题目：1 + 2 + 2 = 5

    • 解决 1 道第 2 种类型的题目：5

    ```

    示例 3：

    ```txt

    输入：target = 18, types = [[6,1],[3,2],[2,3]]

    输出：1

    解释：只有回答所有题目才能获得 18 分。

    ```

    提示：

    • 1 <= target <= 1000

    • n == types.length

    • 1 <= n <= 50

    • types[i].length == 2

    • 1 <= counti, marksi <= 50

阅读全文 »

发表于 分类于

    划分数组得到最小的值之和

    给你两个数组 nums 和 andValues，长度分别为 n 和 m。

    数组的 值 等于该数组的 最后一个 元素。

    你需要将 nums 划分为 m 个 不相交的连续 子数组，对于第 ith 个子数组 `[li,

    ri]，子数组元素的按位AND运算结果等于andValues[i]，换句话说，对所有的1 <= i <= m，nums[li] &

    nums[li + 1] & ... & nums[ri] == andValues[i]，其中&表示按位AND`运算符。

    返回将 nums 划分为 m 个子数组所能得到的可能的 最小 子数组 值 之和。如果无法完成这样的划分，则返回 -1 。

    示例 1：

    输入： nums = [1,4,3,3,2], andValues = [0,3,3,2]

    输出： 12

    解释：

    唯一可能的划分方法为：

    1. [1,4] 因为 1 &amp; 4 == 0

    2. [3] 因为单元素子数组的按位 AND 结果就是该元素本身

    3. [3] 因为单元素子数组的按位 AND 结果就是该元素本身

    4. [2] 因为单元素子数组的按位 AND 结果就是该元素本身

    这些子数组的值之和为 4 + 3 + 3 + 2 = 12

    示例 2：

    输入： nums = [2,3,5,7,7,7,5], andValues = [0,7,5]

    输出： 17

    解释：

    划分 nums 的三种方式为：

    1. [[2,3,5],[7,7,7],[5]] 其中子数组的值之和为 5 + 7 + 5 = 17

    2. [[2,3,5,7],[7,7],[5]] 其中子数组的值之和为 7 + 7 + 5 = 19

    3. [[2,3,5,7,7],[7],[5]] 其中子数组的值之和为 7 + 7 + 5 = 19

    子数组值之和的最小可能值为 17

    示例 3：

    输入： nums = [1,2,3,4], andValues = [2]

    输出： -1

    解释：

    整个数组 nums 的按位 AND 结果为 0。由于无法将 nums 划分为单个子数组使得元素的按位 AND 结果为 2，因此返回

    -1。

    提示：

    • 1 &lt;= n == nums.length &lt;= 104

    • 1 &lt;= m == andValues.length &lt;= min(n, 10)

    • 1 &lt;= nums[i] &lt; 105

    • 0 &lt;= andValues[j] &lt; 105

阅读全文 »

发表于 分类于

    不包含相邻元素的子序列的最大和

    给你一个整数数组 nums 和一个二维数组 queries，其中 queries[i] = [posi, xi]。

    对于每个查询 i，首先将 nums[posi] 设置为 xi，然后计算查询 i 的答案，该答案为 nums 中 不包含相邻元素

    的子序列的 最大 和。

    返回所有查询的答案之和。

    由于最终答案可能非常大，返回其对 109 + 7 取余 的结果。

    子序列 是指从另一个数组中删除一些或不删除元素而不改变剩余元素顺序得到的数组。

    示例 1：

    输入： nums = [3,5,9], queries = [[1,-2],[0,-3]]

    输出： 21

    解释：

    执行第 1 个查询后，nums = [3,-2,9]，不包含相邻元素的子序列的最大和为 3 + 9 = 12。

    执行第 2 个查询后，nums = [-3,-2,9]，不包含相邻元素的子序列的最大和为 9 。

    示例 2：

    输入： nums = [0,-1], queries = [[0,-5]]

    输出： 0

    解释：

    执行第 1 个查询后，nums = [-5,-1]，不包含相邻元素的子序列的最大和为 0（选择空子序列）。

    提示：

    • 1 &lt;= nums.length &lt;= 5 * 104

    • -105 &lt;= nums[i] &lt;= 105

    • 1 &lt;= queries.length &lt;= 5 * 104

    • queries[i] == [posi, xi]

    • 0 &lt;= posi &lt;= nums.length - 1

    • -105 &lt;= xi &lt;= 105

阅读全文 »

发表于 分类于

    物块放置查询

    有一条无限长的数轴，原点在 0 处，沿着 x 轴 正 方向无限延伸。

    给你一个二维数组 queries ，它包含两种操作：

    1. 操作类型 1 ：queries[i] = [1, x] 。在距离原点 x 处建一个障碍物。数据保证当操作执行的时候，位置 x 处 没有 任何障碍物。

    2. 操作类型 2 ：queries[i] = [2, x, sz] 。判断在数轴范围 [0, x] 内是否可以放置一个长度为 sz 的物块，这个物块需要 完全 放置在范围 [0, x] 内。如果物块与任何障碍物有重合，那么这个物块 不能 被放置，但物块可以与障碍物刚好接触。注意，你只是进行查询，并 不是 真的放置这个物块。每个查询都是相互独立的。

    请你返回一个 boolean 数组results ，如果第 i 个操作类型 2 的操作你可以放置物块，那么 results[i] 为

    true ，否则为 false 。

    示例 1：

    输入： queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]]

    输出：[false,true,true]

    解释：

    查询 0 ，在 x = 2 处放置一个障碍物。在 x = 3 之前任何大小不超过 2 的物块都可以被放置。

    示例 2：

    输入： queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]

    输出：[true,true,false]

    解释：

    • 查询 0 在 x = 7 处放置一个障碍物。在 x = 7 之前任何大小不超过 7 的物块都可以被放置。

    • 查询 2 在 x = 2 处放置一个障碍物。现在，在 x = 7 之前任何大小不超过 5 的物块可以被放置，x = 2 之前任何大小不超过 2 的物块可以被放置。

    提示：

    • 1 &lt;= queries.length &lt;= 15 * 104

    • 2 &lt;= queries[i].length &lt;= 3

    • 1 &lt;= queries[i][0] &lt;= 2

    • 1 &lt;= x, sz &lt;= min(5 * 104, 3 * queries.length)

    • 输入保证操作 1 中，x 处不会有障碍物。

    • 输入保证至少有一个操作类型 2 。

阅读全文 »

发表于 更新于 分类于 ，

    给出一个长度为n的浮点数数组a。数组每个值在0到1之间。

    现在你要n个人出题。

    第i个人出题成功的概率为a[i]

    如果可以从n个人中选一些人出题，恰好只有一个人出题的最大概率是多少？

阅读全文 »