최소 문자 Leetcode 솔루션의 빈도로 문자열 비교

난이도 쉽게
자주 묻는 질문 구글 신탁
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 조회수 17

가장 작은 문자 Leetcode 솔루션의 빈도로 문자열 비교 문제는 비어 있지 않은 함수 f (s)를 정의한다고 말합니다. f (s)가 문자열에서 가장 작은 문자의 빈도와 같도록합니다. 그런 다음 몇 가지 단어와 몇 가지 질문이 주어집니다. 각 쿼리에 대해 f (words)> f (query_word)와 같은 단어 수를 찾아야합니다. 그런 다음 모든 쿼리에 대한 답을 벡터 또는 배열로 반환해야합니다. 따라서 솔루션에 대해 자세히 살펴보기 전에 몇 가지 예를 살펴 보겠습니다.

queries = ["cbd"], words = ["zaaaz"]
[1]

설명 : f ( "zaaaz") = 3, 가장 작은 문자는 주파수가 3 인 'a'이고 f ( "cbd") = 1이기 때문에 f (i )> f (쿼리 _ 단어).

최소 문자 Leetcode 솔루션의 빈도로 문자열 비교

queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
[1,2]

설명 : 따라서 주어진 모든 단어에 대해 정의 된 함수의 값을 계산 한 후. f ( "a") = 1, f ( "aa") = 2, f ( "aaa") = 3, f ( "aaaa") = 4를 찾습니다. 쿼리에서 f ( "bbb") = 3, f ( "cc") = 2를 찾습니다. 따라서 단어 f ( "bbb")에 대해 함수 값이있는 단일 단어 "aaaa"가 있음을 찾습니다. 3보다 큽니다. 마찬가지로 "cc"라는 단어의 경우 기능 값이 더 큰 "aaa", "aaaa"라는 단어가 있습니다.

최소 문자 Leetcode 솔루션의 빈도로 문자열을 비교하는 방법

가장 작은 문자 Leetcode 솔루션의 빈도로 문자열 비교 문제는 정의 된 함수에 대한 값이 쿼리 단어에 대한 함수의 값보다 큰 입력에서 단어의 수를 찾도록 요청합니다. 비어 있지 않은 문자열에 대해 정의 된 함수 f (s)는 문자열에서 가장 작은 문자의 빈도와 같습니다. 따라서 먼저 모든 쿼리 단어에 대한 함수의 값을 찾습니다. 모든 입력 단어에 대해 동일한 작업을 수행합니다. 또한 함수 값이 i 인 단어의 수를 저장하는 추가 배열을 만듭니다. 이 배열은 일정한 시간 내에 쿼리에 대한 답을 찾는 데 도움이됩니다. 배열의 각 인덱스 i는 함수 값이 i 인 단어 수를 나타냅니다.

함수 값을 평가하고 임시 배열에 저장 한 후. 이제 각 인덱스가 i보다 크거나 같은 함수 값을 갖는 총 단어 수를 저장하도록 임시 배열의 접미사 합계를 취합니다. 이제 우리는 각 쿼리 단어에 대한 답을 배열이나 벡터에 저장하고 반환합니다.

최소 문자 Leetcode 솔루션의 빈도로 문자열을 비교하기위한 코드

C ++ 코드

#include <bits/stdc++.h>
using namespace std;

vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
    vector<int> q;
    for(auto x: queries){
        int f[26] = {0};
        int mn = 26;
        for(auto y: x){
            f[y-'a']++;
            mn = min(mn, y-'a');
        }
        q.push_back(f[mn]);
    }

    int fr[12];memset(fr, 0, sizeof fr);
    for(auto x: words){
        int f[26] = {0};
        int mn = 26;
        for(auto y: x){
            f[y-'a']++;
            mn = min(mn, y-'a');
        }
        fr[f[mn]]++;
    }
    for(int i=9;i>=0;i--)
        fr[i] += fr[i+1];
    vector<int> ans;
    for(auto x: q){
        ans.push_back(fr[x+1]);
    }
    return ans;
}

int main(){
    vector<string> queries = {"bbb","cc"};
    vector<string> words = {"a","aa","aaa","aaaa"};

    vector<int> answer = numSmallerByFrequency(queries, words);
    for(auto x: answer)
        cout<<x<<" ";
}
1 2

자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    public static int[] numSmallerByFrequency(String[] queries, String[] words) {
        ArrayList<Integer> q = new ArrayList<Integer>();
        for(String x: queries){
            int[] f = new int[26];
            for(int i=0;i<26;i++)
                f[i] = 0;
            int mn = 26;
            int sz = x.length();
            for(int i=0;i<sz;i++){
                int y = x.charAt(i);
                f[y-'a']++;
                mn = Math.min(mn, y-'a');
            }
            q.add(f[mn]);
        }
 
        int[] fr = new int[12];
        for(int i=0;i<12;i++)
            fr[i] = 0;
        for(String x: words){
            int[] f = new int[26];
            for(int i=0;i<26;i++)
                f[i] = 0;
            int mn = 26;
            int sz = x.length();
            for(int i=0;i<sz;i++){
                int y = x.charAt(i);
                f[y-'a']++;
                mn = Math.min(mn, y-'a');
            }
            fr[f[mn]]++;
        }
        for(int i=9;i>=0;i--)
            fr[i] += fr[i+1];
        int[] ans = new int[queries.length];
        for(int i=0;i<q.size();i++){
            ans[i] = (fr[q.get(i)+1]);
        }
        return ans;
    }
 
  public static void main (String[] args) throws java.lang.Exception
  {
    String[] queries = {"bbb","cc"};
      String[] words = {"a","aa","aaa","aaaa"};
 
      int[] answer = numSmallerByFrequency(queries, words);
      for(int x: answer)
          System.out.print(x+" ");
  }
}
1 2

복잡성 분석

시간 복잡성

O (Q + N), 모든 단어에 대한 함수 값을 계산해야하므로 단어의 길이도 10보다 작거나 같습니다. 따라서 시간 복잡도는 선형입니다.

공간 복잡성

O (Q), 대답을 저장할 배열과 임시 사용을 위해 크기 10의 추가 배열을 만들기 때문입니다. 공간 복잡성도 선형입니다.

코멘트를 남겨

Translate »