資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用Python查詢滿足給定和條件的子序列數量的程式
假設我們有一個名為nums的陣列和另一個值k。我們必須找到nums的非空子序列的數量，使得其最小和最大元素之和小於或等於k。答案可能非常大，所以返回答案模10^9 + 7。
因此，如果輸入類似於nums = [4,6,7,8] k = 11，則輸出將為4，因為存在諸如以下的子序列：
[4]，其中最小值為4，最大值為4，所以4+4 <= 11
[4,6]，其中最小值為4，最大值為6，所以4+6 <= 11
[4,6,7]，其中最小值為4，最大值為7，所以4+7 <= 11
[4,7]，其中最小值為4，最大值為7，所以4+7 <= 11
為了解決這個問題，我們將遵循以下步驟：
對列表nums進行排序
m := 10^9 + 7
left := 0
right := nums的大小 - 1
res := 0
當left <= right時，執行：
如果nums[left] + nums[right] > k，則
right := right - 1
否則，
num_inside := right - left
res :=(res + (2^num_inside) mod m) mod m
left := left + 1
返回res
讓我們看看下面的實現以更好地理解：
示例
def solve(nums, k): nums.sort() m = 10**9 + 7 left = 0 right = len(nums) - 1 res = 0 while(left <= right): if nums[left] + nums[right] > k: right -= 1 else: num_inside = right - left res = (res + pow(2, num_inside, m)) % m left += 1 return res nums = [4,6,7,8] k = 11 print(solve(nums, k))
輸入
[4,6,7,8], 11
輸出
4
更新於：2021年5月29日
526 次瀏覽
廣告