Kā atrast virknē visbiežāk sastopamo rakstzīmi

Stīgas ir ļoti svarīga tēma programmēšanas intervijās. Pirms intervijām ir prātīgi praktizēt dažas programmēšanas problēmas, kas koncentrētas uz virknēm. Šajā rakstā uzzināsiet, kā atrast virknē visbiežāk sastopamo rakstzīmi.

Piemēri, lai izprastu problēmu

1. piemērs: Ļaujiet dotajai virknei būt "Makeuseof". Raksts “e” dotajā virknē notiek 2 reizes, un visas pārējās rakstzīmes notiek tikai vienu reizi. Tādējādi rakstzīmei “e” dotajā virknē ir visaugstākā frekvence.

2. piemērs: Ļaujiet dotajai virknei būt "Viņa redz sieru". Raksts “e” dotajā virknē sastopams 6 reizes, bet visas pārējās rakstzīmes - mazāk nekā 6 reizes. Tādējādi rakstzīmei “e” dotajā virknē ir visaugstākā frekvence.

Pieeja, lai atrastu virknē visbiežāk sastopamo rakstzīmi

Jaukšanas tehnika ir visefektīvākais veids, kā atrast rakstzīmi, kurai virknē ir visaugstākā frekvence. Šajā tehnikā virkne tiek šķērsota, un katrs virknes raksturs tiek sajaukts ASCII rakstzīmju masīvā.

Ļaujiet ievades virknei būt “Makeuseof”, katra šīs virknes rakstzīme tiek jaukta šādi:

frekvence ['M'] = 1

