Friday, October 10, 2014

[Leetcode] 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".

vector<string> splitPath(string path)
    {
        vector<string> ret;
        int i=0;
        while(i < path.size())
        {
            while(i < path.size() && path[i] != '/')
                i++;
            int j = i;
            i++;
            while(i < path.size() && path[i] != '/')
                i++;
                
            if (j != path.size())
                ret.push_back(path.substr(j+1, i-(j+1)));
        }
        return ret;
    }

    string simplifyPath(string path) {
        vector<string> paths = splitPath(path);
        stack<string> s;
        for(int i=0; i<paths.size(); i++)
        {
            //case: "/.."
            if (paths[i] == "..")
            {
                if (!s.empty())
                    s.pop();
            }
            //case: "////"
            else if (paths[i] != "." && paths[i].size() > 0)
                s.push(paths[i]);
        }
        
        string outPath;
        while(!s.empty())
        {
            string p = s.top();
            s.pop();
            outPath.insert(0, p);
            outPath.insert(0,"/");
        }
        
        if (outPath.size() == 0)
            outPath = "/";
            
        return outPath;
        
    }

[Leetcode] Set Matrix Zeroes

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?

void setZeroes(vector<vector<int> > &matrix) {
        //borrow first row and first column as the temporary storage to indicate whether this row/col need to be zeroed
        //use two flag to indicate whether first row/col need to be zeroed 
        bool firstRowZero = false;
        bool firstColZero = false;
        for(int i=0; i<matrix.size(); i++)
        {
            for(int j=0; j<matrix[0].size(); j++)
            {
                if (matrix[i][j] == 0)
                {
                    //0 in the first row
                    if (i == 0)
                        firstRowZero = true;
                    if (j == 0)
                        firstColZero = true;
                    //the col j should be zeroed    
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        
        //begin from 1 because first row/col can be zero only if firstRowZero is true
        for(int i=1; i<matrix.size(); i++)
        {
            if (matrix[i][0] == 0)
            {
                for(int j =0; j<matrix[0].size(); j++)
                    matrix[i][j] = 0;
            }
        }

        for(int i=1; i<matrix[0].size(); i++)
        {
            if (matrix[0][i] == 0)
            {
                for(int j =0; j<matrix.size(); j++)
                    matrix[j][i] = 0;
            }
        }
        
        //zero first row if necessary
        if (firstRowZero)
        {
            for(int i =0; i<matrix[0].size(); i++)
                matrix[0][i] = 0;
        }

        if (firstColZero)
        {
            for(int i =0; i<matrix.size(); i++)
                matrix[i][0] = 0;
        }
    }

[Leetcode] 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 from left to right.
  • The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
Given target = 3, return true.

    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        int b = 0;
        int e = matrix.size() * matrix[0].size() - 1;
        while(b <= e)
        {
            //treat the whole matrix as a long array and do the binary search
            int m = (b+e)/2;
            int row = m / matrix[0].size();
            int col = m % matrix[0].size();
            if (matrix[row][col] == target)
                return true;
            else if (target < matrix[row][col])
                e = m - 1;
            else
                b = m + 1;
        }
        
        return false;
    }

[Leetcode] Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.

    void sortColors(int A[], int n) {
        int i = 0;
        int j = 0;
        int k = n-1;
        while(i <= k)
        {
            if (A[i] == 0)
            {
                //swap 0 with the first 1 so that all 0s are before 1s
                swap(A[i], A[j]);
                i++;
                j++;
            }
            else if (A[i] == 1)
            {
                //do nothing if it is 1
                i++;
            }
            else
            {
                //swap 2 with the last element which is not 2
                //note A[k] could be 2 as well so we should not move i forward
                swap(A[i], A[k]);
                k--;
            }
        }
    }

[Leetcode] Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

void dfs(vector<vector<int> >& ret, int n, int k, int m, vector<int>& nums)
{
 if (nums.size() == k)
 {
  ret.push_back(nums);
 }
 else
 {
  for (int i = m; i <= n; i++)
  {
   nums.push_back(i);
   dfs(ret, n, k, i + 1, nums);
   nums.pop_back();
  }
 }
}

vector<vector<int> > combine(int n, int k) {
 vector<vector<int> > ret;
 vector<int> nums;
 dfs(ret, n, k, 1, nums);

 return ret;
}

[Leetcode] Subsets

Given a set of distinct integers, S, return all possible subsets.
Note:
  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3], a solution is:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

void helper(vector<int> S, vector<vector<int> >& ret, vector<int>& tmp, int k)
    {
        ret.push_back(tmp);
        for(int i=k; i<S.size(); i++)
        {
            tmp.push_back(S[i]);
            helper(S, ret, tmp, i+1);
            tmp.pop_back();
        }
    }

    vector<vector<int> > subsets(vector<int> &S) {
        sort(S.begin(), S.end());
        vector<vector<int> > ret;
        vector<int> tmp;
        helper(S, ret, tmp, 0);
        
        return ret;
    }

[Leetcode] Word Search

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.


    bool helper(vector<vector<char> > &board, string word, int i, int j, int k)
    {
        //if all char in the word has been found in the board
        if (k == word.size())
            return true;
        //if not the correct way    
        else if (i <0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] == '#' || word[k] != board[i][j])
            return false;
        else 
        {
            char tmp = board[i][j];
            board[i][j] = '#';
            //if andy of all its neighbors matches, we found a solution
            if (helper(board, word, i +1, j, k+1) ||
                helper(board, word, i, j+1, k+1) ||
                helper(board, word, i-1, j, k+1) ||
                helper(board, word, i, j-1, k+1))
                return true;
            //otherwise, backtrack
            board[i][j] = tmp;
            
            return false;            
        }

    }

    bool exist(vector<vector<char> > &board, string word) {
        for(int i=0; i<board.size(); i++)
        {
            for(int j=0; j<board[0].size(); j++)
            {
                //find a char in the board match the first char of the word
                if (board[i][j] == word[0])
                {
                    if (helper(board, word, i, j, 0))
                        return true;
                }
            }
        }
        
        return false;
    }