Bilangan subrentetan dengan bilangan huruf kecil dan huruf besar yang sama

Dalam masalah ini, kita perlu mengira jumlah bilangan rentetan yang mengandungi bilangan huruf kecil dan huruf besar yang sama dalam rentetan yang diberikan. Cara naif untuk menyelesaikan masalah ini ialah mencari semua subrentetan dan mengira jumlah bilangan subrentetan dengan bilangan huruf kecil dan huruf besar yang sama.

Pendekatan yang cekap ialah menggunakan masalah penjumlahan subarray. Kita boleh menganggap aksara kecil sebagai -1 dan aksara besar sebagai +1, dan kita akan mempelajari kedua-dua cara untuk menyelesaikan masalah tersebut.

Pernyataan Masalah- Kami diberi rentetan str yang mengandungi huruf kecil dan huruf besar abjad. Kita perlu mengira jumlah bilangan subrentetan yang mengandungi bilangan huruf kecil dan huruf besar yang sama.

Contoh

Input– str = ‘TutOR’

Output– 4

Penjelasan–Kita boleh mendapatkan 4 subrentetan, iaitu 'Tu', 'TutO', 'tO' dan 'utOR', yang mengandungi bilangan huruf kecil dan huruf besar yang sama

Input– str = ‘abcd’

Output– 0

Penjelasan– Kami tidak boleh mendapatkan sebarang subrentetan yang mengandungi aksara kecil dan huruf besar yang sama kerana rentetan tersebut hanya mengandungi aksara kecil

Input– str = 'XYz'

Output– 1

Penjelasan- Kami hanya boleh mendapatkan subrentetan 'Yz'.

Kaedah 1

Ini adalah cara naif untuk menyelesaikan masalah. Kami akan menggunakan 3 gelung bersarang untuk mencari semua subrentetan rentetan yang diberikan. Kami akan menyemak sama ada setiap subrentetan mengandungi bilangan huruf kecil dan huruf besar yang sama. Jika ya, kami menambah kiraan sebanyak 1.

Algoritma

• Tentukan pembolehubah 'cnt' dan mulakannya kepada sifar.

• Gunakan gelung for untuk melintasi rentetan

• Dalam gelung, tentukan pembolehubah 'huruf besar' dan 'huruf kecil' dan mulakannya dengan sifar

• Tambah satu lagi gelung bersarang dalam kod anda untuk mengulang rentetan bermula dari indeks ke-i. Dengan cara ini, kita boleh mendapatkan subrentetan daripada indeks ke-i ke indeks ke-j

• Dalam gelung bersarang, jika aksara adalah huruf besar, naikkan nilai pembolehubah huruf besar sebanyak 1. Jika tidak, tingkatkan nilai pembolehubah huruf kecil sebanyak 1.

• Jika nilai pembolehubah 'huruf besar' dan 'huruf kecil' adalah sama, naikkan nilai 'cnt' sebanyak 1.

• Kembalikan nilai 'cnt'.

Contoh

Contoh

#include  using namespace std; // function to find the total number of substrings that have an equal number of lowercase and uppercase characters int totalSubStrings(string &str, int N){ // variable to store the count. int cnt = 0; for (int i = 0; i < str.length(); i++){ // variable to store the count of upper and lower case characters int upperCase = 0; int lowerCase = 0; for (int j = i; j < str.length(); j++){ // If the character is in uppercase, then increment upperCase if (str[j] >= 'A' && str[j] <= 'Z') upperCase++; else lowerCase++; // If the count of uppercase and lowercase characters is equal, then increment cnt if (upperCase == lowerCase) cnt++; } } return cnt; } int main(){ string str = "TutOR"; cout << "The total number of substrings that have equal lowercase and uppercase characters is " << totalSubStrings(str, str.length()); return 0; }

Output

The total number of substrings that have equal lowercase and uppercase characters is 4

Kerumitan masa - O(N^2) kerana kami menggunakan gelung bersarang untuk mencari semua subrentetan.

Kerumitan ruang - O(1) kerana kami menggunakan ruang malar.

Kaedah 2

