資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用C++查詢和為k^m形式的子陣列個數，其中m>=0
在本文中，我們將解釋如何使用C++解決求和為k^m形式(m>=0)的子陣列個數的問題。給定一個數組arr[]和一個整數K，我們需要找到和為K^m形式的子陣列個數，其中m大於等於零，也就是說，我們需要找到和等於K的某個非負冪的子陣列個數。
Input: arr[] = { 2, 2, 2, 2 } K = 2
Output: 8
Sub-arrays with below indexes are valid:
[1, 1], [2, 2], [3, 3], [4, 4], [1, 2],
[2, 3], [3, 4], [1, 4]
Input: arr[] = { 3, -6, -3, 12 } K = -3
Output: 3主要有兩種方法：
暴力法
這種方法會遍歷所有子陣列，並檢查它們的和是否為K的正整數冪；如果是，則計數器加一。
示例
#include <bits/stdc++.h>
#define MAX 1000000
using namespace std;
int main(){
int arr[] = {2, 2, 2, 2}; // given array
int k = 2; // given integer
int n = sizeof(arr) / sizeof(arr[0]); // the size of our array
int answer = 0; // counter variable
for(int i = 0; i < n; i++){
int sum = 0;
for(int j = i; j < n; j++){ // this will loop will make all the subarrays
sum += arr[j];
int b = 1;
while(b < MAX && sum > b) // k^m Max should be 10^6
b *= k;
if(b == sum) // if b == sum then increment count
answer++;
}
}
cout << answer << "\n";
}輸出
8
然而，這種方法效率不高，因為程式的時間複雜度為O(N*N*log(K))，其中N是陣列的大小，K是使用者給定的整數。
這種複雜度並不理想，因為在約束條件較高時，處理時間會過長。因此，我們將嘗試另一種方法，以便在約束條件較高時也能使用該程式。
高效方法
這種方法將使用字首和和對映來減少處理量，從而顯著降低時間複雜度。
示例
#include <bits/stdc++.h>
#define ll long long
#define MAX 1000000
using namespace std;
int main(){
int arr[] = {2, 2, 2, 2}; // The given array
int n = sizeof(arr) / sizeof(arr[0]); // size of our array
int k = 2; // given integer
ll prefix_sum[MAX];
prefix_sum[0] = 0;
partial_sum(arr, arr + n, prefix_sum + 1); // making prefix sum array
ll sum;
if (k == 1){
// we are going to check separately for 1
sum = 0;
map<ll, int> m;
for (int i = n; i >= 0; i--){
// If m[a+b] = c, then add c to the current sum.
if (m.find(prefix_sum[i] + 1) != m.end())
sum += m[prefix_sum[i] + 1];
// Increase count of prefix sum.
m[prefix_sum[i]]++;
}
cout << sum << "\n";
}
else if (k == -1){
// we are going to check separately for -1
sum = 0;
map<ll, int> m;
for (int i = n; i >= 0; i--){
// If m[a+b] = c, then add c to the current sum.
if (m.find(prefix_sum[i] + 1) != m.end())
sum += m[prefix_sum[i] + 1];
if (m.find(prefix_sum[i] - 1) != m.end())
sum += m[prefix_sum[i] - 1];
// Increase count of prefix sum.
m[prefix_sum[i]]++;
}
cout << sum << "\n";
}
else{
sum = 0;
ll b;
map<ll, int> m;
for (int i = n; i >= 0; i--){
b = 1;
while (b < MAX){ // we are not going to check for more than 10^6
// If m[a+b] = c, then add c to the current sum.
if (m.find(prefix_sum[i] + b) != m.end())
sum += m[prefix_sum[i] + b];
b *= k;
}
m[prefix_sum[i]]++;
}
cout << sum << "\n";
}
return 0;
}輸出
8
結論
我們解決了查詢和為k^m形式(m>=0)的子陣列個數的問題，時間複雜度為O(nlog(k)log(n))。我們還學習了該問題的C++程式以及解決該問題的完整方法（常規方法和高效方法）。可以使用C、Java、Python和其他語言編寫相同的程式。希望本文對您有所幫助。
更新於：2021年11月25日
94次瀏覽
廣告