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)recurse至所有元素都放入了结束。遇到已存在的元素则跳过。(TODO:这里的time complexity是多少啊?)

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

List<List<Integer>> ans;
public List<List<Integer>> permute(int[] nums) {
ans = new ArrayList<>();
if (nums == null) {
return ans;}

if (nums.length == 0){
ans.add(new ArrayList<Integer>());
return ans;}

ArrayList<Integer> tmp = new ArrayList<Integer>();
permutationHelper(tmp, nums);
return ans;
}

private void permutationHelper(ArrayList<Integer> result, int[] nums){
if(result.size() == nums.length){ //找齐了所有的元素,return
ans.add(new ArrayList<Integer>(result));
return;
}

for (int i = 0; i < nums.length; i ++){
if (result.contains(nums[i])){ //该数已经取过加入到result里了,跳过
continue;
}

result.add(nums[i]);
permutationHelper(result, nums); //这里开始下一个recurse,下一个recurse将从第一个元素开始找
result.remove(result.size() – 1);//backtrackin
}}

16. Permutations II

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

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

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

其他:

Arrays.sort()来对数组进行排序。

ArrayList<List<Integer>> ans;
public List<List<Integer>> permuteUnique(int[] nums) {
ans = new ArrayList<>();
if (nums == null) {
return ans;}
if (nums.length == 0) {
ans.add(new ArrayList<Integer>());
return ans;}
Arrays.sort(nums);
int[] visited = new int[nums.length];
for(int i = 0; i < nums.length; i ++) {
visited[i] = 0;
}
//store the result of each recursive
ArrayList<Integer> tmp = new ArrayList<Integer>();
permutationHelper(tmp, nums, visited);
return ans;
}

private void permutationHelper(ArrayList<Integer> result, int[] nums, int[] visited){
if (result.size() == nums.length){
ans.add(new ArrayList<Integer>(result));
return;
}

for (int i = 0; i < nums.length; i ++) {
if (visited[i] == 0) {//detect duplication.
if (i >0 && nums[i] == nums[i – 1] && visited[i – 1] == 0)
{
continue;
}
result.add(nums[i]);
visited[i] = 1;
permutationHelper(result, nums, visited);
visited[i] = 0;
result.remove(result.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<String> ans;

public List<String> stringPermutation2(String str) {

ans = new ArrayList<String>();
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: