Cari nilai selepas mengalih keluar N aksara daripada rentetan 'S' dalam operasi N di bawah kekangan yang diberikan

Apakah spesifikasi penggunaan rentetan?

Selesaikan cabaran khusus yang melibatkan rentetan S yang diberikan. Rentetan S mengandungi hanya huruf kecil Inggeris dan kekangan tertentu mesti diikuti apabila mengalih keluar aksara.

Kekangan yang diberikan ialah -

• Terdapat huruf kecil Inggeris dalam rentetan S

• Hanya aksara yang muncul beberapa kali dalam rentetan boleh dipadamkan.

• Hanya aksara berturut-turut boleh dipadamkan. Langkah berikut boleh digunakan untuk mengalih keluar aksara daripada rentetan S -

• Cari semua aksara yang muncul berbilang kali semasa mengulangi rentetan S. Cari semua kejadian berturut-turut bagi aksara dengan mengulangi rentetan S sekali lagi untuk setiap aksara.

• Jika bilangan kejadian berturut-turut aksara lebih besar daripada atau sama dengan bilangan lelaran, padamkan N kejadian pertama aksara.

• Teruskan langkah 2 dan 3 sehingga semua lelaran selesai.

Akhir sekali, dengan mengembalikan rentetan akhir S, anda boleh mencari nilai rentetan selepas mengalih keluar N aksara selepas N operasi.

Tatabahasa

Topik ini ialah soalan pengekodan yang melibatkan memanipulasi rentetan tertentu dengan melakukan beberapa operasi padanya. Pada setiap operasi, aksara yang paling biasa dalam rentetan dialih keluar dan kekerapan setiap aksara yang tinggal dikemas kini. Selepas melakukan operasi ini N kali, nilai akhir rentetan dikira dengan mengkuadangkan kekerapan setiap aksara yang tinggal dan menjumlahkan. Matlamat masalah ini adalah untuk menulis program yang mengambil rentetan dan nombor N sebagai input dan mengeluarkan nilai akhir rentetan selepas melakukan operasi N mengikut kekangan yang diberikan.

Berikut ialah sintaks fungsi yang mencari nilai selepas N operasi untuk mengalih keluar N aksara rentetan S di bawah kekangan yang diberikan -

int findvalueafterNoperations(int n, string s) {
   int len = s.length();
   int freq[26] = {0};
   for (int i = 0; i < len; i++) {
      freq[s[i] - 'a']++;
   }
   sort(freq, freq + 26, greater<int>());
   for (int i = 0; i < n; i++) {
      freq[0]--; 
      sort(freq, freq + 26, greater<int>()); 
   }
   int value = 0;
   for (int i = 0; i < 26; i++) {
      value += freq[i] * freq[i];
   }
   return value;
}

Fungsi ini menerima dua parameter -

• n - integer yang mewakili bilangan operasi yang perlu dilakukan.

• s - rentetan yang mewakili rentetan input.

Fungsi pertama mengira kekerapan setiap aksara dalam rentetan input menggunakan tatasusunan. Tatasusunan frekuensi ini kemudiannya diisih dalam susunan menurun dan dilakukan N kali, di mana dalam setiap operasi kekerapan aksara yang paling biasa dikurangkan dan tatasusunan frekuensi diisih semula.

Akhir sekali, fungsi mengira nilai rentetan dengan menjumlahkan kekerapan kuasa dua bagi setiap aksara dalam tatasusunan frekuensi yang diisih dan mengembalikannya sebagai integer.

Algoritma

Selepas proses penyingkiran aksara N, algoritma mengira nilai rentetan di bawah kekangan berikut. Input terdiri daripada nombor N dan rentetan S.

• Langkah 1 - Gunakan tatasusunan untuk menentukan kekerapan setiap aksara dalam rentetan input.

• Langkah 2 - Isih tatasusunan frekuensi ini dalam tertib menurun.

• Langkah 3 - Lakukan operasi N, setiap operasi akan mengurangkan kekerapan aksara yang paling kerap dalam tatasusunan frekuensi.

• Langkah 4 - Susun semula tatasusunan frekuensi.

• Langkah 5 - Tambahkan kekerapan kuasa dua bagi setiap aksara dalam tatasusunan frekuensi diisih untuk menentukan nilai rentetan.

