0%

    6352. 美丽子集的数目


    给你一个由正整数组成的数组 nums 和一个 整数 k

    如果 nums 的子集中,任意两个整数的绝对差均不等于 k ,则认为该子数组是一个 美丽 子集。

    返回数组 nums非空美丽 的子集数目。

    nums 的子集定义为:可以经由 nums 删除某些元素(也可能不删除)得到的一个数组。只有在删除元素时选择的索引不同的情况下,两个子集才会被视作是不同的子集。

    示例 1:

    ```txt

    输入:nums = [2,4,6], k = 2

    输出:4

    解释:数组 nums 中的美丽子集有:[2], [4], [6], [2, 6] 。

    可以证明数组 [2,4,6] 中只存在 4 个美丽子集。

    ```

    示例 2:

    ```txt

    输入:nums = [1], k = 1

    输出:1

    解释:数组 nums 中的美丽数组有:[1] 。

    可以证明数组 [1] 中只存在 1 个美丽子集。

    ```

    提示:

    • 1 <= nums.length <= 20

    • 1 <= nums[i], k <= 1000

阅读全文 »

    1997. 访问完所有房间的第一天


    你需要访问 n 个房间,房间从 0n - 1 编号。同时,每一天都有一个日期编号,从 0 开始,依天数递增。你每天都会访问一个房间。

    最开始的第 0 天,你访问 0 号房间。给你一个长度为 n下标从 0 开始 的数组 nextVisit 。在接下来的几天中,你访问房间的 次序 将根据下面的 规则 决定:

    • 假设某一天,你访问 i 号房间。

    • 如果算上本次访问,访问 i 号房间的次数为 奇数 ,那么 第二天 需要访问 nextVisit[i] 所指定的房间,其中 0 <= nextVisit[i] <= i

    • 如果算上本次访问,访问 i 号房间的次数为 偶数 ,那么 第二天 需要访问 (i + 1) mod n 号房间。

    请返回你访问完所有房间的第一天的日期编号。题目数据保证总是存在这样的一天。由于答案可能很大,返回对 10^9 + 7 取余后的结果。

    示例 1:

    ```txt

    输入:nextVisit = [0,0]

    输出:2

    解释:

    • 第 0 天,你访问房间 0 。访问 0 号房间的总次数为 1 ,次数为奇数。

    下一天你需要访问房间的编号是 nextVisit[0] = 0

    • 第 1 天,你访问房间 0 。访问 0 号房间的总次数为 2 ,次数为偶数。

    下一天你需要访问房间的编号是 (0 + 1) mod 2 = 1

    • 第 2 天,你访问房间 1 。这是你第一次完成访问所有房间的那天。

    ```

    示例 2:

    ```txt

    输入:nextVisit = [0,0,2]

    输出:6

    解释:

    你每天访问房间的次序是 [0,0,1,0,0,1,2,...] 。

    第 6 天是你访问完所有房间的第一天。

    ```

    示例 3:

    ```txt

    输入:nextVisit = [0,1,2,0]

    输出:6

    解释:

    你每天访问房间的次序是 [0,0,1,1,2,2,3,...] 。

    第 6 天是你访问完所有房间的第一天。

    ```

    提示:

    • n == nextVisit.length

    • 2 <= n <= 10^5

    • 0 <= nextVisit[i] <= i

阅读全文 »

    6987. 使数组和小于等于 x 的最少时间


    给你两个长度相等下标从 0 开始的整数数组 nums1 和 nums2 。每一秒,对于所有下标 0 <= i < nums1.length ,nums1[i] 的值都增加 nums2[i] 。操作 完成后 ,你可以进行如下操作:

    • 选择任一满足 0 <= i < nums1.length 的下标 i ,并使 nums1[i] = 0 。

    同时给你一个整数 x 。

    请你返回使 nums1 中所有元素之和 小于等于 x 所需要的 最少 时间,如果无法实现,那么返回 -1 。

    示例 1:

    ```txt

    输入:nums1 = [1,2,3], nums2 = [1,2,3], x = 4

    输出:3

    解释:

    第 1 秒,我们对 i = 0 进行操作,得到 nums1 = [0,2+2,3+3] = [0,4,6] 。

    第 2 秒,我们对 i = 1 进行操作,得到 nums1 = [0+1,0,6+3] = [1,0,9] 。

    第 3 秒,我们对 i = 2 进行操作,得到 nums1 = [1+1,0+2,0] = [2,2,0] 。

    现在 nums1 的和为 4 。不存在更少次数的操作,所以我们返回 3 。

    ```

    示例 2:

    ```txt

    输入:nums1 = [1,2,3], nums2 = [3,3,3], x = 4

    输出:-1

    解释:不管如何操作,nums1 的和总是会超过 x 。

    ```

    提示:

    • 1 <= nums1.length <= 10^3

    • 1 <= nums1[i] <= 10^3

    • 0 <= nums2[i] <= 10^3

    • nums1.length == nums2.length

    • 0 <= x <= 10^6

