f*********m
发帖数: 726 | 1 题目：
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].
请教不用set的方法。
谢谢。 | w****x
发帖数: 2483 | 2 你看这样行不行：
void _inner_print(char strOrg[], char strCur[], int nLen)
{
assert(strOrg && strCur && nLen >= 0);
if (0 == nLen)
{
cout<
return;
}
//record if a character is calculated as a header
//to eliminate duplicated characters
bool bRec[256];
memset(bRec, 0, sizeof(bRec));
for (int i = 0; i < nLen; i++)
{
if (!bRec[strCur[i]])
{
swap(strCur[0], strCur[i]);
_inner_print(strOrg, strCur+1, nLen-1);
swap(strCur[0], strCur[i]);
bRec[strCur[i]] = true;
}
}
} | h*****3
发帖数: 1391 | | f*********m
发帖数: 726 | 4 能仔细说说吗？
【在 h*****3 的大作中提到】
: 要我做，就是用递归+一个prev变量。
| c***e
发帖数: 542 | 5 print the permutation in lexi order, no dup will be printed. | h*****3
发帖数: 1391 | 6 好像carreer cup150上有这题？我写的最后一个test case没通过，我觉的好像他的
test case有问题，但我的思路应该没问题。
//这个子程序可以忽略不计
void swap (int &i,int &j){
int tmp;
tmp = i;
i = j;
j = tmp;
}
void permitUniq(vector &num,int res[],int lev,vector > &
list,int start)
{//res- buffer一个solution, lev - res 中的index， list- keep all
solutions,start- num中的起始位置
int prev;
vector tmp;
if(lev == num.size()){//找到一个solution, 存起来啊
tmp.assign(res,res+lev);
list.push_back(tmp);
return;
}
//开始做从start起的permutation
for(int i = start;i
if(i == start){//第一个元素，没有prev，那保存下，res相应位填起来
，递归做从start+1起的permutation
prev = num[i];
res[lev] = num[i];
permitUniq(num,res,lev+1,list,start+1);
}
else if(prev != num[i]){ 不是第一个元素，那是否和前面的相等？
不相等，那res相应位填NUM[I]，和起始位置交换下位置，递归做从start+1起的
permutation，做完后得换回来，prev update
res[lev] = num[i];
swap(num[i],num[start]);
permitUniq(num,res,lev+1,list,start+1);
swap(num[start],num[i]);
prev = num[i];
}
//没else了，那就是相等了，ignore了
}
}
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int *res= new int[num.size()];
vector > list;
if(num.size()<=1){
list.push_back(num);
delete []res;
return list;
}
sort(num.begin(),num.end());
permitUniq(num,res,0,list,0);
delete []res;
return list;
}
【在 f*********m 的大作中提到】
: 能仔细说说吗？
| c***e
发帖数: 542 | 7 print in lexi order, here is my code which passed both small and large tests:
class Solution {
public:
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > allPerm;
sort(num.begin(), num.end());
allPerm.push_back(num);
if(num.size() < 2)
return allPerm;
vector tmp=num;
while(true)
{
tmp= getNext(tmp);
if(tmp.size()==0)
break;
else
allPerm.push_back(tmp);
}
return allPerm;
}
void swap(vector &num, int i, int j)
{
int tmp = num[i];
num[i]=num[j];
num[j]=tmp;
}
vector getNext(vector perm)
{
int size= perm.size();
int i=size-1;
while(i>0 && perm[i-1] >= perm[i])
i--;
if(i<=0)
{
perm.clear();
return perm;
}
int j=size-1;
while(perm[j]<=perm[i-1])
j--;
swap(perm, j, i-1);
j=size-1;
while(i
{swap(perm, i, j);
i++;
j--;
}
return perm;
}
}; | i**********e
发帖数: 1145 | 8 你最后一个 test case 之所以没通过是因为存在了重复。
这个组合 [9,0,0,0,1] 就出现了两次。
【在 h*****3 的大作中提到】
: 好像carreer cup150上有这题？我写的最后一个test case没通过，我觉的好像他的
: test case有问题，但我的思路应该没问题。
: //这个子程序可以忽略不计
: void swap (int &i,int &j){
: int tmp;
: tmp = i;
: i = j;
: j = tmp;
: }
: void permitUniq(vector &num,int res[],int lev,vector > &
| h*****3
发帖数: 1391 | 9 嗯。交换以后还是得sort一遍。
改2个地方就可以了
1）paramter要改。num不用reference.
permitUniq(vector &num,int res[],int lev,vector > &
list,int start)
-〉
permitUniq(vector num,int res[],int lev,vector > &
list,int start)
2) 在for循环之前，sort一遍number，从start，到end。
【在 i**********e 的大作中提到】
: 你最后一个 test case 之所以没通过是因为存在了重复。
: 这个组合 [9,0,0,0,1] 就出现了两次。
| f*********m
发帖数: 726 | | | | e***s
发帖数: 799 | 11 为什么不用hastset，然后再写回去vector呢？这样是不是不符合题目要求？ | d****n
发帖数: 1637 | 12 /*
trick is to sort 'num' first
Run Status: Accepted!
Program Runtime: 156 milli secs
Progress: 30/30 test cases passed.
*/
#include
#include
using namespace std ;
class Solution {
public:
int int_cmp(int i, int j){ return (i
vector > permuteUnique(vector &num) {
sort(num.begin(), num.end() ) ;
vector > ret;
do{
ret.push_back( num );
}while(next_permutation(num.begin(), num.end())!=false);
return ret;
}
}; | f*********m
发帖数: 726 | 13 题目：
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].
请教不用set的方法。
谢谢。 | w****x
发帖数: 2483 | 14 你看这样行不行：
void _inner_print(char strOrg[], char strCur[], int nLen)
{
assert(strOrg && strCur && nLen >= 0);
if (0 == nLen)
{
cout<
return;
}
//record if a character is calculated as a header
//to eliminate duplicated characters
bool bRec[256];
memset(bRec, 0, sizeof(bRec));
for (int i = 0; i < nLen; i++)
{
if (!bRec[strCur[i]])
{
swap(strCur[0], strCur[i]);
_inner_print(strOrg, strCur+1, nLen-1);
swap(strCur[0], strCur[i]);
bRec[strCur[i]] = true;
}
}
} | h*****3
发帖数: 1391 | | f*********m
发帖数: 726 | 16 能仔细说说吗？
【在 h*****3 的大作中提到】
: 要我做，就是用递归+一个prev变量。
| c***e
发帖数: 542 | 17 print the permutation in lexi order, no dup will be printed. | h*****3
发帖数: 1391 | 18 好像carreer cup150上有这题？我写的最后一个test case没通过，我觉的好像他的
test case有问题，但我的思路应该没问题。
//这个子程序可以忽略不计
void swap (int &i,int &j){
int tmp;
tmp = i;
i = j;
j = tmp;
}
void permitUniq(vector &num,int res[],int lev,vector > &
list,int start)
{//res- buffer一个solution, lev - res 中的index， list- keep all
solutions,start- num中的起始位置
int prev;
vector tmp;
if(lev == num.size()){//找到一个solution, 存起来啊
tmp.assign(res,res+lev);
list.push_back(tmp);
return;
}
//开始做从start起的permutation
for(int i = start;i
if(i == start){//第一个元素，没有prev，那保存下，res相应位填起来
，递归做从start+1起的permutation
prev = num[i];
res[lev] = num[i];
permitUniq(num,res,lev+1,list,start+1);
}
else if(prev != num[i]){ 不是第一个元素，那是否和前面的相等？
不相等，那res相应位填NUM[I]，和起始位置交换下位置，递归做从start+1起的
permutation，做完后得换回来，prev update
res[lev] = num[i];
swap(num[i],num[start]);
permitUniq(num,res,lev+1,list,start+1);
swap(num[start],num[i]);
prev = num[i];
}
//没else了，那就是相等了，ignore了
}
}
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int *res= new int[num.size()];
vector > list;
if(num.size()<=1){
list.push_back(num);
delete []res;
return list;
}
sort(num.begin(),num.end());
permitUniq(num,res,0,list,0);
delete []res;
return list;
}
【在 f*********m 的大作中提到】
: 能仔细说说吗？
| c***e
发帖数: 542 | 19 print in lexi order, here is my code which passed both small and large tests:
class Solution {
public:
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > allPerm;
sort(num.begin(), num.end());
allPerm.push_back(num);
if(num.size() < 2)
return allPerm;
vector tmp=num;
while(true)
{
tmp= getNext(tmp);
if(tmp.size()==0)
break;
else
allPerm.push_back(tmp);
}
return allPerm;
}
void swap(vector &num, int i, int j)
{
int tmp = num[i];
num[i]=num[j];
num[j]=tmp;
}
vector getNext(vector perm)
{
int size= perm.size();
int i=size-1;
while(i>0 && perm[i-1] >= perm[i])
i--;
if(i<=0)
{
perm.clear();
return perm;
}
int j=size-1;
while(perm[j]<=perm[i-1])
j--;
swap(perm, j, i-1);
j=size-1;
while(i
{swap(perm, i, j);
i++;
j--;
}
return perm;
}
}; | i**********e
发帖数: 1145 | 20 你最后一个 test case 之所以没通过是因为存在了重复。
这个组合 [9,0,0,0,1] 就出现了两次。
【在 h*****3 的大作中提到】
: 好像carreer cup150上有这题？我写的最后一个test case没通过，我觉的好像他的
: test case有问题，但我的思路应该没问题。
: //这个子程序可以忽略不计
: void swap (int &i,int &j){
: int tmp;
: tmp = i;
: i = j;
: j = tmp;
: }
: void permitUniq(vector &num,int res[],int lev,vector > &
| | | h*****3
发帖数: 1391 | 21 嗯。交换以后还是得sort一遍。
改2个地方就可以了
1）paramter要改。num不用reference.
permitUniq(vector &num,int res[],int lev,vector > &
list,int start)
-〉
permitUniq(vector num,int res[],int lev,vector > &
list,int start)
2) 在for循环之前，sort一遍number，从start，到end。
【在 i**********e 的大作中提到】
: 你最后一个 test case 之所以没通过是因为存在了重复。
: 这个组合 [9,0,0,0,1] 就出现了两次。
| f*********m
发帖数: 726 | | e***s
发帖数: 799 | 23 为什么不用hastset，然后再写回去vector呢？这样是不是不符合题目要求？ | d****n
发帖数: 1637 | 24 /*
trick is to sort 'num' first
Run Status: Accepted!
Program Runtime: 156 milli secs
Progress: 30/30 test cases passed.
*/
#include
#include
using namespace std ;
class Solution {
public:
int int_cmp(int i, int j){ return (i
vector > permuteUnique(vector &num) {
sort(num.begin(), num.end() ) ;
vector > ret;
do{
ret.push_back( num );
}while(next_permutation(num.begin(), num.end())!=false);
return ret;
}
}; | n****r
发帖数: 471 | 25 谁能给讲解一下这位大牛的解法？ http://discuss.leetcode.com/questions/225/permutations-ii
Code:
class Solution {
public:
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector used(num.size(), false);
vector path;
vector > ret;
sort(num.begin(), num.end());
sub(num, used, path, ret);
return ret;
}
void sub(vector &num, vector &used, vector &path, vector
> &ret) {
if (num.size() == path.size()) {
ret.push_back(path);
return;
}
for (int i = 0; i < num.size(); ++i) {
if (used[i] || (i != 0 && num[i] == num[i - 1] && used[i - 1]))
continue;
used[i] = true;
path.push_back(num[i]);
sub(num, used, path, ret);
used[i] = false;
path.pop_back();
}
}
};
【在 f*********m 的大作中提到】
: 题目：
: 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].
: 请教不用set的方法。
: 谢谢。
| n****r
发帖数: 471 | 26 谁能给讲解一下这位大牛的解法？ http://discuss.leetcode.com/questions/225/permutations-ii
Code:
class Solution {
public:
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector used(num.size(), false);
vector path;
vector > ret;
sort(num.begin(), num.end());
sub(num, used, path, ret);
return ret;
}
void sub(vector &num, vector &used, vector &path, vector
> &ret) {
if (num.size() == path.size()) {
ret.push_back(path);
return;
}
for (int i = 0; i < num.size(); ++i) {
if (used[i] || (i != 0 && num[i] == num[i - 1] && used[i - 1]))
continue;
used[i] = true;
path.push_back(num[i]);
sub(num, used, path, ret);
used[i] = false;
path.pop_back();
}
}
};
【在 f*********m 的大作中提到】
: 题目：
: 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].
: 请教不用set的方法。
: 谢谢。
| p*****2
发帖数: 21240 | 27 我写了一个练练
val arr=Array(1,1,2)
arr.permutations.toList.distinct.foreach(i=>println(i.mkString(","))) | n****r
发帖数: 471 | 28 大牛这个太高深了。。。
能不能给分析一下上面那个算法的思路，想了2个小时没想明白，放弃了。
【在 p*****2 的大作中提到】
: 我写了一个练练
: val arr=Array(1,1,2)
: arr.permutations.toList.distinct.foreach(i=>println(i.mkString(",")))
| p*****2
发帖数: 21240 | 29
看了一下。没感觉有什么太特别的。
【在 n****r 的大作中提到】
: 大牛这个太高深了。。。
: 能不能给分析一下上面那个算法的思路，想了2个小时没想明白，放弃了。
| l*****a
发帖数: 14598 | 30 大牛给菜鸟们展开讲讲吧
【在 p*****2 的大作中提到】
:
: 看了一下。没感觉有什么太特别的。
| | | n****r
发帖数: 471 | 31 能不能给总结一下就是这种题用dfs什么样的设计才能避免duplicate的解。
类似的简单一些的是8皇后的题，那个我感觉好理解一些。这个确实是有点儿理解起来
比较困难。
求大牛给点儿提示，感觉这也算是一类题目了。
【在 p*****2 的大作中提到】
:
: 看了一下。没感觉有什么太特别的。
| p*****2
发帖数: 21240 | 32
这种题大牛你最擅长。你给大家讲讲吧。
【在 l*****a 的大作中提到】
: 大牛给菜鸟们展开讲讲吧
| a******8
发帖数: 90 | 33 我的1和2区别很小啊，测试都过了。我的思路是2无非是有一些重复的，怎么去重复，
先排序，然后我手动run了几个test case,发现在某些情况下，会重复的swap,这样我从
后往前走，一旦遇到相同的数，就可以停止了，否则就是重复，有点排列组合的概念。
请各大牛验证：
比如 yyy9yyy9x 9,比如下个数是9，只需要换下x与9，进下一步，其他之前的不管了
，管了就重复了。
class Solution {
public:
void myPerm(vector &num, vector curv, int curi, vector
int> > &ret)
{
if(curi == num.size())ret.push_back(curv);
else
{
curv.push_back(num[curi]);
myPerm(num,curv,curi+1,ret);
for(int i = curv.size()-2; i >= 0; i--)
{
if(curv[i] == curv[curv.size()-1])break;//perm 2
swap(curv[i],curv[curv.size()-1]);
myPerm(num,curv,curi+1,ret);
swap(curv[curv.size()-1],curv[i]);
}
}
}
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > ret;
if(num.size() == 0)return ret;
vector v;
sort(num.begin(),num.end());//perm 2
myPerm(num,v,0,ret);
return ret;
}
}; | s***g
发帖数: 257 | 34 这个是可以实现的，每次循环前，查一下余下的是否有duplicate就行。
【在 h*****3 的大作中提到】
: 要我做，就是用递归+一个prev变量。
| j******s
发帖数: 48 | 35 public ArrayList> permuteUnique(int[] num) {
Arrays.sort(num);
ArrayList> output
= new ArrayList>();
ArrayList list = new ArrayList();
boolean col[] = new boolean[num.length];
permute(output,list,col,num,0);
return output;
}
public void permute(ArrayList> output,
ArrayList list,boolean col[],
int num[],int level)
{
if(level >= num.length)
{
output.add((ArrayList)list.clone());
return ;
}
int pre = num[0]-1; //保存上一次visit，
for(int i=0;i
{
//guarantee we do not reuse a same element in this round.
if(col[i]==false && num[i] != pre)
{
col[i] = true;
if(list.size() < level+1)
list.add(num[i]);
else
list.set(level,num[i]);
permute(output,list,col,num,level+1);
col[i] = false;
pre = num[i];
}
}
}
之前看了peking2大牛写得一道类似的题，自己跟着用例子跑了一遍他的程序，算是半
学会这个基本思路。
用例子来说就是
假如input是11122
look at the first sub-problem: pick one as the first number and generate all
all permutation with this num as the first number.
我们第一次pick的是1，并生成了所有以1开头的permutation，第二次我们遇到的还是1
，如
果我们这次还是以这个1为开头(why? because the first number is 1, and
everything left is also the same)，那么这次我们所有这次生成的序列都会和上一
次重复.If you still not understand, run it step by step by hand for one time. | z*******8
发帖数: 30 | 36 http://blog.csdn.net/zxzxy1988/article/details/8579357
基本思路就是用"next permutation"的概念，也就是下一个字典序的permutation，无
论有没有dup，都可以解决 |
|
