每周一课:L90 Tasks from Indeed Prime

作者: AiFany | 来源:发表于2019-02-26 15:01 被阅读1次
    0.png
    P90.3 SlalomSkiing

    Given a sequence, find the longest subsequence that can be decomposed into at most three monotonic parts.

    • P90.3 障碍滑雪
      给定一个序列,找出最多可分解为三个单调部分的最长子序列

    一个参加障碍滑雪的运动员。滑雪跑道位于一个斜坡上,并且两侧用栅栏围起来。跑道上设置有N个障碍门。每个障碍门的位置都垂直于斜坡顶部的起始线。 每个障碍门与起始线、右栅栏(从起始线向下看时的右方)的距离都不同。可以从起始线上的任何地方出发,滑下赛道,尽可能多地通过障碍门,最终到达终点线。 通过障碍门意味着要滑过障碍门的位置。

    开始滑时可以从两个方向滑下:向左或向右。当运动员滑到左边时,会通过与右栅栏的距离较大的障碍门,当滑到右边时,会通过与右边栅栏的距离较小的障碍门。开始滑动的方向固定为向左

    需要说明的是,频繁改变方向(从左到右或从右到左)是不被允许的的,规定运动员整个滑雪过程中最多改变两次方向。目标是计算经过最多两次方向的变化,通过障碍门的最大数量。障碍门的设置由N个整数组成的数组A给出,数组的元素指定了障碍门的位置: (0 ≤ K < N)号障碍门与起跑线的距离为K+1,与右边栅栏的距离为A[K]。

    例如,考虑数组A,其中N=13:
    A[0] = 15,A[1] = 13,A[2] = 5,A[3] = 7,A[4] = 4,A[5] = 10,A[6] = 12,A[7] = 8,A[8] = 2,A[9] = 11,A[10] = 6, A[11] = 9,A[12] = 3

    90.3.11.png

    上图数组A中记录的障碍门的位置和一条经过8个障碍门的路线的示例轨迹。开始后,向左滑雪(从运动员的角度),经过2、3、5、6号障碍门,然后向右改变方向。 在那之后,可以经过7号门,8号障碍门,然后向左转。最后,经过10号,11号障碍门,到达终点线完成整个过程。最多经过两次方向的变化,无法通过更多的门,因此8是最大值。

    编写函数:

    def solution(A)
    

    给定一个由N个整数组成的数组A,则返回可以通过的最大障碍门数。例如,针对上面的示例,函数应该返回8。对于数组A:A[0]=1, A[1]=5,应返回2。

    假定:

    1. N是区间[1,100,000]内的整数;
    2. 数组A的每个元素都是区间[1,1,000,000,000]内的整数;
    3. 数组A的元素都是不同的;
    • 解题思路

    对于给定的数组A,其实本题要解决的是:三个连续(所谓连续,就是前一个序列的最后一个元素就是后一个序列的第一个元素)的单调序列中包含元素的最大个数。并且开头和结尾都是递增序列,中间的是递减序列。假设对于数组A而言,下图绿色线段所示的序列为满足条件的最大序列:

    image

    如上图所示,黑色的点代表原始数据中的但不是满足条件的序列中的点。绿色实线上的点为满足条件的序列中的点。红色虚线上的点为数组转换后的对应点。上图描述的是,将原始数组经过转换,把原始数组中的递增、递减、递增序列转变为递增序列。然后再针对得到的数组计算最大递增子序列,从而得到最终的答案。现在的问题是如果进行转换,而不会影响最终的结果。下面给出一种方式:

    首先考虑中间的递减序列,因为递减变递增,肯定要将原来递减的数变为其相反数,也就是数组A中的元素S,变为-S,此外这个序列要大于第一个递增序列中的元素。假设数组A的元素最大值为M,M+M-S>=S肯定成立,因此M+M-S可看作一种转换。考虑到最后的递增序列,M+M+S>=M+M-S肯定成立,所以M+M+S也是一种转换。所以遍历数组A中的元素S,首先添加M+M+S,然后添加M+M-S,最后添加S构成新的数组B,然后针对B计算最大递增子序列。之所以先添加M+M+S,是因为所求的是递增序列,后加的话会影响结果。

    关于计算最大递增子序列有2种算法,分别是时间复杂度为O(N*logN)的基于二分查找+动态规划的算法的和时间复杂度为O(N**2)的单纯的动态规划算法。

    • Python3代码
    # -*- coding:utf-8 -*-
    # &Author  AnFany
    # Lesson 90:Tasks from Indeed Prime 2015 challenge
    # P 90.3 SlalomSkiing
    
    
    def longest_increasing_subsequence_dp(a):
        """
        利用动态规划算法,计算最长的递增子序列
        时间复杂度o(N**2)
        :param a: 数组a
        :return: 最长递增子序列的长度
        """
        length = len(a)
        save_max = [1] * length
        for i in range(1, length):
            for j in range(i):
                if a[i] > a[j] and save_max[j] + 1 > save_max[i]:
                    save_max[i] = save_max[j] + 1
        return max(save_max)
    
    
    def longest_increasing_subsequence_bs(a):
        """
        利用二分查找算法+动态规划,计算最长的递增子序列
        时间复杂度o(N*logN)
        :param a: 数组a
        :return: 最长递增子序列的长度
        """
        num_list = [-1, a[0]]   # 添加-1是为了二分查找的时候,要保证num_list[j-1]是存在的
        for i in a[1:]:
            if i > num_list[-1]:
                num_list.append(i)
            elif i < num_list[-1]:  # 使用二分查找算法,在num_list查找第一个不小于i的数,并替换之
                # 也就是寻找使得num_list[j-1] < i,并且num_list[j] >= i的j,然后令num_list[j] = i
                # 注意数组a中可能存在相同的元素
                start = 0
                end = len(num_list) - 1
                sign = 0
                middle = 0
                while start <= end:
                    middle = int((start + end) / 2)
                    if num_list[middle] < i:
                        start = middle + 1
                    elif num_list[middle] > i:
                        end = middle - 1
                    else:
                        sign = 1  # 恰好相等的时候
                        break
                if sign:
                    num_list[middle] = i
                else:
                    num_list[start] = i
        return len(num_list) - 1
    
    
    def solution(A):
        """
        给定数组,找出最多可分解为三个单调部分的最长子序列
        :param A: 数组
        :return: 三个单调部分的最长子序列
        """
        max_num = max(A)   # 数组trans中会存在相同的元素
        trans = []
        for i in A:
            trans.append(max_num + max_num + i)
            trans.append(max_num + max_num - i)
            trans.append(i)
        return longest_increasing_subsequence_bs(trans)
    

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

    image image

    相关文章

      网友评论

        本文标题:每周一课:L90 Tasks from Indeed Prime

        本文链接:https://www.haomeiwen.com/subject/govayqtx.html