資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告