Skip to content

Commit 4089fef

Browse files
awangdevawangdev
committed
day0
1 parent dc36b76 commit 4089fef

21 files changed

Lines changed: 604 additions & 293 deletions

‎Java/Backpack.java‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,8 @@
1919
O(m)的做法，注意j是倒序的啊！
2020
```
2121
/*
22-
Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?
22+
Given n items with size Ai, an integer m denotes the size of a backpack.
23+
How full you can fill this backpack?
2324
2425
Example
2526
If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select [2, 3, 5], so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.

‎Java/Best Time to Buy and Sell Stock IV.java‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,8 @@
1212
Given prices = [4,4,6,1,1,4,2,5], and k = 2, return 6.
1313
1414
Note
15-
You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
15+
You may not engage in multiple transactions at the same time
16+
(i.e., you must sell the stock before you buy again).
1617
1718
Challenge
1819
O(nk) time.

‎Java/Clone Graph.java‎

Lines changed: 68 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -23,19 +23,78 @@
2323
\_/
2424
Hide Tags Depth-first Search Breadth-first Search Graph
2525
26+
27+
*/
28+
29+
/*
30+
//NEED TO RUN THIS ON LINT
31+
Thoughts: 12.12.2015
32+
The original thoughs of using ArrayList, and using a index to track of which node has not been visited.
33+
It's alright, but it uses extra space, and basically copie all nodes again.
34+
It's similar to using a queue.
35+
At the end, it's doing O(m * n)
36+
Maybe can improve this.
37+
38+
Need a queue and process each element. and a hashmap to track duplicates.
39+
1. make sure the node is no duplicate
40+
2. make sure to all all child
41+
42+
border: case: node == nul, or node has not child, return a new instance of it'self?
43+
44+
*/
45+
46+
public class Solution {
47+
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
48+
if (node == null || node.neighbors.size() == 0) {
49+
return node;
50+
}
51+
52+
HashMap<UndirectedGraphNode, UndirectedGraphNode> map =
53+
new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
54+
Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
55+
56+
queue.offer(node);
57+
//process each node
58+
while (!queue.isEmpty()) {
59+
UndirectedGraphNode curr = queue.poll();
60+
UndirectedGraphNode newNode;
61+
if (!map.containsKey(curr)) {
62+
map.put(curr, new UndirectedGraphNode(curr.label));
63+
}
64+
UndirectedGraphNode newNode = map.get(curr);
65+
//Add neighbors for each node
66+
for (UndirectedGraphNode neighbor : curr.neighbors) {
67+
UndirectedGraphNode newNeighbor;
68+
if (!map.containsKey(neighbor)) {
69+
map.put(neighbor, new UndirectedGraphNode(neighbor.label));
70+
}
71+
newNeighbor = map.get(neighbor);
72+
73+
newNode.neighbors.add(newNeighbor);
74+
}//end for
75+
76+
}//end while
77+
78+
return map.get(node);
79+
}
80+
}
81+
82+
83+
84+
/*
85+
86+
2687
Thinking process:
2788
1. Clone all nodes available: using HashMap to go through all possible query. No duplicates added using HashMap.
28-
HashMap map has the list of all new nodes. No neighbors added yet
29-
<key,value> = <original node, new node with just a label (without neighbor list)>
30-
At same time, the arrayList nodes has all original nodes(with neighbors) in Breadth-first order.
89+
HashMap map has the list of all new nodes. No neighbors added yet
90+
<key,value> = <original node, new node with just a label (without neighbor list)>
91+
At same time, the arrayList nodes has all original nodes(with neighbors) in Breadth-first order.
3192
2. Add neighbor for nodes in map:
32-
- Locate the 'newNode' from map by using the key: the original node
33-
- loop through the original node's neighbor size
34-
- use original neighbor as key to get the new neighbor instance from map
35-
- add this new neighbor instance to the neighbor list of 'newNode'
36-
93+
- Locate the 'newNode' from map by using the key: the original node
94+
- loop through the original node's neighbor size
95+
- use original neighbor as key to get the new neighbor instance from map
96+
- add this new neighbor instance to the neighbor list of 'newNode'
3797
*/
38-
3998
/**
4099
* Definition for undirected graph.
41100
* class UndirectedGraphNode {

‎Java/Coins in a Line.java‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -26,7 +26,8 @@
2626

2727
/*
2828
Thoughts:
29-
Clarify: '1st play will win' means: if play properly, 1st play will surely have a way to win that 2nd play can't beat.
29+
Clarify: '1st play will win' means: if play properly,
30+
1st play will surely have a way to win that 2nd play can't beat.
3031
Make dp[i]: the result when n = i.
3132
fn:
3233
Think back a step, state-1:

‎Java/Find the Connected Component in the Undirected Graph.java‎

Lines changed: 34 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,18 @@
1+
BFS遍历，把每个node的neighbor都加进来。
2+
3+
一定注意要把visit过的node Mark一下。因为curr node也会是别人的neighbor，会无限循环。
4+
5+
Component的定义：所有Component内的node必须被串联起来via path (反正这里是undirected, 只要链接上就好)
6+
7+
这道题：其实component在input里面都已经给好了，所有能一口气visit到的，全部加进queue里面，他们就是一个component里面的了。
8+
9+
而我们这里不需要判断他们是不是Component。
10+
```
111
/*
2-
Find the number connected component in the undirected graph. Each node in the graph contains a label and a list of its neighbors.
3-
(a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths,
12+
Find the number connected component in the undirected graph.
13+
Each node in the graph contains a label and a list of its neighbors.
14+
(a connected component (or just component) of an undirected graph is a subgraph in which
15+
any two vertices are connected to each other by paths,
416
and which is connected to no additional vertices in the supergraph.)
517
618
Example
@@ -127,36 +139,38 @@ public class Solution {
127139
public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
128140
List<List<Integer>> rst = new ArrayList<>();
129141
if (nodes == null || nodes.size() == 0) {
130-
return rst;
142+
return rst;
131143
}
132144
//Init:
133-
Set<UndirectedGraphNode> checked = new HashSet();
145+
Set<UndirectedGraphNode> checked = new HashSet();
134146
Queue<UndirectedGraphNode> queue = new LinkedList();
135147
ArrayList<Integer> component = new ArrayList<Integer>();
136148

137149
queue.offer(nodes.get(0));
138150

139151
while (!nodes.isEmpty()) {
140-
if (queue.isEmpty()) {
141-
Collections.sort(component);
142-
rst.add(component);
143-
queue.offer(nodes.get(0));
144-
component = new ArrayList<Integer>();
145-
} else {
146-
UndirectedGraphNode curr = queue.poll();
147-
if (!checked.contains(curr)) {
148-
checked.add(curr);
149-
component.add(curr.label);
150-
nodes.remove(curr);
151-
for (UndirectedGraphNode node : curr.neighbors) {
152-
queue.add(node);
153-
}
154-
}
155-
}
152+
if (queue.isEmpty()) {
153+
Collections.sort(component);
154+
rst.add(component);
155+
queue.offer(nodes.get(0));
156+
component = new ArrayList<Integer>();
157+
} else {
158+
UndirectedGraphNode curr = queue.poll();
159+
if (!checked.contains(curr)) {
160+
checked.add(curr);
161+
component.add(curr.label);
162+
nodes.remove(curr);
163+
for (UndirectedGraphNode node : curr.neighbors) {
164+
queue.add(node);
165+
}
166+
}
167+
}
156168
}
157169
if (!component.isEmpty()) {
158170
rst.add(component);
159171
}
160172
return rst;
161173
}
162174
}
175+
176+
```

‎Java/Find the Weak Connected Component in the Directed Graph.java‎

Lines changed: 40 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,23 @@
1+
Identify这是个union-find问题还挺巧妙。
2+
看到了weak component的形式： 一个点指向所有，那么所有的点都有一个公共的parent，然后就是要找出这些点。
3+
4+
为何不能从一个点出发，比如A，直接print它所有的neighbors呢？
5+
不行，如果轮到了B点，那因为是directed,它也不知道A的情况，也不知道改如何继续加，或者下手。
6+
7+
所以，要把所有跟A有关系的点，或者接下去和A的neighbor有关系的点，都放进union-find里面，让这些点有Common parents.
8+
9+
最后output的想法：
10+
做一个 map <parent ID, list>。
11+
之前我们不是给每个num都存好了parent了嘛。
12+
每个num都有个parent, 然后不同的parent就创造一个不同的list。
13+
最后，把Map里面所有的list拿出来就好了。
14+
```
115
/*
2-
Find the number Weak Connected Component in the directed graph. Each node in the graph contains a label and a list of its neighbors. (a connected set of a directed graph is a subgraph in which any two vertices are connected by direct edge path.)
16+
Find the number Weak Connected Component in the directed graph.
17+
Each node in the graph contains a label and a list of its neighbors.
18+
(a connected set of a directed graph is a subgraph in which
19+
any two vertices are connected by direct edge path.)
320
4-
Have you met this question in a real interview? Yes
521
Example
622
Given graph:
723
@@ -88,13 +104,14 @@ void union(int x, int y) {
88104
}
89105
}
90106
public List<List<Integer>> generateRst (List<List<Integer>> rst, UnionFind uf, HashSet<Integer> set) {
91-
107+
92108
HashMap<Integer, List<Integer>> listMap = new HashMap<Integer, List<Integer>>();
93109
for (int num : set) {
94110
int rootParent = uf.find(num);//uf.map.get(num);
95111
if (!listMap.containsKey(rootParent)) {
96112
listMap.put(rootParent, new ArrayList<Integer>());
97113
}
114+
//Add num into its correct set (meaning its root ancestor)
98115
listMap.get(rootParent).add(num);
99116
}
100117

@@ -141,5 +158,25 @@ public List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes) {
141158

142159

143160

161+
/*
162+
Can we do the following for find() ? Inspired by the union-find implemented with int[]
163+
Sort of recurisvely trying to get the parent orign, instead of using a while loop?
164+
I guess it's doable.
165+
*/
166+
//Root parent should have itself as child in map<child,parent>
167+
int find(int x) {
168+
int parent = map.get(x);
169+
if (parent != map.get(parent)) {
170+
parent = map.get(parent);
171+
map.put(x, parent);
172+
}
173+
return parent;
174+
}
175+
176+
177+
178+
179+
144180

