Yu's Coding Garden : April 2013

leetcode Question 76: Regular Expression Matching

Regular Expression Matching

This is the same problem as leetcode Question 123: Wildcard Matching.
See here

leetcode Question 98: Simplify Path

Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

Corner Cases:

Did you consider the case where path = "/../"?
In this case, you should return "/".
Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".

Updated(201309):

Analysis:

(1) Use a stack to store the path.
(2) Use a int flag to store the '/' pair
(3) First remove the "//" in the path.
(4) meets ".", do nothing, meets ".." pop stack if not empty, other strings push into stack.

Code:

class Solution {
public:
    string simplifyPath(string path) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        //Remove double "//"
        int i=0;
        while (i<path.size()-1){
            if (path[i]=='/' && path[i+1]=='/'){
                path.erase(i,1);
            }else{ i++; }
        }
        //Add a '/' in the end.
        if (path[path.size()-1]!='/'){path=path+"/";}
        
        //main part
        stack<string> dirs;
        string str="";
        int flag =0;
        for (int i=0;i<path.size();i++){
            if (path[i]=='/'){flag++;}        
            if (flag==1){ str+=path[i];}
            if (flag==2){
                if (str=="/.." && !dirs.empty()){
                    dirs.pop();
                }
                if (str!="/." && str!="/.."){
                    dirs.push(str);    
                }
                flag=1;
                str="/";
            }
        }
        
        //Output Result
        if (dirs.empty()){return "/";}
        str="";
        while (!dirs.empty()){
            str=dirs.top()+str;
            dirs.pop();
        }
        return str;
    }
};

Analysis(old version):
The criterion is when meet "..", go to previous folder, meet ".", current folder, otherwise, go into next folder.

For implementation:

(1) function strtok(char*, const char*), note that " string.c_str() " returns "const char*" but not "char*", one way is to create a new char* with the same length (by char* = new char [length+1] ), and then use function "strcpy(target_char*, source_char*)".

(2) In the loop of getting strtok() " pth = strtok(NULL, "/") " NULL mean continues scanning previous call.

(3) Use "strcmp" to compare char* , where returns 0 if equals.

(4) Be careful with the output order of stack.

Code(old version):

class Solution {
public:
    string simplifyPath(string path) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
                        
        stack<char*> st; //store folders
        
        //get token
        char* pth = new char [path.size()+1];
        strcpy(pth,path.c_str());
        char* tok = strtok(pth,"/");
        
        while (tok!=NULL){
            
            if (strcmp(tok,".")!=0){st.push(tok);}  //if meet "." do nothing.
            if ((!st.empty())&&(strcmp(st.top(),"..")==0)){ 
            //if meet "..", pop ".." and pop one more if available
                st.pop();
                if (!st.empty()){st.pop();}
            }
            tok = strtok(NULL,"/");
        }
        
        string res; //get result (be careful with the order of stack)
        while (!st.empty()){
            res = "/" + string(st.top())+ res;
            st.pop();
        }
        
        if (res.empty()) return "/";
        return res;
        
        
    }
};

leetcode Question 97: Set Matrix Zeros

Set Matrix Zeros

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Analysis:
To reduce the space required, we can use the matrix itself to store the flags for each row and column if they need to set to 0. So we need 1 row and 1 column, the 1st row and 1st column then can be chosen to store the flag. But we need first check the two if they need to be 0. Then go the other rows and columns.

e.g.

1 0 2 3 4 5
2 0 2 3 4 5
3 1 2 3 4 5

First check 102345 and
1
2
3
use two flags storing the status. fr0 = true, fc0=false;
then check the rest of matrix, use the 1st col and 1st row store the status.
1 0 2 3 4 5
0 0 2 3 4 5

1 1 2 3 4 5
Then set 0s to sub-matrix(excludes 1st row and 1st column), according to the values in 1st row and 1st column, and finally set 1st row and 1st column according to flags.

The new space used is O(1+1) = O(1).

