Leetcode шешімінің шарларының максималды саны  


Күрделілік дәрежесі оңай
Жиі кіреді Tesla Wayfair
алгоритмдер кодтау Хэш сұхбат сұхбат дайындау LeetCode LeetCodeSolutions String

Проблемалық мәлімдеме  

Бұл мәселеде бізге кіші ағылшын әріптерін қамтитын символдар тізбегі беріледі. Біз сөздің қанша данасын табуымыз керекәуе шары”Берілген жолдың таңбаларын қолдана отырып жасай аламыз ба.

мысал

String = "banooll"
1

Түсіндіру:

Leetcode шешімінің шарларының максималды санытүйреуіш

String = baqwweeeertylln

Түсіндіру: Жолда ешқандай 'o' жоқ болғандықтан, біз «шардың» бір данасын да жасай алмаймыз. Сонымен, біз 0 басып шығарамыз.

жақындау  

Біз «шар» сөзін жасайтын жолдағы әріптердің жиілігін білуіміз керек екені анық. Яғни, біз үшін 'b', 'a', 'l', 'o' және 'n' әріптерінің жиілігін сақтау өте маңызды, өйткені олар «шар» жолын құрайды. Содан кейін, мүмкін болатын сөздің мысалдар санын анықтайтын минималды санды әріпті таба аламыз. Бұл типтік мысал хэштеу олардың жиіліктері бар таңбалар. Біз 'l' және 'o' әріптерінің жиіліктерінің тек жартысы ғана бір сөз жасауға болатындығын ескеруіміз керек екенін ескеріңіз. Бұл жағдайды жалпылау үшін біз алдын-ала осы екі әріптің жартысын шығарамыз.

Алгоритм

  1. 5 бүтін инициализация: б, а, л, о, және n сәйкес жиіліктерін сақтау үшін
  2. Әр кейіпкер үшін 'Char'жолында:
    • Егер 'Char'- бұл жоғарыда аталған символдардың кез-келгені, оның жиілігін арттырыңыз
  3. Бөлу l және o 2 арқылы
  4. Арасында минималды қайтарыңыз б, а, л, о, және n
  5. Нәтижені басып шығарыңыз
Сондай-ақ, қараңыз
Лицензия кілтін форматтау шешімі

Әуе шарларының максималды санының шешімі

C ++ бағдарламасы

#include <bits/stdc++.h>
using namespace std;

int maxNumberOfBalloons(string text)
{
    int b = 0 , a = 0 , l = 0 , o = 0 , n = 0;
    for(char &chr : text)
    {
        switch(chr)
        {
            case 'b' : b++;
                break;
            case 'a' : a++;
                break;
            case 'l' : l++;
                break;
            case 'o' : o++;
                break;
            case 'n' : n++;
                break;
        }
    }

    l /= 2;
    o /= 2;
    return min({b , a , l , o , n});
}

int main()
{
    string text = "blloona";
    cout << maxNumberOfBalloons(text) << '\n';
    return 0;
}

Java бағдарламасы

import java.lang.*;

class max_balloons
{
    public static void main(String args[])
    {
        String text = "blloona";
        System.out.println(maxNumberOfBalloons(text));
    }

    static int maxNumberOfBalloons(String text)
    {
        int b = 0 , a = 0 , l = 0 ,  o = 0 , n = 0;
        char chr;
        for(int i = 0 ; i < text.length() ; i++)
        {
            chr = text.charAt(i);
            switch(chr)
            {
                case 'b' : b++;
                case 'a' : a++;
                case 'l' : l++;
                case 'o' : o++;
                case 'n' : n++;
                default: ;
            }
        }

        l /= 2;
        o /= 2;

        return Math.min(b , Math.min(a , Math.min(l, Math.min(o , n))));
    }
}
1

Шарлардың максималды санының күрделілігін талдау Leetcode ерітіндісі

Уақыттың күрделілігі

O (N) біз белгілі бір символдардың жиілігін сақтау үшін жолды бір рет айналып өткенде. Мұнда, N = массивтің өлшемі.

Ғарыштың күрделілігі 

O (1) өйткені кіріске тәуелсіз тұрақты жад кеңістігін қолданамыз. Біз олардың айнымалыларын олардың жиілігін санау үшін ғана сақтаймыз.