Lexi's Leetcode solutions

[leetcode] Permutations | 一个array的所有permutation

Posted on: August 7, 2013

这个思路本来很简单,如果用recursion来enumeration的话,即用set,每次第i个位置用了set的第j个元素,然后set remove j, recurse on i + 1。非常straight forward的做法,但是用java这么做有好几个问题:

  • 如果input有重复,如aabc,set没法处理同时存在2个a的情况。
  • 在recurse on set的每个元素的时候,因为for循环是interate thru set itself,但里面还有set.add(), set.remove这些改变set本身的语句,所以会有modify iterator exception。还得弄个copy先。
  • 代码巨长。越写越没信心。

所以还是CC150上的另一种思路:每次取一个元素,对于之前(上一层循环的list结果)的每个permutation, 在能插的地方就插这个新元素,然后生成新的permutation,放入这一层的结果。这样代码相对简单,而且不用recursion。有几个要点:

  1. 最开始要传一个空的permutation进去,否则没处可insert第一个元素。
  2. 这种做法不能防止duplication(1212可能有好几种insert成它的方法)。
public ArrayList<ArrayList<Integer>> permute(int[] num) {
  ArrayList<ArrayList<Integer>> lastLayer = new ArrayList<ArrayList<Integer>>();
  lastLayer.add(new ArrayList<Integer>());
  for (int i = 0; i < num.length; i++) {
    ArrayList<ArrayList<Integer>> newLayer = new ArrayList<ArrayList<Integer>>();
    for (int j = 0; j < lastLayer.size(); j++) {
      ArrayList<Integer> curr = lastLayer.get(j);
      insertEverywhere(curr, num[i], newLayer);
    }
    lastLayer = newLayer;
  }
  return lastLayer;
}
private void insertEverywhere(ArrayList<Integer> curr, int num, ArrayList<ArrayList<Integer>> newLayer) {
  for (int i = 0; i <= curr.size(); i++) {
    ArrayList<Integer> newList = new ArrayList<Integer>(curr);
    newList.add(i, num);
    newLayer.add(newList);
   }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

Blog Stats

  • 217,999 hits
August 2013
M T W T F S S
« Jul   Sep »
 1234
567891011
12131415161718
19202122232425
262728293031  
Advertisements
%d bloggers like this: