Leetcode: Permutation Sequence in C++

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):

1. "123"

1. "132"

1. "213"

1. "231"

1. "312"

1. "321"

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

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

Solution:
string getPermutation(int n, int k) {
        string result;
        vector<int> num(n);
        int total = 1;
        for(int i=0;i<n;i++)
        {
            num[i] = i+1;
            total *= i+1;
        }
        int q;
        for(int i=n;i>=1;i--)
        {
            total = total/i;
            q = (k-1)/total;
            k = k - q*total;
            result+='0'+num[q];
            num.erase(num.begin()+q);
        }
        return result;
    }

Leetcode: Permutations II in C++

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

Solution:

void cal(vector<int> &num, vector<int>& cur, vector<int>& visited, vector<vector<int> >& result)
    {
        if(cur.size()==num.size())
        {
            result.push_back(cur);
            return;
        }
        for(int i=0;i<num.size();i++)
        {
            if(visited[i]!=1)
            {
/* if previous number equal to current one but is not used, we can not use this one. Since If we use, we will use previous number in next round which is duplicated.*/
                if(i>0&&num[i]==num[i-1]&&visited[i-1]==0) 
                   continue;
                cur.push_back(num[i]);
                visited[i] =1;
                cal(num, cur, visited, result);
                cur.pop_back();
                visited[i] =0;
            }
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > result;
        int len = num.size();
        vector<int> visited(len, 0);
        vector<int> cur;
        sort(num.begin(),num.end());
        cal(num, cur, visited, result);
        return result;
    }

Leetcode: Permutations in C++

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

void cal(vector<int> &num, vector<int>& cur, vector<int>& visited, vector<vector<int> >& result)
    {
        if(cur.size()==num.size())
        {
            result.push_back(cur);
            return;
        }
        for(int i=0;i<num.size();i++)
        {
            if(visited[i]!=1)
            {
                cur.push_back(num[i]);
                visited[i] =1;
                cal(num, cur, visited, result);
                cur.pop_back();
                visited[i] =0;
            }
        }
    }
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > result;
        int len = num.size();
        vector<int> visited(len, 0);
        vector<int> cur;
        cal(num, cur, visited, result);
        return result;
    }

Leetcode: Largest Rectangle in Histogram in C++

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

Solution:
int largestRectangleArea(vector<int> &height) {
        stack<int> p;
        int i = 0, m = 0;
        height.push_back(-1);
        while(i < height.size()) {
        if(p.empty() || height[p.top()] < height[i])
        {
            p.push(i);
            i++;
        }
        else {
            int t = p.top();
            p.pop();
            m = max(m, height[t] * (p.empty() ? i : i - p.top() - 1 ));
        }
    }
    return m;
    }

Leetcode: Count and Say in C++

The count-and-say sequence is the sequence of integers beginning as follows:

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

1 is read off as "one 1" or 11.

Given an integer n, generate the n^th sequence.

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

Solution:
string countAndSay(int n) {
        if(n==1)
        return "1";
        string current = "1";
        for(int i=2;i<=n;i++)
        {
            int pos = 1;
            int count =1;
            char pre = current[0];
            string tmp = "";
            while(pos<current.size())
            {
                if(current[pos]==pre)
                {
                    count++;
                }
                else
                {
                    stringstream ss;
                    ss << count;
                    tmp+=ss.str()+pre;
                    pre = current[pos];
                    count = 1;
                }
                pos++;
            }
            stringstream ss;
            ss << count;
            tmp+=ss.str()+pre;
            current = tmp;
        }
        return current;
    }

Leetcode: Combination in C++

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

Solution: 
void helper(vector<vector<int> >& result,vector<int> current, int k, int n, int cur )
    {
        if(current.size()==k)
        {
            result.push_back(current);
            return;
        }
        for(int i=cur;i<=n;i++)
        {
            current.push_back(i);
            helper(result,current,k,n,i+1);
            current.pop_back();
        }
    }
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > result;
        vector<int> solution;  
        helper(result,solution, k,n,1);
        return result;
    }

Leetcode: Pow(x, n) in C++

Implement pow(x, n).
Solution:
double pow(double x, int n) {
        if(n==1)
        return x;
        else if(n==0)
        return 1;
        int absn = abs(n);
        double k = pow(x,absn/2);
        double result =  k*k*pow(x,absn%2);
        if(n<0)
        result = 1.000/result;
        return result;
    }