重复与不重复之全排列与所有子串

发表于 | 分类于 | 阅读次数

Description

这里举leetcode中的46，47，77，78，90这几道题【难度： medium】

都是dfs问题，当然可以用其他的方法解决

全排列部分
[1,2,3]的全排列如下：

1
2
3
4
5
6
7
8
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

又如[1,1,2]的全排列如下：

1
2
3
4
5
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

子串部分

从小于等于n的数中选取k个数的集合，如n=4,k=2的情况如下：

1
2
3
4
5
6
7
8
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

[1,2,3]的全部子串:

1
2
3
4
5
6
7
8
9
10
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

[1,2,2]的全部子串：

1
2
3
4
5
6
7
8
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Solution

46.Permutations

全排列的最基本解法：dfs

以1，2，3为例，第一次选择可以选1，2或者3，

然后第二次选择：如果第一次选择的是1则此次对应的是2和3；2对应的是1和3；3对应的是1和2

最后第三次选择，选择剩下的即可

下面使用python实现的：

思路就是每一次从剩下元素组成的数组中挑选出一个元素来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def permute(self, nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    all_list=self.full_arrangement([],[],nums)
    return all_list
def full_arrangement(self,all_list,res_list,nums):
    if len(nums)==0:
        temp=[i for i in res_list]
        all_list.append(temp)
        return all_list
    i=0
    while i<len(nums):
        res_list.append(nums[i])
        temp=[num for num in nums]
        temp.pop(i)
        all_list=self.full_arrangement(all_list,res_list,temp)
        res_list.pop(-1)
        i+=1
    return all_list

47.Permutations II

这个题是上面一道题的衍生，开始我用python做的时候，是先按照没有重复元素的方法做，然后再去重；发现超时了，不过这个题目和上面的题目的区别在于：元素选取时，必须满足相同元素选取的顺序不能变（即相同元素的第一个元素必须在第二个元素的前面）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static List<List<Integer>> permuteUnique(int[] nums){
    List<List<Integer>> lists=new ArrayList<>();
    if(nums==null||nums.length==0) return lists;//如果为空，返回
    boolean []used=new boolean[nums.length];//用来判断元素是否已近使用
    List<Integer> arr=new ArrayList<>();
    Arrays.sort(nums);
    dfs(nums,lists,arr,used);
    return lists;
}
private static void dfs(int[] nums, List<List<Integer>> lists, List<Integer> arr, boolean[] used) {
    if(nums.length==arr.size()){
        lists.add(new ArrayList<>(arr));//如果长度已近达到了，则将其添加
    }else {
        for(int i=0;i<nums.length;i++){
            if(used[i])continue;//表示已经选过了
            if(i>0&&nums[i-1]==nums[i]&&!used[i-1])continue;//如果该元素前面的元素与之相等，且前面的元素没有被选取，则不能选取该元素
            used[i]=true;
            arr.add(nums[i]);
            dfs(nums,lists,arr,used);//前两行和后两行对称，保证遍历时一样
            used[i]=false;
            arr.remove(arr.size()-1);
        }
    }
}

77.Combinations

从n个元素中选k个的所用组合方式，这里用的是dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> lists=new ArrayList<>();
    List<Integer> list=new ArrayList<>();
    combinedDfs(lists,list,n,k,1);
    return lists;
}
private void combinedDfs(List<List<Integer>> lists, List<Integer> list, int n, int k, int i) {
    if(list.size()==k)lists.add(new ArrayList<>(list));
    else {
        while (i<=n){
            list.add(i);
            combinedDfs(lists,list,n,k,i+1);
            list.remove(list.size()-1);
            i++;
        }
    }
}

78. Subsets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> lists=new ArrayList<>();
    lists.add(new ArrayList<>());
    List<Integer> list=new ArrayList<>();
    for(int i=1;i<=nums.length;i++){
        subsetsDfs(lists,list,nums,i,0);
    }
    return lists;
}
private void subsetsDfs(List<List<Integer>> lists, List<Integer> list, int[] nums, int k, int i) {
    if(list.size()==k)lists.add(new ArrayList<>(list));
    else {
        for(int j=i;j<nums.length;j++){
            list.add(nums[j]);
            subsetsDfs(lists,list,nums,k,j+1);
            list.remove(list.size()-1);
        }
    }
}

90. Subsets II

这个去重部分，可以好好思考一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> lists=new ArrayList<>();
    lists.add(new ArrayList<>());
    List<Integer> list=new ArrayList<>();
    Arrays.sort(nums);
    for(int k=1;k<=nums.length;k++){
        subsets2Dfs(lists,list,nums,k,0);
    }
    return lists;
}
private void subsets2Dfs(List<List<Integer>> lists, List<Integer> list, int[] nums, int k,int i) {
    if(list.size()==k) lists.add(new ArrayList<>(list));
    else {
        for(int j=i;j<nums.length;j++){
            list.add(nums[j]);
            subsets2Dfs(lists,list,nums,k,j+1);
            list.remove(list.size()-1);
            while (j<nums.length-1&&nums[j]==nums[j+1])j++;
        }
    }
}
如果觉得有帮助，给我打赏吧！