[笔记整理]九章算法第一章
[笔记整理]九章算法第一章
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 set of integers, possibly with duplicates, S, determine all possible subsets from the set S.
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 represents a set that permits duplicates of integers while ensuring uniqueness in the output by restricting each integer to a single occurrence. Therefore, our second challenge involves eliminating duplicated integers.
In what scenarios would the use of the subsets template result in duplicated integer instances when attempting 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 established the approach to prevent duplication of cases within the output: when attempting to retrieve the next element from the sorted array and inserting it into our result set, we must first verify if this element has already been duplicated. If so, it will be skipped; otherwise, if there exists an equivalent element that hasn’t been added yet.
为了实现这一模式，在插入重复元素时，请确保我们的插入操作应从排序数组中的第一个重复元素开始进行操作。这意味着我们将仅允许[1, 2(first)]、[1, 2(first), 2(second)]这样的序列出现，并且不允许类似的情况出现：例如[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: 为了分析递归解决一个问题的时间复杂度, 我们应该考虑这种方法能产生多少个"结果". 在这种情况下, 我们需要计算路径被加入到"result"中的次数. 时间复杂度应为O(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分钟内答出两道题目才能通过面试！