Kuidas leida stringi kõige sagedamini esinev tegelane

Stringid on intervjuude programmeerimisel väga oluline teema. Mõistlik on enne intervjuusid harjutada mõnda stringidele keskendunud programmeerimisprobleemi. Sellest artiklist saate teada, kuidas leida stringi kõige sagedamini esinev märk.

Näited probleemi mõistmiseks

Näide 1: Olgu antud string "Makeuseof". Märk 'e' esineb antud stringis 2 korda ja kõik ülejäänud märgid esinevad ainult üks kord. Seega on märgil 'e' antud stringis kõige suurem sagedus.

Näide 2: Olgu antud string "Ta näeb juustu". Märk 'e' esineb antud stringis 6 korda ja kõik ülejäänud märgid esinevad vähem kui 6 korda. Seega on märgil 'e' antud stringis kõige suurem sagedus.

Lähenemine stringi kõige sagedamini esineva tegelase leidmiseks

Räsimistehnika on kõige tõhusam viis stringi kõrgeima sagedusega tegelase leidmiseks. Selles tehnikas läbitakse string ja stringi iga märk räsitakse ASCII tähemärkide massiiviks.

Olgu sisendstringiks "Makeuseof", selle stringi iga märk räsitakse järgmiselt:

sagedus ['M'] = 1

