資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：計算將硬幣分配給工人的方法數
假設我們有兩個正數列表，分別稱為coins和salaries。其中coins[i]表示硬幣i的值，salaries[j]表示支付給工人j所需的最低工資。現在假設每種型別的硬幣只有一個，並且必須給每個工人正好一枚硬幣，我們需要計算將硬幣分配給每個工人的方法數。如果某個工人在一種方法中收到一種型別的硬幣，而在另一種方法中收到另一種型別的硬幣，則這兩種方法不同。如果結果非常大，則返回結果模10^9+7。
所以，如果輸入類似於coins = [1, 2, 3]，salaries = [1, 2]，則輸出將是4，因為如果我們不使用第一個硬幣（值1），則兩個硬幣對兩個工人都有效，因此有兩種支付工人的方法。現在，如果我們使用第一個硬幣，那麼它只能給第一個工人，然後我們可以使用任何一個剩餘的硬幣來支付第二個工人。因此有四種方法。
為了解決這個問題，我們將遵循以下步驟：
- 對列表coins進行排序，並對列表salaries進行排序。
- num_coins := coins的大小。
- num_salaries := salaries的大小。
- dp := 一個新的對映。
- 對於salaries中的每個工資，執行以下操作：
- l := 0，r := num_coins - 1。
- idx := num_coins。
- 當l <= r時，執行以下操作：
- m := l +(r - l) / 2。
- 如果coins[m] >= salary，則：
- idx := m。
- r := m - 1。
- 否則：
- l := m + 1。
- 如果idx與num_coins相同，則：
- 返回0。
- dp[salary] := idx。
- res := 1。
- 對於從num_salaries - 1到0的範圍內的i，遞減1，執行以下操作：
- salary := salaries[i]。
- idx := dp[salary]。
- res := res *(num_coins - idx + 1) -(num_salaries - i)。
- 返回res模10^9+7。
讓我們看看以下實現，以便更好地理解：
示例
class Solution:
def solve(self, coins, salaries):
coins.sort()
salaries.sort()
num_coins = len(coins)
num_salaries = len(salaries)
dp = {}
for salary in salaries:
l = 0
r = num_coins - 1
idx = num_coins
while l <= r:
m = l + (r - l) // 2
if coins[m] >= salary:
idx = m
r = m - 1
else:
l = m + 1
if idx == num_coins:
return 0
dp[salary] = idx
res = 1
for i in range(num_salaries - 1, -1, -1):
salary = salaries[i]
idx = dp[salary]
res *= (num_coins - idx + 1) - (num_salaries - i)
return res % (10**9+7)
ob = Solution()
coins = [1, 2, 3]
salaries = [1, 2]
print(ob.solve(coins, salaries))輸入
[1, 2, 3],[1, 2]
輸出
4
更新於: 2020年10月20日
274 次瀏覽
廣告