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

Pythonで最も長いバランスの取れたサブシーケンスの長さを見つけるプログラム

括弧「（」および「）」を含む文字列sがあるとすると、バランスの取れた括弧の最長のサブシーケンスの長さを見つける必要があります。

したがって、入力がs ="（））（（）（"の場合、出力は4になります。これは、 "（）（）"

のようなサブシーケンスを取ることができるためです。

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

  • res：=0

  • n：=sのサイズ

  • close：=0

  • n-1から0の範囲のiの場合、1ずつ減らします。

    • s[i]が"）"と同じ場合、

      • close：=close + 1

    • それ以外の場合

      • 近い場合>0の場合、

        • close：=close-1

        • res：=res + 2

  • 解像度を返す

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

例

class Solution:
   def solve(self, s):
      res = 0
      n = len(s)
      close = 0
      for i in range(n - 1, -1, -1):
         if s[i] == ")":
            close += 1
         else:
            if close > 0:
               close -= 1
                  res += 2
            return res
ob = Solution()
s = "())(()("
print(ob.solve(s))

入力

"())(()("

出力

4

  1. Pythonで最長の連続シーケンスの長さを見つけるプログラム

    並べ替えられていない数値の配列があるとすると、連続する要素の最長シーケンスの長さを見つける必要があります。 したがって、入力がnums =[70、7、50、4、6、5]の場合、連続する要素の最長シーケンスは[4、5、6、7]であるため、出力は4になります。したがって、その長さを返します：4。 これを解決するには、次の手順に従います- nums：=numsのすべての一意の要素 max_cnt：=0 numsのnumごとに、実行します num-1がnumsにない場合、 cnt：=0 numがnumsに存在する間、実行します num：=num + 1

  2. Pythonで最長のアナグラムサブシーケンスの長さを見つけるプログラム

    2つの小文字の文字列SとTがあるとすると、最長のアナグラムサブシーケンスの長さを見つける必要があります。 したがって、入力がS =helloworld、T =hellorldの場合、出力は8になります これを解決するには、次の手順に従います- c：=新しいマップ、d：=新しいマップ 0からaのサイズの範囲のiの場合、実行 cのa[i]の場合、 c [a [i]]：=c [a [i]] + 1 それ以外の場合 c [a [i]]：=1 0からbのサイズの範囲のiの場合、実行 dのb[i]の場合、 d [b [i]]：=