Leetcode Binary Search 50, 222 @Python－CONY的世界

50. Pow(x, n)

Implement pow(x, n).

Success:

56 ms, beats 14.53 % of python submissions

先用最簡單的方式做

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        return x**n

當然我知道這不會是最快的做法啦，而且這跟binary search 也沒關係

參考做法是這個，ex. 3^5 = 3^(2^0) + 3^(2^2)

對power去做二次方拆解 ex. 5 = 2^0 + 2^2 ，然後底數不斷double，如果有對應的power 就乘上去

36 ms, beats 83.72 % of python submissions

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        pow_time = abs(n)
        value = 1
        while pow_time:
            if pow_time & 1:
                value *= x
            x *= x
            pow_time >>= 1
        return value if n > 0 else (1/value)

222. Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Success:

176 ms, beats 60.67 % of python submissions


 一開始只想到depth first search 然後就time exceed （死...)
這邊參考用的想法很妙

compare the depth between left sub tree and right sub tree.
A, If it is equal, it means the left sub tree is a full binary tree
B, It it is not , it means the right sub tree is a full binary tree

基本上就是先比較 tree 兩邊有沒有等長，如果左樹最左長度 ＝ 左樹最左長度 ＝ h，表示可能沒有滿的在右樹，而左樹是全滿的 h高 complete binary tree

如果左樹最左長度（ h）＝\=  左樹最左長度（h-1） ，表示可能沒有全滿的在左數，而右樹會是h-1 高的 complete binary tree

之後再針對沒滿的 tree 迭代下去算，直到算完

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def getHeight(self, root):
        if not root:
            return 0
        height = 0
        while root:
            root = root.left
            height += 1
        return height
    
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        height = 0
        while root:
            [r, l] = map(self.getHeight, [root.right,root.left])
            if r == l:          #left subtree is complete binary search tree
                height += 2**l
                root = root.right
            else:          #right subtree is complete binary search tree
                height += 2**r
                root = root.left
        return height