• Langkah 6 - Selepas operasi N, nilai rentetan ialah hasil tambah kuasa duanya.

Teknik ini berfungsi kerana masalah memerlukan mengalih keluar aksara N daripada rentetan input S, iaitu seperti menjalankan operasi N di mana setiap operasi mengalih keluar aksara yang paling biasa dalam rentetan sekali. Disebabkan oleh kekangan tugas, kita sebenarnya tidak boleh mengalih keluar aksara daripada rentetan, jadi kita perlu mensimulasikan operasi ini dengan mengurangkan kekerapan aksara yang paling biasa dalam tatasusunan frekuensi dalam setiap operasi.

Kaedah untuk diikuti

Kaedah 1

Gunakan kod untuk memulakan rentetan sampel S dan pelbagai operasi N. Selepas setiap operasi dalam gelung, aksara awal yang lebih besar daripada aksara seterusnya dialih keluar. Jika tidak dipadamkan, aksara terakhir akan dipadamkan. Selepas semua operasi selesai, ia mencetak nilai akhir rentetan.

Di sini, kod mengandaikan bahawa N adalah kurang daripada atau sama dengan panjang rentetan S. Jika N lebih panjang daripada S, kod tidak akan berjalan seperti yang diharapkan.

Contoh 1

#include <iostream>
#include <string>
using namespace std;
int main(){
   string S = "abcdefg";
   int N = 3;
   for (int l = 1; l <= N; l++) {
      int p=0;
      while(p<S.length()- 1) {
         if(S[p]>S[p+1]) {
            S.erase(p, 1);
            break;
         }
         p++;
      }
      if(p==S.length()- 1) {
         S.erase(p, 1);
      }
   }
   cout<< S << endl;
   return 0 ;
}

Output

a b c d

Kaedah 2

Dalam kod ini, tatasusunan pertama kali digunakan untuk menentukan kekerapan setiap aksara dalam rentetan input. Seterusnya kami melakukan operasi N, mengurangkan kekerapan aksara yang paling biasa dalam setiap operasi, dan mengisih tatasusunan frekuensi sekali lagi. Seterusnya, kami mengisih tatasusunan frekuensi ini dalam tertib menurun.

Nilai rentetan akhirnya ditentukan dengan menambahkan kekerapan kuasa dua bagi setiap aksara dalam tatasusunan frekuensi yang diisih.

Contoh 2

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main(){
   // Given values
   int n = 3; 
   string s = "abcabc"; 
   int len = s.length();
   int freq[26] = {0};
   for (int i = 0; i < len; i++) {
      freq[s[i] - 'a']++;
   }
   sort(freq, freq + 26, greater<int>());
   for (int i = 0; i < n; i++) {
      freq[0]--; 
      sort(freq, freq + 26, greater<int>()); 
   }
   int value = 0;
   for (int i = 0; i < 26; i++) {
      value += freq[i] * freq[i];
   }
   cout << "Value of string after " << n << " operations: " << value << endl;
   return 0;
}

Output

Value of string after 3 operations: 3

Kesimpulan

Untuk meringkaskan, kita boleh menghapuskan N aksara daripada rentetan "S" di bawah kekangan di atas dengan menggunakan teknik langsung untuk mendapatkan nilai selepas operasi N. Mula-mula, mari kita mulakan tatasusunan kekerapan untuk menjejaki bilangan aksara dalam rentetan. Sebaik sahaja kita telah menghapuskan N aksara, kita boleh mengulangi proses mengalih keluar aksara dengan kiraan terbesar daripada tatasusunan frekuensi. Proses ini boleh diulang sebanyak N kali.

Dengan kaedah ini, kita boleh menentukan dengan cepat nilai rentetan "S" selepas operasi N (termasuk menghapuskan N aksara). Oleh kerana peringkat pengisihan dalam kaedah, kerumitan masa penyelesaian ini ialah O(N logN), yang boleh diterima untuk kebanyakan aplikasi praktikal.

Atas ialah kandungan terperinci Cari nilai selepas mengalih keluar N aksara daripada rentetan 'S' dalam operasi N di bawah kekangan yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!