Codility每周一课:L7 Stacks and Queue

作者: AiFany | 来源:发表于2019-01-28 22:42 被阅读4次
    7.png
    P7.4 StoneWall

    Cover "Manhattan skyline" using the minimum number of rectangles.

    • P7.4 石墙
      用最少的矩形覆盖“曼哈顿天际线”

    要建一面长N米的石墙。石墙墙壁笔直,厚度不变,但不同地方的高度不同。由N个正整数组成的数组H,代表石墙的不同地方的高度。H[I]表示墙从I到I+1米处的高度。特别地,H[0]是墙最左端到1米处的高度,H[N-1]是墙N-1米处到最右端的高度。

    墙体应采用长方体石块(即,此类石块的所有侧面均为矩形)。目标是计算构建墙所需的最小块数。

    编写函数

    def solution(H)
    

    给定一个由N个正整数组成的数组H,指定墙的高度,则返回构建墙所需的最小块数。

    例如,给定包含N=9个整数的数组H:

    H[0] = 8,H[1] = 8,H[2] = 5,H[3] = 7,H[4] = 9,H[5] = 8,H[6] = 7,H[7] = 4,H[8] = 8

    要建立的石墙见下图:

    image

    下图显示了七个石块所有布局中的3种:

    image

    因为七个石块是最小的,因此函数应返回7。

    假定:

    1. N是区间[1,100000]内的整数;

    2. 数组H的每个元素都是区间[1,100000000]内的整数;

    • 解题思路
    image

    如上图,遍历高度数组,如果当前高度大于上一个高度,就添加到列表中;等于的话,就可以视为一个,不用考虑;小于的话,此处需要添加新的矩形了,就等于在这个高度上横切。前面有几个大于他的高度,就需要为这几个高度添加覆盖他们的矩形。因为已经为他们添加过矩形,所以以后就不用考虑了。 然后把当前高度添加到列表中即可。

    • Python3代码
    # -*- coding:utf-8 -*-
    # &Author  AnFany
    # Lesson 7:Stacks and Queues
    # P 7.4 StoneWall
    
    
    def solution(H):
        """
        返回构成石墙H,所需要的最小的矩形石块的个数
        :param H: 代表石墙的高度数组
        :return: 返回矩形石块的个数
        """
        stone_count = 0
        stone_list = []
        for i in H:
            while len(stone_list) != 0 and stone_list[-1] > i:
                stone_list.pop(-1)
                stone_count += 1
            if len(stone_list) == 0 or i > stone_list[-1]:
                stone_list.append(i)
        stone_count += len(stone_list)
    
        return stone_count
    
    • 结果
    image

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

    image image

    相关文章

      网友评论

        本文标题:Codility每周一课:L7 Stacks and Queue

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