資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢最多可放入其他盒子中的盒子數量
假設我們有一個盒子列表，其中每一行代表給定盒子的高度和寬度。如果第一個盒子小於第二個盒子（當它的寬度和高度都小於另一個盒子時），我們可以將一個盒子放入另一個盒子中，我們必須找到可以放入一個盒子中的最大盒子數。
因此，如果輸入類似於
| 寬度 | 高度 |
| 12 | 12 |
| 10 | 10 |
| 6 | 6 |
| 5 | 10 |
則輸出將為 3，因為我們可以將盒子 [6, 6] 放入 [10, 10] 中，該盒子可以放入 [12, 12] 盒子中。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式 insert_index()。這將獲取 arr 和 this_h。
- l := 0
- r := arr 的大小 - 1
- res := 0
- 當 l <= r 時，執行以下操作
- m := l +(r - l) // 2
- cur_h := arr[m]
- 如果 cur_h < this_h 不為零，則
- res := m
- l := m + 1
- 否則，
- r := m - 1
- 返回 res + 1
- 從主方法中，執行以下操作
- 根據寬度對矩陣進行排序，如果寬度相同，則根據高度對其進行排序
- n := 矩陣中專案的數量
- heights := 一個大小為 (n + 1) 的列表，並將其填充為 inf
- heights[0] := -inf
- res := 0
- 對於矩陣中的每個盒子，執行以下操作
- [cur_w, cur_h] := 盒子
- index := insert_index(heights, cur_h)
- 如果 heights[index] >= cur_h，則
- heights[index] := cur_h
- res := res 和 index 的最大值
- 返回 res
讓我們看看以下實現以獲得更好的理解：
示例
class Solution:
def solve(self, matrix):
matrix = sorted(matrix, key=lambda x: (x[0], -x[1]))
n = len(matrix)
heights = [float("inf")] * (n + 1)
heights[0] = float("-inf")
res = 0
for box in matrix:
cur_w, cur_h = box
index = self.insert_index(heights, cur_h)
if heights[index] >= cur_h:
heights[index] = cur_h
res = max(res, index)
return res
def insert_index(self, arr, this_h):
l = 0
r = len(arr) - 1
res = 0
while l <= r:
m = l + (r - l) // 2
cur_h = arr[m]
if cur_h < this_h:
res = m
l = m + 1
else:
r = m - 1
return res + 1
ob = Solution()
matrix = [
[12, 12],
[10, 10],
[6, 6],
[5, 10]
]
print(ob.solve(matrix))輸入
matrix = [ [12, 12], [10, 10], [6, 6], [5, 10] ]
輸出
3
更新於: 2020年12月2日
962 次檢視
廣告