l*******A
发帖数: 209 | 1 题目:
Write a method in Java to:
Find all set of permutations from N number of ArrayLists. Each ArrayList has
a different length.
Each permutation is formed by picking one item from each input ArrayList.
You have to exhaust ALL permutations and can't return duplicate permuations.
Each permutation is a Set, so the order of the items does not matter. For
example [a1,b1,c1] is the same permutation as [c1,b1,a1].
Example:
Input: N number of array lists with different length
[a1,a2,a3....]
[b1,b2....]
[c1, c2... ]
...
Output: ALL permutations
[a1, b1, c1...],
[a1,b1,c2..]
....
Note: the above example is just an sample of potential input to illustrate
the output. You have to write code to solve for generalized input. Please t
ype in the pad below so we can follow your thought process.Show us your mos
t elegant solution
我的解法:
public HashSet> findPermutation(ArrayList
er>> input, int N) {
int inputSize = input.size();
HashSet> result = new HashSet>();
ArrayList tempList = new ArrayList();
if (inputSize!=N) {
System.out.println("Input invliad"); //very simple input checking.
could throw an inputinvalid exception if needed
return result; //be nice to just return an empty set for now. could
do many other things
}
//use depth first search to traverse through the input and return result
dfs(input,result, 0, N-1, tempList);
return result;
}
private void dfs (ArrayList input, HashSet
ger>> result, int depth, int size, ArrayList tempList) {
// base condition - when we reach the desired depth(size), add tempList
to result
if (depth==size) {
result.add(new ArrayList(tempList)); //use of set API to r
emove duplicate
return;
}
ArrayList thisList = input.get(depth);
for (Integer item : thisList) {
tempList.add(item);
dfs(input,result,depth+1,size,tempList);
tempList.remove(tempList.size()-1); //remove last element
}
}
把解法发给面试的人以后,他说"you unfortunately missed the solution and did no
t solve the question asked in the exercise."
请大家帮忙指点一下,是我理解题意错了么?还是解法错了?
谢谢 | T******e
发帖数: 157 | 2 1. 用HashSet> 是题目要求还是你自己决定的？ 感觉如果用
HashSet了对应的set都被算成hash值了，最后即使返回去也不能把对应的set从hashset
里面抠出来吧？
2.dfs(input,result, 0, N-1, tempList);
这句里应该是N而不是N-1吧，试想假如N = 1，此时有一个arraylist但由于一旦调用
dfs就会有size == depth，导致把一个空arraylist加进去 | l*******A
发帖数: 209 | 3 啊，你说的第二点很对.大意了,忘了检查一下...
你说的第一点我不太理解,用HashSet是为了避免加入同样的ArrayList,返回一
个set,然后可以用set的API来读任何一个元素啊
大不了再造一个ArrayList> result,然后result.addAll(set),
return result.
hashset
【在 T******e 的大作中提到】
: 1. 用HashSet> 是题目要求还是你自己决定的？ 感觉如果用
: HashSet了对应的set都被算成hash值了，最后即使返回去也不能把对应的set从hashset
: 里面抠出来吧？
: 2.dfs(input,result, 0, N-1, tempList);
: 这句里应该是N而不是N-1吧，试想假如N = 1，此时有一个arraylist但由于一旦调用
: dfs就会有size == depth，导致把一个空arraylist加进去
| b**********5
发帖数: 7881 | 4 你这个duplicate， 我不大懂。 你这个每个input 里面会有duplicate element么？
但你这个HashSet>不大对吧。你说利用HashSet的API,就认为两个
ArrayList相同， 但ArrayList是个reference，不是element-wise
comparison。
回一
【在 l*******A 的大作中提到】
: 啊，你说的第二点很对.大意了,忘了检查一下...
: 你说的第一点我不太理解,用HashSet是为了避免加入同样的ArrayList,返回一
: 个set,然后可以用set的API来读任何一个元素啊
: 大不了再造一个ArrayList> result,然后result.addAll(set),
: return result.
:
: hashset
| T******e
发帖数: 157 | 5 我对java不是太了解，但个人感觉你用hashset只能检查对于某个set它在不在hashset
里，这个检查靠hashcode（）来实现，但你能不能从hashset里取出原来的set我就不清
楚了，我的理解是hashset把每一种set对应的hashcode的值存进去了，而不是存的set
回一
【在 l*******A 的大作中提到】
: 啊，你说的第二点很对.大意了,忘了检查一下...
: 你说的第一点我不太理解,用HashSet是为了避免加入同样的ArrayList,返回一
: 个set,然后可以用set的API来读任何一个元素啊
: 大不了再造一个ArrayList> result,然后result.addAll(set),
: return result.
:
: hashset
| b**********5
发帖数: 7881 | 6 。。。
hashset
set
【在 T******e 的大作中提到】
: 我对java不是太了解，但个人感觉你用hashset只能检查对于某个set它在不在hashset
: 里，这个检查靠hashcode（）来实现，但你能不能从hashset里取出原来的set我就不清
: 楚了，我的理解是hashset把每一种set对应的hashcode的值存进去了，而不是存的set
:
: 回一
| l*******A
发帖数: 209 | 7 good point - 我明天写几个input测试一下应该就知道了
谢谢！
wise
【在 b**********5 的大作中提到】
: 你这个duplicate， 我不大懂。 你这个每个input 里面会有duplicate element么？
: 但你这个HashSet>不大对吧。你说利用HashSet的API,就认为两个
: ArrayList相同， 但ArrayList是个reference，不是element-wise
: comparison。
:
: 回一
| T******e
发帖数: 157 | 8 刚才看了下HashSet的代码，感觉就是楼上说的处理duplicates的问题，
[1,2,3] 和 [3,2,1] 的hashcode估计不一样吧，加入到hashset里之前可以先排个序 | l*n
发帖数: 529 | 9 从你这个dfs解法倒是学到了点东西：n重循环可以通过dfs来做。:D
解法当中唯一的问题就是set判重错了，ArrayList是没有重定义hash()跟
equals()方法的，所以判重就只看是否是同一个reference。
List> arrayCombinate(List arrs) {
List> ol = new ArrayList>();
if (arrs.size() == 0)
return ol;
dfs(arrs, 0, new ArrayList(), ol, new HashSet());
return ol;
}
void dfs(List arrs, int i, List curr,
List> ol, Set memo) {
if (i == arrs.size()) {
List copy = new ArrayList(curr);
Collections.sort(copy);
String sig = Arrays.toString(copy.toArray());
if (!memo.contains(sig)) {
ol.add(copy);
memo.add(sig);
}
return;
}
int[] arr = arrs.get(i);
for (int j = 0; j < arr.length; j++) {
curr.add(arr[j]);
dfs(arrs, i + 1, curr, ol, memo);
curr.remove(curr.size() - 1);
}
}
has
permuations.
【在 l*******A 的大作中提到】
: 题目:
: Write a method in Java to:
: Find all set of permutations from N number of ArrayLists. Each ArrayList has
: a different length.
: Each permutation is formed by picking one item from each input ArrayList.
: You have to exhaust ALL permutations and can't return duplicate permuations.
: Each permutation is a Set, so the order of the items does not matter. For
: example [a1,b1,c1] is the same permutation as [c1,b1,a1].
: Example:
: Input: N number of array lists with different length
| l*n
发帖数: 529 | 10 不光[1,2,3]跟[3,2,1]的hashcode不一样，[1,2,3]跟[1,2,3]的也不一样！
java的object(ArrayList就只是个object)如果没有重定义hashcode方法的话
，hashcode就都是对应object的地址而已。
【在 T******e 的大作中提到】
: 刚才看了下HashSet的代码，感觉就是楼上说的处理duplicates的问题，
: [1,2,3] 和 [3,2,1] 的hashcode估计不一样吧，加入到hashset里之前可以先排个序
| l*******A
发帖数: 209 | 11 cool. you guys are correct. Just tested it. thanks! | l********7
发帖数: 40 | 12 public static ArrayList> getPermutation(ArrayList<
ArrayList> lists){
ArrayList> result = new ArrayList
Integer>>();
if(lists != null && lists.size() != 0){
permutation(lists, result, new ArrayList(), 0);
}
return result;
}
public static void permutation(ArrayList> lists,
ArrayList> result, ArrayList current, int index){
if(index == lists.size()){
result.add((ArrayList)current.clone());
return;
}
ArrayList currentList = lists.get(index);
for(int i = 0; i < currentList.size(); i++){
current.add(currentList.get(i));
permutation(lists, result, current, index+1);
current.remove(current.size()-1);
}
} | T******e
发帖数: 157 | 13 你确定吗？ 我那天用hashmap试了试，对于两个不同的arraylist，如果都是空的话，
hash值是不一样的，如果里面是1 2 3 且顺序一样，可以用list1找出list2的value
【在 l*n 的大作中提到】
: 不光[1,2,3]跟[3,2,1]的hashcode不一样，[1,2,3]跟[1,2,3]的也不一样！
: java的object(ArrayList就只是个object)如果没有重定义hashcode方法的话
: ，hashcode就都是对应object的地址而已。
|
|