Code:

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int row = matrix.size();
        if (row==0){return;}
        int col = matrix[0].size();
        if (col==0){return;}
        
        bool fc0=false;
        bool fr0=false;
        
        for (int i=0;i<col;i++){
            if (matrix[0][i]==0){fr0 = true;}
        }
        
        for (int i=0;i<row;i++){
            if (matrix[i][0]==0){fc0 = true;}
        }
        
        for (int i=1;i<row;i++){
            for (int j=1;j<col;j++){
                if (matrix[i][j]==0){
                    matrix[i][0]=0;
                    matrix[0][j]=0;
                }
            }
        }
        
        
        for (int i=1;i<col;i++){
            if (matrix[0][i]==0){
                for(int j=0;j<row;j++){
                    matrix[j][i]=0;
                }
            }
        }
        
        for (int i=1;i<row;i++){
            if (matrix[i][0]==0){
                for(int j=0;j<col;j++){
                    matrix[i][j]=0;
                }
            }
        }
        
        if (fr0){
            for (int i=0;i<col;i++){matrix[0][i]=0;}
        }
        if (fc0){
            for (int i=0;i<row;i++){matrix[i][0]=0;}
        }
        
        return;
        
    }
};

leetcode Question 96: Search Insert Position

Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Analysis:
O(n) algorithm is just searching from 1st to last, compare target with each element.

More efficient O(log n) algorithm is to use binary search, only difference is to change return condition to the start position instead of "false", when start position > end position. (line 6 in code below )

Code:

class Solution {
public:

    int se(int st, int ed, int A[], int target){
        if (st>ed){
            return st;
        }else{
            int mid = st+(ed-st)/2;
            if (A[mid]==target){
                return mid;
            }
            if (A[mid]<target){
                return se(mid+1,ed,A,target);
            }
            if (A[mid]>target){
                return se(st,mid-1,A,target);
            }
        }
    }
    int searchInsert(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function   
        return se(0,n-1,A,target);
    }
};

leetcode Question 95: Search in Rotated Sorted Array II

Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

Analysis:
Similar to the previous question (see here).
Just when A[mid]==A[st], we cannot say the previous part is ordered, then we just go to the next element and check again.

Code:

class Solution {
public:

    bool se(int st, int ed, int target, int A[]){
        if (st>ed) {return false;}
        else{
            int mid = st+(ed-st)/2;
            if (A[mid]==target){return true;}
            
            if (A[mid]>A[st]){
                if (target<=A[mid] && target>=A[st]){
                    return se(st,mid-1,target,A);
                }else{
                    return se(mid+1,ed,target,A);
                }
            }
            
            if (A[mid]<A[st]){
                
                if (target<=A[mid] || target >= A[st]){
                    return se(st,mid-1,target,A);
                }else{
                    return se(mid+1,ed,target,A);
                }
                
            }
            
            if (A[mid]==A[st]){return se(st+1,ed,target,A);}
            
            return false;
        }
        
    }

    bool search(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (n==0){return false;}
        return  se(0,n-1,target,A);
    }
};

leetcode Question 94: Search in Rotated Sorted Array

Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Analysis:
Main idea is Binary Search.
As the sequence is rotated, for any mid element, either it is of order with its previous part, or it is of order with its next part. e.g. 561234, middle element 1 has an order with its next part 1234.
5678123, middle element 8 has an order with its previous part 5678.

Normal binary search just compare the middle element with the target, here we need more than that.
e.g.
567123, the middle element is 1, if we want to search 6, first compare middle element with 1st element, to know which part is of order, if mid>1st, the first part is ordered,otherwise the last part is ordered. Then compare the target value with the bound value in each case. Details see the code.

Complexity is O(log_n).

Code:

class Solution {
public:

    int se(int st, int ed, int target, int A[]){
        if (st>ed) {return -1;}
        else{
            int mid = st+(ed-st)/2;
            if (A[mid]==target){return mid;}
            
            if (A[mid]>=A[st]){
                if (target<=A[mid] && target>=A[st]){
                    return se(st,mid-1,target,A);
                }else{
                    return se(mid+1,ed,target,A);
                }
            }
            
            if (A[mid]<A[st]){
                
                if (target<=A[mid] || target >= A[st]){
                    return se(st,mid-1,target,A);
                }else{
                    return se(mid+1,ed,target,A);
                }
                
            }
            return -1;
        }
        
    }

    int search(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (n==0){return -1;}
        return  se(0,n-1,target,A);
    }
};

leetcode Question 93: Search for a Range

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Updated 201604

This question requires O(logn) complexity, it is natural to think about binary search.

Different from the traditional binary search, what we met in this problem is the case that:

Two positions are needed: the starting and ending point of the target.

OK, now, let's first construct the basic binary search, and then modify the implementation to this problem.

Given the sequence, binary search often (recursively):

find the middle point
do some comparison
search left part of the sequence
search right part of the sequence

until we find the element we need.

In this problem, target is what we need, given the above the steps, only one of the target (which may occurs many times). Since the array is sorted, once we find one target, just keep searching the left and right part of this position, we will find the other targets.

