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

Pythonでyの前にすべてのxを作成するために必要なフリッピングの数をカウントするプログラム

文字xとyを含む小文字の文字列sがあるとします。ここで、単一のxをyに、またはその逆に変更する操作について考えてみます。すべてのxがすべてのyの前に来るように設定するために、その操作を実行するために必要な最小回数を見つける必要があります。

したがって、入力がs ="yxyyyyxyxx"のような場合、出力は4になります。

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

  • y_left：=0

  • x_right：=sの「x」の数、res：=sの「x」の数

  • sの各項目について、実行します

    • アイテムが「x」と同じ場合、

      • x_right：=x_right − 1

    • それ以外の場合

      • y_left：=y_left + 1

    • res：=最小のresと（y_left + x_right）

  • 解像度を返す

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

例

class Solution:
   def solve(self, s):
      y_left = 0
      x_right = res = s.count("x")
      for item in s:
         if item == "x":
            x_right -= 1
         else:
            y_left += 1
         res = min(res, y_left + x_right)
      return res
ob = Solution()
s = "yxyyyyxyxx"
print(ob.solve(s))

入力

"yxyyyyxyxx"

出力

4

  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