[笔记整理]九章算法第一章

[笔记整理]九章算法第一章

1 排列组合模版

1.1 Subsets

Problem: Given a set of distinct integers, S, return all possible subsets

Note:

Elements in a subset must be in non-descending order.

The solution set must not contain duplicate subsets.

For example,

If S = [1,2,3], a solution is:  [  [3],  [1],  [2],  [1,2,3],  [1,3],  [2,3],  [1,2],  []]

Solution: Use recursion to construct the solution.

         Tip: Use a tree structure to consider the recursion, e.g.:

{}

{1}    {2}    {3}    {4}

{1,2}{1,3}{1,4}    {2,3}{2,4}    {3,4}        ...                   

Template:

public class Solution {
    //Test cases:
    //[1,2,3,4,5,6]
    //[]
    //null
    //[1]
    //[1,2,...,1000]
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (S == null || S.length == 0) {
            return result;
        }
        Arrays.sort(S);
        ArrayList<Integer> path = new ArrayList<Integer>();
        subsetsHelper(S, 0, path, result);
        return result;
    }
    
    private void subsetsHelper(int[] S, int pos, ArrayList<Integer> path, 
    ArrayList<ArrayList<Integer>> result) {
        result.add(new ArrayList<Integer>(path));
        
        for (int i = pos; i < S.length; i++) {
            path.add(S[i]);
            subsetsHelper(S, i + 1, path, result);//Attention: 
            //shall not set "pos + 1" as the second argument, 
            //because the logic is: after add the ith element, 
            //you can only add the elements which has index greater than i.
            path.remove(path.size() - 1);
        }
    }
}

1.2 Subsets II (Unique Subsets)

Problem:Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.

The solution set must not contain duplicate subsets.

For example,

If S = [1,2,2], a solution is:[  [2],  [1],  [1,2,2],  [2,2],  [1,2],  [] ]

Solution: 

(1) Use the Subsets template to solve this problem.

(2) The input is a collection, which will allow duplicate int, but the output should be unique, which means each int is allow to appear no more than once. Therefore, the second problem for us is to remove the duplicated ints.

(3) In which cases, there would be duplicated ints if we use subsets template to solve this problem?

e.g: input: [1, 2(first), 2(second), 2(third)]

       output: [1, 2(first)]  and  [1, 2(second)], are "duplicated"

                   [1, 2(first), 2(second)]  and  [1, 2(second), 2(third)], are "duplicated"

Then, we got the pattern to prevent duplicated cases in out output, that is: When we try to get the next element from the sorted array and insert it into our result set, we should first check whether this element is duplicated. If it is, it will not be inserted, if there is an element equal to it and was not inserted into the result set.

(4) To implement this pattern, when we insert duplicated elements, our insertion should start from the first duplicated element in the sorted array, which means we will only allow [1, 2(first)], [1, 2(first), 2(second)] not allow cases like: [1, 2(second)].

Code:

public class Solution {
    //Test cases:
    //[]
    //null
    //[1,2,3]
    //[1,2,2,3]
    //[1]
    //[2,2]
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (num == null || num.length == 0) {
            return result;
        }
        Arrays.sort(num);
        ArrayList<Integer> path = new ArrayList<Integer>();
        helper(num, result, path, 0);
        return result;
    }
    
    private void helper(int[] num, ArrayList<ArrayList<Integer>> result, 
    ArrayList<Integer> path, int start) {
        result.add(new ArrayList<Integer>(path));
        
        for (int i = start; i < num.length; i++) {
            if (i != start && num[i] == num[i - 1]) {
                continue;
            }
            path.add(num[i]);
            helper(num, result, path, i + 1);//calling itself: recursion
            path.remove(path.size() - 1);//change the status back to how it was: backtracking        }    }
}

1.3 Time Complexity

Thinking: To analyze the time complexity of a problem solved by recursion, we should think about how many "results" we got from this method. In this case, we should calculate how many times we have added the "path" to "result". And the time complexity should be O(2^n).

2 Homework

2.1 Permutations
2.2 Unique Permutations
2.3 Combination Sum
2.4 Letter Combination of a Phone Number
2.5 Palindrome Partitioning
2.6 Restore IP Address
2.7 N Queens

3 总结

subsets模版的适用范围：几乎所有的搜索问题

只需根据题意改动：1）什么时候输出 2）哪些情况需要跳过

45分钟内答出两道题目才能通过面试！