


Tulis program menggunakan C++ untuk mencari bilangan subarray dengan jumlah dalam julat tertentu
Dalam artikel ini, kami akan menggunakan program C++ untuk mencari bilangan sub-tatasusunan yang jumlahnya berada dalam julat tertentu. Kami mempunyai tatasusunan integer positif arr[] dan julat {L, R} dan kami perlu mengira jumlah bilangan subarray yang jumlahnya berada dalam julat L hingga R yang diberikan. Jadi berikut adalah contoh mudah masalah -
Input : arr[] = {1, 4, 6}, L = 3, R = 8 Output : 3 The subarrays are {1, 4}, {4}, {6}. Input : arr[] = {2, 3, 5, 8}, L = 4, R = 13 Output : 6 The subarrays are {2, 3}, {2, 3, 5}, {3, 5}, {5}, {5, 8}, {8}.
Cara untuk mencari penyelesaian
Kami akan menerangkan dua cara untuk menyelesaikan masalah ini menggunakan C++ -
Kaedah brute force
Kaedah brute force yang paling asas digunakan untuk mengira setiap sub Jumlah tatasusunan dan kemudian mencari sama ada jumlah itu wujud dalam julat yang diberikan. (Tetapi pendekatan ini akan membawa kita banyak masa kerana kerumitan masanya ialah O(n*n), di mana n ialah saiz tatasusunan).
Kaedah yang cekap
Save Now, kaedah yang cekap ialah menggunakan teknik sliding window, menggunakan teknik ini kita akan mengira hasilnya dengan lebih pantas atau lebih cekap dalam O(n).
Contoh
#include <bits/stdc++.h> using namespace std; int subCount(int *arr, int n, int x){ int start = 0, end = 0, sum = 0, count = 0; while (end < n){ // we will be moving right border in this loop sum = sum + arr[end]; while(start <= end && sum >= x){ // this loop will move our left border sum = sum - arr[start]; // we will decrement sum while moving left border. // For excluding the previous elements. start++; // and move the left border. } count = count + ((end - start) + 1); // counting the subarrays. end++; } return count; } int main(){ int arr[] = { 1, 4, 6 }; int n = sizeof(arr) / sizeof(arr[0]); int L = 3; int R = 8; int answer; answer = subCount(arr, n, R) - subCount(arr, n, (L - 1)); // Final Answer. cout << answer << "\n"; return 0; }
Output
3
Di atas perihalan kod
Dalam kaedah ini, kita mengira bilangan sub-tatasusunan yang jumlahnya kurang daripada had atas julat yang diberikan dan kemudian menolak bilangan sub-tatasusunan yang jumlahnya adalah kurang daripada had atas julat yang diberikan. Gunakan fungsi subcount untuk mendapatkan kurang daripada had bawah julat tertentu.
Fungsi subcount
Fungsi ini menggunakan teknik tetingkap gelongsor untuk mencari kiraan subarray yang kiraan kurang daripada x.
Pertama, kita mulakan dengan "Tamat" dan "Mula", yang kedua-duanya mempunyai nilai 0. Apabila kita mengulangi tatasusunan, kita mengekalkan jumlah elemen dari awal hingga akhir. Selepas itu, jika permulaan kita bersamaan dengan akhir dan jumlahnya lebih besar daripada atau sama dengan x, kita mula menggerakkan permulaan dan terus mengurangkan jumlah semasa kita mengeluarkan elemen daripada jumlah itu.
Sehingga jumlah kita menjadi kurang daripada x atau permulaan kita menjadi lebih besar daripada penghujung kita. Sekarang kita meningkatkan kiraan dengan kiraan subarray dan kemudian meningkatkan sempadan kanan sebanyak 1. Sekarang, selepas gelung luar tamat, kami mengembalikan jumlah kiraan subarray.
Kesimpulan
Dalam kertas ini, kami menyelesaikan masalah mencari bilangan subarray yang jumlahnya berada dalam julat tertentu dalam kerumitan masa O(n) menggunakan teknik tetingkap gelongsor. Kami juga belajar tentang masalah ini daripada program C++ dan cara lengkap kami boleh menyelesaikannya dengan mudah (biasa dan cekap). Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dll.
Atas ialah kandungan terperinci Tulis program menggunakan C++ untuk mencari bilangan subarray dengan jumlah dalam julat tertentu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Alat AI Hot

Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool
Gambar buka pakaian secara percuma

Clothoff.io
Penyingkiran pakaian AI

AI Hentai Generator
Menjana ai hentai secara percuma.

Artikel Panas

Alat panas

Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6
Alat pembangunan web visual

SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Topik panas



