풍선 Leetcode 솔루션의 최대 수

난이도 쉽게
자주 묻는 질문 테슬라 웨이 페어
알고리즘 코딩 해싱 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 조회수 107

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

이 문제에서는 소문자 영어 문자를 포함하는 문자열이 주어집니다. ""라는 단어의 인스턴스 수를 찾아야합니다.풍선”주어진 문자열의 문자를 사용하여 만들 수 있습니다.

String = "banooll"
1

설명:

풍선 Leetcode 솔루션의 최대 수

String = baqwweeeertylln
0

설명: 문자열에 'o'가 없기 때문에“balloon”의 인스턴스를 하나도 만들 수 없습니다. 그래서 우리는 0을 인쇄합니다.

접근

"풍선"이라는 단어를 만드는 문자열의 문자 빈도를 알아야한다는 것은 분명합니다. 즉, 문자 'b', 'a', 'l', 'o'및 'n'이 문자열 "풍선"을 구성하므로 빈도를 저장하는 것이 중요합니다. 그런 다음 가능한 단어의 인스턴스 수를 결정하기 위해 최소 개수를 가진 문자를 찾을 수 있습니다. 이것은 전형적인 예입니다 해싱 주파수가있는 문자. 'l'과 'o'문자의 빈도 중 절반 만 단일 단어를 만드는 데 사용할 수 있다는 점을 고려해야합니다. 이 경우를 일반화하기 위해 사전에이 두 글자의 빈도를 절반으로 줄였습니다.

암호알고리즘

  1. 5 개의 정수를 초기화합니다. 나, 아, 나, 오,n 각각의 주파수를 0
  2. 모든 캐릭터 'chr'문자열 :
    • 만약 'chr'는 위에 언급 된 문자 중 하나입니다. 빈도를 높입니다.
  3. 분할 lo 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;
}

자바 프로그램

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) 입력에 관계없이 일정한 메모리 공간을 사용하기 때문입니다. 주파수를 계산하기 위해 몇 가지 변수를 저장합니다.

균열 시스템 설계 인터뷰
Translate »