While, there are many details in the above. Let's do it step by step using an example, e.g.,
$$A=[1,2,3,4,6,6,6,6,8,9]$$

First we use the traditional binary search to locate the target, if there is no target, the program will return and output [-1,-1] as required in the question. This part is done by Line 13 to Line 18 in my cpp code below.

Once we get the target position, in this example, $A[4] = 6$. Then we start search both the left and right part from $A[4]$, at the same time, we have to keep the ranges, i.e., the starting point, and ending point. In my code below, res[0] stores the starting point, res[1] is for ending point. I always save the minimum starting position each time (be careful with the initial starting point -1), and maximum end position each time.

Code(C++):

class Solution {
public:
    void search(vector<int>& nums, int target, int st, int ed, vector<int> &res){
        if (st>ed){
            return;
        }else{
            int mid = st + (ed-st)/2;
            if (nums[mid] == target){
                res[0] = res[0] ==-1 ? mid: min(mid,res[0]);
                search(nums, target, st, mid-1, res);
                res[1] = max(mid,res[1]);
                search(nums, target, mid+1, ed, res);
            } else{
                if (nums[mid] < target){
                    search(nums, target, mid+1, ed, res);
                } else{
                    search(nums, target, st, mid-1, res);    
                }
            }
        }
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res(2,-1);
        search(nums,target,0,nums.size()-1,res);
        return res;
    }
};

Code (Python):

class Solution(object):
    def search(self, nums, target, st, ed, res):
        if st>ed:
            return
        else:
            mid = st + (ed-st)/2
            if nums[mid] == target:
                if res[0] == -1:
                    res[0] = mid
                else:
                    res[0] = min(mid,res[0])
                self.search(nums, target, st, mid-1, res)
            
                res[1] = max(res[1],mid)
                self.search(nums, target, mid+1, ed, res)
            else:
                if nums[mid] < target:
                    self.search(nums, target, mid+1, ed, res)
                else:
                    self.search(nums, target, st, mid-1, res)
        
    
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        res = [-1,-1]
        self.search(nums, target, 0, len(nums)-1, res)
        return res

Updated 201309

Analysis:
When see the O(log n) complexity requirement, it is highly possible that binary search is needed.
As the array is sorted, thus, the "next" element of the result range must be less (left) or greater (right) than the target value, or meets the boundary of the array. So, we can do the binary search twice, one search the left range, where A[mid-1]<A[mid], and one search for the right range, where A[mid+1]>A[mid].

Code:

class Solution {
public:
    int search(int A[], int n, int target,int st,int ed, bool left){
        if (st>ed){
            return -1;
        }else{
            int mid = st+(ed-st)/2;
            if (A[mid]==target){
                if (left){
                    if (mid==0 || A[mid-1]<A[mid]){return mid;}
                    else{return search(A,n,target,st,mid-1,left);}
                }
                if (!left){
                    if (mid==n-1 || A[mid+1]>A[mid]){return mid;}
                    else{return search(A,n,target,mid+1,ed,left);} 
                }
            }
            if (A[mid]<target){
                return search(A,n,target,mid+1,ed,left);
            }
            if (A[mid]>target){
                return search(A,n,target,st,mid-1,left);
            }
        }
    }
    
    vector<int> searchRange(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> res(2,-1);
        res[0]=search(A,n,target,0,n-1,true);
        res[1]=search(A,n,target,0,n-1,false);
        return res;        
    }
};

leetcode Question 92: Search a 2D matrix

Search a 2D matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

Analysis:

First glance at this problem easily reminds us the classic search algorithm: binary search. But this time it is required to search if the "target" value exists in the 2D matrix rather than 1D array.

A good start point is to consider the 1D binary search, every time we choose the middle element and compare to the target value, then recursively search the related subset until found or finished.

What about 2D sorted matrix? Let's see the matrix below:
[1, 4, 7, 11, 15]
[2, 5, 8, 12, 19]
[3, 6, 9, 16, 22]
[10, 13, 14, 17, 24]
[18, 21, 23, 26, 30]

Since it is sorted both row-wise and column-wise, for any sub matrix, the smallest element must be the top-left element, and the largest one must be on the right bottom.

Now, it seems that the diagonal should be the mid-element similar to the 1D binary search. But how shall we divide the matrix into sub matrices? Let's see the matrix below:

[1,   4, 7, 11, 15]
[2,   5,   8, 12, 19]
[3, 6, 9,  16, 22]
[10, 13, 14, 17, 24]
[18, 21, 23, 26, 30]

