Day 59, #47, #48, Permutations II, Rotate Image

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].
--------------------------------------------------------------------------------
Check duplicates in each for loop run

class Solution {
public:
    void per (vector<int> num,vector<int> cur,vector<vector<int> > &ret) {
        if (num.size() == 0) {
            ret.push_back(cur);
        }
        unordered_set<int> mapping;
        for (int i = 0; i < num.size(); i++) {
            if (mapping.find(num[i]) == mapping.end()) {
                mapping.insert(num[i]);
                vector<int> v = cur;
                vector<int> w = num;
                v.push_back(w[i]);
                w.erase(w.begin()+i);
                per(w,v,ret);
            }
        }
    }

    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > ret;
        vector<int> cur;
        per(num,cur,ret);
        return ret;
    }
};

Update on Nov-8th-2014
Solution#2, using sort

class Solution {
public:
    void permute(vector<vector<int> > &rt,vector<int> cur,vector<int> num) {
        if (0 == num.size()) {
            rt.push_back(cur);
        }
        
        for (int i = 0; i < num.size(); i++) {
            vector<int> cpCur = cur;
            vector<int> cpNum = num;
            cpCur.push_back(num[i]);
            cpNum.erase(cpNum.begin() + i);
            permute(rt,cpCur,cpNum);
            
            while (i + 1 < num.size() && num[i] == num[i + 1]) {
                i++;
            }
            
        }
    }

    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(),num.end());
        vector<vector<int> > rt;
        vector<int> cur;
        permute(rt,cur,num);
        
        return rt;
    }
};

类似Permutation 1，每次确定一个数，重复的跳过

class Solution {
public:
    void swap(vector<int> &nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    void per(vector<vector<int> > &rt, vector<int> nums, int index) {
        if (index == nums.size() - 1) {
            rt.push_back(nums);
            return;
        }
        
        for (int i = index; i < nums.size(); i++) {
            if (i != index && nums[i] == nums[index]) continue;
            swap(nums,i,index);
            per(rt,nums,index + 1);
        }
        
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> rt;
        per(rt,nums,0);
        
        return rt;
    }
};

Rotate Image
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?
-------------------------------------------------------------
Solution #1, n*n space

class Solution {
public:
    void rotate(vector<vector<int> > &matrix) {
        int n = matrix.size();
        vector<vector<int> > cp(n,vector<int>(n));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cp[j][n-1-i] = matrix[i][j];
            }
        }
        matrix = cp;
    }
};

Solution #2, in space

class Solution {
public:
    void rotate(vector<vector<int> > &matrix) {
        int n = matrix.size();
        for (int row = 0; row < n / 2 ; row++) {
            for (int col = row; col < n - 1 - row; col++) {
                int temp = matrix[row][col];
                matrix[row][col] = matrix[n-1-col][row];
                matrix[n-1-col][row] = matrix[n-1-row][n-1-col];
                matrix[n-1-row][n-1-col] = matrix[col][n-1-row];
                matrix[col][n-1-row] = temp;
            }
        }
    }
};