Ditulis dalam C++, cari bilangan subarray yang jumlahnya ialah k^m, dengan m >= 0-C++-php.cn

使用C++编写，找到和为k^m形式的子数组数量，其中m >= 0

Dalam artikel ini, kami akan menerangkan segala-galanya tentang mencari bilangan subarray yang jumlahnya ialah k^m, m >= 0 dalam C++. Memandangkan tatasusunan arr[] dan integer K, kita perlu mencari bilangan subarray dengan jumlah dalam bentuk K^m di mana m lebih besar daripada atau sama dengan 0, atau kita boleh katakan kita perlu mencari bilangan subarray dengan hasil tambah bentuk K^m Jumlah kuantiti adalah sama dengan beberapa kuasa bukan negatif 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

Salin selepas log masuk

Terdapat dua kaedah -

Brute force

Dalam kaedah ini kita akan menggelungkan semua sub-tatasusunan dan memeriksa sama ada ia adalah K atau tidak, jika ya maka kita menambah kiraan.

Contoh

#include  #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"; }

Salin selepas log masuk

Output

Salin selepas log masuk

Walau bagaimanapun, kaedah ini tidak begitu baik kerana kerumitan masa program ini ialahO(N*N*log(K)),, di mana N ialah saiz tatasusunan, K ialah saiz tatasusunan. Integer yang diberikan oleh pengguna.

Kerumitan ini tidak bagus kerana kerumitan ini boleh digunakan untuk kekangan yang lebih tinggi kerana jika kekangannya besar ia mengambil masa terlalu lama untuk diproses jadi kami akan cuba pendekatan lain supaya kami boleh menggunakan program untuk mencapai kekangan yang lebih tinggi.

Kaedah yang cekap

Dalam kaedah ini, kami akan menggunakan jumlah awalan dan pemetaan untuk mengurangkan pemprosesan, sekali gus mengurangkan kerumitan masa. < /p>

Contoh

#include  #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 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 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 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; }

Salin selepas log masuk

Output

Salin selepas log masuk

Kesimpulan

Kami menyelesaikan masalah untuk mencari bilangan subarray yang jumlahnya adalah k^m, dengan m >= 0, dengan kerumitan masa O(nlog(k)log(n)) Kerumitan masa. Kami juga mempelajari program C++ untuk menyelesaikan masalah ini dan cara lengkap untuk menyelesaikan masalah ini (biasa dan cekap). Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dan bahasa lain. Semoga artikel ini bermanfaat kepada anda.

Atas ialah kandungan terperinci Ditulis dalam C++, cari bilangan subarray yang jumlahnya ialah k^m, dengan m >= 0. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!