本站消息

站长简介/公众号


站长简介:逗比程序员,理工宅男,前每日优鲜python全栈开发工程师,利用周末时间开发出本站,欢迎关注我的微信公众号:幽默盒子,一个专注于搞笑,分享快乐的公众号

  价值13000svip视频教程,python大神匠心打造,零基础python开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2020-07(10)

2020-08(50)

LeetCode题解(1642):使用梯子和砖块能够到达的最远建筑(Python)

发布于2020-11-09 16:56     阅读(322)     评论(0)     点赞(23)     收藏(1)



题目:原题链接(中等)

标签:贪心算法、堆、二分查找

解法时间复杂度空间复杂度执行用时
Ans 1 (Python) O ( N ) O(N) O(N) O ( N ) O(N) O(N)44ms
Ans 2 (Python)
Ans 3 (Python)

解法一:

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        # 计算翻越高度及翻越数量
        marks = [0]  # 翻越数量
        tasks = [0]  # 翻越高度
        last = heights[0]
        for i in range(1, len(heights)):
            height = heights[i]
            if height <= last:
                marks[-1] = i
            else:
                tasks.append(height - last)
                marks.append(i)
            last = height

        # print(marks, tasks)

        # 贪心攀爬

        now = []  # 当前的需要搭梯子的高度的堆
        heapq.heapify(now)

        total = 0  # 当前用砖块的高度总值

        for idx, task in enumerate(tasks):
            # 当前还有剩余梯子的情况
            if ladders > len(now):
                heapq.heappush(now, task)

            # 当前没有剩余梯子的情况
            else:
                # 如果有梯子的话,检查是否需要替换梯子的位置
                if ladders > 0:
                    smallest = heapq.heappop(now)  # 当前用梯子的最小值

                    # 替换梯子的位置
                    if smallest < task:
                        heapq.heappush(now, task)
                        total += smallest
                    # 不替换梯子的位置
                    else:
                        heapq.heappush(now, smallest)
                        total += task

                # 如果没有梯子的话,直接用砖块
                else:
                    total += task

                # 检查当前砖块是否够用
                if bricks < total:
                    # print("砖块不够用:", idx, now)
                    return marks[idx - 1]

            # print(idx, task, "->", now, total)

        return marks[-1]

原文链接:https://blog.csdn.net/Changxing_J/article/details/109478880






所属网站分类: 技术文章 > 博客

作者:丸子

链接:https://www.pythonheidong.com/blog/article/611542/86bd0bb9c7e8d9d63924/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

23 0
收藏该文
已收藏

评论内容:(最多支持255个字符)