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<List> permute(int[] nums) {
List<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<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<Integer>> permuteUnique(int[] nums) {
List<List<Integer> res = new ArrayList<>();
if (nums == null || nums.length == 0) {
return ans;}
Arrays.sort(nums);
boolean[] visited = new boolean[nums.length];
helper(new ArrayList<Integer>(), res, nums, visited);
return ans;
}

private void permutationHelper(List<Integer> list, List<List<Integer>> 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);}}}

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: