Kaip rasti dažniausiai pasitaikančią eilutės veikėją

Stygos yra labai svarbi programavimo interviu tema. Protinga prieš interviu praktikuoti kai kurias programavimo problemas, nukreiptas į stygas. Šiame straipsnyje sužinosite, kaip surasti dažniausiai pasitaikančią eilutės simbolį.

Problemos supratimo pavyzdžiai

1 pavyzdys: Tegu duota eilutė yra „Makeuseof“. Simbolis „e“ nurodytoje eilutėje atsiranda 2 kartus, o visi kiti simboliai - tik vieną kartą. Taigi simbolis „e“ turi didžiausią dažnį pateiktoje eilutėje.

2 pavyzdys: Tegu duota eilutė yra „Ji mato sūrį“. Simbolis „e“ nurodytoje eilutėje yra 6 kartus, o visi kiti simboliai - mažiau nei 6 kartus. Taigi simbolis „e“ turi didžiausią dažnį pateiktoje eilutėje.

Požiūris į dažniausiai pasitaikančio veikėjo simbolio paiešką

Maišymo technika yra efektyviausias būdas rasti simbolį, kurio eilutėje dažnis yra didžiausias. Taikant šią techniką, einama eilutė ir kiekvienas eilutės simbolis suskaidomas į ASCII simbolių masyvą.

Tegul įvesties eilutė yra „Makeuseof“, kiekvienas šios eilutės simbolis maišomas taip:

dažnis ['M'] = 1

