翻訳: M クエリの場合、指定された文字列の範囲を逆にします。-C++-php.cn

翻訳: M クエリの場合、指定された文字列の範囲を逆にします。

王林

リリース： 2023-08-25 20:09:09

転載

1253 人が閲覧しました

翻訳: M クエリの場合、指定された文字列の範囲を逆にします。

この問題では、配列の値に従って、指定された文字列に対して M 回の逆クエリを実行します。

問題を解決する素朴なアプローチは、指定された配列値に従って各文字列セグメントを反転することです。

最適化されたアプローチでは、同じ部分文字列を 2 回反転すると、元の文字列が得られるというロジックが使用されます。

問題ステートメント -アルファベット文字を含むアルファ文字列を指定しました。また、正の整数を含むサイズ M の arr[] 配列を指定しました。指定された文字列に対して M 操作を実行し、最終的な文字列を返す必要があります。

各操作では、arr[i] を取得し、部分文字列 arr[i] を N − arr[i] 1 まで尊重する必要があります。

例

入力

リーリー

出力

リーリー＃＃＃＃＃＃説明＃＃＃＃＃＃

最初のコメントを実行すると、文字列は「psrqt」に変わります。

入力
リーリー

出力

リーリー

説明

- 同じ質問に対して何回かカップリングを実行すると、同じ文字列が得られます。入力

リーリー出力

リーリー説明

-同じクエリを奇数回実行すると、文字列の逆が得られます。

アプローチ 1 このアプローチでは、 reverse() メソッドを使用して部分文字列を反転します。指定されたクエリを使用して開始ポインタと終了ポインタを取得し、指定された文字列の部分文字列を反転します。＃＃＃アルゴリズム＃＃＃

ステップ 1 - 遍歴の数グループを開始します。

第 2 ステップ

- arr[p] を使用 - 1 'left' 量を初期化します。

ステップ3

- str_len で「right」変数を初期化します - arr[p] 1.

ステップ 4 - reverse() メソッドを使用して、部分文字列を左ポインターから右ポインターに反転します。＃＃＃例＃＃＃リーリー出力

リーリー

時間計算量 - 部分文字列を M 回反転する場合の O(N*M)。空間の複雑さ - 動的空間を使用しないため、O(1)。

方法二

このアプローチでは、特定のインデックスと、指定されたクエリを使用して反転に含まれる回数を計算します。インデックスが偶数回含まれている場合、それを元に戻す必要はありません。指定されたすべてのクエリにインデックスが奇数回含まれている場合は、特定のインデックスで文字を反転する必要があります。＃＃＃アルゴリズム＃＃＃

ステップ 1 - 文字列の長さに等しい初期化長さの「cnt」リスト。0 は、逆転送中に出現する特定のインデックスを格納します。

ステップ2

-指定されたクエリの配列を走査し、現在のクエリに従って文字列の左右のポインタを取得します。

ステップ 3

-また、changeRange() 関数を実行して、現在のクエリの左右のポインターに従って「cnt」リストを更新します。

ステップ3.1

-changeRange()関数で、「cnt」リストの「左」インデックスの値を増加させます。

第 3.2 ステップ

- 小さい「cnt」リスト内の「右 1」は右側のすべての値を指します。

ここでは、「cnt」リストのすべての値を [左、右] の範囲で 1 ずつ増やす必要がありました。したがって、プレフィックスの合計を取得すると、「left」インデックスの右側にあるすべての値が 1 ずつインクリメントされるため、cnt[left] のみ 1 だけインクリメントしました。また、[right, str_len] インデックス間の cnt 値をインクリメントしたくないので、プレフィックスの合計によって 1 ずつ増加するため、すでに 1 ずつ減少させています。