czxttkl

https://leetcode.com/problems/perfect-squares/

Code 1:

from collections import deque
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        # corner case 1
        if n < 0:
            return -1
        # corner case 2
        if n==0:
            return 1
    
        q = deque()         
        visited = set()
        # val, step
        q.append((0,0))
        visited.add(0)

        while q:
            val, step = q.popleft()    
            for i in xrange(1, n+1):
                tmp = val + i**2
                if tmp > n:
                    break
                if tmp == n:
                    return step+1
                else:
                    if tmp not in visited:
                        visited.add(tmp)
                        q.append((tmp, step+1))                 
        
        # Should never reach here
        return -1   

Idea 1:

Use BFS to solve this problem. We can think of a tree graph in which nodes are value 0, 1,…,n. A link only exists between i and j (i<j) if j=i+square_num. We start from node 0 and add all nodes reachable from 0 to queue. Then we start to fetch elements from the queue to continue to explore until we reach node n. Since BFS guarantees that for every round all nodes in the queue have same depth, so whenever we reach node n, we know the least depth needed to reach n, i.e., the least number of square number to add to n.

Don’t forget to use a set `visited` to record which nodes have been visited. A node can be reached through multiple ways but BFS always makes sure whenever it is reached with the least steps, it is flagged as visited.

Why can’t we use DFS? Why can’t we report steps when we reach n by DFS? Because unlike BFS, DFS doesn’t make sure you are always using the least step to reach a node. Imagine DFS may traverse all nodes to reach n becaues each node is its previous node plus one (because one is a square number.) When you reach n, you use n steps. But it may or may not be the least number required to reach n.

This teaches us a lesson that if you want to find “….’s least number to do something”, you can try to think about solving it in BFS way.

Code 2:

import sys
import itertools
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        # corner case 1
        if n < 0:
            return -1
        # corner case 2
        if n==0:
            return 1
    
        dp = [sys.maxint]*(n+1)
        dp[0] = 0

        for i in xrange(1, n+1):
            tmp = dp[i]
            for j in xrange(1, n+1):
                if j**2 > i:
                    break
                tmp = min(tmp, 1 + dp[i-j**2])
            dp[i] = tmp

        return dp[-1]

Idea 2:

Just normal DP. Leetcode actually reported TLE for this version. I guess it will pass if written in other language but with the same idea.

Reference

https://leetcode.com/discuss/57380/python-common-bfs-with-fewer-lines

https://docs.python.org/2/tutorial/datastructures.html

https://leetcode.com/problems/sqrtx/

Code

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 0:
            return -1
        
        left, right = 0, x
        while left <= right:
            mid = left + (right - left)/2
            if mid**2 < x:
                left = mid + 1
            elif mid**2 > x:
                right = mid - 1
            else:
                return mid
        
        return left-1    
        

Idea

Binary Search

https://leetcode.com/problems/power-of-two/

class Solution(object):
    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return (n & (n-1)) == 0 and n > 0
        

Idea:

Using the idea that if a number is power of two, its binary format should be: `1000..`. Then the number subtracted one should be: `011111..`. So `(n&(n-1))==0` can be used to judge if a number if power of two. 

An follow up is to calculate number k to the power of n: power(n, k). You can see how to use divide and conquer to solve this problem in `O(logN)`: http://www.geeksforgeeks.org/write-a-c-program-to-calculate-powxn/, https//nb4799.neu.edu/wordpress/?p=1078