frekvence ['a] = 1

frekvence ['k'] = 1

frekvence ['e'] = 2

frekvence ['u'] = 1

frekvence ['s'] = 1

frekvence ['o'] = 1

frekvence ['f'] = 1

Tiek atgriezts frekvences masīva maksimālās vērtības indekss. Šeit 2 ir augstākā vērtība, tāpēc tiek atgriezta “e”.

C ++ programma, lai atrastu rakstzīmi ar visaugstāko frekvenci

Zemāk ir programma C ++, lai atrastu rakstzīmi ar visaugstāko virknes virkni:

Saistīts: Kā saskaitīt dotās rakstzīmes gadījumus virknē

// C ++ programma, lai atrastu rakstzīmi
// virknē ir visaugstākā frekvence
# iekļaut 
# iekļaut 
#define ASCII_SIZE 256
izmantojot nosaukumvietu std;
char maxFrequencyChar (virkne str)
{
// Masīvs katras rakstzīmes biežuma glabāšanai
// Inicializēja katras rakstzīmes biežumu kā 0
int frekvence [ASCII_SIZE] = {0};
// Ievades virknes garuma atrašana
int lenOfStr = str.length ();
// Inicializējiet mainīgo maxFrequency
int maxFrekvence = -1;
// Inicializējiet mainīgo maxFrequencyChar
char maxFrequencyChar;
// Pārvietošanās un uzturēšana
// katras rakstzīmes biežums
par (int i = 0; i {
frekvence [str [i]] ++;
ja (maxFrequency {
maxFrequency = frekvence [str [i]];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Vadītāja kods
int main ()
{
string str1 = "Kura ragana ir kura?";
cout << "str1:" << str1 << endl;
cout << "Augstākās frekvences raksturs ir:" << maxFrequencyChar (str1) << endl;
string str2 = "Viņš iemeta trīs soda metienus";
cout << "str2:" << str2 << endl;
cout << "Augstākās frekvences raksturs ir:" << maxFrequencyChar (str2) << endl;
string str3 = "Edijs to rediģēja";
cout << "str3:" << str3 << endl;
cout << "Augstākās frekvences raksturs ir:" << maxFrequencyChar (str3) << endl;
virkne str4 = "Makeuseof";
cout << "str4:" << str4 << endl;
cout << "Augstākās frekvences raksturs ir:" << maxFrequencyChar (str4) << endl;
string str5 = "Viņa redz sieru";
cout << "str5:" << str5 << endl;
cout << "Augstākās frekvences raksturs ir:" << maxFrequencyChar (str5) << endl;
}

Izeja:

str1: kura ragana ir kura?
Augstākās frekvences raksturs ir: h
str2: Viņš iemeta trīs soda metienus
Augstākās frekvences raksturs ir: e
str3: Edijs to rediģēja
Augstākās frekvences raksturs ir: d
4. str.: lietojums
Augstākās frekvences raksturs ir: e
str5: Viņa redz sieru
Augstākās frekvences raksturs ir: e

Python programma, lai atrastu rakstzīmi ar visaugstāko frekvenci

Zemāk ir programma Python, lai atrastu rakstzīmi ar visaugstāko virknes virkni:

Saistīts: Kā mainīt virkni C ++, Python un JavaScript

# Python programma, lai atrastu rakstzīmi
# virknē ir visaugstākā frekvence
ASCII_SIZE = 256
def maxFrequencyChar (str):
# Masīvs, lai saglabātu katras rakstzīmes biežumu
# Inicializēja katras rakstzīmes biežumu kā 0
biežums = [0] * ASCII_SIZE
# Inicializējiet mainīgo maxFrequency
maxFrekvence = -1
# Inicializējiet mainīgo maxFrequencyChar
maxFrequencyChar = ""
# Pārvietošanās un uzturēšana
# katras rakstzīmes biežums
priekš i str:
frekvence [ord (i)] + = 1
priekš i str:
ja maxFrequency maxFrequency = frekvence [ord (i)]
maxFrequencyChar = i
return maxFrequencyChar
# Vadītāja kods
str1 = "Kura ragana ir kura?"
drukāt ("str1:", str1)
print ("Augstākās frekvences rakstzīme ir:", maxFrequencyChar (str1))
str2 = "Viņš iemeta trīs soda metienus"
drukāt ("str2:", str2)
print ("Augstākās frekvences rakstzīme ir:", maxFrequencyChar (str2))
str3 = "Edijs to rediģēja"
drukāt ("str3:", str3)
print ("Augstākās frekvences rakstzīme ir:", maxFrequencyChar (str3))
str4 = "Izlietojums"
drukāt ("str4:", str4)
print ("Augstākās frekvences rakstzīme ir:", maxFrequencyChar (str4))
str5 = "Viņa redz sieru"
drukāt ("str5:", str5)
print ("Augstākās frekvences rakstzīme ir:", maxFrequencyChar (str5))

Izeja:

str1: kura ragana ir kura?
Augstākās frekvences raksturs ir: h
str2: Viņš iemeta trīs soda metienus
Augstākās frekvences raksturs ir: e
str3: Edijs to rediģēja
Augstākās frekvences raksturs ir: d
4. str.: lietojums
Augstākās frekvences raksturs ir: e
str5: Viņa redz sieru
Augstākās frekvences raksturs ir: e

C programma, lai atrastu rakstzīmi ar visaugstāko frekvenci

Zemāk ir C programma, lai atrastu rakstzīmi ar visaugstāko virknes virkni:

Saistīts: Kā atrast patskaņus, līdzskaņus, ciparus un īpašās rakstzīmes virknē

// C programma, lai atrastu rakstzīmi
// virknē ir visaugstākā frekvence
# iekļaut 
# iekļaut 
#define ASCII_SIZE 256
izmantojot nosaukumvietu std;
char maxFrequencyChar (char * str)
{
// Masīvs katras rakstzīmes biežuma glabāšanai
// Inicializēja katras rakstzīmes biežumu kā 0
int frekvence [ASCII_SIZE] = {0};
// Ievades virknes garuma atrašana
int lenOfStr = strlen (str);
// Inicializējiet mainīgo maxFrequency
int maxFrekvence = 0;
// Inicializējiet mainīgo maxFrequencyChar
char maxFrequencyChar;
// Pārvietošanās un uzturēšana
// katras rakstzīmes biežums
par (int i = 0; i {
frekvence [str [i]] ++;
ja (maxFrequency {
maxFrequency = frekvence [str [i]];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Vadītāja kods
int main ()
{
char str1 [] = "Kura ir ragana?";
printf ("str1:% s", str1);
printf ("Augstākās frekvences raksturs ir:% c \ ⁠n", maxFrequencyChar (str1));
char str2 [] = "Viņš iemeta trīs soda metienus";
printf ("str2:% s", str2);
printf ("Augstākās frekvences raksturs ir:% c \ ⁠n", maxFrequencyChar (str2));
char str3 [] = "Edijs to rediģēja";
printf ("str3:% s", str3);
printf ("Augstākās frekvences rakstzīme ir:% c \ ⁠n", maxFrequencyChar (str3));
char str4 [] = "Izlietojums";
printf ("str4:% s", str4);
printf ("Augstākās frekvences raksturs ir:% c \ ⁠n", maxFrequencyChar (str4));
char str5 [] = "Viņa redz sieru";
printf ("str1:% s", str5);
printf ("Augstākās frekvences raksturs ir:% c \ ⁠n", maxFrequencyChar (str5));
}

Izeja:

str1: kura ragana ir kura?
Augstākās frekvences raksturs ir: h
str2: Viņš iemeta trīs soda metienus
Augstākās frekvences raksturs ir: e
str3: Edijs to rediģēja
Augstākās frekvences raksturs ir: d
4. str.: lietojums
Augstākās frekvences raksturs ir: e
str5: Viņa redz sieru
Augstākās frekvences raksturs ir: e

JavaScript programma, lai atrastu rakstzīmi ar visaugstāko frekvenci

Zemāk ir JavaScript programma, lai atrastu rakstzīmi ar visaugstāko virknes virkni:

// JavaScript programma, lai atrastu rakstzīmi
// virknē ir visaugstākā frekvence
ļaujiet ASCII_SIZE = 256;
funkcija maxFrequencyChar (str)
{
// Masīvs katras rakstzīmes biežuma glabāšanai
// Inicializēja katras rakstzīmes biežumu kā 0
ļaujiet frekvencei = jauns masīvs (ASCII_SIZE);
par (lai i = 0; i {
frekvence [i] = 0;
}
// Ievades virknes garuma atrašana
ļaujiet lenOfStr = str.length;
par (lai i = 0; i {
frekvence [str [i] .charCodeAt (0)] + = 1;
}
// Inicializējiet mainīgo maxFrequency
ļaujiet maxFrekvence = -1;
// Inicializējiet mainīgo maxFrequencyChar
ļaujiet maxFrequencyChar = "";
// Pārvietošanās un uzturēšana
// katras rakstzīmes biežums
par (lai i = 0; i {
ja (maxFrequency {
maxFrequency = frekvence [str [i] .charCodeAt (0)];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Vadītāja kods
ļaujiet str1 = "kura ragana ir kura?";
document.write ("str1:" + str1 + "
");
document.write ("Augstākās frekvences raksturs ir:" + maxFrequencyChar (str1) + "
")
let str2 = "Viņš iemeta trīs soda metienus";
document.write ("str2:" + str2 + "
");
document.write ("Augstākā frekvence ir:" + maxFrequencyChar (str2) + "
")
let str3 = "Edijs to rediģēja";
document.write ("str3:" + str3 + "
");
document.write ("Augstākās frekvences rakstzīme ir:" + maxFrequencyChar (str3) + "
")
ļaujiet str4 = "Makeuseof";
document.write ("str4:" + str4 + "
");
document.write ("Augstākās frekvences raksturs ir:" + maxFrequencyChar (str4) + "
")
let str5 = "Viņa redz sieru";
document.write ("str5:" + str5 + "
");
document.write ("Augstākā frekvence ir:" + maxFrequencyChar (str5) + "
")

Izeja:

str1: kura ragana ir kura?
Augstākās frekvences raksturs ir: h
str2: Viņš iemeta trīs soda metienus
Augstākās frekvences raksturs ir: e
str3: Edijs to rediģēja
Augstākās frekvences raksturs ir: d
4. str.: lietojums
Augstākās frekvences raksturs ir: e
str5: Viņa redz sieru
Augstākās frekvences raksturs ir: e

Analizējiet laika un telpas sarežģītību

Laika sarežģītība maxFrequencyChar () funkcija ir O (n). Kosmosa sarežģītība maxFrequencyChar () funkcija ir O (1) kā fiksēta telpa (Hash masīvs). Tas nav atkarīgs no ievades virknes lieluma.

Big-O apzīmējums dod jums iespēju aprēķināt, cik ilgs laiks būs nepieciešams, lai palaistu kodu. Tas ir viens no vissvarīgākajiem algoritmu analīzes jēdzieniem. Ja esat programmētājs, jums jāzina par Big-O notāciju.

Yuvraj Chandra (30 raksti publicēti)

Yuvraj ir datorzinātņu bakalaura students Deli universitātē, Indijā. Viņš aizrauj pilnas skursteņa tīmekļa izstrādi. Kad viņš neraksta, viņš pēta dažādu tehnoloģiju dziļumu.

Vairāk no Yuvraj Chandra