您的位置:首页 > 健康 > 养生 > 杭州网站建设_三国杀网页在线客服_百度搜索引擎平台_中国新闻网最新消息

杭州网站建设_三国杀网页在线客服_百度搜索引擎平台_中国新闻网最新消息

2025/4/16 16:00:14 来源:https://blog.csdn.net/m0_67598823/article/details/144129713  浏览:    关键词:杭州网站建设_三国杀网页在线客服_百度搜索引擎平台_中国新闻网最新消息
杭州网站建设_三国杀网页在线客服_百度搜索引擎平台_中国新闻网最新消息

题目描述:

给你一个长度为 n 的 正 整数数组 nums 。

如果两个 非负 整数数组 (arr1, arr2) 满足以下条件,我们称它们是 单调 数组对:

两个数组的长度都是 n 。
arr1 是单调 非递减 的,换句话说 arr1[0] <= arr1[1] <= ... <= arr1[n - 1] 。
arr2 是单调 非递增 的,换句话说 arr2[0] >= arr2[1] >= ... >= arr2[n - 1] 。
对于所有的 0 <= i <= n - 1 都有 arr1[i] + arr2[i] == nums[i] 。
请你返回所有 单调 数组对的数目。

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

代码思路:

这个代码是用来解决一个特定问题的,即给定一个整数数组 nums,找出满足 |nums[i] - nums[j]| <= nums[i] + nums[j] 的数对 (i, j)(其中 i < j)的数量,并且结果需要对 10^9 + 7 取模。

1.MOD 的定义:
MOD = 10 ** 9 + 7
这行代码定义了一个大质数 MOD,用于在最终结果上进行取模操作,以避免整数溢出并保持结果在一个可管理的范围内。

2.类和方法
class Solution:
    def countOfPairs(self, nums: List[int]) -> int:
定义了一个名为 Solution 的类,并在其中定义了一个名为 countOfPairs 的方法,该方法接受一个整数列表 nums 作为输入,并返回一个整数作为输出。

3.初始化变量
n = len(nums)
prex, prey = inf, 0
n 是数组 nums 的长度。
prex 和 prey 是两个辅助变量,用于记录遍历数组时的一些边界条件。prex 初始化为正无穷大(inf),prey 初始化为 0。
4.反向遍历数组
for num in nums[::-1]:
代码选择从数组的末尾开始反向遍历数组。这是因为算法依赖于某种形式的“前缀”和“后缀”的更新逻辑,反向遍历有助于这种逻辑的实现。

5.更新条件
python
if num < prey:
    return 0
如果在反向遍历的过程中,发现当前元素 num 小于 prey,则直接返回 0。这是因为如果 num 小于 prey,那么不可能再有数对 (i, j) 满足条件 |nums[i] - nums[j]| <= nums[i] + nums[j](因为 j 的值会更大,而 nums[j] 会更小)。

6.更新 prex 和 prey
prex, prey = min(prex, num - prey), max(prey, num - prex)
这行代码是算法的核心。它基于当前元素 num 更新 prex 和 prey 的值,以确保 prex 始终记录可能的“最小差”,而 prey 始终记录可能的“最大差”。这种更新方式允许我们在后续步骤中确定所有可能的数对。

7.计算组合数并返回结果
return comb(prex + n, n) % MOD
最后,使用某种组合数计算函数 comb(n, k)(该函数未在代码中定义,但假设它计算的是从 n 个元素中选出 k 个元素的组合数)来计算满足条件的数对数量。由于 prex + n 表示可能的最大差值加上数组长度(代表可以放置的额外元素数量),所以 comb(prex + n, n) 实际上是在计算一个“范围”内的组合数。然后,结果对 MOD 取模并返回。

代码实现:

MOD = 10 ** 9 + 7
class Solution:def countOfPairs(self, nums: List[int]) -> int:n = len(nums)prex, prey = inf, 0for num in nums[::-1]:if num < prey:return 0prex, prey = min(prex, num - prey), max(prey, num - prex)return comb(prex + n, n) % MOD

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com