O(1) 個の余分なスペースを使用して単語を反転する

#文字列は複数の単語で構成されている場合があります。 C 文字列内の各単語には、文字、数字、または特殊記号を含めることができます。文字列は、これらの文字の記憶要素とみなされます。各単語はスペース文字で区切られます。各単語も 1 文字の文字列を形成します。 C では、文字列の反転は、-

に続く文字列です。

• 文字を末尾から先頭まで取得して形成されます。

• 元の文字列の長さは変わりません。

文字列内の

文字の順序は、単語の先頭と末尾の文字を入れ替えることで簡単に逆転できます。

一定の補助スペースは O(1) で表されます。これは、プログラムの実行中に追加のスペースが必要ないことを意味します。

問題を説明するためのいくつかの例は次のとおりです:

例例

例 1 - str:Abc def

出力: cbA が供給されました

説明: 文字列を反転しても、文字の状態は変わりません。

例 2 - str: こんにちは spe2

出力: yeH 23%eps

問題ステートメントは、各単語を抽出し、各単語の開始ポインターと終了ポインターのペアを保持してからそれを反転することで解決できます。

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

ステップ 1
• -for ループを使用して、指定された入力文字列を走査します。

ステップ 2
• - 変数 st を使用して、最初の単語の開始文字を取得します。

ステップ 3
• -最初のスペースが検出されると、 lst 変数が前の文字に固定され、単語の開始文字と終了文字をマークします。

ステップ 4
• -これら 2 つのポインターと while ループを使用して、単語の文字を反転します。 while ループの各反復で、ポインタが移動して文字列を使い果たします。

ステップ 5
• -ポインターを次の後続の単語にシフトするために値が更新され、以下同様です。st はスペースの後の次の文字に再初期化されます。

ステップ 6
• - 文字列全体が反復され、対応する単語が反転されます。

  ＃＃＃例＃＃＃

  次の C コード スニペットは、文字列を入力として受け取り、その中に含まれる単語を反転します -
リーリー ＃＃＃出力＃＃＃ リーリー

空間の複雑さ

任意のタイプの変数を新たに初期化する必要がないため、上記のメソッドで必要なスペースは一定です。ワードを交換するために外部スペースストレージは必要ありません。すべての変更は、使用可能なストレージ変数で行われます。

＃＃＃結論は＃＃＃

文字列は、任意の順序で配置したり、単純な反復によって逆に配置したりできる文字で構成されます。このアルゴリズムは、格納されている文字の全範囲に対して 1 回の反復を実行するため、必要な合計時間は O(n) です (n は文字列の長さ)。

以上がO(1) 個の余分なスペースを使用して単語を反転するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。