Codility每周一课：L10 Prime and compo
2019-01-29 本文已影响4人
AiFany
0.png
P10.4 Flags
Find the maximum number of flags that can be set on mountain peaks.
-
P10.4 旗标
找到可以在山峰上设置的最大旗标数
由N个整数组成的非空数组A。峰值是索引P，其满足 0 < P < N − 1 和A[P − 1] < A[P] > A[P + 1]。
例如，数组A：
A[0]=1，A[1]=5，A[2]=3，A[3]=4，A[4]=3，A[5]=4，A[6]=1，A[7]=2，A[8]=3，A[9]=4，A[10]=6，A[11]=2。正好有四个峰值：索引1、3、5和10。
某人带了一些旗标前往某山，这些山峰的高度由数组A表示，山峰如下图所示：
image
计算可以在山峰上设置的最大旗标数。
旗标只能在山峰上设置。此外，如果带了K个旗标，则任意2个旗标的索引距离应不小于K。索引P和Q之间的距离是|P − Q|。
例如，使用数组A表示不同山峰的高度，山峰数N=12，如果某人带了：
- 2个旗标，可以把它们设置在1号和5号山峰上，或者在3号和10号山峰上， 或者1号和10号山峰上；
- 3个旗标，可以在1、5和10号山峰上设置它们；
- 4个旗标，只能在1、5和10号山峰上设置三个旗标。
因此，在这种情况下最多可以设置3个旗标。
编写函数：
def solution(A)
给定一个由N个整数组成的，代表山峰高度的非空数组A，则返回可以在这些山峰上设置的最大旗标数。
例如，针对上例函数应该返回3。
假定：
- N是区间[1，400000]内的整数；
- 数组A的每个元素都是区间[0，100000000]内的整数。
- 解题思路
首先得出峰值序列P。根据峰值序列的第一个值和最后一个值可以判断，理论上的最大旗标数为K：K*(K-1)<=P[-1] - P[0]=dis。所以K的最大值为int(sqrt(dis) +1)。然后从K的最大值开始，遍历峰值序列，只要满足距离不大于K，就视为可以设置旗标，最后只要旗标的个数不小于K值，就返回。
- Python3代码
# -*- coding：utf-8 -*-
# &Author AnFany
# Lesson 10：Prime and composite numbers
# P 10.4 Flags
def solution(A):
"""
数组A代表的山峰高度的山上，可以设置旗标的最大个数,时间复杂度O(N)
:param A: 数组
:return: 旗标的最大个数
"""
peaks_list = [] # 存储峰值的序列
for index, value in enumerate(A):
if index != 0:
try:
if value > A[index - 1] and value > A[index + 1]:
peaks_list.append(index)
except IndexError:
break
if len(peaks_list) == 0:
return 0
elif len(peaks_list) == 1:
return 1
else:
max_k = int((peaks_list[-1] - peaks_list[0]) ** 0.5 + 1) # 理论上可以带的最大旗标数
for i in range(max_k, 1, -1):
address_flag = [peaks_list[0]]
for val in peaks_list[1:]:
if val - address_flag[-1] >= i:
address_flag.append(val)
if len(address_flag) >= i:
return i
return 1
- 结果
image
点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。
image
image
