剑指Offer 二


剑指Offer 二

0-n-1中缺失的数字

class Solution(object):
    def missingNumber(self, nums):
        lenth = len(nums)
        left, right = 0, lenth-1

        while left<right:
            mid = (left + right)/2
            if nums[mid] == mid:
                left = mid + 1
            else:
                right = mid
        if nums[left] == left:
            return left+1
        else:
            return left

剪绳子I

class Solution(object):
    def cuttingRope(self, n):
        dp = [0 for _ in range(n+1)]
        dp[2] = 1
        for i in range(3, n + 1):
            for j in range(i):
                dp[i] = max(dp[i], max((i - j) * j, j * dp[i - j]))
        return dp[n]
class Solution:
    def cuttingRope(self, n):
        dp = [0, 1, 1]

        for i in range(3, n + 1):
            dp[i % 3] = max(max(dp[(i - 1) % 3], i - 1),
                    2 * max(dp[(i - 2) % 3], i - 2),
                    3 * max(dp[(i - 3) % 3], i - 3))
        return dp[n % 3]

二叉树的镜像

class Solution(object):
    def mirrorTree(self, root):
        if root == None or (root.left == None and root.right == None):
            return root
        mytree = root 
        temp = mytree.right
        mytree.right = mytree.left
        mytree.left = temp

        if mytree.left:
            self.mirrorTree(mytree.left)
        if mytree.right:
            self.mirrorTree(mytree.right)
        return mytree
class Solution(object):
    def mirrorTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        root.left,root.right = root.right,root.left
        self.mirrorTree(root.left)
        self.mirrorTree(root.right)
        return root

文章作者: Nczkevin
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Nczkevin !
评论
 上一篇
关于KBQA的一些总结 关于KBQA的一些总结
关于KBQA的一些总结什么是基于知识图谱的问答(KBQA)?KBQA–knowledge base question answering,通过对问题进行语义理解及解析,通过知识库进行查询。 KBQA的基本要素:输入:自然语言问句,例如“姚明
2019-09-21
下一篇 
jupyter 添加虚拟环境 jupyter 添加虚拟环境
jupyter 添加虚拟环境使用jupyter会遇到这样一个问题,在anaconda中创建了多个环境,启动jupyter notebook后,在new的下拉菜单中却找不到。本文就解决这样的问题。 解决方法假如我现在anaconda默认的是p
2019-03-16
  目录