在Python中查找方形数组数的程序

在Python中查找方形数组数的程序

假设我们想要制作一个小写字母的目标字符串。起初,我们有一个长度为n的包含n个“?”标记的序列。我们还有一个小写字母的戳。在每个回合中,我们可以将戳放在序列上,并将其中的每个字母替换为相应的戳中的字母。您最多可以进行10 * n次操作。

例如,考虑初始序列为“?????”,戳为“abc”,那么我们可以在第一轮中制作出“abc??”,“?abc?”,“??abc”等字符串。如果可能对序列进行戳,则返回一个索引的数组,左侧的字母为被戳印的字母。如果不可能,则返回一个空的数组。因此,当序列为“ababc”,戳为“abc”时,答案可能如[0,2],因为我们可以形成“?????” – >“abc?” – >“ababc”。

因此,如果输入为s =“abcd”t =“abcdbcd”,则输出将为[3,0]

要解决此问题,我们将执行以下步骤:

  • 如果s的大小与1相同,则
    • 当t中所有字符都相同时,返回从0到t的列表,并且它们是s\[0\],否则返回新的空列表
  • ans:=一个新列表

  • 当t与t号数的“?”标记大小不同时,重复执行以下操作

    • tmp:= t

    • 对于i在0到s的大小的范围内,执行以下操作

      • 对于j在s的大小下降到i + 1的范围内:

      • search:= i个“?”连接s的子字符串\[从下标i到j-1\]连接(s的大小-j)个“?”

      • 当search在t中时,执行以下操作:

        • 将search存在t中的位置插入到ans的末尾

        • 使用s的大小替换search与“?”相同的t仅一次

      • 如果t与t号数的“?”标记大小相同,则

        • 从循环中出来
      • 如果t与t号数的“?”标记大小相同,则
        • 从循环中出来
      • 如果tmp与t相同,则

      • 从循环中出来

  • 返回ans的反转。

示例

让我们看以下实现,以获得更好的理解

def solve(s, t):
   if len(s) == 1:
      return [i for i in range(len(t))] if all(t==s[0] for t in t)else []

   ans = []
   while t != "?" * len(t):
      tmp = t
      for i in range(len(s)):
         for j in reversed(range(i+1, len(s)+1)):
            search = "?" * i + s[i:j] + "?" * (len(s)-j)
            while t.find(search) != -1:
               ans.append(t.find(search))
               t = t.replace(search, "?"*len(s), 1)
            if t == "?" * len(t): break
         if t == "?" * len(t): break
      if tmp == t: return []
   return ans[::-1]

s = "abcd"
t = "abcdbcd"
print(solve(s, t))

输入

"abcd", "abcdbcd"

输出

[3,0]

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程