The whole matrix is divided into 4 sub matrices (blue, green, yellow, and red in the above matrix), by diagonal element 9. So it is not hard to get the following properties:
(1) elements in blue < 9
(2) elements in red > 9
(3) elements in yellow and green, we don't know.

So, given a target value t, we could first compare the value to the mid element in the current matrix, then search either (blue, green and yellow) or (red, green and yellow) sub matrices, according to the value comparison. Then a simple recursion can be done for the whole searching process, which is same as the classic binary search.

Code(C++):

class Solution {
public:
    bool search(vector > &matrix, int &target, int st_r, int ed_r, int st_c, int ed_c){
        if (st_r > ed_r || st_c > ed_c || matrix[st_r][st_c] > target || matrix[ed_r][ed_c]< target) {return false;}
        int mid_r = st_r + (ed_r-st_r)/2;
        int mid_c = st_c + (ed_c-st_c)/2;
        
        if (matrix[mid_r][mid_c] == target){
            return true;
        }else if (matrix[mid_r][mid_c] > target) {
            return (search(matrix, target, st_r, mid_r, st_c, mid_c) ||
                    search(matrix, target, st_r,mid_r, mid_c+1, ed_c)||
                    search(matrix, target, mid_r+1, ed_r, st_c, mid_c));
        }else{
            return (search(matrix, target, mid_r+1, ed_r, mid_c+1, ed_c) ||
                    search(matrix, target, st_r,mid_r, mid_c+1, ed_c)||
                    search(matrix, target, mid_r+1, ed_r, st_c, mid_c));
        }
    }

    bool searchMatrix(vector>& matrix, int target) {
        int sz_row = matrix.size();
        if (sz_row == 0) { return false; }
        int sz_col = matrix[0].size();
        
        return search(matrix, target, 0, sz_row-1, 0, sz_col-1);
    }
};

Code(Python):

class Solution(object):
    def search(self, matrix, target, st_r, ed_r, st_c, ed_c):
        if st_r > ed_r or st_c > ed_c or matrix[st_r][st_c] > target or matrix[ed_r][ed_c]< target:
            return False
            
        mid_r = st_r + (ed_r-st_r)/2
        mid_c = st_c + (ed_c-st_c)/2
        
        if matrix[mid_r][mid_c] == target:
           return True
           
        elif matrix[mid_r][mid_c] > target:
            return self.search(matrix, target, st_r, mid_r, st_c, mid_c) or \
                   self.search(matrix, target, st_r,mid_r, mid_c+1, ed_c) or \
                   self.search(matrix, target, mid_r+1, ed_r, st_c, mid_c)
        else:
            return self.search(matrix, target, mid_r+1, ed_r, mid_c+1, ed_c) or \
                   self.search(matrix, target, st_r,mid_r, mid_c+1, ed_c) or \
                   self.search(matrix, target, mid_r+1, ed_r, st_c, mid_c)
    
    
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        sz_r = len(matrix)
        if sz_r == 0:
            return False
        sz_c = len(matrix[0])
        
        return self.search(matrix, target, 0, sz_r-1, 0, sz_c-1)

leetcode Question 70: Permutations II

Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

