リスト内の各項目が単語であるリンクされたリストにまたがる文があるとします。たとえば、次のようになります。
Hello -> みんな -> How -> Are -> You -> Feeling -> |
このリストがソートされていると仮定すると、次のようになります。
Are -> みんな -> Feeling -> Hello -> How -> You -> |
文の最初の文字 (この例では、Hello & How の文字 H) を見つける再帰をどのように記述しますか?
リスト内の各項目が単語であるリンクされたリストにまたがる文があるとします。たとえば、次のようになります。
Hello -> みんな -> How -> Are -> You -> Feeling -> |
このリストがソートされていると仮定すると、次のようになります。
Are -> みんな -> Feeling -> Hello -> How -> You -> |
文の最初の文字 (この例では、Hello & How の文字 H) を見つける再帰をどのように記述しますか?
単語をループして、各文字で始まる単語の数を集計します。集計に応じて最も人気のある手紙を返します (集計に優先キューを使用した場合は簡単です)。
これには O(n) 時間 (単語数) と O(26) メモリ (アルファベットの文字数) がかかります。
単語をアルファベット順に並べ替えます。単語をループします。現在の手紙とその頻度、およびこれまでで最も人気のある手紙とその頻度を記録します。ループの最後では、これがリスト全体で最も人気のある文字です。
これには O(n log n) 時間と O(1) メモリが必要です。
長さ 26 の配列があります (英語の文字として、インデックス 1 は 'a'、2 は 'b' などです)。文字が出現するたびに、配列内の値をインクリメントします。値が最大量を超えた場合は、最大値を更新し、その文字を最も発生した文字として取得します。次に、次のノードのメソッドを呼び出します。
これは Java のコードです。
import java.util.LinkedList;
public class MostOccurance {
char mostOccured;
int maxOccurance;
LinkedList<String> list= new LinkedList<String>();
int[] letters= new int[26];
public void start(){
findMostOccuredChar( 0, '0', 0);
}
public char findMostOccuredChar ( int node, char most, int max){
if(node>=list.size())
return most;
String string=list.get(node);
if (string.charAt(0)== most)
{max++;
letters[Character.getNumericValue(most)-10]++;
}
else{
letters[Character.getNumericValue(most)-10]++;
if (letters[Character.getNumericValue(most)-10]++>max){
max=letters[Character.getNumericValue(most)-10];
most=string.charAt(0);
}
}
findMostOccuredChar( node++, most, max);
return most;
}
}
もちろん、各単語をリンク リストに追加する必要があります。例を示しただけなので、私はそれをしませんでした。
出現回数を格納する配列を保持し、リンクされたリストを 1 回調べてカウントします。最後に、配列をループして最高のものを見つけます。
C でのラフ スケッチ:
int count[26]={0};
While ( head->next != NULL)
{
count[head->word[0] - 'A']++; // Assuming 'word' is string in each node
head = head->next;
}
max = count[0];
for (i=0;i<26;i++)
{
if(max<a[i])
max = a[i];
}
再帰を使用して小文字を処理するように変更できます。