数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++ 子序列宽度之和
假设我们有一个整数数组 A，考虑 A 的所有非空子序列。对于任何序列 S，考虑 S 的宽度为 S 的最大元素和最小元素之间的差。我们必须找到 A 的所有子序列的宽度之和。答案可能非常大，因此返回答案模 10^9 + 7。
因此，如果输入类似于 [3,1,2]，则输出将为 6，这是因为子序列类似于 [1]、[2]、[3]、[2,1]、[2,3]、[1,3]、[2,1,3]，宽度分别为 0、0、0、1、1、2、2，因此宽度值的总和为 6。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 add()，它将接收 a、b，
返回 ((a mod m) + (b mod m)) mod m
定义一个函数 sub()，它将接收 a、b，
返回 (((a mod m) - (b mod m)) + m) mod m
定义一个函数 mul()，它将接收 a、b，
返回 ((a mod m) * (b mod m)) mod m
从主方法中执行以下操作：
对数组 a 进行排序
ans := 0
n := a 的大小
rcnt := 1
初始化 i := 0，当 i < n 时，更新（i 增加 1），执行：
x = mul(a[i], sub(rcnt, 1))
y = mul(a[n-1-i], sub(rcnt, 1))
ans = add(ans, sub(x, y))
rcnt = rcnt * 2
rcnt := rcnt mod m
返回 ans
让我们看看下面的实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return ( (a % m) + (b % m) ) % m;
}
lli sub(lli a, lli b){
return ( ( (a % m) - (b % m) ) + m ) % m;
}
lli mul(lli a, lli b){
return ( (a % m) * (b % m) ) % m;
}
int sumSubseqWidths(vector<int>& a) {
sort(a.begin(), a.end());
int ans = 0;
int n = a.size();
lli rcnt = 1;
for(int i = 0 ; i < n; i++){
ans = add (ans, sub(mul(a[i] , sub(rcnt , 1)), mul(a[n-1-i], sub(rcnt,1))));
rcnt <<=1;
rcnt %= m;
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {3,1,2};
cout << (ob.sumSubseqWidths(v));
}输入
{3,1,2}输出
6
更新于：2020年6月4日
116 次查看
广告