Analysis:
Facing this kind of problem, just consider this is a similar one to the previous(see here), but need some modifications. In this problem, what we need it to cut some of the subtrees. e.g. 122
122
/ | \
122 212 X (here because 2=2, we don't need to swap again)
/ \ / \
122 X 212 221

So, if there exist same element after current swap, there there is no need to swap again.
Details see code.

Code:

class Solution {
public:
    bool noswap(int k, int i, const vector<int> num){
        for (int j=k;j<i;j++){
            if (num[j]==num[i]){
                return true;
            }
        }
        return false;
    }

    void perm(vector<int> num,int k,int n, vector<vector<int> > &res){
        if (k==n){
            res.push_back(num);
        }else{
            for (int i=k;i<=n;i++){
                
                if (noswap(k,i,num)){continue;}
                
                int tmp = num[k];
                num[k]=num[i];
                num[i]=tmp;
                
                perm(num,k+1,n,res);
                
                tmp = num[k];
                num[k]=num[i];
                num[i]=tmp;
            }
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > res;
        perm(num,0,(num.size()-1),res);
        return res;
    }
};

leetcode Question 69: Permutations

Permutations

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Analysis:

The idea of this classic problem is to use backtracking.
We want to get permutations, which is mainly about swap values in the list.
Consider:
a --> a
ab --> ab, ba
abc --> abc, acb, bac, bca, cab, cba.
...
where for the length of n, the permutations can be generated by
(1) Swap the 1st element with all the elements, including itself.
(2) Then the 1st element is fixed, go to the next element.
(3) Until the last element is fixed. Output.
It's more clear in the figure above. The key point is to make the big problem into smaller problem, here is how to convert the length n permutation into length n-1 permutation problem.

Code:

class Solution {
public:
    
    void perm(vector<int> num,int k,int n, vector<vector<int> > &res){
        if (k==n){
            res.push_back(num);
        }else{
            for (int i=k;i<=n;i++){
                int tmp = num[k];
                num[k]=num[i];
                num[i]=tmp;
                
                perm(num,k+1,n,res);
                
                tmp = num[k];
                num[k]=num[i];
                num[i]=tmp;
            }
        }
    }

    vector<vector<int> > permute(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > res;
        perm(num,0,(num.size()-1),res);
        return res;
    }
};

leetcode Question 68: Permutation Sequence

Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the k^th permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Analysis:

One way to solve the problem (can only pass the small test) is to generate from the 1st permutation to the required one (similar to the problem Next permutation.). However, when n=9, the last permutation is the 362880th one, which is too time consuming.

A better way is to fully use the properties of permutation: the total number of permutation with length n is n!.
First, let's take a look at how permutation works:

Major steps are swap and fix:

Here in order to grow the tree, every time start the first unfixed element in each node, generate child nodes by swapping the first element with every other element.The leave nodes are those do not have element to swap.

So, when we have the idea of how to generate the permutation, next step is to generate it faster. Think the tree in this way:

ABC

/ | \

ABC BAC CBA

/ \ / \ / \

ABC ACB BAC BCA CBA CAB

Every leave node is a permutation. Take a look at the second level, each subtree (second level nodes as the root), there are (n-1)! permutations in it. Totally there are n nodes in 2nd level, thus the total number of permutations are n*(n-1)!=n!.

So, what we want to do is to locate one permutation among the leave nodes. The simple method is to generate and search each leave node until we find the one. Now, what we can do here we want to skip some trees to reduce the complexity. e.g. in the above tree, if we know the required leave node is in the third sub tree (under CBA), we can skip the first two and search from the "CBA".

Say we have the required permutation is the kth one, first we can locate which subtree it belongs to in the 2nd level, by computing s = k / ((n-1)!). Then we get the sth subtree, and set k=k%((n-1)!) , now search the sub tree until we get the leave node. How to get the sth subtree root node? Just like the idea of how permutation works (the first figure): Just put the sth elment after fixed letter. e.g. ABCD, we want the 3rd subtree root node in 2nd level, just put C in the 1st place, which is CABD; For ABCDE, we want the 3rd subtree root node in the 3rd level, it is ADBCE.

Code(C++, loop):

class Solution {
public:
    string getPermutation(int n, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int nf[9]={1,2,6,24,120,720,5040,40320,362880}; //n factorail 
        string res;//result string
        for (int i=1;i<=n;i++){res+=char(i+'0');} // initialization
        k--;
        for (int i=0;i<n;i++){
            int m = k%nf[n-i-1];
            int s = k/nf[n-i-1];
            if (m==0 && s==0){ return res;} 
            else{
                if (s>0){     
                    for (int j=i-1+s; j>i-1;j--){
                        char tmp = res[j];
                        res[j]=res[j-1];
                        res[j-1]=tmp;
                    }
                    if (m==0){return res;}
                }
                k=m;
            }            
        }
        return res;
    }
};

Code(c++, recursion):

class Solution {
public:
    void swap(string &str,int st, int l){
        for (int i=st+l;i>st;--i){
            char tmp = str[i];
            str[i]=str[i-1];
            str[i-1]=tmp;
        }
    }

    void getP(string &str,int &st, int &n,int &k, int *nf){
        if (k==0 || st>n-1){
            return;
        }else{
            swap(str,st,k/nf[n-st-1]);
            k=k%nf[n-st-1];
            getP(str,++st,n,k,nf);
        }
    }

    string getPermutation(int n, int k) {
        string str="";
        int nf[10]={1,1,2,6,24,120,720,5040,40320,362880}; //n factorail 
        for (int i=1;i<=n;i++){str+=char(i+'0');}
        int st=0;
        getP(str,st,n,--k,nf);
        return str;
    }
};

Code (Python, Recursion):

class Solution:
    def getP(self,strs,st,n,k,nf):
        if k==0 or st>n-1:
            return
        else:
            l=k/nf[n-st-1]
            p=strs.pop(st+l)
            strs.insert(st,p)
            k=k%nf[n-st-1]
            self.getP(strs,st+1,n,k,nf)
        return
    
    # @return a string
    def getPermutation(self, n, k):
        strs = [str(x) for x in range(1,n+1)]
        nf=[1,1,2,6,24,120,720,5040,40320,362880]
        st=0
        k=k-1
        self.getP(strs,st,n,k,nf)
        return "".join(x for x in strs)

leetcode Question 112: Triangle

Triangle:

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

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

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Analysis:
This problem is more likely to be a (dynamic programming) DP problem,
where a[n][i] = a[n][i]+min(a[n-1][i], a[n-1][i-1]).
Note that in this problem, "adjacent" of a[i][j] means a[i-1][j] and a[i-1][j-1], if available(not out of bound), while a[i-1][j+1] is not "adjacent" element.

The minimum of the last line after computing is the final result.

Code:

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = triangle.size();
        if (n==0){return 0;}
        
        for (int i=1;i<n;i++){
            for (int j=0;j<triangle[i].size();j++){
                if (j==0){triangle[i][j] += triangle[i-1][j];}
                if (j>0){
                    if (i>j){
                        triangle[i][j] += min(triangle[i-1][j-1],triangle[i-1][j]);
                    }else{
                        triangle[i][j] += triangle[i-1][j-1];
                    }
                    
                }
                
            }
        }
        sort(triangle[n-1].begin(),triangle[n-1].end());
        return triangle[n-1][0];    
    }
};

