Permutation Related

Leave a comment

September 16, 2016 by oneOokay

排列组合 PERMUTATION

15. Permutations

Given a list of numbers (no duplicates), return all possible permutations.

DFS + backtracing。(另外还一个non-recursive的解法,以后有空再研究吧。。。)

思路:

  • 需要找出N条搜索路径,每一条对应的搜索路径为一个解.
  • 任意一个元素都可以当做起点,所以每次recurse的时候都需要从第一个元素开始进行(树的recursive是从该元素的下一个继续recurse,所以每次的recurse的起点为i + 1).所以这里的helper method里不需要传入index的值.
  • 接着放入没有放入过的元素(每个元素只能用一次),遇到已存在的元素则跳过. 所以需要一个数据结构来存visited的点.helper method里面传入boolean[]或者set其实也可以.
  • Recurse至所有元素都放入了list,把当前list加入到最终结果中,开始back tracking。

这一题要注意的就是如何initialize List()

public List permute(int[] nums) {
List res = new ArrayList<>();
if (nums == null || nums.length == 0) {return ans;}
boolean[] visited = new boolean[nums.length];
helper(new ArrayList(), res, nums, visited);
return ans;
}

private void helper(List list, List res,
int[] nums, boolean[] visited){
if(list.size() == nums.length){ //找齐了所有的元素,return
res.add(new ArrayList(list));
return;
}

for (int i = 0; i < nums.length; i ++){
if (visited[i]){ //该数已经取过加入到result里了,跳过
continue;
}
list.add(nums[i]);
helper(list, res, nums, visited); //这里开始下一个recurse,下一个recurse将从第一个元素开始找
list.remove(list.size() - 1);//backtracking
}}

16. Permutations II

数组存在着重复元素,找出所有的非重复的permutation解

与permutations I同样的思路,加入查重的步骤。

  • 首先对数组进行排序
  • 进行DFS的时候,先判断前面的一个数是否与自己相等,相等的时候前面的值必须已经使用了(用一个数组来记录是否已经visited),自己才能够使用。如此不会产生重复排序。

Key: Arrays.sort(int[])来对数组进行排序。

public List<List> permuteUnique(int[] nums) {
List<List res = new ArrayList<>();
if (nums == null || nums.length == 0) {
return ans;}
Arrays.sort(nums);
boolean[] visited = new boolean[nums.length];
helper(new ArrayList(), res, nums, visited);
return ans;
}

private void permutationHelper(List list, List<List> res,
int[] nums, boolean[] visited){
if (list.size() == nums.length){
res.add(new ArrayList(list));
return;
}

for (int i = 0; i < nums.length; i ++) {
//detect duplication.
 if (i >0 && nums[i] == nums[i - 1] && !visited[i - 1]|| visited[i])
 {continue; }
list.add(nums[i]);
visited[i] = true;
helper(list, res, nums, visited);
visited[i] = false;
list.remove(list.size() - 1);}}}

Palindrome Permutation II

和Permutation II的区别就是:

  • permutation II 给你一个存在重复的字符串
  • Palindrome Permutation: 给你一个字符串的计数,比如a出现了2次,b出现了3次,把这2个a和3个b进行permutation. (当然一种做法是把: 这个字符串的计数转换成permutationII来做.这里看一下另外一种直接在map/计数上面操作的算法.

为什么这么做不会产生重复的呢?比如a:2, b:1

  • 这里的每一次DFS都是从for i = 0开始的.
  • 第一次simple path就是a(1)a(2)b(1). 如果考虑重复的话,就需要出现a(2)a(1)b(1).
  • 这是不可能的,因为每次从a的集合里面取,一直都是按顺序取的,把所有a想象成有编号的,每次都是先取a(1)才能继续取a(2). 所以这里并不会有duplicates.

同时想一下这里是怎么决定dfs结束把s加到res里面的. (计算出了一个length.)

小技巧:

  • 用一个256的数组来存char,把index转换回char的时候:(char)i
  • 把一个String s翻转的话: (new StringBuilder(s).reverse()).toString().
public List generatePalindromes(String s) {
        List res = new ArrayList<>();
        if(s == null || s.length() == 0) return res;
        int[] count = new int[256];
        char[] chs = s.toCharArray();
        for(char c : chs)
            count[c] ++;
        
        boolean hasOdd = false;
        String mid = "";
        int length = 0;
        for(int i = 0; i < 256; i ++){
            if(hasOdd && count[i] % 2 == 1) return res;
            if (count[i] % 2 == 1) {
                mid += (char)i;
                hasOdd = true;
            }
            length += count[i] / 2;
            count[i] = count[i] / 2;
        }
        helper(count, mid, "", res, length);
        return res;
    }
    
    private void helper(int[] count, String mid, String s, List res, int len){
        if (s.length() == len){
            s = s + mid + (new StringBuilder(s).reverse()).toString();
            res.add(new String(s));
            return;
        }
        for(int i = 0; i < 256; i ++){
            if (count[i] == 0) 
                continue;
            count[i] --;
            helper(count, mid, s + (char)i, res, len);
            count[i] ++;
        }
    }

 


10. String Permutation II: 我用了类似16. Permutations II的方法,就是对String进行处理,九章的答案看不太懂。把String转成char[]之后sort,result用StringBuilder来存。注意一些对String和StringBuilder的操作。

  • String str.length(), str.charAt(i)
  • StringBuilder sb.length(); sb.deleteCharAt(i); sb.toString();

List ans;

public List stringPermutation2(String str) {

ans = new ArrayList();
if(str == null){
return ans;
}

int[] visited = new int[str.length()];
for (int i = 0; i < str.length(); i ++){
visited[i] = 0;
}
char[] tmp = str.toCharArray();
Arrays.sort(tmp);
StringBuilder sb = new StringBuilder();
permutationHelper(sb, visited, tmp);
return ans;
}
private void permutationHelper(StringBuilder sb, int[] visited, char[] str) {
if (sb.length() == str.length) {
ans.add(new String(sb.toString()));
return;
}
for (int i = 0; i < str.length; i ++) { if (visited[i] == 0) { if (i > 0 && str[i] == str[i – 1] && visited[i – 1] == 0){
continue;
}
visited[i] = 1;
sb.append(str[i]);
permutationHelper(sb, visited, str);
visited[i] = 0;
sb.deleteCharAt(sb.length() – 1);
}}}

String Permutation:

Given two strings, write a method to decide if one is a permutation of the other.

跟DFS无关,我的想法是把两个String都变成char array之后sort再转换为string,看是否相等。

九章的算法很妙;用一个int[]来统计string a中char的值,完了之后再loop一遍string b对int[]中相减。最终判断int[]中是否每个元素都为0.若为0,return true。否则return false。http://www.jiuzhang.com/solutions/string-permutation/

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

%d bloggers like this: