Skip to content

Commit 408e797

Browse files
liangliplusliangliplus
committed
第三周课后作业完成
1 parent 2422b85 commit 408e797

7 files changed

Lines changed: 239 additions & 5 deletions

‎week03/src/Combinations.java‎

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
//给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
2+
//
3+
// 示例:
4+
//
5+
// 输入: n = 4, k = 2
6+
//输出:
7+
//[
8+
// [2,4],
9+
// [3,4],
10+
// [2,3],
11+
// [1,2],
12+
// [1,3],
13+
// [1,4],
14+
//]
15+
// Related Topics 回溯算法
16+
// 👍 433 👎 0
17+
18+
19+
import java.util.ArrayList;
20+
import java.util.Deque;
21+
import java.util.List;
22+
23+
public class Combinations {
24+
public static void main(String[] args) {
25+
26+
Solution solution = new Combinations().new Solution();
27+
List<List<Integer>> combine = solution.combine(6, 2);
28+
System.out.println(combine);
29+
30+
}
31+
//leetcode submit region begin(Prohibit modification and deletion)
32+
class Solution {
33+
34+
private List<List<Integer>> result;
35+
Deque<Integer> deque;
36+
37+
public List<List<Integer>> combine(int n, int k) {
38+
/*if (n == 0 || n < k) {
39+
return new ArrayList<>();
40+
}
41+
result = new ArrayList<List<Integer>>();
42+
deque = new ArrayDeque<Integer>();
43+
dfs(n , k, 1);
44+
return result;*/
45+
46+
List<List<Integer>> result = new ArrayList<List<Integer>>();
47+
if (k > n || k < 0) {
48+
return result;
49+
}
50+
if (k == 0) {
51+
result.add(new ArrayList<Integer>());
52+
return result;
53+
}
54+
result = combine(n - 1, k - 1);
55+
for (List<Integer> list : result) {
56+
list.add(n);
57+
}
58+
result.addAll(combine(n - 1, k));
59+
return result;
60+
61+
62+
63+
64+
}
65+
66+
private void dfs(int n, int k, int start) {
67+
if (k == 0) {
68+
result.add(new ArrayList<>(deque));
69+
return;
70+
}
71+
if (start > n - k + 1) {
72+
return;
73+
}
74+
//不选择当前考虑数的begin ，递归到下一层
75+
dfs(n, k , start + 1);
76+
//不选当前考虑数的begin
77+
deque.offerLast(start);
78+
//不考虑当前考虑的数的begin ， 递归到下一层的时候k -1， 这里k表示还需要多少个数
79+
dfs(n, k -1, start + 1);
80+
deque.pollLast();
81+
}
82+
83+
84+
}
85+
//leetcode submit region end(Prohibit modification and deletion)
86+
87+
}

week03/ErChaShuDeZuiJinGongGongZuXianLcof.java renamed to week03/src/ErChaShuDeZuiJinGongGongZuXianLcof.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -38,7 +38,7 @@
3838
// 👍 158 👎 0
3939

4040

