Փուչիկների առավելագույն քանակը Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Tesla Վայֆայեր
Հեշինգ String

Խնդիրի հայտարարություն

Այս խնդրում մեզ տրված է նիշերի տող, որոնք պարունակում են փոքրատառ անգլերեն տառեր: Մենք պետք է գտնենք, թե քանի բառ է «փուչիկ”Կարո՞ղ ենք անել, օգտագործելով տրված տողի նիշերը:

Օրինակ

String = "banooll"
1

բացատրություն:

Փուչիկների առավելագույն քանակը Leetcode լուծում

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. Տպեք արդյունքը

Փուչիկների առավելագույն քանակի լետկոդ լուծույթի իրականացում

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

Փուչիկների առավելագույն քանակի լետկոդ լուծույթի բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ) երբ մենք մեկ անգամ անցնում ենք լարը ՝ որոշակի նիշերի հաճախականությունները պահելու համար: Այստեղ, N = զանգվածի չափը:

Տիեզերական բարդություն 

Ո (1) քանի որ մենք օգտագործում ենք անընդհատ հիշողության տարածություն ՝ անկախ մուտքից: Մենք պարզապես պահում ենք որոշ փոփոխականներ `դրանց հաճախականությունները հաշվելու համար: