Leetcode Weekly Contest 433

楼主: oin1104 (是oin的说)   2025-01-19 12:27:05
我又进1000名了
家人们
我有一天会拿到Guardian 的
虽然可能要拿一辈子
一辈子...
Q1
每一个i-nums[i] 到 n的元素和
思路
照做
```cpp
class Solution {
public:
int subarraySum(vector<int>& nums)
{
int n = nums.size();
int res = 0;
for(int i = 0 ; i < n ; i ++)
{
int start = max(0 , i - nums[i]);
for(int j = start ; j <= i ; j ++)
{
res += nums[j];
}
}
return res;
}
};
```
Q2
最多k个元素的集合 不用连续
求他们的最大最小值的总合
思路
先sort之后就可以确定每次的最大最小值
然后就可以用C n取k 算出有多少组合
这些组合就是包含当前极值的所有集合
然后全部加起来
```cpp
class Solution {
public:
int minMaxSums(vector<int>& nums, int k)
{
long long res = 0;
int n = nums.size();
vector<vector<long long>> comb(n + 1, vector<long long>(k + 1, 0));
for (int i = 0; i <= n; i++) {
comb[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
if (j > i) break;
comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
comb[i][j] %= 1000000007;
}
}
sort(nums.begin() , nums.end());
for(int i = 0 ; i < n ; i ++)
{
for(int take = 0 ; take < min( k , n - i ) ; take ++)
{
long long now = nums[i] * comb[n-i-1][take] ;
now %= 1000000007;
res += now ;
res %= 1000000007;
}
}
for(int i = n-1 ; i >= 0 ; i
作者: bollseven (噜噜子)   2024-01-19 12:27:00
加油

Links booklink

Contact Us: admin [ a t ] ucptt.com