145181

182+
```

‎Java/Graph Valid Tree.java‎

Lines changed: 11 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -67,15 +67,24 @@ public boolean validTree(int n, int[][] edges) {
6767

6868
/*
6969
Not only find parent, also update the spot parents[node] with parent node, recursively.
70+
71+
*** The fact is, at all levels, if any curr != its parent, it'll trigger the find() method,
72+
Then it makes sure parent node will be assigned to this curr node index.
73+
74+
Goal: Mark curr node: who is your ancestor parent; and that indicates if other nodes are
75+
in the same union as curr.
7076
*/
7177
public int find(int node) {
72-
if (parents[node] == node) {
78+
if (parents[node] == node) {//If curr node == its parent, return curr node.
7379
return node;
7480
}
81+
//If curr node != its parent, we will attempt to find its grandparents, and assign to curr node.
7582
parents[node] = find(parents[node]);
7683
return parents[node];
7784
}
78-
85+
/*
86+
Either union x into y, or the other way
87+
*/
7988
public void union(int x, int y) {
8089
int findX = parents[x];
8190
int findY = parents[y];

‎Java/Hash Function.java‎

Lines changed: 14 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,30 +1,38 @@
11
/*
2-
In data structure Hash, hash function is used to convert a string(or any other type) into an integer smaller than hash size and bigger or equal to zero. The objective of designing a hash function is to "hash" the key as unreasonable as possible. A good hash function can avoid collision as less as possible. A widely used hash function algorithm is using a magic number 33, consider any string as a 33 based big integer like follow:
2+
In data structure Hash, hash function is used to convert a string(or any other type)
3+
into an integer smaller than hash size and bigger or equal to zero. The objective of
4+
designing a hash function is to "hash" the key as unreasonable as possible.
5+
A good hash function can avoid collision as less as possible.
6+
A widely used hash function algorithm is using a magic number 33,
7+
consider any string as a 33 based big integer like follow:
38
4-
hashcode("abcd") = (ascii(a) * 333 + ascii(b) * 332 + ascii(c) *33 + ascii(d)) % HASH_SIZE
9+
hashcode("abcd") = (ascii(a) * 33^3 + ascii(b) * 33^2 + ascii(c) *33^1 + ascii(d)*33^0) % HASH_SIZE
510
611
= (97* 333 + 98 * 332 + 99 * 33 +100) % HASH_SIZE
712
813
= 3595978 % HASH_SIZE
914
10-
here HASH_SIZE is the capacity of the hash table (you can assume a hash table is like an array with index 0 ~ HASH_SIZE-1).
15+
here HASH_SIZE is the capacity of the hash table
16+
(you can assume a hash table is like an array with index 0 ~ HASH_SIZE-1).
1117
12-
Given a string as a key and the size of hash table, return the hash value of this key.f
18+
Given a string as a key and the size of hash table, return the hash value of this key.
1319
1420
1521
1622
Example
1723
For key="abcd" and size=100, return 78
1824
1925
Clarification
20-
For this problem, you are not necessary to design your own hash algorithm or consider any collision issue, you just need to implement the algorithm as described.
26+
For this problem, you are not necessary to design your own hash algorithm
27+
or consider any collision issue, you just need to implement the algorithm as described.
2128
2229
Tags Expand
2330
Hash Table
2431
2532
Thinking process:
2633
Use given hash function.
27-
However, need to consider integer overflow. A simple way: save it as a long during calculation. Then return a (int).
34+
However, need to consider integer overflow.
35+
A simple way: save it as a long during calculation. Then return a (int).
2836
*/
2937

3038
class Solution {

0 commit comments

Comments
 (0)