文字列の文字を並べ替えて有効な英語の数値表現を形成します

この問題では、有効な英語の数値表現を取得するために、指定された文字列の文字を並べ替える必要があります。最初のアプローチは、文字列のすべての順列を見つけて、数字に関連する英単語を抽出し、それらを数字に変換することです。

この問題を解決するもう 1 つの方法は、各単語から一意の文字を見つけることです。このチュートリアルでは、特定の問題を解決する 2 つの方法を学びます。

問題ステートメント- 小文字を含む長さ N の文字列が与えられています。この文字列には、数字 [0 ～ 9] の英単語表現がランダムな順序で含まれています。文字列から英単語を抽出し、数値に変換し、その数値を昇順で表示する必要があります。

入力– str = "ゼオロエンウォット"

出力–'012'

説明– 指定された文字列から「0」、「1」、「2」を抽出し、それらを昇順に並べ替えることができます。

入力– str = 'zoertowxisesevn'

出力–'0267'

説明– 指定された文字列から「zero」、「two」、「six」、「seven」を抽出できます。

＃＃＃アルゴリズム＃＃＃

変数「count」を定義し、ゼロに初期化します。

• while ループを使用して文字列を走査します。現在の位置で単語が見つかった場合、'count' の値は 1 増加し、'pos' の値は単語の長さだけスキップされます。

• 「count」の値を返します

• 数字の英語表現を含む 'words' という名前のベクトルを定義します。また、文字列の任意の順列における最大単語数を格納するために「max_digits」を定義します。さらに、任意の順列から最大の単語を抽出できる場合の各桁の頻度を格納する「digital_freq」マップを定義します。

• sort() メソッドを使用して、指定された文字列を並べ替えます。

• do-while() ループで next_permutations() メソッドを使用します。ループ内で、別のループを使用して単語ベクトルを反復処理します。

• 現在の順列内の各単語の出現数をカウントし、これに基づいて 'word_freq' マップを更新します。同時に、結果の値を「cnt」変数に追加します。

• 「cnt」の値が「max_digitals」より大きい場合は、「max_digitals」と「digital_frequency」の値を更新します。

• 「digit_freq」マップを調べて、数値を文字列に変換します。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

  時間計算量 - O(N*N!)。すべての順列を見つける必要があるためです。

＃＃＃観察する＃＃＃

• 「4」個の中に「u」個の固有のものがあります。

• 「6 個」のうち「x」個の固有のものがあります。

• 「eight」には「gg」のユニークなものがあります。

• 上で検討したのと同じように、「three」から「h」を含むすべての一意の単語を抽出できます。

• 「o」を含むすべての単語を考慮したため、「one」から「o」だけを取り出すことができます。

• 上記のように、「f」を含むすべての単語として「five」から「f」を選択できます。

• 「7」には「v」個のユニークなものがあります。

• 「nine」の「i」は、上で検討した「i」を含むすべての単語として解釈できます。

＃＃＃アルゴリズム＃＃＃

• 英語の単語を含む「単語」ベクトルを定義し、それに応じて一意の単語を考慮しているため、以下の例の順序に従ってください。また、一意の文字とその数値表現のベクトルを定義します

• 各文字の頻度をカウントし、マップに保存します。

• マップに現在一意の文字が含まれている場合は、その頻度値を「cnt」変数に保存します。

• 次に、現在の単語を繰り返し処理します。マップ内の「cnt」によって単語の各文字の頻度を減らします。

• 在‘digits’向量中添加一个单词，重复‘cnt’次。

• 对数字字符串进行排序，并从函数中返回。

示例

#include  #include  #include  #include  using namespace std; string convertToDigits(string str){ // store the words corresponding to digits vector words = { "zero", "two", "four", "six", "eight", "three", "one", "five", "seven", "nine" }; // store the unique characters of the words vector unique_chars = {'z', 'w', 'u', 'x', 'g', 'h', 'o', 'f', 'v', 'i'}; // store the digits corresponding to the words vector numeric = {0, 2, 4, 6, 8, 3, 1, 5, 7, 9}; // to store the answer vector digits = {}; // unordered map to store the frequency of characters unordered_map freq; // count the frequency of each character for (int i = 0; i < str.length(); i++){ freq[str[i]]++; } // Iterate over the unique characters for (int i = 0; i < unique_chars.size(); i++){ // store the count of the current unique character int cnt = 0; // If the current unique character is present, store its count. Otherwise, it will be 0. if (freq[unique_chars[i]] != 0) cnt = freq[unique_chars[i]]; // Iterate over the characters of the current word for (int j = 0; j < words[i].length(); j++){ // Reduce the frequency of the current character by cnt times in the map if (freq[words[i][j]] != 0) freq[words[i][j]] -= cnt; } // Push the current digit cnt times in the answer for (int j = 0; j < cnt; j++) digits.push_back(numeric[i]); } // sort the digits in non-decreasing order sort(digits.begin(), digits.end()); string finalStr = ""; // store the answer in a string for (int i = 0; i < digits.size(); i++) finalStr += to_string(digits[i]); return finalStr; } int main(){ string str = "zoertowxisesevn"; // Function Call cout << "The string after converting to digits and sorting them in non-decreasing order is " << convertToDigits(str); }

输出

The string after converting to digits and sorting them in non-decreasing order is 0267

时间复杂度 - O(N)，其中N是字符串的长度。

空间复杂度 - O(N)，用于存储最终的字符串。

以上が文字列の文字を並べ替えて有効な英語の数値表現を形成しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。