网站删除代码,模板网站 可以做推广吗,东营网站建设课程定位优化,详情页设计论文Leetcode 3428. Maximum and Minimum Sums of at Most Size K Subsequences 1. 解题思路2. 代码实现 题目链接#xff1a;3428. Maximum and Minimum Sums of at Most Size K Subsequences
1. 解题思路
这一题不需要连续性#xff0c;因此我们就是考虑取得子串长度为别为1…Leetcode 3428. Maximum and Minimum Sums of at Most Size K Subsequences 1. 解题思路2. 代码实现 题目链接3428. Maximum and Minimum Sums of at Most Size K Subsequences
1. 解题思路
这一题不需要连续性因此我们就是考虑取得子串长度为别为1到k的情况下时每一个元素作为最小的元素以及最大的元素时可以选取的方法总数。而这就是一个简单的排列组合的问题假设一个元素有n和元素比他大m个元素比他小则在长度为k的子串当中其可以作为最大或者最小元素的选择方法总数就是 C n k − 1 C m k − 1 C_n^{k-1} C_m^{k-1} Cnk−1Cmk−1。
我们将其翻译为python代码语言即可。
2. 代码实现
给出python代码实现如下
MOD 10**97Factorials [1 for _ in range(10**51)]
Revs [1 for _ in range(10**51)]
for i in range(2, 10**51):Factorials[i] (i * Factorials[i-1]) % MODRevs[i] pow(Factorials[i], -1, modMOD)def C(n, m):return (Factorials[n] * Revs[n-m] * Revs[m]) % MOD if n m else 0class Solution:def minMaxSums(self, nums: List[int], k: int) - int:nums sorted(nums)n len(nums)ans 0for i, x in enumerate(nums):for m in range(1, k1):ans (ans x * (C(i, m-1) C(n-1-i, m-1))) % MODreturn ans提交代码评测得到耗时8359ms占用内存37.6MB。
