指定された範囲内のジャンプ値を選択することによって、指定されたバイナリ文字列の末尾に到達できるかどうかを確認します。

バイナリ文字列は、2 種類の文字 (0 と 1) のみを含む文字列です。バイナリ文字列と 2 つの整数 L および R が与えられたとします。文字列値が「0」であるインデックスから、「L」と「R」の間のサイズのジャンプを行うことができます。 0 番目のインデックスから開始して、最後のインデックスに到達できるかどうかを確認する必要があります。

例例

リーリー

説明

は次のように翻訳されます:

説明

インデックス 0 から 3 回ジャンプし、さらに 2 回ジャンプして 4 にジャンプすると、最終的に目的のインデックスに到達します。

リーリー

説明

は次のように翻訳されます:

説明

2 つのジャンプを行うことができます。各ジャンプは 2 または 3 です。0 番目のインデックスからジャンプした場合、2 番目または 3 番目のインデックスに到達すると、インデックスが「1」の値にのみジャンプできます。 、それ以上ジャンプすることはできません。

方法 1

アイデア

の中国語訳は次のとおりです:

アイデア

このアイデアは、動的プログラミングの概念を適用することです。場所が到達可能かどうかを示す配列を維持できます。

1 つの位置に到達できれば、次の l から r の位置も達成できます。

＃＃＃実装＃＃＃

文字列、左位置、右位置をパラメータとして受け取り、ブール値を返す関数を作成します。

この関数では、配列を反復処理し、ネストされた for ループを使用して範囲を横断し、現在の位置から現在の範囲の位置を引いた値が到達可能かどうかを確認し、到達可能な場合は、その位置に到達できます。

最終的には、最終的な答えを表す DP 配列の最後のインデックスのステータスを返します。

Example

の中国語訳は次のとおりです:

Example

リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量と空間計算量

上記のコードの時間計算量は O(N^2) です。ここで、N は指定された文字列のサイズです。ネストされた for ループを使用したため、時間計算量は N^2 になりました。 DP 状態を格納するために長さ N の配列を使用するため、上記のコードの空間複雑さは O(N) です。

方法 2

このメソッドは前のメソッドの改良版です。このメソッドでは、整数を維持して、実行できるジャンプの数を取得します。ジャンプするたびに、ジャンプが可能であればカウントをインクリメントし、どの位置でもジャンプが不可能であればカウントをデクリメントできます。

データを DP 配列の各インデックスに保存し、後で使用します。

Example

の中国語訳は次のとおりです:

Example

リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量と空間計算量

上記のコードの時間計算量は O(N) です。ここで、N は指定された文字列のサイズです。時間計算量が線形になるように、単一のループを使用して文字列を反復処理します。

DP 状態を格納するために長さ N の配列を使用するため、上記のコードの空間複雑さは O(N) です。 ＃＃＃結論は＃＃＃ このチュートリアルでは、最初のインデックスから開始して、指定された文字列の末尾に「0」を含むインデックスから指定された数のインデックスを移動することによって、指定されたインデックスに到達できるかどうかを判断するコードを実装しました。動的計画法を採用し、時間計算量はO(N^2)とO(N)、空間計算量はO(N)です。

以上が指定された範囲内のジャンプ値を選択することによって、指定されたバイナリ文字列の末尾に到達できるかどうかを確認します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。