Codility每周一课：L10 Prime and compo

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。

假定：

1. N是区间[1，400000]内的整数；
2. 数组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