czxttkl

https://leetcode.com/problems/closest-binary-search-tree-value/

import sys
# 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 closestValue(self, root, target):
        """
        :type root: TreeNode
        :type target: float
        :rtype: int
        """
        if root is None:
            return None
        self.m = sys.maxint
        self.helper(root, target)
        return self.closest

    def helper(self, root, target):
        if self.m > abs(root.val - target):
            self.closest = root.val
            self.m = abs(root.val - target)
        
        if root.left and target < root.val:
            self.helper(root.left, target)
        if root.right and target > root.val:
            self.helper(root.right, target)

Idea

If a value is larger than root.val, then difference between the value and any node in the root’s left tree must be larger than that between the value and the root itself. If a value is smaller than root.val, then difference between the value and any node in the root’s right tree must be larger than that between the value and the root itself.

The time complexity of this algorithm is O(logN), where N is the total number of nodes in the BST and we assume the BST is balanced.

Reference

https://leetcode.com/discuss/54438/4-7-lines-recursive-iterative-ruby-c-java-python

https://leetcode.com/discuss/56122/standard-binary-search

Code 1: 

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        if citations is None or len(citations) == 0:
            return 0
        for i in xrange(len(citations)):
            if citations[i] >= len(citations) - i:
                return len(citations) - i
        return 0

Code 2:

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        if citations is None or len(citations) == 0:
            return 0
        left, right = 0, len(citations)-1
        while left < right:
            mid = (left + right) / 2
            if citations[mid] < (len(citations) - mid):
                left = mid +1
            else:
                right = mid - 1
        print left
        if citations[left] >= len(citations) - left:
            return len(citations) - left
        elif left+1 <= len(citations)-1 and citations[left+1] >= len(citations) - left -1: 
            return len(citations) - left -1
        else:
            return 0

Code 3:

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        if citations is None or len(citations) == 0:
            return 0
        left, right = 0, len(citations)-1
        while left <= right:
            mid = (left + right) / 2
            if citations[mid] < (len(citations) - mid):
                left = mid +1
            elif citations[mid] > (len(citations) - mid):
                right = mid - 1
            else:
                return len(citations) - mid
                
        return len(citations) - right- 1

Idea:

Code 1 takes O(N) time to traverse every citation backwards. But actually, since citations are already sorted, you can use binary search to achieve O(logN) time complexity. We will take code 3 for example. (Code 2 is ugly implemented by my intermediate thoughts, so skip it.) We create `left` and `right` pointers. We use `mid` to binary search the correct point `i`, at which we can return len(citations) – i as h-index. `i` should have the following properties:

1. citations[j] < len(citations)-j for j < i
2. citations[k] >= len(citations)-k for k>=i

We have two condition branches in line 13 and line 15. In this way, we always make sure that:

a. `citations[right+1] > len(citations) – right -1` holds.

b. `citations[left-1] < len(citations) – left +1` holds

The last execution of while loop is when left == right == mid: you check `citations[mid] ? len(citations) – mid` the last time:

1. If line 13 holds, you know that current `right` has: `citations[right] < len(citations) – right`. You set `left = mid + 1`. Then the while loop terminates because `left<=right` doesn’t hold anymore. From property a, we know that: `citations[right+1] > len(citations) – right -1`. Therefore we return `len(citations)-right-1` as h-index.
2. If line 15 holds,  you know `right` before set to `mid-1` has: `citations[right] > len(citations) – right`. Then you set `right = mid – 1`. Then the while loop terminates because `left<=right` doesn’t hold anymore. Now, `right = mid – 1 = left – 1`. From property b, we know: `citations[right] < len(citations) – right`. So we still return `len(citations)-right-1` as h-index.

This works even in the corner case in which `citations=[0,0,…,0]` because right will be initialized as `len(citations)-1` and will not get changed in the while loop. At the last line, `len(citations)-right -1 =0`, which is still the correct h-index for this case.

Reference:

https://leetcode.com/discuss/56122/standard-binary-search

https://leetcode.com/problems/h-index/

Code:

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        cnt = [0] * (len(citations)+1)
        for c in citations:
            if c>= len(citations):
                cnt[-1] += 1
            else:
                cnt += 1
        
        total = 0
        for i in xrange(len(cnt)-1, -1, -1):
            print i
            total += cnt[i]
            if total >= i:
                return i

Idea:

This algorithm needs O(N) time and O(N) space. A researcher’s h-index can’t be beyond the number of his publications, i.e., len(citations). So we create an array `cnt` of length len(citations)+1. For any citation, if it is larger than len(citations), we count that in cnt[-1]. The meaning of `cnt` array is that cnt[i] is the number of publications which have i citations. Exceptionally, cnt[-1] is a count for all other publications with the citations >= `len(citations)`. 

Then we traverse from cnt[-1] to cnt[0]. If cnt[-1] is already larger than len(citations), that means all publications have citations more than len(citations). if not, whenever the accumulated sum of cnt until `i` is equal to or larger than `i`, that means we have found at least `i` publications with at least i citations. Thus we return `i` immediately.

Another idea is to sort `citations` first in place in O(nlogn) then you don’t need the O(n) space. See H-Index II.

Reference:

https://leetcode.com/discuss/56987/python-o-n-lgn-time-with-sort-o-n-time-with-o-n-space

https://leetcode.com/problems/3sum-smaller/

