ホームページ  >  記事  >  バックエンド開発  >  指定された配列内の文字列ペアの最初の文字を交換することによって取得された新しい文字列ペアの数をカウントします。

指定された配列内の文字列ペアの最初の文字を交換することによって取得された新しい文字列ペアの数をカウントします。

PHPz
PHPz転載
2023-09-16 18:49:111013ブラウズ

指定された配列内の文字列ペアの最初の文字を交換することによって取得された新しい文字列ペアの数をカウントします。

この問題では、文字列のペアを選択し、それらの最初の文字を交換する必要があります。その後、新しいペアの総数を計算する必要があります。この問題は、各ペアの最初の文字を交換し、それが配列内に存在するかどうかを確認することで解決できます。

この問題を解決する効率的な方法は、ハッシュ マップ データ構造を使用することです。

問題ステートメント - N 個の文字列を含む配列があります。すべての配列要素から任意の 2 つの文字列を選択し、これら 2 つの文字列の最初の文字を交換できます。配列内に存在しない、生成された新しい文字列ペアの合計数をカウントする必要があります。

例例

入力 – array[] = {「すべき」、「だろう」、「できる」};

出力 – 3

説明 – 新しく生成されたペアは、 Could と wan になります。別のペアは、誰が、そしてそうすべきである可能性があります。 3 番目のペアは san と chould です。

入力 – array[] = {"デモ", "テスト"};

出力 – 1

説明 – 配列内に存在しない、新しく生成されたペアは temo と dest です。

方法1

このメソッドでは、2 つのネストされたループを使用して、配列要素のすべてのペアを取得します。その後、2 つのペアの最初の文字を交換します。次に、3 番目のネストされたループを使用して、配列にペアが含まれているかどうかを確認します。

###アルゴリズム###

    「cnt」変数を定義し、0 に初期化して、ペアの総数を保存します。
  • 2 つのネストされたループを使用して文字列配列を反復処理し、配列要素の各ペアを取得します。
  • 現在の 2 つの文字列のペアを取得します。
  • 2 つの文字列の最初の文字が等しくない場合は、それらを交換します
  • 「isFirst」変数と「isSecond」変数を定義し、それらを false で初期化して、新しく生成された文字列が配列内に存在するかどうかを追跡します。
  • 3 番目のネストされたループを使用して、配列内に新しく生成された文字列があるかどうかを確認します。さらに、isFirst 変数と isSecond 変数の値は、配列内の文字列に基づいて更新されます。
  • 配列に最初の文字列も 2 番目の文字列も存在しない場合は、「cnt」の値を 1 増やします。
  • 「cnt」変数の値を返します。
  • ###例### リーリー ###出力### リーリー
時間計算量

- O(N^3)。3 つのネストされたループを使用しているためです。

空間の複雑さ

– O(1) 方法 2

このメソッドでは、マップ データ構造を使用して、マップ内のすべての配列値を保存します。その後、マップに新しく生成された文字列が含まれているかどうかを確認できます。そうでない場合は、カウントを 1 つ増やします。 ###アルゴリズム###

変数「cnt」を定義します

文字列配列をループし、すべての配列値をマップに保存します。

  • 2 つのネストされたループを使用して、配列要素のすべてのペアを取得します。

  • 文字列のペアを取得し、「first」変数と「first」変数に格納します。

  • 2 つの文字列の最初の文字が等しくない場合は、それらを交換します。

  • マップに、新しく生成された文字列が含まれているかどうかを確認します。そうでない場合は、「cnt」の値を 1 増やします。

  • 「cnt」値を返します。

  • ###例### リーリー ###出力### リーリー

    時間計算量
  • - O(N^2)、入れ子になったループを 2 つ使用するため。
  • 空間複雑度
  • – マッピングを使用してすべての配列要素を格納するため、O(N)。

配列要素の最初の文字を交換することで、新しく生成されたペアの総数を学習します。時間計算量の点で 2 番目のメソッドのコードを最適化しましたが、空間計算量の点では最初のコードの方が優れています。

以上が指定された配列内の文字列ペアの最初の文字を交換することによって取得された新しい文字列ペアの数をカウントします。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事はtutorialspoint.comで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。