Pythonのサブリスト合計操作を使用して1つのリストを他のリストと同一に変換するプログラム

2つのリストl1とl2があるとすると、この操作を繰り返し適用してリストを等しくする必要があります-サブリストを選択し、サブリスト全体をその合計に置き換えます。最後に、上記の操作を適用した後、可能な限り長い結果のリストのサイズを返します。解決策がない場合は、-1を返します。

したがって、入力がl1 =[1、4、7、1、2、10] l2 =[5、6、1、3、10]の場合、この操作を次のように実行するかのように、出力は4になります。次の-

• l1のサブリスト[1、4]を取得すると、[5、7、1、2、10]が得られます
• l1のサブリスト[1、2]を取得すると、[5、7、3、10]が得られます
• l2のサブリスト[6、1]を取得すると、[5、7、3、10]になります。

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

• i：=l1のサイズ-1、j：=l2のサイズ-1、res：=0
• i>=0およびj>=0の場合、do
  • l1[i]がl2[j]と同じ場合、
    • res：=res + 1、i：=i --1、j：=j-1
  • それ以外の場合、l1 [i]
  • i> 0がゼロ以外の場合、
    • l1 [i-1]：=l1 [i-1] + l1 [i]
  • i：=i-1
• それ以外の場合、l1 [i]> l2 [j]の場合、
  • j> 0の場合、
    • l2 [j-1]：=l2 [j-1] + l2 [j]
  • j：=j-1

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

例

class Solution:
   def solve(self, l1, l2):
      i, j, res = len(l1) - 1, len(l2) - 1, 0
      while i >= 0 and j >= 0:
         if l1[i] == l2[j]:
            res, i, j = res + 1, i - 1, j - 1
         elif l1[i] < l2[j]:
            if i > 0:
               l1[i - 1] += l1[i]
            i -= 1
         elif l1[i] > l2[j]:
            if j > 0:
               l2[j - 1] += l2[j]
            j -= 1
         return res if i == -1 and j == -1 else -1
ob = Solution()
l1 = [1, 4, 7, 1, 2, 10]
l2 = [5, 6, 1, 3, 10] print(ob.solve(l1, l2))

入力

[1, 4, 7, 1, 2, 10], [5, 6, 1, 3, 10]

出力

4