[-2, 0, 1]
[-2, 0, 3]

Code:

class Solution(object):
    def threeSumSmaller(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if nums is None or len(nums) <=2:
            return 0
        nums.sort()
        cnt = 0
        for k in xrange(2, len(nums)):
            i, j = 0, k-1
            while i < j:
                if nums[i] + nums[j] + nums[k] < target:
                    cnt += j - i
                    i += 1
                    j = k-1
                else:
                    j -= 1
        return cnt

Idea:

This is O(N^2) solution. You first sort nums in O(nlogn). Then, for every `k` in xrange(2, len(nums)), you start to pivot `i` at 0, and j on the left of `k`. Since nums is already a sorted array, if nums[i] + nums[j] + nums[k] < target, then fixing `i` and `k`, moving the index `j`  between`i+1` and `j` can always satisfy the inequality. On the other hand, if nums[i] + nums[j] + nums[k] >= target, you need to move j one position left and retry. The algorithm is O(N^2) because for each `k`, i and j will be traversed until they meet together in the middle of nums, i.e. `i` and `j` will be traversed together in O(N).

https://leetcode.com/problems/wiggle-sort/

Code:

class Solution(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        for x in xrange(1, len(nums), 2):
            if x < len(nums)-1 and nums[x+1] > nums[x]:
                nums[x], nums[x+1] = nums[x+1], nums[x]
            if nums[x] < nums[x-1]:
                nums[x], nums[x-1] = nums[x-1], nums[x]

Idea:

You start from every odd index of x, if nums[x+1] > nums[x], you exchange them. At the moment after the exchange, nums[x] > nums[x+1] for sure. Now, if you also find that nums[x-1] > nums[x], nums[x-1] must already be larger than nums[x+1]. So you are safe to exchange nums[x-1] and nums[x] to meet nums[x-1] <= nums[x] >= nums[x+1] without any potential to break the inequality.

https://leetcode.com/problems/binary-tree-paths/

   1
 /   \
2     3
 \
  5

["1->2->5", "1->3"]

Code1:

# 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 binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        if root is None:
            return []
            
        self.res = [] if root.left or root.right else [str(root.val)]
        if root.left:
            self.helper(str(root.val), root.left) 
        if root.right:
            self.helper(str(root.val), root.right)
        return self.res

    def helper(self, path, node):
        if node.left is None and node.right is None:
            self.res.append(path + "->" + str(node.val))
        else:
            if node.left:
                self.helper(path+ "->" + str(node.val), node.left)
            if node.right:
                self.helper(path+ "->" + str(node.val), node.right)

Code2:

# 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 binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        res = []
        if root is None:
            return res

        if root.left is None and root.right is None:
            res.append(str(root.val))
        else:
            if root.left:
                res.extend([str(root.val) + "->" + p for p in self.binaryTreePaths(root.left)])
            if root.right:
                res.extend([str(root.val) + "->" + p for p in self.binaryTreePaths(root.right)])
        print res
        return res

Code 1 is more optimized than code 2 in that code 2 will always return `res` list as result hence waste a lot of space. All in all it is just a DFS algorithm.

https://leetcode.com/problems/repeated-dna-sequences/

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Code:

class Solution(object):
    def findRepeatedDnaSequences(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        ecd = 0
        res = []
        d = dict()
        for i in xrange(len(s)):
            ecd = ecd << 3
            ecd = ecd | ord(s[i]) & 7
            ecd = ecd & int('0b'+'1'*30, 2) 
            
            if d.get(ecd) is None:
                d[ecd] = 1
            elif d[ecd] == 1 and i >= 9:
                res.append(s[i-9:i+1])
                d[ecd] = 2
        return res

Idea:

Since we only have “A”, “C”, “G” and “T”, we can encode each character using the last three bits of its binary representation. We want to encode every 10 character substring eventually. We create a variable `ecd`, which should only have 30 bits valid (10 character*3 bits/character). Since python can allow you to have very large integer, you need to mask the last 30 bits. (Line 13) For every reading bit, you left shift the previous code 3 bits (line 11), intercept this character’s last 3 bits and then fill the last 3 empty bits (line 12).

Then it is easy to find whether one encode has been saved or not. If the encode already exists as a key in the dictionary, you only need to report it once.

Reference:

https://leetcode.com/discuss/24478/i-did-it-in-10-lines-of-c

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

Code:

# 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 lowestCommonAncestor(self, root, p, q):
        if root is None:
            return None
        if root == p or root == q:       
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        elif left:
            return left
        elif right:
            return right
        else:
            None

Idea:

lowestCommonAncestor will do the following judgement:

1. if applying lowestCommonAncestor on root.left returns non-None value, it means at least p or q is in its left subtree.
2. if appling lowestCommonAncestor on root.right returns non-None value, it means at least p or q is in its right subtree.
3. if both root’s left and root’s right return non-None values, then p and q are in its left subtree and right subtree. So the common ancestor should be root. 
4. if only one of root’s left and root’s right returns non-None value, that means both p and q is in that subtree. In this case, just return whichever non-None value you get.
5. If lowestCommonAncestor returns none, that means neither p or q is in root and its subtrees.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Code

# 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 invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root is None:
            return

        root.left, root.right = root.right, root.left

        if root.left:
            self.invertTree(root.left)
        if root.right:
            self.invertTree(root.right) 

        return root