https://leetcode.com/problems/integer-to-english-words/

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Code (https://leetcode.com/discuss/55477/recursive-python):

def numberToWords(self, num):
    to19 = 'One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \
           'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()
    tens = 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()
    def words(n):
        if n < 20:
            return to19[n-1:n]
        if n < 100:
            return [tens[n/10-2]] + words(n%10)
        if n < 1000:
            return [to19[n/100-1]] + ['Hundred'] + words(n%100)
        # p starts from 1
        for p, w in enumerate(('Thousand', 'Million', 'Billion'), 1):
            if n < 1000**(p+1):
                return words(n/1000**p) + [w] + words(n%1000**p)
    return ' '.join(words(num)) or 'Zero'

Idea:

Just use a recursive function to solve this problem. Nothing much to say.

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

Code

class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        if not prices or not k:
            return 0
        if k >= len(prices)/2:
            profit = 0
            for i in xrange(1, len(prices)):
                if prices[i] - prices[i-1] > 0:
                    profit += prices[i] - prices[i-1]
            return profit

        profit = [[0] * len(prices) for _ in xrange(k+1)]        
        for i in xrange(1, k+1):
            tmp = -prices[0]
            for j in xrange(1, len(prices)):
                profit[i][j] = max(profit[i][j-1], tmp + prices[j])
                tmp = max(tmp, profit[i-1][j-1] - prices[j])
        
        return profit[-1][-1]
        

Idea

First of all, let’s deal with the case where `k >= len(prices)/2`. In this case, you can use at most `k` transactions to get profits in all ascending intervals of prices. You can imagine an extreme case where the prices go like this:

In this extreme case, the number of ascending intervals is never going to be larger than `len(prices)/2`. So is the number of transactions needed to capture all ascending intervals.

For more smooth cases, you don’t need `len(prices)/2` that many transactions to get all ascending intervals. However, we can use the same piece of codes to deal with any cases, as long as `k >= len(prices)/2`.  (line 10 – 15)

Now let’s look at the core part. I use a 2D array `profit` to capture the temporary maximum profit I can get: `profit[i][j]` is the maximum profit you can get by using `i` transactions and the first `j` prices. There is also a variable `tmp`. Its value is the maximum money left in the pocket after you buy the stock but haven’t sold it before you process `profit[i][j]`.  You can imagine `tmp` as the current best buy point.

Reference

https://leetcode.com/discuss/25603/a-concise-dp-solution-in-java

https://leetcode.com/problems/unique-paths-ii/

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

My Code:

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        if len(obstacleGrid)==0 or len(obstacleGrid[0])==0:
            return 0
        
        ways = [0] * len(obstacleGrid[0])        
        ways[0] = 1 
        for j in xrange(0, len(obstacleGrid)):
            for i in xrange(0, len(obstacleGrid[0])):
                if obstacleGrid[j][i]:
                    ways[i] = 0
                elif i:  # only handle cells after the first column
                    ways[i] = ways[i] + ways[i-1] 
        
        return ways[-1]

Idea:

Following my previous post, you only need 1D array to store intermediate number of ways reaching `cell[j][i]`. Other than that, the only difference is that you need to handle obstacle. It is intuitive to do that though: you set `ways[i]=0` if you see an obstacle, i.e., no way can reach a cell without obstacle.

https://leetcode.com/problems/unique-paths/

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        if m <0 or n < 0:
            return 0
        
        ways = [[0] * n for _ in xrange(m)]
        for i in xrange(0, n):
            ways[0][i] = 1
        for j in xrange(0,m):
            ways[j][0] = 1
        
        for j in xrange(1,m):
            for i in xrange(1,n):
                ways[j][i] = ways[j-1][i] + ways[j][i-1]
        
        return ways[-1][-1]
        

Idea

Use very naive idea of Dynamic Programming by creating an m*n matrix ,`ways`. Each cell records the number of ways that can reach there. At the end, just return `ways[-1][-1]`. This requires `O(m*n)` time and `O(m*n)` space.

The space can be reduced by observing that you are either updating `ways` row by row or column by column. This means you only need to keep O(m) or O(n) space in memory all the time. Below is the updated code (not in Python) (https://leetcode.com/discuss/38353/0ms-5-lines-dp-solution-in-c-with-explanations):

class Solution {
    int uniquePaths(int m, int n) {
        if (m > n) return uniquePaths(n, m);
        vector<int> cur(m, 1);
        for (int j = 1; j < n; j++)
            for (int i = 1; i < m; i++)
                cur[i] += cur[i - 1]; 
        return cur[m - 1];
    }
}; 

Another idea is to derive `ways[-1][-1]` using combination formula: you always need `n+m-2` steps to reach (m,n) from (1,1) by either going down or right. Among the `n+m-2` steps, you need exactly `m-1` steps going down. Therefore ways[-1][-1] = $latex C_{n+m-2}^{m-1}$. The code implementing this idea (https://leetcode.com/discuss/9110/my-ac-solution-using-formula):

class Solution {
    public:
        int uniquePaths(int m, int n) {
            int N = n + m - 2;// how much steps we need to do
            int k = m - 1; // number of steps that need to go down
            double res = 1;
            // here we calculate the total possible path number 
            // Combination(N, k) = n! / (k!(n - k)!)
            // reduce the numerator and denominator and get
            // C = ( (n - k + 1) * (n - k + 2) * ... * n ) / k!
            for (int i = 1; i <= k; i++)
                res = res * (N - k + i) / i;
            return (int)res;
        }
    };

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

My original code:

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

My original idea:

A rotated array has a property: if you do binary search by having `left`, `mid` and `right` pointers, if  nums[left] < nums[mid] and nums[mid] > nums[right], that means the left part is intact and the minimum has been rotated to `nums[mid:right+1]`. Similarly, if nums[left] > nums[mid] and nums[mid] < nums[right]  , that means the right part is intact and the minimum has been rotated to `nums[0:mid+1]`. However, in the code above, I didn’t set `left` and `right` to `mid+1` and `mid-1` as in standard binary search because I was afraid that after excluding the current element `nums[mid]`, I may let the whole subarray being without rotation. I thought my algorithm will not work if the array is in a correct format. For example, if we always set `left` to `mid+1`:

input: [3412]

iteration 0: left=0, right=3, mid=1

iteration 1: left=2, right=3. Now nums[left:right+1] is [12] which has correct order

But later I find I can safely set `left` and `right` to `mid+1` and `mid` to not exclude the minimum in `nums[left:right+1]`. As long as the minimum is in `nums[left:right+1]`, the algorithm can finally find the minimum. This can be done by:

setting `left` to mid+1 if nums[mid] > nums[right]. 

setting `right` to mid if nums[left] > nums[mid].

So the more concise code can be (https://leetcode.com/discuss/63514/9-line-python-clean-code): 

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        j = len(nums) - 1
        while i < j:
            m = i + (j - i) / 2
            if nums[m] > nums[j]:
                i = m + 1
            else:
                j = m
        return nums[i]

https://leetcode.com/problems/zigzag-iterator/

v1 = [1, 2]
v2 = [3, 4, 5, 6]

[1,2,3]
[4,5,6,7]
[8,9]

My verbose code:

class ZigzagIterator(object):

    def __init__(self, v1, v2):
        """
        Initialize your data structure here.
        :type v1: List[int]
        :type v2: List[int]
        """
        self.v1 = v1
        self.v2 = v2
        self.pointer = 0
        if len(v1) != 0:
            self.l = 0  
        else:
            self.l = 1
        self.x = 0

    def next(self):
        """
        :rtype: int
        """
        n = None
        if self.l == 0:
            n = self.v1[self.x]
            if self.x < len(self.v2):
                self.l = 1
                # keep self.x same
            else:
                # keep self.l same
                self.x += 1
        else: 
            n = self.v2[self.x]
            if self.x < len(self.v1) - 1:
                self.l = 0
                self.x += 1
            else:
                self.x += 1
        
        self.pointer += 1
        return n
        
        
    def hasNext(self):
        """
        :rtype: bool
        """
        return self.pointer < len(self.v1)+len(self.v2)

# Your ZigzagIterator object will be instantiated and called as such:
# i, v = ZigzagIterator(v1, v2), []
# while i.hasNext(): v.append(i.next())

However, there are more elegant codes which leverage Python generator (https://leetcode.com/discuss/57997/python-o-1-space-solutions):

class ZigzagIterator(object):

    def __init__(self, v1, v2):
        self.vals = (v[i] for i in itertools.count() for v in (v1, v2) if i < len(v))
        self.n = len(v1) + len(v2)

    def next(self):
        self.n -= 1
        return next(self.vals)

    def hasNext(self):
        return self.n > 0

Here, self.vals = (v[i] for i in itertools.count() for v in (v1, v2) if i < len(v))  uses `itertools.count()` as a generator to generate infinite integer `i`. For each `i`, if `i < len(v)` then the list `self.vals` will add v[i]. This essentially constitutes a zigzag output in the initialization. However, since `itertools.count()` is just a generator, `self.vals` don’t occupy the memory: every element in `self.val` will be yielded whenever you call `next(self.vals)`. 

https://leetcode.com/problems/binary-search-tree-iterator/

Code:

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

class BSTIterator(object):
    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.stack = []
        self.pushAll(root)
        print [s.val for s in self.stack]

    def hasNext(self):
        """
        :rtype: bool
        """
        return self.stack 

    def next(self):
        """
        :rtype: int
        """
        n = self.stack.pop()
        self.pushAll(n.right)
        return n.val
        
    def pushAll(self, node):
        while node:
            self.stack += [node]
            node = node.left
        
# Your BSTIterator will be called like this:
# i, v = BSTIterator(root), []
# while i.hasNext(): v.append(i.next())

Idea

First, load `self.stack` from root to the leftmost leaf. This requires O(log n) memory and time. Then, when you call `next()`, you pop the top element from `self.stack`, which is guaranteed to be smallest. Before you return this, you also need to load this element’s right child’s path to its leftmost child into `self.stack`. To do so, you call `self.pushAll(node.right)`.