Максималан број балона Решење са кодом


Ниво тешкоће Лако
Често питани у Тесла Ваифаир
Хасхинг низ

Изјава о проблему

У овом проблему добијамо низ знакова који садрже мала енглеска слова. Морамо да пронађемо колико примера речи „балон”Можемо ли направити помоћу знакова датог низа.

Пример

String = "banooll"
1

Објашњење:

Максималан број балона Решење са кодом

String = baqwweeeertylln
0

Објашњење: Како низ нема никакво 'о', не можемо направити ни један примерак „балона“. Дакле, исписујемо 0.

Приступ

Очигледно је да морамо знати учесталост слова у низу који чине реч „балон“. Односно, важно нам је само да сачувамо фреквенције слова „б“, „а“, „л“, „о“ и „н“ јер чине низ „балон“. Тада можемо наћи слово са минималним бројем за одлучивање о броју примерака речи. Ово је типичан пример хасхинг ликови са њиховим фреквенцијама. Имајте на уму да морамо узети у обзир да се само половина фреквенција слова 'л' и 'о' може користити за прављење једне речи. Да бисмо генерализовали овај случај, претходно смо упола смањили учесталост ова два слова.

Алгоритам

  1. Иницијализујте 5 целих бројева: б, а, л, о, n да чувају њихове одговарајуће фреквенције као 0
  2. За сваки лик 'цхр'у низу:
    • Ако 'цхр'је било који од горе поменутих знакова, повећајте његову учесталост
  3. Дивиде l o од КСНУМКС
  4. Врати минимум међу б, а, л, о, n
  5. Одштампајте резултат

Примена максималног броја балона са решењем за код

Програм Ц ++

#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;
}

Јава Програм

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

Анализа сложености максималног броја балона Решење са кодом

Сложеност времена

НА) док једном прелазимо низ да бисмо чували фреквенције одређених знакова. Ево, N = величина низа.

Сложеност простора 

О (1) пошто користимо константни меморијски простор без обзира на улаз. Само чувамо неке променљиве за бројање њихових фреквенција.