LeetCode Permutations I && II - JAVA

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

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

不用修改，就两个问题都适用的算法，调用STL就行的。运行速度还是很快的。

class Solution {
public:
    vector
  
    > permuteUnique(vector
   
     &num) { vector
    
      > permu; sort(num.begin(), num.end()); permu.push_back(num); while (next_permutation(num.begin(), num.end())) { permu.push_back(num); } return permu; } };

但是感觉做这些算法题，直接调用STL是不是有点感觉是作弊的嫌疑，呵呵O(∩_∩)O~

下面看看不使用STL如何做。

Permutations:

回溯法：

代码出自这个blog： http://blog.csdn.net/tuantuanls/article/details/8717262

只有手动走几遍吧，就能理解了。

这个算法是最简单的了

	vector
  
    > ret;
	int N;
	void perm(vector
   
     &num, int i){ if( i == N){ ret.push_back(num); } for(int j = i; j < N; j++){ swap(num[i], num[j]); perm(num, i + 1); swap(num[j], num[i]); } } vector
    
      > permute3(vector
     
       &num) { N = num.size(); ret.clear(); perm(num, 0); return ret; }

下面我用先序遍历树的思想写的代码，画个树理解就好了：

如第一次遍历：访问abc节点，取出a放入结果中，从abd节点到访问bc节点，访问节点c，把b放入结果中，最后访问c，把c放入结果中，每一条路径就是一个解，这里总共有6条路径，刚好是六个解。遍历完，答案就出来了。

和前面的回溯思想有一点差别，但是最基本思想差不多是一致的，要把这些思想融合起来，做到融会贯通！

//5===============
	vector
  
    > permute5(vector
   
     &num) { vector
    
      mediRes; vector
     
       > res; permu(num, mediRes, res); return res; } void permu(vector
      
        &num, vector
       
         &mediRes, vector
        
          > &ret) { int N = num.size(); if (N == 1) { mediRes.push_back(num[0]); ret.push_back(mediRes); mediRes.pop_back(); return; } for (int i = 0; i < N; i++) { mediRes.push_back(num[i]); vector
         
           cur = num; cur.erase(cur.begin()+i); permu(cur, mediRes, ret); mediRes.pop_back();//注意：别忘记了这里需要弹出，不要等到循环结束 } }

Permutations II

这个问题主要就增加防止重复的判断就可以了。

两种方法：

1 使用sort排序，然后排除相邻的重复数字。注意没排序的不可以这么判断

2 利用一个新的容器，装已经处理的数字，不重复处理数字，利用map和set等都可以。

方法一程序：

vector
  
    > permuteUnique2(vector
   
     &num) { mediRes.clear(); res.clear(); sort(num.begin(), num.end()); permuII2(num); return res; } void permuII2(vector
    
      &num) { int m = num.size(); if (m == 1) { mediRes.push_back(num[0]); res.push_back(mediRes); mediRes.pop_back(); return; } //如果已经排序了的就可以值处理相邻的重复了 for (int i = 0; i < m; i++) { while (i < m-1 && num[i] == num[i+1]) i++; mediRes.push_back(num[i]); vector
     
       cur = num; cur.erase(cur.begin()+i); permuII2(cur); mediRes.pop_back();//注意：别忘记了这里需要弹出，不要等到循环结束 } }

方法二程序：

vector
  
    > res;
	vector
   
     mediRes; vector
    
      > permuteUnique(vector
     
       &num) { mediRes.clear(); res.clear(); permuII(num); return res; } void permuII(vector
      
        &num) { int m = num.size(); if (m == 1) { mediRes.push_back(num[0]); res.push_back(mediRes); mediRes.pop_back(); return; } //注意：不能光判断相邻的是否重复，不相邻的重复也会出现重复结果的。 //脑子要放大 unordered_set
       
         used; for (int i = 0; i < m; i++) { if (used.find(num[i]) == used.end()) { mediRes.push_back(num[i]); vector
        
          cur = num; cur.erase(cur.begin()+i); permuII(cur); mediRes.pop_back();//注意：别忘记了这里需要弹出，不要等到循环结束 used.insert(num[i]); } } }