数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：查找平方数组的数量
假设我们想要创建一个由小写字母组成的目标字符串。首先，我们有一个序列，其中包含n个'?'标记（n是目标字符串的长度）。我们还有一个由小写字母组成的小印章。每一轮，我们都可以将印章放在序列上，并用印章中对应的字母替换序列中的每个字母。你可以最多进行10 * n轮。
例如，如果初始序列是“?????”，印章是“abc”，那么我们可以在第一轮中创建“abc??”、“?abc?”、“??abc”之类的字符串。如果序列可以被印章盖印，则返回一个数组，其中包含每一轮最左边被盖印字母的索引。如果不可能，则返回一个空数组。因此，当序列是“ababc”，印章是“abc”时，答案可以是[0, 2]，因为我们可以这样形成：“?????” -> “abc??” -> “ababc”。
因此，如果输入类似于s = "abcd" t = "abcdbcd"，则输出将为[3,0]
为了解决这个问题，我们将遵循以下步骤：
如果s的大小为1，则
返回一个从0到t的列表，当t中的所有字符都相同且它们都是s[0]时，否则返回一个新的空列表。
ans := 一个新的列表
当t不等于t大小的'?'标记数时，执行以下操作：
tmp := t
对于范围从0到s大小的i，执行以下操作：
对于范围从s大小到i+1的j
search := i个'?'连接s[从索引i到j-1的子字符串]连接(s的大小 - j)个'?'
当search在t中时，执行以下操作：
将search在t中出现的位置插入到ans的末尾。
t := 将search替换为s大小的'?'（只替换一次）。
如果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]
更新于：2021年10月7日
91 次查看
广告