阅读全文 »

    2902. 和带限制的子多重集合的数目


    给你一个下标从 0 开始的非负整数数组 nums 和两个整数 l 和 r 。

    请你返回 nums 中子多重集合的和在闭区间 [l, r] 之间的 子多重集合的数目

    由于答案可能很大,请你将答案对 10^9 + 7 取余后返回。

    子多重集合 指的是从数组中选出一些元素构成的 无序 集合,每个元素 x 出现的次数可以是 0, 1, ..., occ[x] 次,其中 occ[x] 是元素 x 在数组中的出现次数。

    注意:

    • 如果两个子多重集合中的元素排序后一模一样,那么它们两个是相同的 子多重集合 。

    •  集合的和是 0 。

    示例 1:

    ```txt

    输入:nums = [1,2,2,3], l = 6, r = 6

    输出:1

    解释:唯一和为 6 的子集合是 {1, 2, 3} 。

    ```

    示例 2:

    ```txt

    输入:nums = [2,1,4,2,7], l = 1, r = 5

    输出:7

    解释:和在闭区间 [1, 5] 之间的子多重集合为 {1} ,{2} ,{4} ,{2, 2} ,{1, 2} ,{1, 4} 和 {1, 2, 2} 。

    ```

    示例 3:

    ```txt

    输入:nums = [1,2,1,3,5,2], l = 3, r = 5

    输出:9

    解释:和在闭区间 [3, 5] 之间的子多重集合为 {3} ,{5} ,{1, 2} ,{1, 3} ,{2, 2} ,{2, 3} ,{1, 1, 2} ,{1, 1, 3} 和 {1, 2, 2} 。

    ```

    提示:

    • 1 <= nums.length <= 2 * 10^4

    • 0 <= nums[i] <= 2 * 10^4

    • nums 的和不超过 2 * 10^4

    • 0 <= l <= r <= 2 * 10^4

阅读全文 »

    2518. 好分区的数目


    给你一个正整数数组 nums 和一个整数 k

    分区 的定义是:将数组划分成两个有序的 ,并满足每个元素 恰好 存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k ,则认为分区是一个好分区。

    返回 不同 的好分区的数目。由于答案可能很大,请返回对 10^9 + 7 取余 后的结果。

    如果在两个分区中,存在某个元素 nums[i] 被分在不同的组中,则认为这两个分区不同。

    示例 1:

    ```txt

    输入:nums = [1,2,3,4], k = 4

    输出:6

    解释:好分区的情况是 ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) 和 ([4], [1,2,3]) 。

    ```

    示例 2:

    ```txt

    输入:nums = [3,3,3], k = 4

    输出:0

    解释:数组中不存在好分区。

    ```

    示例 3:

    ```txt

    输入:nums = [6,6], k = 2

    输出:2

    解释:可以将 nums[0] 放入第一个分区或第二个分区中。

    好分区的情况是 ([6], [6]) 和 ([6], [6]) 。

    ```

    提示:

    • 1 <= nums.length, k <= 1000

    • 1 <= nums[i] <= 10^9

阅读全文 »

    6364. 无平方子集计数


    给你一个正整数数组 nums

    如果数组 nums 的子集中的元素乘积是一个 无平方因子数 ,则认为该子集是一个 无平方 子集。

    无平方因子数 是无法被除 1 之外任何平方数整除的数字。

    返回数组 nums无平方非空 的子集数目。因为答案可能很大,返回对 10^9 + 7 取余的结果。

    nums非空子集 是可以由删除 nums 中一些元素(可以不删除,但不能全部删除)得到的一个数组。如果构成两个子集时选择删除的下标不同,则认为这两个子集不同。

    示例 1:

    ```txt

    输入:nums = [3,4,4,5]

    输出:3

    解释:示例中有 3 个无平方子集:

    • 由第 0 个元素 [3] 组成的子集。其元素的乘积是 3 ,这是一个无平方因子数。

    • 由第 3 个元素 [5] 组成的子集。其元素的乘积是 5 ,这是一个无平方因子数。

    • 由第 0 个和第 3 个元素 [3,5] 组成的子集。其元素的乘积是 15 ,这是一个无平方因子数。

    可以证明给定数组中不存在超过 3 个无平方子集。

    ```

    示例 2:

    ```txt

    输入:nums = [1]

    输出:1

    解释:示例中有 1 个无平方子集:

    • 由第 0 个元素 [1] 组成的子集。其元素的乘积是 1 ,这是一个无平方因子数。

    可以证明给定数组中不存在超过 1 个无平方子集。

    ```

    提示:

    • 1 <= nums.length <= 1000

    • 1 <= nums[i] <= 30

阅读全文 »

    1125. 最小的必要团队


    作为项目经理,你规划了一份需求的技能清单 req_skills,并打算从备选人员名单 people 中选出些人组成一个「必要团队」( 编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表)。

    所谓「必要团队」,就是在这个团队中,对于所需求的技能列表 req_skills 中列出的每项技能,团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员:

    • 例如,团队 team = [0, 1, 3] 表示掌握技能分别为 people[0]people[1],和 people[3] 的备选人员。

    请你返回 任一 规模最小的必要团队,团队成员用人员编号表示。你可以按 任意顺序 返回答案,题目数据保证答案存在。

    示例 1:

    ```txt

    输入:req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]

    输出:[0,2]

    ```

    示例 2:

    ```txt

    输入:req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]

    输出:[1,2]

    ```

    提示:

    • 1 <= req_skills.length <= 16

    • 1 <= req_skills[i].length <= 16

    • req_skills[i] 由小写英文字母组成

    • req_skills 中的所有字符串 互不相同

    • 1 <= people.length <= 60

    • 0 <= people[i].length <= 16

    • 1 <= people[i][j].length <= 16

    • people[i][j] 由小写英文字母组成

    • people[i] 中的所有字符串 互不相同

    • people[i] 中的每个技能是 req_skills 中的技能

    • 题目数据保证「必要团队」一定存在

阅读全文 »