Максімальная колькасць паветраных шароў


Узровень складанасці Лёгка
Часта пытаюцца ў Цеслы Wayfair
хэшавання Радок

Пастаноўка праблемы

У гэтай задачы мы атрымліваем радок сімвалаў, якія змяшчаюць ангельскія літары. Нам трэба знайсці, колькі асобнікаў слова "паветраны шар"Ці можам мы зрабіць, выкарыстоўваючы сімвалы дадзенага радка.

Прыклад

String = "banooll"
1

Тлумачэнне:

Максімальная колькасць паветраных шароў

String = baqwweeeertylln
0

Тлумачэнне: Паколькі ў радку няма аніякага "o", мы не можам зрабіць нават асобніка "паветранага шара". Такім чынам, мы друкуем 0.

Падыход

Відавочна, што нам трэба ведаць частату літар у радку, які робіць слова "паветраны шар". Гэта значыць, для нас важна толькі захаваць частаты літар "b", "a", "l", "o" і "n", паколькі яны складаюць радок "паветраны шар". Тады мы можам знайсці літар з мінімальным лікам, каб вызначыць колькасць выпадкаў слова. Гэта тыповы прыклад мяшанне сімвалы з іх частатамі. Звярніце ўвагу, што нам трэба ўлічваць, што толькі палова частат літар "l" і "o" можа быць выкарыстана для стварэння аднаго слова. Для таго, каб абагульніць гэты выпадак, загадзя мы палову частаты гэтых двух літар.

Алгарытм

  1. Ініцыялізаваць 5 цэлых лікаў: б, а, л, о, і n захоўваць іх адпаведныя частоты як 0
  2. Для кожнага персанажа 'chr'у радку:
    • Калі 'chr'з'яўляецца любым з вышэйзгаданых сімвалаў, павялічвайце яго частату
  3. дзяльба l і o па 2
  4. Вярнуць мінімум сярод б, а, л, о, і 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

Аналіз складанасці максімальнай колькасці паветраных шароў

Складанасць часу

O (N) калі мы праходзім радок адзін раз для захоўвання частот пэўных сімвалаў. Вось, N = памер масіва.

Касмічная складанасць 

O (1) паколькі мы выкарыстоўваем пастаянную памяць незалежна ад уваходных дадзеных. Мы проста захоўваем некаторыя зменныя для падліку іх частат.