剑指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