Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonで1つのリストを別のリストに変更するために必要なスワップの数をカウントするプログラム？

番号L1とL2の2つのリストがあり、各リストの長さがnで、各値がそのリストに固有であり、値が1からnの範囲であるとすると、L1を変換するために必要な隣接スワップの最小数を見つける必要があります。 L2へ。

したがって、入力がL1 =[0、1、2、3] L2 =[2、0、1、3]の場合、1と2を入れ替えることができるため、出力は2になります。L1は[0 、2、1、3]、次に0と2、L1は[2、0、1、3]になります。これは、L2と同じです。

これを解決するには、次の手順に従います。

  • ans：=0

  • L2の要求ごとに、実行します

    • i：=L1のreqのインデックス

    • L1からi番目の要素を削除します

    • ans：=ans + i

  • ansを返す

理解を深めるために、次の実装を見てみましょう。

例

class Solution:
   def solve(self, L1, L2):
      ans = 0
      for req in L2:
         i = L1.index(req)
         L1.pop(i)
         ans += i
      return ans

ob = Solution()
L1 = [0, 1, 2, 3]
L2 = [2, 0, 1, 3]
print(ob.solve(L1, L2))

入力

[0, 1, 2, 3],[2, 0, 1, 3]

出力

2

  1. Pythonのsの個別の部分文字列の数をカウントするプログラム

    文字列sがあるとすると、sの個別の空でない部分文字列の数を見つける必要があります。 したがって、入力がs =abaaの場合、サブストリングは[a、 b、 ab、 ba、 aa、 aba、 であるため、出力は8になります。 baa 、abaa]。 これを解決するには、次の手順に従います- トライ：=新しい地図 n：=sのサイズ 0からn-1の範囲のiの場合、do curr：=trie iからn-1の範囲のjの場合、do c：=s [j] cがcurrにない場合は、 curr [c]：=新しいマップ curr：=curr [c] curr [*]：=True

  2. PythonでnノードのBSTの数をカウントするプログラム

    n個の異なるノードがあるとします。すべてが異なります。二分探索木を形成するためにそれらを配置できる方法の数を見つける必要があります。二分探索木で知っているように、左側のサブツリーは常に小さい値を保持し、右側のサブツリーは大きい値を保持します。 これを解決するために、カタラン数を見つけます。カタラン数C（n）は、n個の異なるキーを持つ二分探索木を表します。式は次のようになります $$ C（n）=\ frac {（2n）！} {（n + 1）！\ times n！} $$ したがって、入力がn =3の場合、出力は5になります。 これを解決するには、次の手順に従います- 関数ncr