가장 작은 문자 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 (쿼리 _ 단어).
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의 추가 배열을 만들기 때문입니다. 공간 복잡성도 선형입니다.
