vlambda博客
学习文章列表

内容：

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。    ‍

程序：

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    def maxDepth(self, root: TreeNode) -> int:

        if not root:

            return 0

        queue = [root]

        res = 0

        while queue:

            tem = []

            res += 1

            for cur in queue:

                if cur.left:

                    tem.append(cur.left)

                if cur.right:

                    tem.append(cur.right)

            queue = tem

        return res

内容：

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。    ‍

程序：

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:

        def func(nums,root):

            if not nums:

                return

            mid = len(nums) // 2

            root = TreeNode(nums[mid])

            root.left = func(nums[:mid],root.left)

            root.right = func(nums[mid+1:],root.right)

            return root

        return func(nums, TreeNode())

内容：

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。    ‍

程序：

# The isBadVersion API is already defined for you.

# @param version, an integer

# @return a bool

# def isBadVersion(version):

class Solution:

    def firstBadVersion(self, n):

        """

        :type n: int

        :rtype: int

        """

        left = 0

        right = n

        mid = (left + right) // 2

        while left < right:

            mid = (left + right) // 2

            if isBadVersion(mid):

                right = mid

            else:

                left = mid+1

        return right

内容：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

程序：

class Solution:

    def climbStairs(self, n: int) -> int:

        if n == 1:

            return 1

        dp = [0] * n

        dp[0] = 1

        dp[1] = 2

        for i in range(2,n):

            dp[i] = dp[i-1] + dp[i-2]

        return dp[-1]

内容：

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。    ‍

程序：

class Solution:

    def maxProfit(self, prices: List[int]) -> int:

        # res = 0

        # for i in range(len(prices)-1):

        #     res = max(res,max(prices[i+1:])-prices[i])

        # return res

        if not prices:

            return 0

        res = 0

        mi = prices[0]

        for i in range(1,len(prices)):

            res = max(prices[i]-mi,res)

            mi = min(mi,prices[i])

        return res

内容：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。    ‍

程序：

class Solution:

    def rob(self, nums: List[int]) -> int:

        if not nums:

            return 0

        dp = [[0] * len(nums) for _ in range(2)]

        dp[0][0] = nums[0]

        dp[1][0] = 0

        for i in range(1,len(nums)):

            dp[0][i] = max(dp[1][:i])+nums[i]

            dp[1][i] = dp[0][i-1]

        return max(dp[0][-1],dp[1][-1])