Максимален брой балони Leetcode разтвор


Ниво на трудност Лесно
Често задавани в Tesla Wayfair
хеширане Низ

Декларация за проблема

В този проблем ни е даден низ от символи, съдържащи малки букви на английски. Трябва да намерим колко екземпляра на думата „балон”Можем ли да направим, като използваме символите на дадения низ.

Пример

String = "banooll"
1

Обяснение:

Максимален брой балони Leetcode разтвор

String = baqwweeeertylln
0

Обяснение: Тъй като низът няма никакво „o“, не можем да направим дори един екземпляр на „балон“. И така, отпечатваме 0.

Подход

Очевидно е, че трябва да знаем честотата на буквите в низа, което прави думата „балон“. Тоест за нас е важно само да запазим честотите на буквите 'b', 'a', 'l', 'o' и 'n', тъй като те представляват низа "балон". След това можем да намерим писмото с минимален брой, за да решим броя на възможните случаи на думата. Това е типичен пример за хеширане знаци с техните честоти. Имайте предвид, че трябва да имаме предвид, че само половината от честотите на буквите „l“ и „o“ могат да бъдат използвани за създаване на една дума. За да обобщим този случай, ние наполовина намаляваме честотата на тези две букви.

алгоритъм

  1. Инициализирайте 5 цели числа: b, a, l, o, и n да съхраняват съответните им честоти като 0
  2. За всеки геройCHR'в низа:
    • Ако "CHR'е някой от гореспоменатите знаци, увеличете честотата му
  3. Разделям l и o от 2
  4. Върнете минимума сред b, a, l, o, и n
  5. Отпечатайте резултата

Прилагане на максимален брой балони Leetcode решение

Програма 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 разтвор

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

НА) докато прекосяваме низа веднъж, за да съхраняваме честоти на определени символи. Тук, N = размер на масива.

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

O (1) тъй като използваме постоянно пространство в паметта, независимо от входа. Ние просто съхраняваме някои променливи за преброяване на техните честоти.