Максимален број на решенија за леткод на балони


Ниво на тешкотија Лесно
Често прашувано во Тесла Wayfair
Хашинг Стринг

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

Во овој проблем, ни е дадена низа карактери кои содржат англиски букви со мали букви. Треба да откриеме колку примери на зборот „балон”Можеме да направиме со користење на знаците на дадената низа.

пример

String = "banooll"
1

Објаснување:

Максимален број на решенија за леткод на балони

String = baqwweeeertylln
0

Објаснување: Бидејќи низата нема „o“, не можеме да направиме ниту една инстанца на „балон“. Значи, ние печатиме 0.

Пристап

Очигледно е дека треба да ја знаеме фреквенцијата на буквите во низата што го прави зборот „балон“. Тоа е, важно е само за нас да ги зачуваме фреквенциите на буквите "b", "a", "l", "o" и "n" бидејќи тие ја сочинуваат низата "балон". Потоа, можеме да ја најдеме буквата со минимално сметање за да одлучиме за можните примери на зборот. Ова е типичен пример за хашинг карактери со нивните фреквенции. Забележете дека треба да земеме предвид дека само половина од фреквенциите на буквите "l" и "o" може да се користат за да се создаде еден збор. Со цел да се генерализира овој случај, ние претходно ја преполовивме фреквенцијата на овие две букви.

Алгоритам

  1. Иницијализирајте 5 цели броја: б, а, л, о, n да ги зачувуваат нивните соодветни фреквенции како 0
  2. За секој ликхр"во низата:
    • Ако 'хр'е кој било од горенаведените знаци, зголемете ја нејзината фреквенција
  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

Анализа на комплексноста на максималниот број решенија за лет код на балони

Временска комплексност

НА) како што ја поминуваме низата еднаш за да зачуваме фреквенции на одредени карактери. Тука, N = големината на низата.

Комплексноста на просторот 

О (1) бидејќи користиме постојан мемориски простор без оглед на влезот. Ние само зачувуваме некои променливи за броење на нивните фреквенции.