41-
package leetcode.editor.cn;
41+
4242
public class ErChaShuDeZuiJinGongGongZuXianLcof {
4343
public static void main(String[] args) {
4444

‎week03/src/Permutations.java‎

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
//给定一个 没有重复 数字的序列，返回其所有可能的全排列。
2+
//
3+
// 示例:
4+
//
5+
// 输入: [1,2,3]
6+
//输出:
7+
//[
8+
// [1,2,3],
9+
// [1,3,2],
10+
// [2,1,3],
11+
// [2,3,1],
12+
// [3,1,2],
13+
// [3,2,1]
14+
//]
15+
// Related Topics 回溯算法
16+
// 👍 989 👎 0
17+
18+
19+
import java.util.ArrayList;
20+
import java.util.Deque;
21+
import java.util.LinkedList;
22+
import java.util.List;
23+
24+
public class Permutations {
25+
public static void main(String[] args) {
26+
27+
Solution solution = new Permutations().new Solution();
28+
int[] nums = {1, 1,3};
29+
System.out.println(solution.permute(nums));
30+
}
31+
//leetcode submit region begin(Prohibit modification and deletion)
32+
33+
class Solution {
34+
35+
36+
private List<List<Integer>> result;
37+
private Deque<Integer> path;
38+
private boolean[] used;
39+
//给你一个可能重复的序列，比如 1, 1 , 2 , 返回所有不重复的序列， 对于这种情况， 我们分支不能在选择 1'， 不然会和前面1的选择重复
40+
public List<List<Integer>> permute(int[] nums) {
41+
// 设计状态变量
42+
//1.depth 递归到第几层
43+
// 2.used 数组表示该数是否被选择
44+
// 3.path 保存已选择 变量
45+
int n = nums.length;
46+
if (n <= 0) return new ArrayList<>();
47+
result = new ArrayList<List<Integer>>();
48+
path = new LinkedList<Integer>();
49+
used = new boolean[n];
50+
dfs(nums, n , 0);
51+
return result;
52+
53+
}
54+
55+
private void dfs(int[] nums, int n, int depth) {
56+
if (depth == n) {
57+
result.add(new ArrayList<>(path));
58+
return;
59+
}
60+
61+
for (int i = 0; i < n; i++) {
62+
if (used[i]) continue;
63+
64+
//nums[i] == nums[i -1] 表示前一个数和后一个数相等 && 前一个数刚刚撤销了选择，这个时候如果让1'重新进入就会生成重复结果
65+
if (i > 0 && nums[i] == nums[i -1] && used[i - 1] == false) continue;
66+
67+
path.offerLast(nums[i]);
68+
used[i] = true;
69+
70+
dfs(nums, n , depth + 1);
71+
72+
// 撤销上一层选择的数
73+
path.pollLast();
74+
used[i] = false;
75+
}
76+
}
77+
78+
79+
}
80+
//leetcode submit region end(Prohibit modification and deletion)
81+
82+
}

‎week03/src/PermutationsIi.java‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
//给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
2+
//
3+
//
4+
//
5+
// 示例 1：
6+
//
7+
//
8+
//输入：nums = [1,1,2]
9+
//输出：
10+
//[[1,1,2],
11+
// [1,2,1],
12+
// [2,1,1]]
13+
//
14+
//
15+
// 示例 2：
16+
//
17+
//
18+
//输入：nums = [1,2,3]
19+
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
20+
//
21+
//
22+
//
23+
//
24+
// 提示：
25+
//
26+
//
27+
// 1 <= nums.length <= 8
28+
// -10 <= nums[i] <= 10
29+
//
30+
// Related Topics 回溯算法
31+
// 👍 522 👎 0
32+
33+
34+
import java.util.List;
35+
36+
public class PermutationsIi {
37+
public static void main(String[] args) {
38+
39+
Solution solution = new PermutationsIi().new Solution();
40+
}
41+
//leetcode submit region begin(Prohibit modification and deletion)
42+
43+
class Solution {
44+
45+
public List<List<Integer>> permuteUnique(int[] nums) {
46+
return null;
47+
}
48+
}
49+
//leetcode submit region end(Prohibit modification and deletion)
50+
51+
}

‎week03/src/TreeNode.java‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
/**
2+
* 树可以看成有两个指针的链表
3+
* @author liangli
4+
* @Date: 2020/10/25 20:40
5+
*/
6+
public class TreeNode {
7+
public int val;
8+
public TreeNode left;
9+
public TreeNode right;
10+
11+
12+
public TreeNode(int val) {
13+
this.val = val;
14+
}
15+
16+
17+
18+
}

week03/ValidateBinarySearchTree.java renamed to week03/src/ValidateBinarySearchTree.java

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -33,8 +33,6 @@
3333
// 👍 822 👎 0
3434

3535

36-
package leetcode.editor.cn;
37-
3836
public class ValidateBinarySearchTree {
3937
public static void main(String[] args) {
4038

week03/ZhongJianErChaShuLcof.java renamed to week03/src/ZhongJianErChaShuLcof.java

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -29,8 +29,6 @@
2929
// 👍 243 👎 0
3030

3131

32-
package leetcode.editor.cn;
33-
3432
import java.util.HashMap;
3533
import java.util.Map;
3634

0 commit comments

Comments
 (0)