czxttkl – Page 27

Leetcode 105: Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

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 buildTree(self, preorder, inorder):
        if inorder:
            ind = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[ind])
            root.left = self.buildTree(preorder, inorder[0:ind])
            root.right = self.buildTree(preorder, inorder[ind+1:])
            return root

Idea

The root of a preorder list is always `preorder[0]`. You need to find the index of the root in inorder list. After that, you can divide the problem into two smaller problems.

I used to use a more memory consuming version (using a lot of slicing). This version ended up with Memory Limit Exceeded exception. Therefore, we should avoid using slicing as much as possible. (See my another post talking about slicing in python: https://czxttkl.com/?p=1353)

# 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 buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        root = self.work(preorder, inorder)
        return root
    
    def work(self, preorder, inorder):
        assert len(preorder) == len(inorder)
        if len(preorder) == 0:
            return None
            
        root = TreeNode(preorder[0])
        for idx, num in enumerate(inorder):
            if num == root.val:
                root.left = self.work(preorder[1:idx+1], inorder[:idx])
                root.right = self.work(preorder[idx+1:], inorder[idx+1:])
        return root

slicing in numpy array and list

For normal list in Python, slicing copies the references without copying underlying contents. (See the fact that`id(a[1])` and `id(b[0])` are identical below.)

>>> a = [1,2,3]
>>> b = a[1:3]
>>> a
[1, 2, 3]
>>> b
[2, 3]
>>> id(a[1])
25231680
>>> id(b[0])
25231680
>>> b[0] = 999
>>> a
[1, 2, 3]
>>> b
[999, 3]

For numpy array, slicing doesn’t copy anything: it just returns a view of the original array. Therefore, changes made in the sliced array is essentially made in the original array.

>>> a = numpy.array([1,2,3])
>>> b = a[1:3]
>>> a
array([1, 2, 3])
>>> b
array([2, 3])
>>> id(a[1])
140093599322520
>>> id(b[0])
140093599322520
>>> b[0]=999
>>> a
array([  1, 999,   3])
>>> b
array([999,   3])

Refs:

http://stackoverflow.com/questions/5131538/slicing-a-list-in-python-without-generating-a-copy

http://stackoverflow.com/questions/3485475/can-i-create-a-view-on-a-python-list

Leetcode 123: Best Time to Buy and Sell Stock III

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Code

import sys

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        lowest_price = sys.maxint
        profit1 = 0
        max_left_after_profit1 = -sys.maxint
        profit_total = 0
        
        for p in prices:
            lowest_price = min(p, lowest_price)
            profit1 = max(profit1, p - lowest_price)
            max_left_after_profit1 = max(max_left_after_profit1, profit1 - p)
            profit_total = max(profit_total, p + max_left_after_profit1)
        
        return profit_total

Idea

Use `profit1` to denote the profit gained from the first transaction. This is similar to what we achieved in the easier problem: https://czxttkl.com/?p=1342. Then `max_left_after_profit1` is the maximum money left in your pocket after you finish the first transaction (buy and sell) and the second buy.

This method achieves O(N) time complexity and O(1) space.

You can also use DP to solve this problem. See the idea here: https://czxttkl.com/?p=990

Leetcode 122: Best Time to Buy and Sell Stock II

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Code

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        max_profit = 0
        for i in range(1, len(prices)):
            diff = prices[i] - prices[i-1]
            if diff > 0:
                max_profit += diff
                
        return max_profit

Idea

Since you can make as many transactions you want, every positive price interval can be one transaction that make profit.

Leetcode 121: Best Time to Buy and Sell Stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Code

import sys

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        min_price = sys.maxint
        max_profit = 0
        for price in prices:
            min_price = min(min_price, price)
            max_profit = max(max_profit, price - min_price)
        
        return max_profit

Idea

`min_price` is the minimum price so far. The maximum profit must happen when `current price – min_price` is max.

Variant

If you are given difference array of prices, what would you do?
https://leetcode.com/discuss/48378/kadanes-algorithm-since-mentioned-about-interviewer-twists

How to understand Eigenvector/Eigenvalue?

This topic has been in my wish list for a long time. I will try to articulate my understanding of eigenvector and eigenvalue after digestion informative materials from different sources.

First of all, we can consider multiplication between a square matrix $A \in \mathbb{R}^{k \times k}$ and a vector $\vec{v} \in \mathbb{R}^k$ as a transformation of $\vec{v}$ such that $\vec{v}$ is rotated and scaled. By definition, eigenvectors of $A$ are vectors on the directions on which $A$ has invariant rotation transformation, i.e., $A\vec{v}=\lambda\vec{v}$ .

What kind of matrices have eigenvectors? Only square matrices are possible to have eigenvectors. This is because:

ref: http://math.stackexchange.com/a/583976/235140

However, not all square matrices have eigenvectors: http://math.stackexchange.com/a/654713/235140

Two useful interpretations of eigenvectors if you regard a square matrix as rotation + scale transformation:

no other vectors when acted by this matrix can be stretched as much as eigenvectors. (ref: http://math.stackexchange.com/a/243553/235140)
eigenvectors keep the same direction after the transformation. (ref: https://www.quora.com/What-do-eigenvalues-and-eigenvectors-represent-intuitively)

Now, let’s see the scenarios in computer science realm where eigenvectors/eigenvalues play a role.

1. PCA

Now we look at all kinds of matrics including square matrices. One way to understand a matrix is that it represents a coordination system. Suppose $P \in \mathbb{R}^{m \times k}$ is a matrix and $\vec{x} \in \mathbb{R}^k$ is a column vector, then one way to interpret $P \vec{x}=\vec{y}$ is that every row of the matrix $P$ is a base vector of its coordination system. Every component of $\vec{y}$ is a dot product of a row of $P$ and $\vec{x}$ , which can be seen as a kind of projection from $\vec{x}$ on the corresponding row of $P$ .

If now we have a transformation matrix $P \in \mathbb{R}^{m \times k}$ in which rows are base vectors of some coordination system, $X \in \mathbb{X}^{k \times n}$ is data matrix where $n$ is the number of data points and $k$ is the number of dimensions, then $Y=PX, Y \in \mathbb{R}^{m \times n}$ is a dimension reduced matrix of $X$ such that every column of $Y$ is representation of every column of $X$ using base vectors in $P$ .

PCA is trying to find such $P$ that not only reduces the dimension of $X$ but also satisfies other properties. And what it concludes is that $P$ is a matrix in which rows are eigenvectors of $X$ ‘s covariance matrix. (ref: https://czxttkl.com/?p=339, https://www.cs.princeton.edu/picasso/mats/PCA-Tutorial-Intuition_jp.pdf)

2. PageRank / Stationary distribution of Markov chains

Both try to find eigenvectors with eigenvalues equal to 1: $P\vec{x} = \vec{x}$ . In PageRank, $P$ is a fractional PageRank constribution link matrix in which $P_{ij}$ is the page rank contributed to webpage $j$ when webpage $i$ links it. $\vec{x}$ is the PageRank value vector for all web pages that we want to calculate. When calculating stationary distribution of Markov States, $P$ is simply a transition matrix denoting pairwise transition probabilities between nodes while $\vec{x}$ is the ultimate stationary distribution of nodes.

Leetcode 111: Minimum Depth of Binary Tree

https://leetcode.com/problems/minimum-depth-of-binary-tree/

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

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 minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
            
        if root.left is None and root.right is None:
            return 1
        
        if root.left is None and root.right is not None:
            return self.minDepth(root.right) + 1
        
        if root.right is None and root.left is not None:
            return self.minDepth(root.left) + 1
        
        return min(self.minDepth(root.left), self.minDepth(root.right))+1

Idea

There are 5 conditions to consider:

if root is None, the current depth is zero
if both root’s left and right child are none, the current root is a leaf node which has depth 1
if only one of root.left or root.right child is none, the depth depends on the depth of the non-none child.
if both root.left and root.right child are not none, then the minimum depth is the min of minDepth(root.left) and minDepth(root.right) plus 1

Of course, you can take a few logical steps to further reduce lines of codes:

class Solution:
    # @param root, a tree node
    # @return an integer    
    def minDepth(self, root):
        if root == None:
            return 0
        if root.left==None or root.right==None:
            return self.minDepth(root.left)+self.minDepth(root.right)+1
        return min(self.minDepth(root.right),self.minDepth(root.left))+1

Leetcode 179: Largest Number

https://leetcode.com/problems/largest-number/

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Code

class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        return ''.join(sorted(map(str, nums),cmp=lambda x,y:cmp(y+x, x+y))).lstrip('0') or '0'

Idea

Efficiently using `sorted` function makes the code very short. When concatenated string starts with zeros, you should strip all left zeros. The sort will take O(NlogN) time.

Reference:

https://leetcode.com/discuss/21550/my-3-lines-code-in-java-and-python

Leetcode 112: Path Sum

https://leetcode.com/problems/path-sum-ii/

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

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 hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: intyy
        :rtype: List[List[int]]
        """
        if root is None: return False
        if root.left is None and root.right is None: return sum==root.val
        
        left = self.hasPathSum(root.left, sum-root.val) if root.left else False
        right = self.hasPathSum(root.right, sum-root.val) if root.right else False
        return left or right

Idea

Use DFS to traverse nodes.

Leetcode 113: Path Sum II

https://leetcode.com/problems/path-sum-ii/

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

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 pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        if root is None: return []
        self.res = []
        self._pathSum(root, sum, [])
        return self.res
        
    def _pathSum(self, root, sum, l):
        l += [root.val]
        if root.left is None and root.right is None: 
            if sum==root.val:
                self.res += [l[:]]
        
        if root.left: self._pathSum(root.left, sum-root.val, l) 
        if root.right: self._pathSum(root.right, sum-root.val, l) 
        l.pop()

Idea

Use DSP to traverse every node in the tree. Pass the path from the root to the current node as a parameter in the traversal. Whenever it reaches a leaf, count if all nodes in the path sum to the target number. When a node finishes traversing its left node and right node, it should be popped out of the path.

Line 24: when you add current path (`l`) into `self.res`, you need to make a deep copy of `l`: `l[:]`