Skip to content

Commit b9f98a2

Browse files
bkningbkning
committed
Week03作业提交
1 parent 993b278 commit b9f98a2

6 files changed

Lines changed: 232 additions & 0 deletions

File tree

‎Week03/AllSort.java‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package week03;
2+
3+
import java.util.ArrayDeque;
4+
import java.util.ArrayList;
5+
import java.util.Deque;
6+
import java.util.List;
7+
import java.util.HashSet;
8+
9+
10+
/**
11+
* 全排列
12+
*/
13+
public class AllSort {
14+
15+
16+
public static void main(String[] args) {
17+
List<List<Integer>> res = permute(new int[] {1, 2});
18+
System.out.println(res);
19+
}
20+
21+
22+
public static List<List<Integer>> permute(int[] nums) {
23+
int len = nums.length;
24+
25+
List<List<Integer>> res = new ArrayList<>(factorial(len));
26+
if (len == 0) {
27+
return res;
28+
}
29+
30+
HashSet<Integer> used = new HashSet<>(len);
31+
Deque<Integer> path = new ArrayDeque<>(len);
32+
33+
dfs(nums, len, 0, path, used, res);
34+
return res;
35+
}
36+
37+
private static int factorial(int n) {
38+
int res = 1;
39+
for (int i = 2; i <= n; i++) {
40+
res *= i;
41+
}
42+
return res;
43+
}
44+
45+
private static void dfs(int[] nums, int len, int depth, Deque<Integer> path, HashSet<Integer> used, List<List<Integer>> res) {
46+
if (depth == len) {
47+
res.add(new ArrayList<>(path));
48+
return;
49+
}
50+
51+
for (int i = 0; i < len; i++) {
52+
if (!used.contains(i)) {
53+
used.add(i);
54+
path.addLast(nums[i]);
55+
56+
dfs(nums, len, depth + 1, path, used, res);
57+
58+
path.removeLast();
59+
used.remove(i);
60+
}
61+
}
62+
}
63+
64+
}

‎Week03/AllSortII.java‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
package week03;
2+
3+
import java.util.ArrayDeque;
4+
import java.util.ArrayList;
5+
import java.util.Arrays;
6+
import java.util.Deque;
7+
import java.util.List;
8+
9+
10+
/**
11+
* 全排列II
12+
*/
13+
public class AllSortII {
14+
15+
public static void main(String[] args) {
16+
int[] nums = {1, 1, 2};
17+
List<List<Integer>> res = permuteUnique(nums);
18+
System.out.println(res);
19+
}
20+
21+
22+
public static List<List<Integer>> permuteUnique(int[] nums) {
23+
int len = nums.length;
24+
List<List<Integer>> res = new ArrayList<>();
25+
if (len == 0) {
26+
return res;
27+
}
28+
29+
Arrays.sort(nums);
30+
31+
boolean[] used = new boolean[len];
32+
Deque<Integer> path = new ArrayDeque<>(len);
33+
dfs(nums, len, 0, used, path, res);
34+
return res;
35+
}
36+
37+
38+
private static void dfs(int[] nums, int len, int depth, boolean[] used, Deque<Integer> path, List<List<Integer>> res) {
39+
if (depth == len) {
40+
res.add(new ArrayList<>(path));
41+
return;
42+
}
43+
44+
for (int i = 0; i < len; ++i) {
45+
if (used[i]) {
46+
continue;
47+
}
48+
49+
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
50+
continue;
51+
}
52+
53+
path.addLast(nums[i]);
54+
used[i] = true;
55+
56+
dfs(nums, len, depth + 1, used, path, res);
57+
used[i] = false;
58+
path.removeLast();
59+
}
60+
}
61+
62+
}

‎Week03/ClosestParentBinaryTree.java‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
package week03;
2+
3+
4+
/**
5+
* 二叉树的最近公共祖先
6+
*/
7+
public class ClosestParentBinaryTree {
8+
9+
10+
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
11+
if(root == null || root == p || root == q) return root;
12+
TreeNode left = lowestCommonAncestor(root.left, p, q);
13+
TreeNode right = lowestCommonAncestor(root.right, p, q);
14+
if(left == null) return right;
15+
if(right == null) return left;
16+
return root;
17+
}
18+
19+
}

‎Week03/Combine.java‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package week03;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
import java.util.Stack;
6+
7+
8+
/**
9+
* 组合
10+
*/
11+
public class Combine {
12+
13+
private static List<List<Integer>> result = new ArrayList<>();
14+
15+
16+
public static void main(String[] args) {
17+
List<List<Integer>> res = combine(4, 2);
18+
System.out.println(res);
19+
}
20+
21+
public static List<List<Integer>> combine(int n, int k) {
22+
if (n <= 0 || k <= 0 || n < k) {
23+
return result;
24+
}
25+
findCombinations(n, k, 1, new Stack<>());
26+
return result;
27+
}
28+
29+
private static void findCombinations(int n, int k, int index, Stack<Integer> p) {
30+
if (p.size() == k) {
31+
result.add(new ArrayList<>(p));
32+
return;
33+
}
34+
35+
for (int i = index; i <= n - (k - p.size()) + 1; i++) {
36+
p.push(i);
37+
findCombinations(n, k, i + 1, p);
38+
p.pop();
39+
}
40+
}
41+
42+
}

‎Week03/ConsBinaryTree.java‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package week03;
2+
3+
4+
import java.util.HashMap;
5+
6+
/**
7+
* 从前序与中序遍历序列构造二叉树
8+
*/
9+
public class ConsBinaryTree {
10+
11+
public TreeNode buildTree(int[] preOrder, int[] inOrder) {
12+
HashMap<Integer, Integer> map = new HashMap<>();
13+
for (int i = 0; i < inOrder.length; i++) {
14+
map.put(inOrder[i], i);
15+
}
16+
return buildTreeHelper(preOrder, 0, preOrder.length, inOrder, 0, inOrder.length, map);
17+
}
18+
19+
private TreeNode buildTreeHelper(int[] preOrder, int preStart, int preEnd, int[] inOrder, int inStart, int inEnd, HashMap<Integer, Integer> map) {
20+
if (preStart == preEnd) {
21+
return null;
22+
}
23+
24+
int rootVal = preOrder[preStart];
25+
TreeNode root = new TreeNode(rootVal);
26+
int inRootIndex = map.get(rootVal);
27+
int leftNum = inRootIndex - inStart;
28+
root.left = buildTreeHelper(preOrder, preStart + 1, preStart + leftNum + 1, inOrder, inStart, inRootIndex, map);
29+
root.right = buildTreeHelper(preOrder, preStart + leftNum + 1, preEnd, inOrder, inRootIndex + 1, inEnd, map);
30+
return root;
31+
}
32+
33+
}

‎Week03/TreeNode.java‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
package week03;
2+
3+
public class TreeNode {
4+
5+
int val;
6+
TreeNode left;
7+
TreeNode right;
8+
9+
TreeNode(int x) {
10+
val = x;
11+
}
12+
}

0 commit comments

Comments
 (0)