0.png
P14.1 NailingPlanks
Count the minimum number of nails that allow a series of planks to be nailed.
-
P14.1 钉木板
计算钉牢所有木板需要的钉子的最小数量
两个非空数组A和B，均由N个整数组成，这些数组表示N个木板。更准确地说，A[K]是第K个木板的起点，B[K]是终点。
一个由M个整数组成的非空数组C，这个数组表示M个钉子。更准确地说，C[I]是可以钉入第I个钉子的位置。
如果存在钉子c[I]，对于任意的K，只要满足A[K] ≤ C[I] ≤ B[K]，就表示木板(A[K], ****B[K])可以被钉牢。
目标是找到使得所有木板都被钉牢，所使用的最小钉子数量。换句话说，应该找到一个值J，这样在只使用前J个钉子之后所有木板都被钉牢了。也就是说，对于每一块木板(A[K], B[K])，其中0 ≤ K < N，应该存在一个钉子C[I] ，使得I < J和A[K] ≤ C[I] ≤ B[K]成立。
例如，给定的数组A、B：
A[0]=1，A[1]=4，A[2]=5，A[3]=8；
B[0]=4，B[1]=5，B[2]=9，B[3]=10
四块木板分别为[1，4]、[4，5]、[5，9]和[8，10]。
给定的数组C：
C[0]=4，C[1]=6，C[2]=7，C[3]=10，C[4]=2
使用以下钉子：
- 使用第1个钉子：[1，4]和[4，5]都被钉牢：因为1<=4<=4，4<=4<=5。
- 使用前2个钉子：木板[1，4]，[4，5]和[5，9]被钉牢。
- 使用前3个钉子：木板[1、4]、[4、5]和[5、9]被钉牢，
- 使用前4个钉子：所有的木板都将被钉牢。
因此，4是使用的最小钉子的数量，可以钉牢所有木板。
编写函数：
def solution(A, B, C)
给定两个由N个整数组成的非空数组A和B,一个由M个整数组成的非空数组C，则返回钉牢所有木板需要使用的最小的钉子数量。如果无法钉牢所有木板，函数应返回-1。
例如，针对上面的例子，函数应返回4。
假定：
- N和M是区间[1，30000]内的整数；
- 数组A、B、C的每个元素都是区间[1，2*M]内的整数；
- A[K] ≤ B[K]；
- 解题思路
用二分法查找，每个木板可以被钉牢需要的钉子数，然后在可以被钉牢的集合中寻找最小的钉子数。也就为每个木板寻找最早的可以钉牢该木板的钉子的位置。最后遍历木板，获取最大的钉子数，即为所求。
- Python3代码
# -*- coding：utf-8 -*-
# &Author AnFany
# Lesson 14：Binary search algorithm
# P 14.1 NailingPlanks
def solution_worst(A, B, C):
"""
数组A、B对应元素代表木板，C元素代表可以钉钉子的位置。计算钉牢所有木板需要的最小的钉子数量。
一般解法：时间复杂度O((N + M) * N)
:param A: 正整数数组
:param B: 正整数数组
:param C: 正整数数组
:return: 最小的钉子数量
"""
D = [0] * len(A)
for index, value in enumerate(C):
for i, j in enumerate(A):
if j <= value <= B[i]:
D[i] = 1
if 0 not in D:
return index + 1
return -1
def solution_worse(A, B, C):
"""
数组A、B对应元素代表木板，C元素代表可以钉钉子的位置。计算钉牢所有木板需要的最小的钉子数量。
一般解法：时间复杂度O(N * M)
:param A: 正整数数组
:param B: 正整数数组
:param C: 正整数数组
:return: 最小的钉子数量
"""
for index, value in enumerate(C):
if A:
DA = []
DB = []
for i, j in enumerate(A): # 这一步可以进行二分查找优化
if j > value or value > B[i]:
DA.append(j)
DB.append(B[i])
A = DA.copy()
B = DB.copy()
if not A:
return index + 1
return -1
def binary_search(nails, start, end, compare_num):
"""
为每个木板计算可以钉牢该木板的第一个出现的钉子位置
:param nails: 按照钉子可以钉的位置顺序排列的二位数组
:param start: 木板的起始点
:param end: 木板的终点
:param compare_num: 之前的所有木板需要的最小的钉子数
:return: 第一次可以被钉子钉牢的钉子的位置
"""
length = len(nails)
# 进行二分查找法
b_s_start = 0
b_s_end = length - 1
nailed_position = -1
search_min = 0
while b_s_start <= b_s_end:
b_s_middle = int((b_s_start + b_s_end) / 2)
number = nails[b_s_middle][1]
if number < start: # 钉子位置小于木板起始点
b_s_start = b_s_middle + 1
elif number > end: # 钉子位置大于木板终点
b_s_end = b_s_middle - 1
else: # 可以被钉牢
nailed_position = nails[b_s_middle][0] # 钉子序列中的前nailed_position个钉子，可以将这个木板钉牢
# 但是b_s_middle并不一定是最小的，导致nailed_position也不一定是最小的。b_s_end需要继续减小
b_s_end = b_s_middle - 1
search_min = b_s_middle
if nailed_position == -1: # 这个木板不能被钉牢
return -1
# 下面从最小的可以钉牢该木板的b_s_middle开始，寻找最小的nailed_position数。
else:
search_min += 1 # 因为b_s_middle处的钉子的个数值为nailed_position
while search_min < length:
if nails[search_min][1] > end: # 之后的钉子都不可能钉牢该木板
break
# 如果可以钉牢，则选择较小的nailed_position，也就是按顺序的钉子的数最小
nailed_position = min(nailed_position, nails[search_min][0])
if nailed_position <= compare_num: # 小于之前木板所需要的钉子数可以钉牢该木板的话，就停止计算即可
return compare_num
search_min += 1 # 继续搜索，寻找最小的nailed_position
return max(nailed_position, compare_num) # 返回
def solution(A, B, C):
"""
数组A、B对应元素代表木板，C元素代表可以钉钉子的位置。计算钉牢所有木板需要的最小的钉子数量。
二分法查找：时间复杂度O((N + M) * log(M))
:param A: 正整数数组
:param B: 正整数数组
:param C: 正整数数组
:return: 最小的钉子数量
"""
nails_c = sorted(enumerate(C), key=lambda x: x[1]) # 按照值的大小排列，索引是无序的。索引代表着前几个钉子
result = -1
for i in range(len(A)):
result = binary_search(nails_c, A[i], B[i], result)
if result == -1:
return -1
return result + 1 # 因为索引从0开始，因此需要加1
- 结果
image
点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。
image
image
网友评论