[leetcode][**] Unique PathII

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

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

The total number of unique paths is 2.

Note: m and n will be at most 100.

My Code:

 
 int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        int m = obstacleGrid.size();
        if(m == 0) return 0;
        int n = obstacleGrid[0].size();
        if(n == 0) return 0;
        int table[m][n];
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(obstacleGrid[i][j] == 1) {
                    table[i][j] = 0;
                    continue;
                }
                if(i == 0 && j == 0) 
                    table[i][j] = 1;
                else if(i == 0 && j != 0){
                    table[i][j] = table[i][j-1];
                } 
                else if(i != 0 && j == 0) {
                        table[i][j] = table[i-1][j];
                }
                else{
                    table[i][j] = table[i-1][j]+table[i][j-1];
                }
            }
        }
        return table[m-1][n-1];
    }

[leetcode][*]Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

int uniquePaths(int m, int n) {
        int table[n][m];
        if(m == 0 || n == 0) return 0;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                if(i == 0 && j == 0) table[i][j] = 1;
                else if(i == 0 && j != 0) table[i][j] = table[i][j-1];
                else if(i != 0 && j == 0) table[i][j] = table[i-1][j];
                else{
                    table[i][j] = table[i-1][j]+table[i][j-1];
                }
            }
        }
        return table[n-1][m-1];
    }

[leetcode][****] Simplify Path

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

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

1. If the train of thought if not clear, this problem is hard.
2. /. does nothing;  /.. will get you back to the upper directory;
Algorithm:
1. delete the repeated "/".
2. add a "/" back to pair up all the "/"s.
3. only "/." and "/.." is considered seperatedly.
4. flag to mark the second "/" and handle the pop or push of stacks.

My Code:

  string simplifyPath(string path) {
       string ret = "";
       //erase "//"
       for(int i = path.length() - 1; i >=0; --i){
           if(path[i]==path[i+1] && path[i] == '/'){
               path.erase(i,1);
           }
       }
       //add "/" to the end to make sure "/" are in pairs
       if(path[path.length() - 1] != '/')
          path += '/';
       stack<string> cur;
       int flag = 0;
       string str = "";
       for(int i = 0; i < path.length(); ++i){
           if(path[i] == '/') ++flag;
           if(flag == 1) str += path[i];
           else if(flag == 2){
               if(str == "/.." && !cur.empty())
                    cur.pop();
               if(str != "/." && str!="/.." )
                    cur.push(str);
               flag = 1;
               str = "/";
           }
       }
       while(!cur.empty()){
            ret = cur.top()+ret;
            cur.pop();
       }
       if(ret.empty()) return "/";
       return ret;
    }

[leetcode][***] Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

bool isNumber(string a){
        if(a.empty()) return false;
        int i = 0;
        if(a.length() == 1){
            return a[0] >= '0' && a[0] <= '9';
        }
        if(a[0] == '-'|| a[0] == '+') ++i;
        for(; i<a.length(); ++i){
            if(a[i]<'0' || a[i] >'9') return false;
        }
        return true;
    }
    int str2num(string a){
        if(a.empty()) return 0;
        int ret = 0;
        bool neg = false;
        int i = 0;
        if(a[0] == '-') {
            neg = true;
            ++i;
        }
        else if(a[0] == '+') {
            neg = false;
            ++i;
        }
        for(; i < a.length(); ++i){
            ret = ret*10+(a[i]-'0');
        }
        if(neg) return -ret;
        return ret;
    }
    int evalRPN(vector<string> &tokens) {
        if(tokens.empty()) return 0;
        stack<string> s1;
        stack<int> s2;
        for(int i = tokens.size() - 1; i >= 0; --i)
            s1.push(tokens[i]);
        while(!s1.empty()){
            string cur = s1.top();
            s1.pop();
            if(isNumber(cur)){
                int curnum = str2num(cur);
                s2.push(curnum);
            }
            else{
                int b = s2.top();
                s2.pop();
                int a = s2.top();
                s2.pop();
                int res;
                switch(cur[0]){
                    case('+'): res = a+b; break;
                    case('-'): res = a-b; break;
                    case('*'): res = a*b; break;
                    case('/'): res = a/b; break;
                    default: break;
                }
                s2.push(res);
            }
        }
        return s2.top();
    }

[leetcode][****] Letter Combinations

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Basics:

1. string construction from char. string s(size_t n, char c).(Fills the string with n consecutive copies of character c.)

2. Switch: 

switch(variable){
  case(xx): xxx; break;
  ....
  default: xxx;
}

Algorithm:

Recursion Solve the problem.

My Code

string getChars(char a){
        switch(a){
        case('0'): return " ";
        case('2'): return "abc";
        case('3'): return "def";
        case('4'): return "ghi";
        case('5'): return "jkl";
        case('6'): return "mno";
        case('7'): return "pqrs";
        case('8'): return "tuv";
        case('9'): return "wxyz";
        default: return "";
    }
 }
    vector<string> RBuild(vector<string> str){
        vector<string> ret;
        if(str.empty()) return ret;
        string cur = str[0];
        str.erase(str.begin());
        vector<string> nxt = RBuild(str);
        if(nxt.empty()){
            for(int i = 0; i < cur.size(); ++i){
                string a(1, cur[i]);
                ret.push_back(a);
            }
            return ret;
        }else{
            for(int i = 0; i < cur.size(); ++i){    
                for(int j = 0; j < nxt.size(); ++j){
                    string a = cur[i]+nxt[j];
                    ret.push_back(a);
                }
            }
            return ret;
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> ret;
        if(digits.empty()) {
            ret.push_back("");
            return ret;
        }
        vector<string> v;
        for(int i = 0; i < digits.length(); ++i){
            string str = getChars(digits[i]);
            if(str != ""){
                v.push_back(str);
            }
        }
        ret = RBuild(v);
        return ret;
       
    }

[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],
]

My Code:

 void bfs(int start,int end, int k, vector<int> &current, vector<vector<int> > &res){
        if(end - start + 1 < k) return;
        if(k == 0){
            res.push_back(current);
            return;
        }
        for(int i = start; i <= end; ++i){
            current.push_back(i);
            bfs(i+1, end, k-1, current, res);
            current.pop_back();
        }
    }
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int>> res;
        if(n < k) return res;
        vector<int> current;
        bfs(1, n, k, current, res);
        return res;
    }

[leetcode][*]

 bool validchar(char a){
        if(a >= '0' && a <= '9' || a >='a' && a <='z' || a >= 'A' && a <= 'Z')
            return true;
        else
            return false;
    }
    bool mequal(char a, char b){
        if((a - 'a' == b - 'a') || (a - 'a' == b - 'A') 
           ||(a - 'A' == b - 'a') || (a - 'A' == b - 'A'))
           return true;
        else
            return false;
    }
    bool isPalindrome(string s) {
        if(s.empty()) return true;
        int r = 0;
        int l = s.length() - 1;
        while(r < l){
            while(!validchar(s[r]) && r < l){
                ++r;
            }
            while(!validchar(s[l]) && r < l){
                --l;
            }
            if(!mequal(s[r], s[l])){
                return false;
            }else{
                ++r;
                --l;
            }
        }
        return true;
    }