Skip to content

Commit 248f06b

Browse files
awangdevawangdev
committed
combinations
1 parent 4720b48 commit 248f06b

25 files changed

Lines changed: 4115 additions & 1714 deletions

‎Java/Binary Tree Maximum Path Sum II.java‎

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,14 @@
11
M
2+
1526771382
3+
tags: Tree, DFS
24

3-
比Binary Tree Maximum Path Sum I 简单许多. 因为条件给的更多：at least 1 node + have to start from root => have to have root.
5+
找到从max path sum from root. 条件: 至少有一个node.
46

5-
方法1:
6-
维持一个global或者recursive里的sum。traversal entire tree via DFS. 简单明了。
7-
8-
9-
方法2:
10-
Single path: either left or right.
11-
If the path sum < 0, just skip it.
7+
#### DFS
8+
- 比Binary Tree Maximum Path Sum I 简单许多. 因为条件给的更多：at least 1 node + have to start from root
9+
- root一定用到
10+
- 3种情况: curr node, curr+left, curr+right
11+
- 因为一定包括root, 说以从 `dfs(root, sum=0)` 开始, 每个level先加root, sum += root.val
1212

1313
```
1414
/*

‎Java/Binary Tree Maximum Path Sum.java‎

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,17 @@
55
找max path sum, 可以从任意treeNode 到任意 treeNode.
66

77
#### DFS, PathSum object
8-
8+
- that just solves everything
9+
```
10+
private class PathSum {
11+
int singlePathMax;
12+
int combinedPathMax;
13+
PathSum(int singlePathMax, int combinedPathMax) {
14+
this.singlePathMax = singlePathMax;
15+
this.combinedPathMax = combinedPathMax;
16+
}
17+
}
18+
```
919

1020

1121
#### Previous Notes

‎Java/Binary Tree Right Side View.java‎

Lines changed: 92 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,28 +1,111 @@
11
M
2+
1526769889
3+
tags: Tree, DFS, BFS
24

3-
最右:即level traversal每一行的最末尾.
5+
给一个binary tree, 从右边看过来, return all visible nodes
46

5-
BFS，用queue.size()来出发saving result.
7+
#### BFS
8+
- 最右:即level traversal每一行的最末尾.
9+
- BFS, queue 来存每一行的内容, save end node into list
10+
11+
#### DFS
12+
- Use Map<Level, Integer> 来存每一个level的结果
13+
- dfs(node.right), 然后 dfs(node.left)
614

715
```
816
/*
917
Given a binary tree, imagine yourself standing on the right side of it,
1018
return the values of the nodes you can see ordered from top to bottom.
1119
12-
For example:
13-
Given the following binary tree,
20+
Example:
21+
22+
Input: [1,2,3,null,5,null,4]
23+
Output: [1, 3, 4]
24+
Explanation:
25+
1426
1 <---
15-
/ \\
27+
/ \
1628
2 3 <---
17-
\\ \\
29+
\ \
1830
5 4 <---
19-
You should return [1, 3, 4].
31+
*/
32+
33+
/*
34+
right side view:
35+
- the tree may not be complete
36+
- always find right-most. if right child not available, dfs into left child
37+
- tracking back is hard for dfs
38+
- bfs: on each level, record the last item of the queue
39+
*/
40+
41+
class Solution {
42+
public List<Integer> rightSideView(TreeNode root) {
43+
List<Integer> result = new ArrayList<>();
44+
// check edge case
45+
if (root == null) {
46+
return result;
47+
}
2048

21-
Tags: Tree, Depth-first Search, Breadth-first Search
22-
Similar Problems: (M) Populating Next Right Pointers in Each Node
49+
// init queue, result list
50+
Queue<TreeNode> queue = new LinkedList<>();
51+
queue.offer(root);
2352

53+
// loop over queue with while loop; inner while loop to complete level
54+
while (!queue.isEmpty()) {
55+
int size = queue.size();
56+
while (size > 0) {
57+
size--;
58+
TreeNode node = queue.poll();
59+
if (size == 0) {
60+
result.add(node.val);
61+
}
62+
if(node.left != null) queue.offer(node.left);
63+
if(node.right != null) queue.offer(node.right);
64+
}
65+
}
66+
return result;
67+
}
68+
}
69+
70+
71+
/*
72+
DFS: mark each level with map<level, node>
73+
1. dfs right side first, then left side at each level
74+
2. if candidate not exist, add to map, if exist, skip.
2475
*/
2576

