アルゴリズム問題の分析プロセス

[[384555]]

トピックを理解する

最近アルゴリズムの問題をたくさん見ていますが、小さな問題を使ってアルゴリズム分析のプロセスを記録したいと思っています。タイトルは「ピッグ・ラテン」

 Pig Latin は英語の単語を変更する方法です。ルールは次のとおりです。 
 
単語が子音で始まる場合は、最初の子音または子音連結を取り、末尾に移動します。  言葉の、そして それに「ay」を追加します。 
 
単語が母音で始まる場合は、末尾に「way」を追加します。

説明が少ない質問に遭遇したとき、最初の反応は、説明が簡単であればあるほど、隠された条件が増えるだろうということです。慌てないで、まずはWikipediaのPig Latinの説明を読んでください：Pig Latin。質問を見るときは、まずWikipediaをチェックして質問の背景や由来を理解するようにしています。そうすることで、質問をより深く理解でき、質問の解決がより面白くなります。簡単にルールを分析してみましょう。単語が子音で始まる場合、子音を末尾に移動してayを追加します。例：

california → aliforniacay : c が末尾に移動し、ay が追加されます
段落 → aragraphspay: p は末尾に移動し、ay を追加します
glove → oveglay: glが末尾に移動し、ayを追加します⚠️ ここで最初の母音の前にあるすべての子音が見つかります

母音: a、e、i、o、u

単語が母音で始まる場合は、単語の直後にwayを付け加えます。例:

algorithm → algorithmway : aは母音なので単語の末尾にwayを追加します
eight → eightway : eは母音なので、単語の最後にwayを追加します

トピックを分析した後、テストケースを読んで、抜け漏れがないか確認する必要があります。最後のものをご覧ください。

母音のない単語を処理する必要があります。translatePigLatin("rhythm") は"rhythmay"を返す必要があります。

このルールは実際には最初のケースに当てはまります。母音が見つからない場合は、最後に ay を追加するだけです。

分析プロセス

アルゴリズムの問題が発生すると、私たちは「都市を攻撃する」ためにいくつかのルーチンに従います。

1. アルゴリズムの分類。この質問は文字列に関するものです。文字列操作には 2 種類しかありません。

a. インデックスによるトラバース

b.replace、特にreplaceでは、倫理の問題ではありません。

2. 最も単純なものから最も高度なものまで:

a. まず、与えられた条件に従って、暴力の方向で擬似コードを記述します。

b. ロジックに基づいて主要なループ要因と最適化方法を見つける

c. 最適化を試みる

疑似コード

まず疑似コードを記述します。コードのこの部分は比較的大まかで、主に分析プロセスを整理するために使用されます。

 VAR 文字列
VAR 母音文字 = [ 'a' 、 'e' 、 'i' 、 'o' 、 'u' ]
 // 母音で始まる
IF STR[0]が母音文字の場合
STR + 'way'を返す 
 // STR内の母音インデックスを見つける
STRのFOR (S, INDEX )
    IF S IN母音文字
STR.slice( INDEX ) + STR.slice(0, INDEX ) + 'ay'を返す 
 // この単語には母音がありません
リターン STR + ay
コードをコピー

分析プロセスができたので、JavaScriptコードを記述できます。

関数translatePigLatin(str) {
    // まず必要な母音配列を準備します
    const 母音文字 = [ 'a' , 'e' , 'i' , 'o' , 'u' ]
    // 特別なケース: 母音で始まる場合
    if (vowelLetters.includes(str[0])) は`${str}way`を返します
     
    // 通常の状況
( i = 0 とします; i < str.length; i++) {
        if (vowelLetters.includes(str[i])) {
 `${str.slice(i)}${str.slice(0, i)}ay` を返す
        }
    } 
 
    // 前部が止まらない場合は、母音が存在しないことを意味します
`${str}ay`を返す
} 
 
 translatePigLatin( "子音" );
コードをコピー

上記のコードを確認してください。テストに合格したので、最適化する方法を分析しましょう。コード分析から、コード全体のコアロジックは${str.slice(i)}${str.slice(0, i)}ayです。重要なポイントは、最初の母音のインデックスを見つけることです。そのため、コードを変更します。

関数translatePigLatin(str) {
    // インデックスを直接検索する
    index = str.split( '' ).findIndex(s => /[aeiou]/.test(s))とします。 
 
    if (インデックス< 0) `${str}ay`を返す
    if (インデックス=== 0 ) `${str}way`を返します
`${str.slice( index )}${str.slice(0, index )}ay`を返します
} 
 
 translatePigLatin( "子音" );
コードをコピー

コードが簡素化され、ロジックが明確になりました

別の方法

分析プロセスの観点から見ると、ループトラバーサル方式を使用して完了したので、他の方法（置換）はどのように実装する必要がありますか？最初の方法の結果から判断すると、位置を交換するには通常のグループ化方法が必要です。アイデアとしては、これを 2 つのグループに分けることです。最初のグループは語頭から母音まで、2 番目のグループは母音から語尾までです。次に、2 つのグループの順序を入れ替えて、接尾辞を追加します。正規表現を開発およびデバッグする場合、正規表現のデバッグには regex101.com が推奨されます。

デバッガーを使用して、この正規表現を完成させてください: /([^aeiou]*)(\w*)/ 説明

2つの括弧を使って2つのグループに分けます
([^aeiou]*) は、(^)aeiou 以外の 0 個以上の文字に一致することを意味します。
(\w*) 残りの文字はグループです

完全なコード

関数translatePigLatin(str) {
 str.replace (/([^aeiou]*)(\w*)/, ' $2$1ay' )を返します
} 
 
 translatePigLatin( "子音" );
コードをコピー

テストを通じて、上記のコードは母音が先頭にあるケースをカバーしましたが、他の 2 つのケースも含まれています。先頭に母音がくる場合、追加される接尾辞は way です。つまり、([^aeiou]*) にマッチしない $1 が空の場合、接尾辞は ay になります。この考え方に従って、JavaScript 文字列置換メソッドの 2 番目のパラメータは、サポート関数 String.prototype.replace() です - JavaScript | MDN

関数translatePigLatin(str) {
 str.replaceを返します(/([^aeiou]*)(\w*)/, (_, p1, p2) => `${p2}${p1|| ' w' }ay`)
 } 
 
 translatePigLatin( "子音" );
コードをコピー

要約する

まとめると、アルゴリズムの問題を解いたときの基本的な手順は

分類とは、質問の種類を指します。分類後、基本的に方向を決定できます。たとえば、ほとんどのツリー質問では再帰が必要です。意図的に再帰をトレーニングしたい場合は、ツリーグループ化でトレーニングできます。
まず問題のロジックを分析し、単純で大まかな方法を使用してロジックの疑似コードを書き出し、その後最適化を突破します。
他の方向にもっと良い解決策があるかどうかを検討します。

最後に、ちょっとしたアドバイスです。短期的に面接で突破口を開きたいなら、Leetcode を実践してください。こちらもおすすめ: https://www.codewars.com/。これに比べると、codewars は最適なアルゴリズムよりも、現在のプログラミング言語の実際の動作に重点を置いており、そこには「予想外の驚き」がたくさんあります。数々の「奇妙なトリックと黒魔術」に感動することでしょう。 CodeWars の難易度制限はもっと高いという噂があります。

<<: ベンジオとヒントンの絶え間ない探求：ディープラーニングアルゴリズムが脳の学習方法を明らかにする

>>: ヘルスケアにおける人工知能の課題にどう対処するか