Шумораи максималии пуфакҳои ҳалли Leetcode  


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Tesla Усмоналӣ
алгоритмҳо рамзгузорӣ Хашм мусоҳиба омодасозии мусоҳиба LeetCode LeetCodeSolutions сатр

Изҳороти мушкилот  

Дар ин масъала, ба мо як қатор аломатҳое дода мешаванд, ки дорои ҳарфҳои хурди англисӣ мебошанд. Мо бояд пайдо кунем, ки чанд мисоли калимаи «баллон”Метавонем бо истифода аз аломатҳои сатри додашуда.

мисол

String = "banooll"
1

Шарҳ:

Шумораи максималии пуфакҳои ҳалли Leetcodeпайвандак

String = baqwweeeertylln

Шарҳ: Азбаски сатр ягон 'o' надорад, мо ҳатто як мисоли "пуфак" карда наметавонем. Ҳамин тавр, мо 0 чоп мекунем.

усул  

Маълум аст, ки мо бояд басомади ҳарфҳоро дар сатр, ки калимаи "пуфак" -ро месозад, донем. Яъне, барои мо наҷот додани басомадҳои ҳарфҳои 'b', 'a', 'l', 'o' ва 'n' танҳо барои мо муҳим аст, зеро онҳо сатри "пуфак" -ро ташкил медиҳанд. Пас, мо метавонем ҳарферо пайдо кунем, ки миқдори ҳадди аққалро барои ҳалли шумораи намунаҳои калимаи имконпазир муайян кунад. Ин як мисоли маъмулӣ аз тарошидан аломатҳо бо басомадҳои худ. Дар хотир доред, ки мо бояд ба назар гирем, ки танҳо як нисфи басомадҳои ҳарфҳои 'l' ва 'o' -ро барои сохтани як калима истифода бурдан мумкин аст. Бо мақсади ба таври умумӣ кардани ин ҳолат, мо пешакӣ нисфи басомади ин ду ҳарфро мегузорем.

Алгоритм

  1. 5 ададро оғоз кунед: б, а, л, о, ва n барои нигоҳ доштани басомадҳои дахлдори худ ҳамчун
  2. Барои ҳар як аломат 'хр'дар сатр:
    • Агар 'хр'ин яке аз аломатҳои дар боло зикршуда мебошад, басомади онро зиёд кунед
  3. тащсим кардан l ва o аз ҷониби 2
  4. Ҳадди аққалро дар байни худ баргардонед б, а, л, о, ва n
  5. Натиҷаро чоп кунед
ҳамчунин нигаред
Ҳалли Leetcode форматкунии калиди иҷозатнома

Татбиқи миқдори максималии пуфакҳо Solution 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 = андозаи массив.

Мураккабии фазо 

О (1) зеро мо новобаста аз вуруд фазои хотираи доимиро истифода мебарем. Мо танҳо баъзе тағирёбандаҳоро барои ҳисоб кардани басомади онҳо нигоҳ медорем.