77+
class Solution {
78+
public List<Integer> rightSideView(TreeNode root) {
79+
List<Integer> result = new ArrayList<>();
80+
// check edge case
81+
if (root == null) {
82+
return result;
83+
}
84+
// init map, dfs
85+
Map<Integer, Integer> map = new HashMap<>();
86+
int depth = dfs(map, root, 0);
87+
// output result
88+
for (int i = 0; i <= depth; i++) {
89+
if (map.containsKey(i))
90+
result.add(map.get(i));
91+
}
92+
return result;
93+
}
94+
95+
private int dfs(Map<Integer, Integer> map, TreeNode node, int depth) {
96+
if(node == null) {
97+
return 0;
98+
}
99+
if (!map.containsKey(depth)) {
100+
map.put(depth, node.val);
101+
}
102+
int rightDepth = dfs(map, node.right, depth + 1);
103+
int leftDepth = dfs(map, node.left, depth + 1);
104+
return Math.max(leftDepth, rightDepth) + depth;
105+
}
106+
}
107+
108+
26109
/**
27110
* Definition for a binary tree node.
28111
* public class TreeNode {

‎Java/Combination Sum II.java‎

Lines changed: 93 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,101 @@
11
M
2+
1526759152
3+
tags: Array, DFS, Backtracking, Combination
4+
5+
给一串数字candidates (can have duplicates), 和一个target.
6+
7+
找到所有unique的 组合(combination) int[], 要求每个combination的和 = target.
8+
9+
注意: 同一个candidate integer, 只可以用一次.
10+
11+
#### DFS, Backtracking
12+
- when the input has duplicates, and want to skip redundant items?
13+
- 1. sort. 2. in for loop, skip same neighbor.
14+
- 考虑input: 有duplicate, 必须sort
15+
- 考虑重复使用的规则: 不可以重复使用
16+
- 1. for loop里面dfs的时候, 使用curr index + 1
17+
- 2. for loop里面, 同一个level, 同一个数字, 不能重复使用: `(i > index && candidates[i] == candidates[i - 1]) continue`
18+
- 因为在同一个level里面重复的数字在下一个dfs level里面是会被考虑到的, 这里必须skip (这个就记住吧)
19+
- the result is trivial, save success list into result.
220

3-
还是DFS. 和Combination Sum I 类似.
4-
确保Helper是用i+1，下一层的数字, 不允许重复。
521

622
```
723
/*
24+
Given a collection of candidate numbers (candidates) and a target number (target),
25+
find all unique combinations in candidates where the candidate numbers sums to target.
26+
27+
Each number in candidates may only be used once in the combination.
28+
29+
Note:
30+
31+
All numbers (including target) will be positive integers.
32+
The solution set must not contain duplicate combinations.
33+
Example 1:
34+
35+
Input: candidates = [10,1,2,7,6,1,5], target = 8,
36+
A solution set is:
37+
[
38+
[1, 7],
39+
[1, 2, 5],
40+
[2, 6],
41+
[1, 1, 6]
42+
]
43+
Example 2:
44+
45+
Input: candidates = [2,5,2,1,2], target = 5,
46+
A solution set is:
47+
[
48+
[1,2,2],
49+
[5]
50+
]
51+
52+
53+
*/
54+
55+
/*
56+
- one item can be picked once. the input candidates may have duplicates.
57+
- IMPORTANT: 1. sort. 2. Skip adjacent item in for loop
58+
- use dfs, for loop to aggregate candidates
59+
- do target - val to track, and when target == 0, that’s a solution
60+
- dfs(curr index i), instead of (i + 1): allows reuse of item
61+
62+
*/
63+
class Solution {
64+
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
65+
List<List<Integer>> result = new ArrayList<>();
66+
// check edge case
67+
if (candidates == null || candidates.length == 0 || target <= 0) {
68+
return result;
69+
}
70+
Arrays.sort(candidates); // critical to skip duplicates
71+
// init reuslt, dfs
72+
dfs(result, new ArrayList<>(), candidates, 0, target);
73+
return result;
74+
}
75+
76+
private void dfs(List<List<Integer>> result, List<Integer> list,
77+
int[] candidates, int index, int target) {
78+
// for loop, where dfs is performed
79+
for (int i = index; i < candidates.length; i++) {
80+
// ensures at same for loop round, the same item (sorted && neighbor) won't be picked 2 times
81+
if (i > index && candidates[i] == candidates[i - 1]) continue;
82+
83+
int value = candidates[i];
84+
list.add(value);
85+
if (target == value) {
86+
result.add(new ArrayList<>(list));
87+
} else (target - value > 0) {
88+
dfs(result, list, candidates, i + 1, target - value);
89+
}
90+
list.remove(list.size() - 1);
91+
}
92+
}
93+
}
94+
95+
96+
97+
/*
98+
LincCode
899
Given a collection of candidate numbers (C) and a target number (T),
9100
find all unique combinations in C where the candidate numbers sums to T.
10101

‎Java/Combination Sum III.java‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
M
2+
1526760084
3+
tags: Array, DFS, Backtracking, Combination
4+
5+
给一个integer k, 和一个target n.
6+
7+
从positive数字[1 ~ 9], 找到所有unique的 组合(combination) int[], size = k, 要求每个combination的和 = n.
8+
9+
(隐藏条件, 需要clarify): 同一个candidate integer [1 ~ 9], 只可以用一次.
10+
11+
#### DFS, Backtracking
12+
- 跟Combination Sum I, II 没什么太大区别, 只不过, 一定要用k个数字, 也就是一个for loop里面的特别条件
13+
- 考虑input: 没有重复数字 [1 ~ 9]
14+
- 考虑candidate重复利用: 不可以重复利用, next level dfs 时候, curr index + 1
15+
- the result is trivial, save success list into result.
16+
17+
```
18+
/*
19+
Find all possible combinations of k numbers that add up to a number n,
20+
given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
21+
22+
Note:
23+
24+
All numbers will be positive integers.
25+
The solution set must not contain duplicate combinations.
26+
Example 1:
27+
28+
Input: k = 3, n = 7
29+
Output: [[1,2,4]]
30+
Example 2:
31+
32+
Input: k = 3, n = 9
33+
Output: [[1,2,6], [1,3,5], [2,3,4]]
34+
35+
*/
36+
37+
/*
38+
- only 1-9 can be used. can use each number only once.
39+
- find k numbers to sum up to n
40+
- each solution must be unique.
41+
- dfs, for loop, each dfs, (i+1) to next level
42+
- decreasing n in each dfs, when n == i, return.
43+
- be careful with the case n - i < 0, no need to dfs
44+
- dfs: result, list, index, k, n
45+
*/
46+
47+
class Solution {
48+
public List<List<Integer>> combinationSum3(int k, int n) {
49+
List<List<Integer>> result = new ArrayList<>();
50+
// init result, check edge case
51+
if (k <= 0 || n <= 0) {
52+
return result;
53+
}
54+
55+
// dfs
56+
dfs(result, new ArrayList<>(), 1, k, n);
57+
return result;
58+
}
59+
60+
private void dfs(List<List<Integer>> result, List<Integer> list,
61+
int index, int k, int n) {
62+
// for loop
63+
for (int i = index; i <= 9; i++) {
64+
list.add(i);
65+
if (n == i && list.size() == k) { // found a success solution
66+
result.add(new ArrayList<>(list));
67+
} else if (n > i){
68+
dfs(result, list, i + 1, k, n - i);
69+
}
70+
list.remove(list.size() - 1);
71+
}
72+
}
73+
}
74+
75+
76+
```

0 commit comments

Comments
 (0)