LeetCode.1170-比較文字列の最小文字の出現頻度(Compare Strings by Frequency of the Smallest Char)
4493 ワード
小川の412回目の更新、444編目のオリジナルです
問題を見て準備する
今日紹介するのはLeetCodeアルゴリズム問題のEasyクラスの263番(順位問題番号は1170)です.非空文字列sには、
ここで、所与の文字列配列
例:
入力:queries=[「cbd」,words=[「zaaaz」]出力:[1]説明:最初のクエリでは
問題を見て準備する
今日紹介するのはLeetCodeアルゴリズム問題のEasyクラスの263番(順位問題番号は1170)です.非空文字列sには、
f(s)の最小文字の出現頻度を計算する関数sが定義される.例えば、s ="dcce"の場合、f(s)= 2は最小文字が"c"であるため、その周波数は2である.ここで、所与の文字列配列
queriesおよびwordsは、answerの各語がanswer[i]の単語数であり、f(queries[i]) < f(W)はWの単語数である整数配列wordsを返す.例:
入力:queries=[「cbd」,words=[「zaaaz」]出力:[1]説明:最初のクエリでは
f("cbd")= 1,f("zaaaz")= 3,従ってf("cbd")。 入力:queries=["bbb","cc"],words=["a","aa","aaa","aaaaa"]出力:[1,2]説明:最初のクエリでf("bbb")， answer[0] = 1のみ.2 のクエリでは、f("cc")，f("cc")， answer[1] = 2.
: 1 <= queries.length <= 2000 1 <= words.length <= 2000 1 <= queries[i].length , words[i].length <= 10 queries[i][j],words[i][j]は の です.
の
タイトルの は、wordsでは、 がqueriesの より さい を し し、 にqueriesの さをint として すことを する.
したがって、 たちは タイトルを することができて、2 の を って、 の はqueriesの の を して、queries[i]の の の を つけて、それからwordsの の を して、2つの の を して、もしqueriesの の が さいならば、カウントして、 の が わった 、カウント をanswer に し、 に します.public int[] numSmallerByFrequency(String[] queries, String[] words) {
int len = queries.length, len2 = words.length;
int[] result = new int[len];
for (int i=0; i
2の
1の では, ループ wordsにおける の について,ループ を することができる.まず、 の を し、 さとwordsと じint に し、 サイクルでは、このint を することができ、すべてを する はありません.public int[] numSmallerByFrequency2(String[] queries, String[] words) {
int len = queries.length, len2 = words.length;
int[] wordFreq = new int[len2];
for (int j=0; j
3の
の2つの について、 たちはさらに することができますか? えば、2つのサイクルを1つのサイクルに えますか?ループを するには、queriesの を するときに、ループを しない、つまり で を るように、 を に する があります.
まず2つ の を てみましょう.wordsの の が すると、1つの wordFreqが られ、その で を えてカウント を い、 の を しい のインデックスとし、さらに を すると、 の4つが られる.count[4] = 1; //"aaaa"
count[3] = 1; //"aaa"
count[2] = 1; //"aa"
count[1] = 1; //"a"
また、queries 、 "bbb"と"cc"を し、wordsの と すると、 のような があります. "bbb" 1 ， arr[3] = 1
"cc" 2 ， arr[2] = 2
のように きます. 1 3 ，arr[1] = 3
0 4 ，arr[0] = 4
queriesの の をインデックスとするarr は、 のcount の の であることが かった.arr[3] = count[4] = 1;
arr[2] = arr[3] + count[3] = 1+1 = 2
のようになります.arr[i-1] = arr[i]+count[i];
この の を した 、あとはコードを くことです.この は の2つの よりずっと いです.public int[] numSmallerByFrequency3(String[] queries, String[] words) {
int len = queries.length;
int[] wordFreq = new int[11];
for (String word : words) {
wordFreq[minFrequency(word)]++;
}
int[] sum = new int[11];
for (int i=sum.length-1; i>0; i--) {
sum[i-1] = sum[i]+wordFreq[i];
}
int[] result = new int[len];
for (int i=0; i
アルゴリズムのテーマは すでにLeetCodeアルゴリズムの 269+ を し、 ダイアログボックスは「データ とアルゴリズム」、「アルゴリズム」、「データ 」のいずれかのキーワードに し、シリーズの の を した.
はすべての で、もしみんなが か い の 、 あるいはその の があれば、 の で することができて、いいね、 、 は に する のリターンと です!