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]. Problem link Solution

  • recursive solution, only when last element is not  (the same and used)
class Solution {
public:
    vector<vector > permuteUnique(vector &num) {
        sort(num.begin(), num.end());
        vector<vector> vv;
        vector v;
        vector u(num.size(), false);
        rec(vv, v, u, num);
        return vv;
    }
    
    void rec(vector<vector> &vv, vector &v, vector &u, vector &num){
        for (int i=0; i<num.size(); ++i){
            if (!u[i] && (i==0 || i>0 && !(num[i]==num[i-1] && !u[i-1]))){
                v.push_back(num[i]);
                u[i] = true;
                if (v.size()==num.size()){
                    vv.push_back(v);
                }else{
                    rec(vv, v, u, num);
                }
                v.pop_back();
                u[i] = false;
            }
        }
    }
};
Advertisements
Permutations II

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

Problem link

Solution

  • backtrack with stack
class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector< vector<int> > vv;
        int i;
        unsigned n=num.size();
        vector<int> v;
        vector<bool> used(n, false);

        i=0;
        while (true){
            // only stop the loop when it is at level zero and i goes over
            v.push_back(i);
            used[i]=true;
            for (i=0; i<n; i++){// looks for next available position to select
                if (used[i]==false){
                    break;
                }
            }
            if (v.size()==n){
                // a complete sequence is generated, backtrack
                vector<int> tmp;
                for (int j=0; j<v.size(); j++){
                    tmp.push_back(num[v[j]]);
                }
                vv.push_back(tmp);
                int j;
                do{
                    j=v.back();
                    v.pop_back();
                    used[j]=false;
                    for (++j; j<n; ++j){// starting from current indices, looks for next available position to select
                        if (used[j]==false){
                        break;
                        }
                    }
                }while(j>=n&&!v.empty()|| (j<n&&used[j]));
                if (j>=n&&v.empty()){
                    break;
                }
                i=j;
            }
        }
        return vv;
    }
};

Recursive solution

  • use an auxiliary array to track whether the current element has been used in the current permutation
class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int>> vv;
        vector<bool> u(num.size(), false); // used or 
        vector<int> v;
        rec(vv, v, u, num);
        return vv;
    }
    
    void rec(vector<vector<int>> &vv, vector<int> &v, vector<bool> &u, vector<int> &num){
        for (int i=0; i<num.size(); i++){
            if (!u[i]){ // if i is not used
                v.push_back(num[i]);
                u[i] = true;
                if (v.size()==num.size()){
                    vv.push_back(v);
                }else{
                    rec(vv, v, u, num);
                }
                v.pop_back();
                u[i] = false;
            }
        }
    }
};
Permutations

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

input n, output the count of how many zeroes at the end of n!. where n! = 1 * 2 * … * n

for example

n = 6, n! = 720, answer = 1.
n = 8, n! = 40320, answer = 1.
n = 32, n! = 263130836933693530167218012160000000, answer = 7

 

Note: Your solution should be in logarithmic time complexity.

Problem link

Solution

  • just count how many 5 factors in the natural number sequence
  • be careful about overflow in int, so use long for “base” variable
class Solution {
public:
    int trailingZeroes(int n) {
        if (!n) return 0;
        int num = 0;
        long base = 5;
        int l;
        while (l = n/base){
            num += l;
            base*=5;
        }
        return num;
    }
};
Factorial Trailing Zeroes

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.

Problem link

Solution

  • the number of possible unique paths is exactly the binomial coefficient {\choose m+n-2 m-1}
  • use loops rather than computing factorial when calculating the binomial coefficients
class Solution {
public:
    int uniquePaths(int m, int n) {
        long long prod = 1;
        --m;
        --n;
        int small = min(m,n);
        int big = max(m,n);
        for (long long i=big+1; i<=m+n; i++){
            prod = prod * i / (i-big);
        }
        return (int)prod;
    }
};
Unique Paths

Subsets II

Given a collection of integers that might contain duplicates, 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,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Problem link

Solution

  • check if previous element is the same when creating a new subset
  • similar to combination sum II
class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        vector<vector<int> > vv;
        sort(S.begin(), S.end());
        for (int i=0; i<=S.size(); ++i){
            vector<int> v;
            rec(S.size(), i, 0, vv, v, S);
        }
        return vv;
    }
    void rec(int n, int k, int l, vector<vector<int> > &vv, vector<int> &v, vector<int> S){
        if (v.size()==k){
            vv.push_back(v);
            return;
        }
        for (int i=l; i<n; ++i){
            if (i>l && S[i]==S[i-1]) continue;
            v.push_back(S[i]);
            rec(n,k,i+1,vv,v,S);
            v.pop_back();
        }
    }
};
Subsets II

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

Problem link

Solution

  • a generalization to combinations
  • the original array is not sorted
  • the indices for recursion runs from 0 to n-1
class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int> > vv;
        sort(S.begin(), S.end());
        for (int i=0; i<=S.size(); ++i){
            vector<int> v;
            rec(S.size(), i, 0, vv, v, S);
        }
        return vv;
    }
    
    void rec(int n, int k, int l, vector<vector<int> > &vv, vector<int> &v, vector<int> S){
        if (v.size()==k){
            vv.push_back(v);
            return;
        }
        for (int i=l; i<n; ++i){
            v.push_back(S[i]);
            rec(n,k,i+1,vv,v,S);
            v.pop_back();
        }
    }
};
Subsets

Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

Problem link

Solution

  • two pass algorithm: count how many digits first
  • negative number are not palindrome
class Solution {
public:
    bool isPalindrome(int x) {
        if (x<0) return false;
        int down=1;
        while (x/down>=10){
            //stop when x/down becomes a single digit
            down*=10;
        }
        while (true){
            if (x%10!=x/down) return false;
            x = x/10;
            down = down/10;
            if (down==0) return true;
            x -= x/down*down;
            down = down/10;
            if (down==0) return true;
        }
        return true;
    }
};

A slightly simpler solution

  • could use mod to remove leftmost digit (while divide removes rightmost digit)
class Solution {
public:
    bool isPalindrome(int x) {
        if (x<0) return false;
        int down=1;
        while (x/down>=10){
            //stop when x/down becomes a >single digit
            down*=10;
        }
        while (x){
            if (x%10!=x/down) return false;
            x = x%down/10;
            down = down/100;
        }
        return true;
    }
};
Palindrome Number