Codility每周一课：L10 Prime and compo

0.png

P10.3 Peaks

Divide an array into the maximum number of same-sized blocks, each of which should contain an index P such that A[P - 1] < A[P] > A[P + 1].

• P10.3 峰值
  将数组分为具有同样元素个数的块，每个块至少包括一个使得A[P - 1] < A[P] > A[P + 1]的峰值。

由N个整数组成的非空数组A。峰值是一个索引P， 其满足0 < P < N − 1, A[P − 1] < A[P]和A[P]>A[P+1]。

例如，数组A：
A[0] = 1，A[1] = 2，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
正好有三个峰值：3、5、10。

要将这个数组分成包含相同元素个数的块。更准确地说，我们要选择一个K数，它将产生以下块：
A[0], A[1], ..., A[K − 1]；
A[K], A[K + 1], ..., A[2K − 1]；
...
A[N − K], A[N − K + 1], ..., A[N − 1].

更重要的是，每个块至少应该包含一个峰值。请注意，块的两端的元素（例如A[K-1]、A[K]、A[N − K]）也可以是峰值，但前提是它们都要有2个邻居（也可以是相邻块中的邻居）。
目标是找到数组A可以划分的最大块数。
示例中的数组A可以分为以下块：

• 一块（1、2、3、4、3、4、1、2、3、4、6、2）。这个块有三个峰值。
• 两块（1、2、3、4、3、4）和（1、2、3、4、6、2）。每个块都有一个峰值。
• 三块（1、2、3、4）、（3、4、1、2）、（3、4、6、2）。每个块都有一个峰值。特别注意，第一个块（1、2、3、4）在[3]处有峰值，因为A[2]<A[3]，并且A[3]>A[4]，即使[4]在相邻区块中。

但是，数组A不能分为四个块（1、2、3）、（4、3、4）、（1、2、3）和（4、6、2），因为（1、2、3）块不包含峰值。请特别注意，（4，3，4）块包含两个峰值：A[3]和A[5]。因此数组A可分为块的最大数目为3。

编写函数：

def solution(A)

给定由N个整数组成的非空数组A，则返回可将A划分为块的最大数。如果A不能划分为若干块，则函数应返回0。
例如，针对上面的例子，函数应该返回3。

假定：

1. N是区间[1，100000]内的整数；
2. 数组A的每个元素都是区间[0，100000000]内的整数；

• 解题思路
  首先得出数组A的峰值序列。因为要把数组A平均分成块，因此块数为数组A的因子。另外每个块都至少有一个峰值，因此因子数不能大于峰值数。如果要分为M个块，每个块中包括G个元素，则所有峰值除以G的余数，只要从0到M-1均有，则就能保证每个块中肯定至少包含一个峰值。
  Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 10：Prime and composite numbers
# P 10.3 Peaks


def factor_no_one(N, p_count):
    """
    返回N的所有因子, 大于1，不大于P_count的因子序列
    :param N: 正整数N，大于等于2
    :param p_count: 峰值的个数
    :return: 返回N的所有不为1，并且不大于p_count的因子
    """
    factor_dict = {}
    for i in range(2, min(int(N ** 0.5), p_count) + 1):
        if N % i == 0 :
            if i not in factor_dict:
                factor_dict[i] = 0
            j = N / i
            if j == int(j) and int(j) not in factor_dict and j <= p_count:
                factor_dict[int(j)] = 0
    return list(factor_dict.keys()) + [N]


def solution(A):
    """
    将数组A切割成同等元素个数的块的最大个数,时间复杂度O(N * log(log(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
    length = len(peaks_list)  # 峰值的个数
    if length == 0:
        return 0
    elif length == 1:
        return 1
    else:
        length_a = len(A)  # 数组中所有元素的个数
        factor_list = factor_no_one(length_a, length)  # 元素个数的因子序列
        block_list = [1]  # 存储可能的块数
        for i in factor_list:
            #  每个块含有的元素的个数
            block_count = int(length_a / i)
            #  判断是否每个块都会有峰值
            blocks = [0] * i
            for j in peaks_list:
                blocks[j // block_count] = 1
            if 0 not in blocks:
                block_list.append(i)
        return max(block_list)

• 结果
  image

点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image