leetcode Question 101: Spiral Matrix II

Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n² in spiral order.

For example,
Given n = 3,

You should return the following matrix:

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

Analysis:
Having solved the previous problem. This problem seems easier than the last one.

The key idea is to consider the single step ----- "Which direction to go filling the next number?"
There are only four directions.
Be careful with one thing----- you keep going one direction until meet the end.

Code(Updated 2013.10):

class Solution {
public:
    vector<vector<int> > generateMatrix(int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        vector<vector<int> > res(n,vector<int>(n,0));
        if (n==0){return res;}
        int i=1;
        int x = 0;
        int y = 0;
        res[0][0]=i++;
        while (i<=n*n){
            while (y+1<n && res[x][y+1]==0){   // keep going right
                res[x][++y]=i++;
            }
            while (x+1<n && res[x+1][y]==0){   // keep going down
                res[++x][y]=i++;
            }
            while (y-1>=0 && res[x][y-1]==0){  // keep going left
                res[x][--y]=i++;
            }
            while (x-1>=0 && res[x-1][y]==0){  // keep going up
                res[--x][y]=i++;
            }
        }
        return res;
    }
};

leetcode Question 100: Spiral Matrix I

Spiral Matrix I

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

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

You should return [1,2,3,6,9,8,7,4,5].

Analysis:

When I first face this problem, it took me hours to handle the array indices, and always missed some cases. Then I give up get a whole line once, but tried to get one element in every step. The problem became much easier and took me less than 10 minutes to solve it!

Let's think in this way:
There are m*n elements I need to push into the result vector. So we just do it one by one.
For each element, there are only 4 directions can go to the next, left, down, right, and up.
The conditions are almost the same: while the next element in such direction is available, go to the next. Otherwise try the next one direction.
Available above means: (1) meet the bound of the array. (2) The next element has been visited.

Once we get the algorithm, coding becomes pretty clear, just use a mask bool array to store the visited elements. Big loop from 1 to n*m, (i,j) is the current position, keep try 4 directions, until all the elements are popped.

Code:

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> res;
        if (matrix.empty()){return res;}
        if (matrix.size()==1){return matrix[0];}
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<bool> > mask(m,vector<bool>(n,false));
        int i=0;
        int j=0;
        int k=0;
        res.push_back(matrix[i][j]);
        mask[0][0]=true;
        while (k<m*n-1){
            while ((j+1<n)&&(mask[i][j+1]==false)){
                j++;
                k++;
                res.push_back(matrix[i][j]);
                mask[i][j]=true;
            }
            
            while ((i+1<m)&&(mask[i+1][j]==false)){
                i++;
                k++;
                res.push_back(matrix[i][j]);
                mask[i][j]=true;
            }
            
            while ((j>0)&&(mask[i][j-1]==false)){
                j--;
                k++;
                res.push_back(matrix[i][j]);
                mask[i][j]=true;
            }
            
            while ((i>0)&&(mask[i-1][j]==false)){
                i--;
                k++;
                res.push_back(matrix[i][j]);
                mask[i][j]=true;
            }
        }
        return res;
    }
};

