資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：計算從單詞列表和字母計數中可以生成的最大字串數量
假設我們有一個字串列表，其中每個字串包含兩個字母“A”和“B”。我們有兩個值a和b。我們必須找到可以形成的最大字串數量。我們可以最多使用a個“A”和最多b個“B”，無需重複使用。
因此，如果輸入類似於strings = ["AAABB", "AABB", "AA", "BB"] a = 4 b = 2，則輸出將為2，因為我們可以使用4個“A”和2個“B”形成字串 ["AABB","AA"]。
為了解決這個問題，我們將遵循以下步驟：
- pairs := 一個新的列表
- 對於strings中的每個w，執行以下操作：
- A := w中“A”的數量
- B := w的大小 - A
- 在pairs的末尾插入一個(A, B)對
- ans := 一個對映，其中(a, b)的值為0
- 對於pairs中的每個(A, B)對，執行以下操作：
- temp := 從ans複製的一個新的對映
- 對於ans中的每個(temp_a, temp_b)對和值wc，執行以下操作：
- 如果temp_a >= A 且 temp_b >= B，則執行以下操作：
- rem := 一個(temp_a - A, temp_b - B)對
- temp[rem] := temp[rem]（如果rem不存在，則為0）和(wc + 1)中的最大值
- ans := temp
- 如果temp_a >= A 且 temp_b >= B，則執行以下操作：
- 返回ans的所有值的列表中的最大值
讓我們看看以下實現，以便更好地理解：
示例
class Solution:
def solve(self, strings, a, b):
pairs = []
for w in strings:
A = w.count("A")
B = len(w) - A
pairs.append((A, B))
ans = {(a, b): 0}
for A, B in pairs:
temp = dict(ans)
for (temp_a, temp_b), wc in ans.items():
if temp_a >= A and temp_b >= B:
rem = (temp_a - A, temp_b - B)
temp[rem] = max(temp.get(rem, 0), wc + 1)
ans = temp
return max(ans.values())
ob = Solution()
strings = ["AAABB", "AABB", "AA", "BB"]
a = 4
b = 2
print(ob.solve(strings, a, b))輸入
["AAABB", "AABB", "AA", "BB"], 4, 2
輸出
2
更新於: 2020年12月2日
232 次檢視
廣告