Skip to content

Commit 707dae3

Browse files
awangdevawangdev
committed
hash update
1 parent 9ca302f commit 707dae3

19 files changed

Lines changed: 2158 additions & 1957 deletions

‎Java/Subarray Sum Closest.java‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,12 @@
11
M
2+
tags: Sort
23

3-
?
4+
TODO: use prefixSum, could be a 2D array, also could be a customized object
45

56
```
67
/*
7-
Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.
8+
Given an integer array, find a subarray with sum closest to zero.
9+
Return the indexes of the first number and last number.
810
911
Example
1012
Given [-3, 1, 1, -3, 5], return [0, 2], [1, 3], [1, 1], [2, 2] or [0, 4]

‎Java/Summary Ranges.java‎

Lines changed: 10 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,12 @@
11
M
2+
1528247314
3+
tags: Array
4+
5+
给一串sorted list, 中间有缺数字, return 所有数字的range string (example 看题目)
6+
7+
#### Basic implementation
8+
- 用一个list as the buffer to store candidates
9+
- when: 1. end of nums; 2. not continuous integer => convert list to result
210

311
```
412
/*
@@ -17,11 +25,11 @@
1725
*/
1826
public class Solution {
1927
public List<String> summaryRanges(int[] nums) {
20-
List<String> rst = new ArrayList<String>();
28+
List<String> rst = new ArrayList<>();
2129
if (nums == null || nums.length == 0) {
2230
return rst;
2331
}
24-
ArrayList<Integer> list = new ArrayList<Integer>();
32+
List<Integer> list = new ArrayList<>();
2533
for (int i = 0; i < nums.length; i++) {
2634
list.add(nums[i]);
2735
if (i + 1 == nums.length || nums[i] + 1 != nums[i + 1]) {

‎Java/Top K Frequent Elements.java‎

Lines changed: 11 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,16 @@
11
M
2+
1528247446
3+
tags: Hash Table, Heap, PriorityQueue
24

3-
题目有提醒: 不能用O(nLog(n)) 也就是说明要Log(n): 首先想到就是PriorityQueue, 并且不能queue.offer on the fly.
4-
那么就先count, O(n); 再priorityQueue, Log(k), k是unique 数字的总量.
5+
给一串数字, 找到top k frequent element, 并且time complexity 要比nLogN要好
6+
7+
#### PriorityQueue
8+
- 题目有提醒: 必须beetter than O(nLog(n)), 也就是说明要O(n)
9+
- 首先想到就是PriorityQueue, 并且不能queue.offer on the fly
10+
- 那么就先count, O(n), using HashMap
11+
- 再priorityQueue, (mLog(m)), m是unique 数字的总量
12+
- 最终find top k, O(k)
13+
- Overall time: O(n) + O(mLogm) + O(k) => O(n), if m is small enough
514

615
```
716
/**

‎Java/Topological Sorting.java‎

Lines changed: 31 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -1,20 +1,23 @@
11
M
2+
1528248097
23
tags: Topological Sort, BFS, DFS
34

4-
比较特别的BFS.
5+
#### Topological Sort BFS
6+
- indegree tracking: Track all neighbors/childrens. 把所有的children都存在 inDegree<label, indegree count>里面
7+
- Process with a queue: 先把所有的root加一遍(indegree == 0)，可能多个root。并且全部加到queue里面。
8+
- BFS with Queue:
9+
- Only when map.get(label) == 0, add into queue && rst. (indegree剪完了, 就是root啦)
10+
- inDegree在这里就 count down indegree, 确保在后面出现的node, 一定最后process.
511

6-
几个graph的condition：
7-
1. 可能有多个root
8-
2. directed node, 可以direct backwards.
912

10-
Steps:
11-
Track all neighbors/childrens. 把所有的children都存在map<label, count>里面
12-
先把所有的root加一遍，可能多个root。并且全部加到queue里面。
13-
14-
然后以process queue, do BFS:
15-
Only when map.get(label) == 0, add into queue && rst.
16-
这用map track apperance, 确保在后面出现的node, 一定最后process.
13+
#### Basics about graph
14+
- 几个graph的condition：
15+
- 1. 可能有多个root
16+
- 2. directed node, 可以direct backwards.
1717

18+
TODO:
19+
- build`Map<DirectedGraphNode, Integer> inDegree = new HashMap<>();` and include the root itself
20+
- that is more traditional indegree building
1821

1922
```
2023
/*
@@ -43,17 +46,21 @@
4346
Tags Expand
4447
LintCode Copyright Geeks for Geeks Depth First Search Breadth First Search
4548
49+
*/
50+
51+
/**
52+
4653
Thoughts:
4754
First idea is Breadth First Search.
48-
1. Find the node which has no parent node: this will be the beginning node. Use a HashMap to map all nodes with children, and whatever not in that map, is a root option.
55+
1. Find the node which has no parent node: this will be the beginning node.
56+
Use a HashMap to map all nodes with children, and whatever not in that map, is a root option.
4957
2. Starting from this node, put all nodes in the queue (breadth-first)
5058
3. process each node in the queue: add to array list
5159
5260
5361
Note: All all possible root node (whatever not added into the map) because there could be multiple heads : (. Really need to ask about this if not sure.
5462
55-
*/
56-
63+
*/
5764
/**
5865
* Definition for Directed graph.
5966
* class DirectedGraphNode {
@@ -73,21 +80,21 @@ public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph)
7380
return graph;
7481
}
7582
//Keep track of all neighbors in HashMap
76-
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
83+
Map<Integer, Integer> inDegree = new HashMap<>();
7784
for (DirectedGraphNode node : graph) {
7885
for (DirectedGraphNode neighbor : node.neighbors) {
7986
int keyN = neighbor.label;
80-
if (map.containsKey(keyN)) {
81-
map.put(keyN, map.get(keyN) + 1);
82-
} else {
83-
map.put(keyN, 1);
87+
if (!inDegree.containsKey(keyN)) {
88+
inDegree.put(keyN, 0);
8489
}
90+
inDegree.put(keyN, inDegree.get(keyN) + 1);
8591
}
8692
}
87-
//BFS: Add root node. Note:
88-
Queue<DirectedGraphNode> queue = new LinkedList<DirectedGraphNode>();
93+
94+
//BFS: Add root node.
95+
Queue<DirectedGraphNode> queue = new LinkedList<>();
8996
for (DirectedGraphNode node : graph) {
90-
if (!map.containsKey(node.label)) {
97+
if (!inDegree.containsKey(node.label)) {
9198
queue.offer(node);
9299
rst.add(node);
93100
}
@@ -97,8 +104,8 @@ public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph)
97104
DirectedGraphNode node = queue.poll();
98105
for (DirectedGraphNode n : node.neighbors) {
99106
int label = n.label;
100-
map.put(label, map.get(label) - 1);
101-
if (map.get(label) == 0) {
107+
inDegree.put(label, inDegree.get(label) - 1);
108+
if (inDegree.get(label) == 0) {
102109
rst.add(n);
103110
queue.offer(n);
104111
}

0 commit comments

Comments
 (0)