leetcode Question 61: Next permutation

Next permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Analysis:
Well, this is more like a math problem, and I don't know how to solve it.
From the wikipedia, one classic algorithm to generate next permutation is:
Step 1: Find the largest index k, such that A[k]<A[k+1]. If not exist, this is the last permutation. (in this problem just sort the vector and return.)
Step 2: Find the largest index l, such that A[l]>A[k].
Step 3: Swap A[k] and A[l].
Step 4: Reverse A[k+1] to the end.

OK! Having the algorithm then coding becomes an easy thing!

Code(C++):

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int sz = num.size();
        int k=-1;
        int l;
        //step1
        for (int i=0;i<sz-1;i++){
            if (num[i]<num[i+1]){
                k=i;
            }
        }
        if (k==-1){
            sort(num.begin(),num.end());
            return;
        }
        
        //step2
        for (int i=k+1;i<sz;i++){
            if (num[i]>num[k]){
                l=i;
            }
        }
        //step3        
        int tmp = num[l];
        num[l]=num[k];
        num[k]=tmp;
        //step4
        reverse(num.begin()+k+1,num.end());
    }
};

Code(Python):

class Solution:
    # @param num, a list of integer
    # @return a list of integer
    def nextPermutation(self, num):
        k = -1;
        #Step 1: find max k A[k]<A[k+1]
        for i in xrange(0,len(num)-1):
            if num[i]<num[i+1]:
                k = i;
        if k == -1:
            num.reverse();
            return num;
        else:
            #Step 2: find l A[l]>A[k]
            for i in xrange(k+1, len(num)):
                if num[i]>num[k]:
                    l = i;
            #Step 3: swap A[l] A[k]
            num[l], num[k] = num[k], num[l];
            #Step 4: reverse k+1 to end
            num[k+1:len(num):1] = num[len(num)-1:k:-1];
            return num;

leetcode Question 114: Unique Binary Search Trees

Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Analysis:

DP works well in this problem.

For each sequence from 1 to n, # of BSTs equals:
Sum of BSTs where each number (from 1 to n) is considered as the root node.
For each node, # of BSTs equals:
# of bsts of its left child times # of bsts of its right child.

Denote bst[i] = the number of BSTs can be constructed that store values from 1..n.

n = 1, Node = {1}, bst[1] = 1

n = 2, Node = {1, 2}
when 1 is the root node, there is 1 bst
1
\
2
when 2 is the root node, there is 1 bst
2
/
1
bst[2] = 2

n = 3, Node = {1, 2, 3}
when 1 is the root node, bst[3] = bst[3] + bst[2] where stores 2 values (2 and 3)
1 1 1
\ = \ \
BSTs of {2,3} 2 3
\ /
3 2
when 2 is the root node, bst[3] = bst[3] + bst[1] + bst[1]
2
/ \
1 3
when 3 is the root node, bst[3] = bst[3] + bst[2] where stores 2 values (1 and 2)
3 3 3
/ = / /
BSTs of {1,2} 2 1
/ \
1 2

Code(C++):

class Solution {
public:
    int numTrees(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> table(n+1,0);
        if (n==0){return 0;}
        table[0]=1;
        table[1]=1;
        table[2]=2;
        for (int i=3;i<=n;i++){
            int res=0;
            for (int j=0;j<=i-1;j++){
                res = res+ table[j]*table[i-1-j];
            }
            table[i]=res;
        }
        return table[n];   
    }
};

Code(Python):

class Solution:
    # @return an integer
    def numTrees(self, n):
        if n <= 1:
            return 1
        res = [0 for x in range(n + 1)]
        res[0] = 1
        res[1] = 1
        i = 2
        while i <= n :
            for j in xrange(i):
                res[i] = res[i] + res[j]* res[i-j-1]
            i = i + 1
        return res[n]

leetcode Question 73: Populating Next Right Pointers in Each Node II

Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

You may only use constant extra space.

For example,
Given the following binary tree,

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

New updates (201308):
Idea is to use dfs and only constant space is used. The key is to use the "next" pointer and search right child first then the left child. Details see the code comment.