dažnis ['a] = 1

dažnis ['k'] = 1

dažnis ['e'] = 2

dažnis ['u'] = 1

dažnis ['s'] = 1

dažnis ['o'] = 1

dažnis ['f'] = 1

Grąžinamas dažnio masyvo didžiausios vertės indeksas. Čia 2 yra didžiausia vertė, todėl grąžinama „e“.

„C ++“ programa, skirta rasti simbolį, kurio dažnis yra didžiausias

Žemiau pateikiama C ++ programa, skirta rasti simbolį, kurio eilutėje yra didžiausias dažnis:

Susijęs: Kaip suskaičiuoti duoto simbolio atsiradimą eilutėje

// C ++ programa, norėdama rasti simbolį
// turintis didžiausią dažnį eilutėje
# įtraukti 
# įtraukti 
#define ASCII_SIZE 256
naudojant vardų sritį std;
char maxFrequencyChar (eilutė str)
{
// Masyvas kiekvienam simboliui išsaugoti
// Inicijavo kiekvieno simbolio dažnį kaip 0
int dažnis [ASCII_SIZE] = {0};
// Įvesties eilutės ilgio radimas
int lenOfStr = str.length ();
// Inicijuoti kintamąjį maxFrequency
int maxDažnis = -1;
// Inicijuoti kintamąjį maxFrequencyChar
char maxFrequencyChar;
// Kelionė ir priežiūra
// kiekvieno simbolio dažnis
už (int i = 0; i {
dažnis [str [i]] ++;
jei (maxFrequency {
maxFrequency = dažnis [str [i]];
maxFrequencyChar = str [i];
}
}
grąžinti maxFrequencyChar;
}
// Vairuotojo kodas
int main ()
{
string str1 = "Kuri ragana yra kuri?";
cout << "str1:" << str1 << endl;
cout << "Aukščiausio dažnio simbolis yra:" << maxFrequencyChar (str1) << endl;
string str2 = "Jis metė tris baudos metimus";
cout << "str2:" << str2 << endl;
cout << "Aukščiausio dažnio simbolis yra:" << maxFrequencyChar (str2) << endl;
string str3 = "Edis redagavo";
cout << "str3:" << str3 << endl;
cout << "Aukščiausio dažnio simbolis:" << maxFrequencyChar (str3) << endl;
eilutė str4 = "Makeuseof";
cout << "str4:" << str4 << endl;
cout << "Aukščiausio dažnio simbolis yra:" << maxFrequencyChar (str4) << endl;
string str5 = "Ji mato sūrį";
cout << "str5:" << str5 << endl;
cout << "Aukščiausio dažnio simbolis yra:" << maxFrequencyChar (str5) << endl;
}

Išvestis:

str1: Kuri ragana yra kuri?
Aukščiausio dažnio simbolis yra: h
str2: Jis metė tris baudos metimus
Aukščiausio dažnio simbolis yra: e
str3: Edis redagavo
Aukščiausio dažnio simbolis yra: d
str4: Makiažas
Aukščiausio dažnio simbolis yra: e
str5: Ji mato sūrį
Aukščiausio dažnio simbolis yra: e

„Python“ programa, skirta rasti simbolį, kurio dažnis yra didžiausias

Žemiau yra „Python“ programa, skirta rasti simbolį, kurio eilutėje yra didžiausias dažnis:

Susijęs: Kaip pakeisti eilutę C ++, Python ir JavaScript

# Python programa, norėdama rasti simbolį
# turintis didžiausią eilutės dažnį
ASCII_SIZE = 256
def maxFrequencyChar (str):
# Masyvas kiekvienam simboliui išsaugoti
# Inicijavo kiekvieno simbolio dažnį kaip 0
dažnis = [0] * ASCII_SIZE
# Inicijuoti kintamąjį „maxFrequency“
maxFrequency = -1
# Inicializuoti kintamąjį maxFrequencyChar
maxFrequencyChar = "
# Kelionė ir priežiūra
# kiekvieno simbolio dažnis
už i str:
dažnis [ord (i)] + = 1
už i str:
jei maxFrequency maxFrequency = dažnis [ord (i)]
maxFrequencyChar = i
grąžinti maxFrequencyChar
# Vairuotojo kodas
str1 = "Kuri ragana yra kuri?"
spausdinti ("str1:", str1)
spausdinti ("Aukščiausio dažnio simbolis yra:", maxFrequencyChar (str1))
str2 = "Jis metė tris baudos metimus"
spausdinti ("str2:", str2)
spausdinti ("Aukščiausio dažnio simbolis yra:", maxFrequencyChar (str2))
str3 = "Edis redagavo"
spausdinti ("str3:", str3)
spausdinti ("Aukščiausio dažnio simbolis yra:", maxFrequencyChar (str3))
str4 = "Makiažas"
spausdinti ("str4:", str4)
spausdinti ("Aukščiausio dažnio simbolis yra:", maxFrequencyChar (str4))
str5 = "Ji mato sūrį"
spausdinti ("str5:", str5)
spausdinti ("Aukščiausio dažnio simbolis yra:", maxFrequencyChar (str5))

Išvestis:

str1: Kuri ragana yra kuri?
Aukščiausio dažnio simbolis yra: h
str2: Jis metė tris baudos metimus
Aukščiausio dažnio simbolis yra: e
str3: Edis redagavo
Aukščiausio dažnio simbolis yra: d
str4: Makiažas
Aukščiausio dažnio simbolis yra: e
str5: Ji mato sūrį
Aukščiausio dažnio simbolis yra: e

C programa, skirta surasti simbolį, kurio dažnis yra didžiausias

Žemiau yra C programa, skirta rasti simbolį, kurio eilutėje yra didžiausias dažnis:

Susijęs: Kaip rasti eilutėje balsius, priebalsius, skaitmenis ir specialiuosius simbolius

// C programa, norėdama rasti simbolį
// turintis didžiausią dažnį eilutėje
# įtraukti 
# įtraukti 
#define ASCII_SIZE 256
naudojant vardų sritį std;
char maxFrequencyChar (char * str)
{
// Masyvas kiekvienam simboliui išsaugoti
// Inicijavo kiekvieno simbolio dažnį kaip 0
int dažnis [ASCII_SIZE] = {0};
// Įvesties eilutės ilgio radimas
int lenOfStr = strlen (str);
// Inicijuoti kintamąjį maxFrequency
int maxDažnis = 0;
// Inicijuoti kintamąjį maxFrequencyChar
char maxFrequencyChar;
// Kelionė ir priežiūra
// kiekvieno simbolio dažnis
už (int i = 0; i {
dažnis [str [i]] ++;
jei (maxFrequency {
maxFrequency = dažnis [str [i]];
maxFrequencyChar = str [i];
}
}
grąžinti maxFrequencyChar;
}
// Vairuotojo kodas
int main ()
{
char str1 [] = "Kuri ragana yra kuri?";
printf ("str1:% s", str1);
printf ("Aukščiausio dažnio simbolis yra:% c \ ⁠n", maxFrequencyChar (str1));
char str2 [] = "Jis metė tris baudos metimus";
printf ("str2:% s", str2);
printf ("Aukščiausio dažnio simbolis yra:% c \ ⁠n", maxFrequencyChar (str2));
char str3 [] = "Edis redagavo";
printf ("str3:% s", str3);
printf ("Aukščiausio dažnio simbolis yra:% c \ ⁠n", maxFrequencyChar (str3));
char str4 [] = "Makiažas";
printf ("str4:% s", str4);
printf ("Aukščiausio dažnio simbolis yra:% c \ ⁠n", maxFrequencyChar (str4));
char str5 [] = "Ji mato sūrį";
printf ("str1:% s", str5);
printf ("Aukščiausio dažnio simbolis yra:% c \ ⁠n", maxFrequencyChar (str5));
}

Išvestis:

str1: Kuri ragana yra kuri?
Aukščiausio dažnio simbolis yra: h
str2: Jis metė tris baudos metimus
Aukščiausio dažnio simbolis yra: e
str3: Edis redagavo
Aukščiausio dažnio simbolis yra: d
str4: Makiažas
Aukščiausio dažnio simbolis yra: e
str5: Ji mato sūrį
Aukščiausio dažnio simbolis yra: e

„JavaScript“ programa, skirta surasti simbolį, kurio dažnis yra didžiausias

Žemiau yra „JavaScript“ programa, skirta rasti simbolį, kurio eilutėje yra didžiausias dažnis:

// „JavaScript“ programa, norėdama rasti simbolį
// turintis didžiausią dažnį eilutėje
tegul ASCII_SIZE = 256;
funkcija maxFrequencyChar (str)
{
// Masyvas kiekvienam simboliui išsaugoti
// Inicijavo kiekvieno simbolio dažnį kaip 0
tegul dažnis = naujas masyvas (ASCII_SIZE);
už (tegul i = 0; i {
dažnis [i] = 0;
}
// Įvesties eilutės ilgio radimas
tegul lenOfStr = str.length;
už (tegul i = 0; i {
dažnis [str [i] .charCodeAt (0)] + = 1;
}
// Inicijuoti kintamąjį maxFrequency
tegul maxFrequency = -1;
// Inicijuoti kintamąjį maxFrequencyChar
tegul maxFrequencyChar = "";
// Kelionė ir priežiūra
// kiekvieno simbolio dažnis
už (tegul i = 0; i {
jei (maxFrequency {
maxFrequency = dažnis [str [i] .charCodeAt (0)];
maxFrequencyChar = str [i];
}
}
grąžinti maxFrequencyChar;
}
// Vairuotojo kodas
tegul str1 = "Kuri ragana yra kuri?";
document.write ("str1:" + str1 + "
");
document.write ("Aukščiausio dažnio simbolis yra:" + maxFrequencyChar (str1) + "
")
tegul str2 = "Jis metė tris baudos metimus";
document.write ("str2:" + str2 + "
");
document.write ("Aukščiausio dažnio simbolis yra:" + maxFrequencyChar (str2) + "
")
tegul str3 = "Edis redagavo";
document.write ("str3:" + str3 + "
");
document.write ("Aukščiausio dažnio simbolis yra:" + maxFrequencyChar (str3) + "
")
tegul str4 = "Makeuseof";
document.write ("str4:" + str4 + "
");
document.write ("Aukščiausio dažnio simbolis yra:" + maxFrequencyChar (str4) + "
")
tegul str5 = "Ji mato sūrį";
document.write ("str5:" + str5 + "
");
document.write ("Aukščiausio dažnio simbolis yra:" + maxFrequencyChar (str5) + "
")

Išvestis:

str1: Kuri ragana yra kuri?
Aukščiausio dažnio simbolis yra: h
str2: Jis metė tris baudos metimus
Aukščiausio dažnio simbolis yra: e
str3: Edis redagavo
Aukščiausio dažnio simbolis yra: d
str4: Makiažas
Aukščiausio dažnio simbolis yra: e
str5: Ji mato sūrį
Aukščiausio dažnio simbolis yra: e

Išanalizuokite laiko ir erdvės sudėtingumą

Laiko sudėtingumas maxFrequencyChar () funkcija yra O (n). Kosmoso sudėtingumas maxFrequencyChar () funkcija yra O (1) kaip fiksuota erdvė (Hash masyvas). Tai nepriklauso nuo įvesties eilutės dydžio.

„Big-O“ žymėjimas suteikia galimybę apskaičiuoti, per kiek laiko reikės paleisti kodą. Tai viena iš svarbiausių algoritmų analizės sąvokų. Jei esate programuotojas, turite žinoti apie „Big-O Notation“.

Yuvraj Chandra (Paskelbta 30 straipsnių)

Yuvraj yra kompiuterių bakalauro studentas Delio universitete, Indijoje. Jis aistringai domisi „Full Stack“ interneto plėtra. Kai nerašo, jis tyrinėja įvairių technologijų gylį.

Daugiau iš „Yuvraj Chandra“