資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告