Code:

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void dfs(TreeLinkNode *root){
        if (!root){return;}  // if current node is not valid return
        
        if (root->next==NULL){ // if current node is not in the right boundary of this level
            if (root->right){root->right->next = NULL;} // if has right child, its next is null
            if (root->left){root->left->next = root->right;}//if has left child, its next is its right
        }else{ // if the current node has next node in its right
            TreeLinkNode* p = root->next; //the pointer travle along this level 
            TreeLinkNode* q=NULL; // the next valid pointer in the level+1 , or NULL if not found
            while (p){ //find the next valid child of root node
                if (p->left){q =p->left; break;}
                if (p->right){q =p->right; break;}
                p=p->next;
            }
            if (root->right){root->right->next = q;} //set right child if exists
            if (root->left && root->right ){root->left->next = root->right;}//set left if right exists
            if (root->left && !root->right) {root->left->next = q;} // set left if right not exist
        }
        
        dfs(root->right); // search right child, order is important
        dfs(root->left);  // search left child
    }
    void connect(TreeLinkNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!root){return;}
        root->next = NULL;
        dfs(root);
    }
};

Old solution (BFS):
Idea is almost the same to previous problem.
Just we cannot use the level information directly, so we can store the level info!
Use a pair instead of a single tree node in the queue.
Details see the code.

Code:

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        queue<pair<TreeLinkNode*, int> > que;
        if (root==NULL) {return;}
        que.push(pair<TreeLinkNode*, int>(root,1));
        
        while (!que.empty()){
            pair<TreeLinkNode*, int>p =que.front();
            que.pop();
            if (p.first->left!=NULL){
                que.push(pair<TreeLinkNode*, int>(p.first->left,p.second+1));
            }
            if (p.first->right!=NULL){
                que.push(pair<TreeLinkNode*, int>(p.first->right,p.second+1));
            }
            
            if (que.empty()){
                p.first->next = NULL;
                return;
            }
            if (p.second != que.front().second){
                p.first->next = NULL;
            }else{
                p.first->next = que.front().first;
            }
        }
         
    }
};

leetcode Question 72: Populating Next Right Pointers in Each Node

Populating Next Right Pointers in Each Node

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void dfs(TreeLinkNode *root){
        if (!root){return;}  // if current node is not valid return
        
        if (root->next==NULL){ // if current node is not in the right boundary of this level
            if (root->right){root->right->next = NULL;} // if has right child, its next is null
            if (root->left){root->left->next = root->right;}//if has left child, its next is its right
        }else{ // if the current node has next node in its right
            TreeLinkNode* p = root->next; //the pointer travle along this level 
            TreeLinkNode* q=NULL; // the next valid pointer in the level+1 , or NULL if not found
            while (p){ //find the next valid child of root node
                if (p->left){q =p->left; break;}
                if (p->right){q =p->right; break;}
                p=p->next;
            }
            if (root->right){root->right->next = q;} //set right child if exists
            if (root->left && root->right ){root->left->next = root->right;}//set left if right exists
            if (root->left && !root->right) {root->left->next = q;} // set left if right not exist
        }
        
        dfs(root->right); // search right child, order is important
        dfs(root->left);  // search left child
    }
    void connect(TreeLinkNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!root){return;}
        root->next = NULL;
        dfs(root);
    }
};

Old solution (BFS):
We know that the tree is full binary tree, which is a very powerful condition that we can use.
As can be seen in the tree above, we need to deal with the nodes according to each level of the tree.
Easily the level-order traversal popped out!
What we need? Yes, just a queue!
What about the level? Here comes the condition of this problem. A full binary tree which have ith level have
2^i - 1 nodes.

Once we have the queue, the problem is quite easy. Just make the last node's next pointer NULL, set other nodes' next to the next element in the queue. Well done!

The space needed is less than 2^i-1;

Code:

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        queue<TreeLinkNode*> que;
        if (root==NULL) {return;}
        que.push(root);
        int i=1;
        int l=1;
        while (!que.empty()){
            TreeLinkNode* p =que.front();
            que.pop();
            if ((p->right!=NULL)&&(p->left!=NULL)){
                que.push(p->left);
                que.push(p->right);
            }
            if (i==(pow(2,l)-1)){
                p->next = NULL;
                i++;
                l++;
            }else{
                p->next = que.front();
                i++;
            }
        }
        
    }
};

I currently have several intern openings for deep learning and computer vision.

This is an internship for both research and development.

You will have opportunities to publish high level papers in computer vision and deep learning, or develop cool real world AI application if you prefer more for coding!

If you have experiences in deep learning and computer vision, and interested in this intern, please send me your resume by email (xperzy AT gmail DOT com) with subject "CV intern".

Useful link: C++ reference

Basics:

Common Sorting Algorithms

Hash Table Basics

Tree Traversal (Recursive & Non-Recursive)