Kita semua tahu nombor yang bukan kuasa dua mana-mana nombor, seperti 2, 3, 5, 7, 8, dll. Terdapat N nombor bukan persegi, dan adalah mustahil untuk mengetahui setiap nombor. Jadi, dalam artikel ini, kami akan menerangkan segala-galanya tentang nombor tanpa kuasa dua atau bukan kuasa dua dan cara untuk mencari nombor bukan kuasa dua N dalam C++. Nombor bukan kuasa dua ken Jika nombor ialah kuasa dua integer, maka nombor itu dipanggil kuasa dua sempurna. Beberapa contoh nombor kuasa dua sempurna ialah -1isquareof14issquareof29issquareof316issquareof425issquareof5 Jika nombor bukan kuasa dua mana-mana integer, maka nombor itu dipanggil bukan kuasa dua. Sebagai contoh, 15 nombor bukan kuasa dua yang pertama ialah -2,3,5,6,

Dalam artikel ini, kita akan mempelajari tentang algoritma pembalikan untuk memutar tatasusunan yang diberikan ke kanan dengan elemen k, contohnya −Input:arr[]={4,6,2,6,43,7,3,7}, k= 4Output:{43,7,3,7,4,6,2,6}Penjelasan:Pusingeachelementofarrayby4-elementtotherightmemberi{43,7,3,7,4,6,2,6}.Input:arr[]= {8 ,5,8,2,1,4,9,3},k=3Output:{4,9,3,8,5,8,2,1} Cari penyelesaian

Bulatan ialah rajah tertutup. Semua titik pada bulatan adalah sama jarak dari titik di dalam bulatan. Titik tengah dipanggil pusat bulatan. Jarak dari satu titik ke pusat bulatan dipanggil jejari. Luas ialah perwakilan kuantitatif bagi rentang dimensi bagi rajah tertutup. Luas bulatan ialah kawasan yang tertutup dalam dimensi bulatan. Formula untuk mengira luas bulatan, Luas=π*r*r Untuk mengira luas, kami memberikan jejari bulatan sebagai input, kami akan menggunakan formula untuk mengira luas, algoritma LANGKAH1: Takeradiusasinputfromtheuserusingstdinput.STEP2 : Kirakaluas bulatan, luas=(

Kami mempunyai dua tatasusunan integer, satu dengan elemen yang dikira dan satu lagi dengan titik pisah yang diperlukan untuk memisahkan tatasusunan untuk menghasilkan subset, kita perlu mengira jumlah setiap subset dalam setiap pecahan dan mengembalikan subset maksimum Mari kita lihat contoh Pemahaman: - input −intarr[]=intarr[]={9,4,5,6,7}intsplitPoints[]={0,2,3,1}; 13,9,9] Penjelasan − Di sini kita menguraikan tatasusunan mengikut titik pecahannya dan mendapatkan subset maksimum selepas setiap pecahan dan selepas pecahan pertama → {9} dan {4,5,6,7 }>>Jumlah maksimum subarray ialah -22 selepas pemisahan kedua→{9},{4

Kami memerlukan pengetahuan yang betul untuk mencipta beberapa pasangan unik dalam sintaks tatasusunan C++. Semasa mencari bilangan pasangan unik, kami mengira semua pasangan unik dalam tatasusunan yang diberikan iaitu semua pasangan yang mungkin boleh dibentuk di mana setiap pasangan harus unik. Contohnya -Input:array[]={5,5,9}Output:4Explanation:Thenumberofalluniquepairsare(5,5),(5,9),(9,5)and(9,9).Input:array[] = {5,4,3,2,2}Output:16 Cara Mencari Penyelesaian Terdapat dua cara untuk menyelesaikan masalah ini, iaitu −

Dalam artikel ini, kami akan menggunakan C++ untuk menyelesaikan masalah mencari bilangan subarray yang nilai maksimum dan minimumnya adalah sama. Berikut ialah contoh masalah −Input:array={2,3,6,6,2,4,4,4}Output:12Penjelasan:{2},{3},{6},{6}, {2 },{4},{4},{4},{6,6},{4,4},{4,4}dan{4,4,4}arethesubarraysyang boleh dibentuk denganmaksimumdanminimumelemensama.Input:array={3, 3, 1,5,

Dalam artikel ini kami akan menerangkan cara untuk mencari hubungan refleksif pada set. Dalam masalah ini, kita diberi nombor n, dan set n nombor asli, dan kita mesti menentukan bilangan hubungan refleksif. Hubungan refleksif - Suatu hubungan R dikatakan sebagai hubungan refleksif pada set A jika bagi setiap 'a' dalam set A, (a, a) tergolong dalam hubungan R. Contohnya -Input:x=1Output:1Explanation:set={1},reflexiverelationsonA*A:{{1}}Input:x=2Output:4Explanation:set={1,2},reflexiverelationsonA*

Dalam masalah ini, kita diberikan penunjuk kepada kepala senarai terpaut dan integer k. Dalam kumpulan saiz k, kita perlu membalikkan senarai terpaut. Contohnya -Input:1<->2<->3<->4<->5(doublylinkedlist),k=3Output:3<->2<->1<->5<->4 mencari penyelesaian Kaedah Dalam masalah ini, kami akan merumuskan algoritma rekursif untuk menyelesaikan masalah ini. Dalam kaedah ini kita akan menggunakan rekursi dan menyelesaikan masalah menggunakan rekursi. Contoh#include<iostream&
