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

Analysis:

class Solution {
public:
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] 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:

Since there are duplicates, A[m] could be equal to A[b] or A[e]. If A[m] == A[e], then A[e] could not be the target so e = e -1 to shrink the search range. Similarly, if A[m] == A[b], let b = b+1 to shrink the range.

class Solution {
public:
    bool search(int A[], int n, int target) {
        int b = 0;
        int e = n - 1;
        while(b <= e)
        {
            int m = (b + e) / 2;
            if (A[m] == target)
                return true;
            else if (A[m] == A[e])
                e = e - 1;
            else if (A[m] == A[b])
                b = b + 1;
            else if (A[m] < A[e])
            {
                if (target > A[m] && target <= A[e])
                    b = m + 1;
                else
                    e = m - 1;
            }
            else
            {
                if (target < A[m] && target >= A[b])
                    e = m - 1;
                else
                    b = m + 1;                
            }
        }
        
        return false;
    }
};

[Leetcode] 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:

After rotated, half of the array, either [b, m] or [m, e] must be sorted. If the target was in the range, do the binary search for the half, otherwise, do the binary search for another half. 

class Solution {
public:
    int search(int A[], int n, int target) {
        int b = 0;
        int e = n-1;
        while(b <= e)
        {
            int m = (b+e)/2;
            if (A[m] == target)
                return m;
            else if (A[m] < A[e])
            {
                if (target > A[m] && target <= A[e])
                    b = m + 1;
                else
                    e = m - 1;
            }
            else
            {
                if (target < A[m] && target >= A[b])
                    e = m - 1;
                else
                    b = m + 1;                
            }
        }
        
        return -1;
    }
};

[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

Analysis:

Use a stack to store the numbers and pop out two numbers and do the operation whenever an operator was encountered. 

class Solution {
public:

    int doOperation(int op1, int op2, string theOperator)
    {
        if (theOperator == "+")
            return op1 + op2;
        else if (theOperator == "-")
            return op1 - op2;
        else if (theOperator == "*")
            return op1 * op2;
        else if (theOperator == "/")
            return op1 / op2;
        else
            return 0;
    }

    int evalRPN(vector &tokens) {
        stack s;
        for(int i=0; i < tokens.size();i++)
        {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
            {
                int op1 = s.top();
                s.pop();
                int op2 = s.top();
                s.pop();
                int r = doOperation(op2, op1, tokens[i]);
                s.push(r);
            }
            else
            {
                s.push(atoi(tokens[i].c_str()));
            }
        }
        
        return s.top();
    }
};

[Leetcode] Reverse Words in a String

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

click to show clarification.

Clarification:

• What constitutes a word?
  A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
  Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
  Reduce them to a single space in the reversed string.

class Solution {
public:

    vector< string > splitWords(string& str)
    {
        vector< string > strs;
        int i =0;
        while(i < str.size())
        {
            while(i < str.size() && str[i] == ' ')
                i++;
                
            int j = i;
            while(i < str.size() && str[i] != ' ')
                i++;
                
            if (j < str.size())
                strs.push_back(str.substr(j, i-j));
        }
        
        return strs;
    }

    void reverseWords(string &s) {
         vector< string > strs = splitWords(s);
         s.clear();
         for(int i=strs.size()-1; i>=0;i--)
        {
            s.append(strs[i]);
            if (i != 0)
                s.append(" ");
        }
    }
};

[Leetcode] Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

Analysis:

class Solution {
public:
    string countAndSay(int n) {
        string str = "1";
        
        for(int i=1; i< n; i++)
        {
            string tmp;
            int count = 1;
            for(int j=1; j< =str.size(); j++)
            {
                //1. using str.size() as flag to handle remaining chars
                //2. if current value is not equal to previous one, then reset the count and save the current counting
                if (j ==str.size() || str[j] != str[j-1])
                {
                    tmp.push_back(count+'0');
                    tmp.push_back(str[j-1]);
                    count = 1;
                }
                else 
                    count++;
            }
            str = tmp;
        }
        
        return str;
    }
};

[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.

Pasted from <http://leetcode.com/onlinejudge>

Analysis:

Do DFS for each matched first character. Note: don't forget to set visited flag for the char in board for BFS and DFS. using board[i][j] = '#' in the code.

bool helper(vector< vector< char> > &board, string word, int i, int j, int k)
{
    if (k == word.size())
        return true;
    else if (i <0 data-blogger-escaped-i="">= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word[k])
        return false;
    else {
        //dfs, marked the cell as visited
        char tmp = board[i][j];
        board[i][j] = '#';
        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;
        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[i].size();j++)
        {
            if (board[i][j] == word[0] && helper(board, word, i, j, 0))
                return true;
        }
    }
    
    return false;
}