sagedus ['a] = 1

sagedus ['k'] = 1

sagedus ['e'] = 2

sagedus ['u'] = 1

sagedus ['s'] = 1

sagedus ['o'] = 1

sagedus ['f'] = 1

Tagastatakse sagedusmassiivi maksimaalse väärtuse indeks. Siin 2 on suurim väärtus, seetõttu tagastatakse 'e'.

C ++ programm kõrgeima sagedusega tegelase leidmiseks

Allpool on C ++ programm stringi kõrgeima sagedusega tähemärgi leidmiseks:

Seotud: Kuidas loendada stringis antud tegelase esinemisi

// C ++ programm märgi leidmiseks
// millel on stringi kõrgeim sagedus
# kaasata 
# kaasata 
#define ASCII_SIZE 256
nimeruumi kasutamine std;
char maxFrequencyChar (string str)
{
// Massiiv iga tähemärgi sageduse salvestamiseks
// Algatas iga märgi sageduseks 0
int sagedus [ASCII_SIZE] = {0};
// Sisendstringi pikkuse leidmine
int lenOfStr = str.pikkus ();
// Initsialiseeri muutuja maxFrequency
int maxSagedus = -1;
// Initsialiseeri muutuja maxFrequencyChar
char maxFrequencyChar;
//. Läbimine ja hooldamine
// iga tähemärgi sagedus
for (int i = 0; i {
sagedus [str [i]] ++;
kui (maxFrequency {
maxFrequency = sagedus [str [i]];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Juhi kood
int main ()
{
string str1 = "Milline nõid on milline?";
cout << "str1:" << str1 << endl;
cout << "Kõrgeim sagedusmärk on:" << maxFrequencyChar (str1) << endl;
string str2 = "Ta viskas kolm vabaviset";
cout << "str2:" << str2 << endl;
cout << "Kõrgeim sagedusmärk on:" << maxFrequencyChar (str2) << endl;
string str3 = "Eddie muutis seda";
cout << "str3:" << str3 << endl;
cout << "Kõrgeim sagedusmärk on:" << maxFrequencyChar (str3) << endl;
string str4 = "Makeuseof";
cout << "str4:" << str4 << endl;
cout << "Kõrgeim sagedusmärk on:" << maxFrequencyChar (str4) << endl;
string str5 = "Ta näeb juustu";
cout << "str5:" << str5 << endl;
cout << "Kõrgeim sagedusmärk on:" << maxFrequencyChar (str5) << endl;
}

Väljund:

str1: Milline nõid on milline?
Kõrgeima sagedusega märk on: h
str2: Ta viskas kolm vabaviset
Kõrgeim sagedusmärk on: e
str3: Eddie toimetas seda
Kõrgeima sagedusega märk on: d
str4: Kasutamine
Kõrgeim sagedusmärk on: e
str5: Ta näeb juustu
Kõrgeim sagedusmärk on: e

Pythoni programm kõrgeima sagedusega märgi leidmiseks

Allpool on programm Python, et leida stringis kõige suurema sagedusega märk:

Seotud: Stringi ümberpööramine C ++, Pythoni ja JavaScripti puhul

# Pythoni programm märgi leidmiseks
# millel on stringi kõrgeim sagedus
ASCII_SIZE = 256
def maxFrequencyChar (str):
# Massiiv iga tähemärgi sageduse salvestamiseks
# Algatas iga märgi sageduseks 0
sagedus = [0] * ASCII_SIZE
# Initsialiseeri muutuja maxFrequency
maxSagedus = -1
# Initsialiseeri muutuja maxFrequencyChar
maxFrequencyChar = ""
# Liikumine ja hooldamine
# tähemärgi sagedus
i jaoks str:
sagedus [ord (i)] + = 1
i jaoks str:
kui maxFrequency maxFrequency = sagedus [ord (i)]
maxFrequencyChar = i
tagastage maxFrequencyChar
# Juhi kood
str1 = "Milline nõid on milline?"
print ("str1:", str1)
print ("Kõrgeim sagedusmärk on:", maxFrequencyChar (str1))
str2 = "Ta viskas kolm vabaviset"
print ("str2:", str2)
print ("Kõrgeim sagedusmärk on:", maxFrequencyChar (str2))
str3 = "Eddie muutis seda"
print ("str3:", str3)
print ("Kõrgeim sagedusmärk on:", maxFrequencyChar (str3))
str4 = "Kasutamine"
print ("str4:", str4)
print ("Kõrgeim sagedusmärk on:", maxFrequencyChar (str4))
str5 = "Ta näeb juustu"
print ("str5:", str5)
print ("Kõrgeim sagedusmärk on:", maxFrequencyChar (str5))

Väljund:

str1: Milline nõid on milline?
Kõrgeima sagedusega märk on: h
str2: Ta viskas kolm vabaviset
Kõrgeim sagedusmärk on: e
str3: Eddie toimetas seda
Kõrgeima sagedusega märk on: d
str4: Kasutamine
Kõrgeim sagedusmärk on: e
str5: Ta näeb juustu
Kõrgeim sagedusmärk on: e

C Programm kõrgeima sagedusega tegelase leidmiseks

Allpool on C-programm, et leida stringi kõrgeima sagedusega tähemärk:

Seotud: Kuidas leida stringist täishäälikuid, kaashäälikuid, numbreid ja erimärke

// C programm märgi leidmiseks
// millel on stringi kõrgeim sagedus
# kaasata 
# kaasata 
#define ASCII_SIZE 256
nimeruumi kasutamine std;
char maxFrequencyChar (char * str)
{
// Massiiv iga tähemärgi sageduse salvestamiseks
// Algatas iga märgi sageduseks 0
int sagedus [ASCII_SIZE] = {0};
// Sisendstringi pikkuse leidmine
int lenOfStr = strlen (str);
// Initsialiseeri muutuja maxFrequency
int maxSagedus = 0;
// Initsialiseeri muutuja maxFrequencyChar
char maxFrequencyChar;
//. Läbimine ja hooldamine
// iga tähemärgi sagedus
for (int i = 0; i {
sagedus [str [i]] ++;
kui (maxFrequency {
maxFrequency = sagedus [str [i]];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Juhi kood
int main ()
{
char str1 [] = "Milline nõid on milline?";
printf ("str1:% s", str1);
printf ("Kõrgeim sagedusmärk on:% c \ ⁠n", maxFrequencyChar (str1));
char str2 [] = "Ta viskas kolm vabaviset";
printf ("str2:% s", str2);
printf ("Kõrgeim sagedusmärk on:% c \ ⁠n", maxFrequencyChar (str2));
char str3 [] = "Eddie muutis seda";
printf ("str3:% s", str3);
printf ("Kõrgeim sagedusmärk on:% c \ ⁠n", maxFrequencyChar (str3));
char str4 [] = "Makeuseof";
printf ("str4:% s", str4);
printf ("Kõrgeim sagedusmärk on:% c \ ⁠n", maxFrequencyChar (str4));
char str5 [] = "Ta näeb juustu";
printf ("str1:% s", str5);
printf ("Kõrgeim sagedusmärk on:% c \ ⁠n", maxFrequencyChar (str5));
}

Väljund:

str1: Milline nõid on milline?
Kõrgeima sagedusega märk on: h
str2: Ta viskas kolm vabaviset
Kõrgeim sagedusmärk on: e
str3: Eddie toimetas seda
Kõrgeima sagedusega märk on: d
str4: Kasutamine
Kõrgeim sagedusmärk on: e
str5: Ta näeb juustu
Kõrgeim sagedusmärk on: e

JavaScripti programm kõrgeima sagedusega tegelase leidmiseks

Allpool on JavaScripti programm stringi kõrgeima sagedusega märgi leidmiseks:

// JavaScripti programm märgi leidmiseks
// millel on stringi kõrgeim sagedus
olgu ASCII_SIZE = 256;
funktsioon maxFrequencyChar (str)
{
// Massiiv iga tähemärgi sageduse salvestamiseks
// Algatas iga märgi sageduseks 0
olgu sagedus = uus massiiv (ASCII_SIZE);
for (olgu i = 0; i {
sagedus [i] = 0;
}
// Sisendstringi pikkuse leidmine
olgu lenOfStr = str.pikkus;
for (olgu i = 0; i {
sagedus [str [i] .charCodeAt (0)] + = 1;
}
// Initsialiseeri muutuja maxFrequency
olgu maxFrequency = -1;
// Initsialiseeri muutuja maxFrequencyChar
olgu maxFrequencyChar = "";
//. Läbimine ja hooldamine
// iga tähemärgi sagedus
for (olgu i = 0; i {
kui (maxFrequency {
maxFrequency = sagedus [str [i] .charCodeAt (0)];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Juhi kood
olgu str1 = "Milline nõid on milline?";
document.write ("str1:" + str1 + "
");
document.write ("Kõrgeim sagedusmärk on:" + maxFrequencyChar (str1) + "
")
las str2 = "Ta viskas kolm vabaviset";
document.write ("str2:" + str2 + "
");
document.write ("Kõrgeim sagedusmärk on:" + maxFrequencyChar (str2) + "
")
las str3 = "Eddie muutis seda";
document.write ("str3:" + str3 + "
");
document.write ("Kõrgeim sagedusmärk on:" + maxFrequencyChar (str3) + "
")
olgu str4 = "Makeuseof";
document.write ("str4:" + str4 + "
");
document.write ("Kõrgeim sagedusmärk on:" + maxFrequencyChar (str4) + "
")
las str5 = "Ta näeb juustu";
document.write ("str5:" + str5 + "
");
document.write ("Kõrgeim sagedusmärk on:" + maxFrequencyChar (str5) + "
")

Väljund:

str1: Milline nõid on milline?
Kõrgeima sagedusega märk on: h
str2: Ta viskas kolm vabaviset
Kõrgeim sagedusmärk on: e
str3: Eddie toimetas seda
Kõrgeima sagedusega märk on: d
str4: Kasutamine
Kõrgeim sagedusmärk on: e
str5: Ta näeb juustu
Kõrgeim sagedusmärk on: e

Analüüsige aja ja ruumi keerukust

Programmi ajaline keerukus maxFrequencyChar () funktsioon on Peal). Kosmosesüsteemi keerukus maxFrequencyChar () funktsioon on O (1) kindla ruumina (Hash array). See ei sõltu sisendstringi suurusest.

Big-O tähistamine annab teile võimaluse arvutada, kui kaua kulub teie koodi käitamiseks. See on üks olulisemaid mõisteid algoritmide analüüsimiseks. Kui olete programmeerija, peate teadma Big-O Notationi kohta.

Yuvraj Chandra (30 artiklit on avaldatud)

Yuvraj on arvutiteaduse eriala üliõpilane Delhis, Indias. Ta on kirglik Full Stacki veebiarenduse vastu. Kui ta ei kirjuta, uurib ta erinevate tehnoloogiate sügavust.

Veel Yuvraj Chandrast