Leetcode шийдлийн бөмбөлгийн хамгийн их тоо


Хэцүү байдлын түвшин Easy
Байнга асуудаг Tesla Wayfair
Хаширч байна String

Асуудлын мэдэгдэл

Энэ асуудалд бидэнд Англи үсгийн жижиг үсгийг агуулсан тэмдэгт мөрүүдийг өгсөн болно. “Гэдэг үгийн хэдэн жишээг олох хэрэгтэй.бөмбөлөг”Өгөгдсөн мөрийн тэмдэгтүүдийг ашиглан хийж болох уу.

Жишээ нь

String = "banooll"
1

Тайлбар:

Leetcode шийдлийн бөмбөлгийн хамгийн их тоо

String = baqwweeeertylln
0

Тайлбар: Мөрөнд ямар ч 'o' байхгүй тул бид нэг ч удаа "бөмбөлөг" хийж чадахгүй. Тиймээс бид 0-ийг хэвлэнэ.

арга барил

“Бөмбөлөг” гэдэг үгийг үүсгэдэг мөрийн үсгийн давтамжийг мэдэх шаардлагатай нь ойлгомжтой. Энэ нь зөвхөн "бөмбөлөг" мөрийг бүрдүүлдэг тул 'b', 'a', 'l', 'o', 'n' үсгийн давтамжийг хадгалах нь бидэнд чухал юм. Дараа нь, боломжтой үгийн тохиолдлын тоог шийдэх хамгийн бага тоололтой үсгийг олж болно. Энэ бол ердийн жишээ юм хэшээл тэдгээрийн давтамжтай тэмдэгтүүд. 'L' ба 'o' үсгийн давтамжийн зөвхөн тэн хагасыг нь л нэг үг хийхэд ашиглаж болно гэдгийг анхаарч үзэх хэрэгтэйг анхаарна уу. Энэ тохиолдлыг ерөнхийд нь нэгтгэхийн тулд бид эдгээр хоёр үсгийн давтамжийг хагасаар нь урьдчилан хийдэг.

Алгоритм

  1. 5 бүхэл тоог эхлүүлэх: б, а, л, о, болон n тус тусын давтамжийг хадгалах 0
  2. Дүр бүрийн хувьд "хр'мөрөнд:
    • Хэрэвхр'бол дээр дурдсан тэмдэгтүүдийн аль нэг нь давтамжийг нэмэгдүүлнэ
  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

Бөмбөлөгний хамгийн их тооны Leetcode шийдлийн нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N) Бид тэмдэгтүүдийн давтамжийг хадгалахын тулд мөрийг нэг удаа туулахдаа. Энд, N = массивын хэмжээ.

Сансрын нарийн төвөгтэй байдал 

O (1) бид оролтоос үл хамааран тогтмол санах ойн зайг ашигладаг. Бид зөвхөн давтамжийг тоолохын тулд зарим хувьсагчийг хадгалдаг.