Dalam kaedah ini, kami akan mengoptimumkan kod kaedah di atas untuk meningkatkan kerumitan masa penyelesaian. Kami menganggap aksara besar sebagai +1 dan aksara kecil sebagai -1. Selain itu, kami akan menggunakan struktur data peta untuk menyimpan kekerapan jumlah awalan. Jika kita mendapati bahawa jumlah awalan adalah sama dengan sifar, atau sama dengan mana-mana jumlah awalan yang disimpan dalam peta, kita boleh menambah nilai kiraan.

Algoritma

• Tentukan peta "jumlah" yang mengandungi integer sebagai pasangan nilai kunci.

• Takrifkan pembolehubah 'cnt' dan mulakannya kepada sifar untuk menyimpan jumlah bilangan subrentetan dengan huruf kecil dan huruf besar yang sama. Pada masa yang sama, tentukan 'semasa' pembolehubah untuk menyimpan awalan dan

• Mula melintasi tali. Jika aksara semasa ialah huruf besar, tambahkan pembolehubah 'semasa' sebanyak 1. Jika tidak, kurangkan aksara 'semasa' sebanyak 1.

• Jika nilai 'semasa' ialah 0, kita mencari subrentetan dan menambah nilai 'cnt' sebanyak 1

• Semak sama ada peta mengandungi "semasa" sebagai kunci. Jika ya, dapatkan nilainya dan tambahkannya pada pembolehubah "cnt".

• Tingkatkan nilai kekunci "semasa" dalam peta sebanyak 1.

Contoh

Contoh

Untuk memahami masalah dengan lebih baik. Mari kita nyahpepijat input contoh, iaitu 'TutOR'.

Jadi, apabila kita mula mengulang rentetan, nilai 'semasa' akan menjadi 0 pada indeks pertama. Jadi, tingkatkan nilai 'cnt' sebanyak 1. Sekali lagi, pada indeks ketiga ia akan pergi ke sifar. Jadi, naikkan nilai 'cnt' sebanyak 1 menjadi 2. Kami juga mendapat 0 sebelum ini, jadi ia hadir dalam peta dan kami perlu menambah nilai itu kepada 'cnt'. Jadi, ia akan menjadi 3.

Apabila kita mencapai indeks ke-4, nilai pembolehubah 'semasa' akan menjadi 1 dan kita mendapatnya semula seperti yang kita perolehi pada indeks ke-0. Jadi tambah '1' kepada 'cnt'.

Logik asas ialah jika 'semasa' ialah 0, kita mendapat subrentetan. Jika kita mendapat nilai 'semasa' sekali lagi, kita boleh mendapatkan rentetan antara dua indeks kerana 'semasa - semasa' adalah sifar.

#include  #include  using namespace std; // function to find the total number of substrings that have an equal number of lowercase and uppercase characters int totalSubStrings(string &str, int N){ // map to store the frequency of sums generated by the difference in the count of lowercase and uppercase characters unordered_map sum; // to store the count of substrings that have an equal number of lowercase and uppercase characters int cnt = 0; // current sum int current = 0; for (int i = 0; i < N; i++){ // If the character is uppercase, then increment the current value if (str[i] >= 'A' and str[i] <= 'Z'){ current++; } // Otherwise, decrement the current value else current--; // If the current value is 0, then a substring is found. So, increment the count by 1 if (current == 0) cnt++; // If the current value exists in the map, then update the cnt by adding the frequency of the current value if (sum[current]){ cnt += (sum[current]); } // Increment the frequency of the current value in the map sum[current]++; } return cnt; } int main(){ string str = "TutOR"; cout << "The total number of substrings that have equal lowercase and uppercase characters is " << totalSubStrings(str, str.length()); return 0; }

Output

The total number of substrings that have equal lowercase and uppercase characters is 4

Kerumitan masa- O(N) memandangkan kami hanya mengulangi rentetan sekali sahaja.

Kerumitan ruang– O(N) kerana kami menggunakan peta untuk menyimpan jumlah awalan. Dalam kes yang paling teruk, apabila rentetan mengandungi semua huruf kecil atau huruf besar, kita memerlukan ruang O(N).

Kami belajar menggunakan dua kaedah berbeza untuk menyelesaikan masalah di atas. Kaedah pertama menggunakan gelung bersarang untuk menyemak semua rentetan, manakala kaedah kedua lebih cekap daripada yang pertama dari segi kerumitan masa, tetapi mengambil lebih banyak ruang.

Atas ialah kandungan terperinci Bilangan subrentetan dengan bilangan huruf kecil dan huruf besar yang sama. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!