Skip to content

Commit 797b050

Browse files
author
TELUS\x194594
committed
init check in
0 parents  commit 797b050

13 files changed

Lines changed: 492 additions & 0 deletions

‎.gitignore‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
target/
2+
.metadata/
3+
.recommenders/
4+
Servers/
5+
RemoteSystemsTempFiles/
6+
7+
.classpath
8+
.project
9+
.settings/

‎algorithm/pom.xml‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
2+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
3+
<modelVersion>4.0.0</modelVersion>
4+
<groupId>my.algorithm</groupId>
5+
<artifactId>algorithm</artifactId>
6+
<version>0.0.1-SNAPSHOT</version>
7+
<properties>
8+
<java.version>1.8</java.version>
9+
</properties>
10+
</project>

‎algorithm/src/main/java/my/algorithm/graph/BFSGraph.java‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package my.algorithm.graph;
2+
3+
import java.util.LinkedHashMap;
4+
import java.util.Map;
5+
6+
/**
7+
*
8+
* http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/
9+
*
10+
*/
11+
public class BFSGraph {
12+
public Map<Integer, UndirectedGraphNode> map = new LinkedHashMap<>();
13+
14+
public void getUniqueNode(UndirectedGraphNode node) {
15+
if (node == null || map.containsKey(node.label)) return;
16+
map.put(node.label, node);
17+
for (UndirectedGraphNode neighbor : node.neighbors) {
18+
if (!map.containsKey(neighbor.label)) {
19+
map.put(neighbor.label, neighbor);
20+
}
21+
}
22+
for (UndirectedGraphNode neighbor : node.neighbors) {
23+
for (UndirectedGraphNode neighbor1 : neighbor.neighbors) {
24+
getUniqueNode(neighbor1);
25+
}
26+
}
27+
return;
28+
}
29+
30+
public static void main(String[] args) {
31+
UndirectedGraphNode node1 = new UndirectedGraphNode(1);
32+
UndirectedGraphNode node2 = new UndirectedGraphNode(2);
33+
UndirectedGraphNode node0 = new UndirectedGraphNode(0);
34+
UndirectedGraphNode node3 = new UndirectedGraphNode(3);
35+
UndirectedGraphNode node4 = new UndirectedGraphNode(4);
36+
37+
node1.neighbors.add(node0);
38+
node1.neighbors.add(node2);
39+
node0.neighbors.add(node1);
40+
node0.neighbors.add(node3);
41+
node2.neighbors.add(node0);
42+
node2.neighbors.add(node1);
43+
node3.neighbors.add(node1);
44+
node3.neighbors.add(node4);
45+
46+
BFSGraph graph = new BFSGraph();
47+
graph.getUniqueNode(node1);
48+
49+
for (int nodeValue : graph.map.keySet()) {
50+
System.out.println(nodeValue);
51+
}
52+
53+
}
54+
}

‎algorithm/src/main/java/my/algorithm/graph/DFSGraph.java‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package my.algorithm.graph;
2+
3+
import java.util.LinkedHashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/
8+
*/
9+
public class DFSGraph {
10+
public Map<Integer, UndirectedGraphNode> map = new LinkedHashMap<>();
11+
12+
public void getUniqueNode(UndirectedGraphNode node) {
13+
if (node == null || map.containsKey(node.label)) return;
14+
map.put(node.label, node);
15+
for (UndirectedGraphNode neighbor : node.neighbors) {
16+
getUniqueNode(neighbor);
17+
}
18+
return;
19+
}
20+
21+
public static void main(String[] args) {
22+
UndirectedGraphNode node1 = new UndirectedGraphNode(1);
23+
UndirectedGraphNode node2 = new UndirectedGraphNode(2);
24+
UndirectedGraphNode node0 = new UndirectedGraphNode(0);
25+
UndirectedGraphNode node3 = new UndirectedGraphNode(3);
26+
UndirectedGraphNode node4 = new UndirectedGraphNode(4);
27+
28+
node1.neighbors.add(node0);
29+
node1.neighbors.add(node2);
30+
node0.neighbors.add(node1);
31+
node0.neighbors.add(node3);
32+
node2.neighbors.add(node0);
33+
node2.neighbors.add(node1);
34+
node3.neighbors.add(node1);
35+
node3.neighbors.add(node4);
36+
37+
DFSGraph graph = new DFSGraph();
38+
graph.getUniqueNode(node1);
39+
40+
for (int nodeValue : graph.map.keySet()) {
41+
System.out.println(nodeValue);
42+
}
43+
44+
}
45+
}

‎algorithm/src/main/java/my/algorithm/graph/GraphClone.java‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package my.algorithm.graph;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
public class GraphClone {
7+
private Map<Integer, UndirectedGraphNode> map = new HashMap<>();
8+
9+
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
10+
if (node == null) return null;
11+
12+
if (map.containsKey(node.label)) {
13+
return map.get(node.label);
14+
}
15+
UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
16+
map.put(node.label, clone);
17+
for (UndirectedGraphNode neighbor : node.neighbors) {
18+
clone.neighbors.add(cloneGraph(neighbor));
19+
}
20+
return clone;
21+
}
22+
23+
public static void main(String[] args) {
24+
UndirectedGraphNode node1 = new UndirectedGraphNode(1);
25+
UndirectedGraphNode node2 = new UndirectedGraphNode(2);
26+
UndirectedGraphNode node0 = new UndirectedGraphNode(0);
27+
UndirectedGraphNode node3 = new UndirectedGraphNode(3);
28+
29+
node1.neighbors.add(node0);
30+
node1.neighbors.add(node2);
31+
node0.neighbors.add(node1);
32+
node0.neighbors.add(node2);
33+
node2.neighbors.add(node0);
34+
node2.neighbors.add(node1);
35+
node2.neighbors.add(node3);
36+
node3.neighbors.add(node1);
37+
38+
GraphClone graphClone = new GraphClone();
39+
UndirectedGraphNode clone = graphClone.cloneGraph(node1);
40+
41+
System.out.println(clone.label);
42+
for (UndirectedGraphNode neighbor : clone.neighbors) {
43+
System.out.println("-" + neighbor.label);
44+
for (UndirectedGraphNode neighbor1 : neighbor.neighbors) {
45+
System.out.println("--" + neighbor1.label + " ");
46+
if (neighbor1.label == 3) {
47+
for (UndirectedGraphNode neighbor2 : neighbor1.neighbors) {
48+
System.out.println("---" + neighbor2.label + " ");
49+
}
50+
}
51+
}
52+
}
53+
54+
}
55+
56+
}

‎algorithm/src/main/java/my/algorithm/graph/UndirectedGraphNode.java‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
package my.algorithm.graph;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
public class UndirectedGraphNode {
7+
int label;
8+
List<UndirectedGraphNode> neighbors;
9+
UndirectedGraphNode(int x) {
10+
label = x;
11+
neighbors = new ArrayList<UndirectedGraphNode>();
12+
}
13+
}

‎algorithm/src/main/java/my/algorithm/string/TopKFrequent.java‎

Lines changed: 110 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,110 @@
1+
package my.algorithm.string;
2+
3+
import java.util.ArrayList;
4+
import java.util.Collection;
5+
import java.util.Collections;
6+
import java.util.HashMap;
7+
import java.util.List;
8+
import java.util.Map;
9+
import java.util.PriorityQueue;
10+
11+
class TopKFrequent {
12+
public static List<String> topKFrequentSort(String[] words, int k) {
13+
List<String> result = new ArrayList<>();
14+
Map<String, WordAndCount> wordAndCountMap = new HashMap<>();
15+
for (String s : words) {
16+
if (wordAndCountMap.get(s) != null) {
17+
wordAndCountMap.get(s).increaseCount();
18+
} else {
19+
wordAndCountMap.put(s, new WordAndCount(s));
20+
}
21+
}
22+
Collection<WordAndCount> wordAndCounts = wordAndCountMap.values();
23+
ArrayList<WordAndCount> wordAndCountList = new ArrayList<WordAndCount>(wordAndCounts);
24+
Collections.sort(wordAndCountList);
25+
for (WordAndCount wordAndCount : wordAndCountList.subList(0, k)) {
26+
result.add(wordAndCount.word);
27+
}
28+
return result;
29+
}
30+
31+
public static List<String> topKFrequentHeap(String[] words, int k) {
32+
List<String> result = new ArrayList<>();
33+
Map<String, WordAndCount> wordAndCountMap = new HashMap<>();
34+
for (String s : words) {
35+
if (wordAndCountMap.get(s) != null) {
36+
wordAndCountMap.get(s).increaseCount();
37+
} else {
38+
wordAndCountMap.put(s, new WordAndCount(s));
39+
}
40+
}
41+
42+
PriorityQueue<WordAndCount> heap = new PriorityQueue<WordAndCount>(wordAndCountMap.values());
43+
for (int i=0; i<k; i++) {
44+
result.add(heap.poll().word);
45+
}
46+
47+
return result;
48+
}
49+
50+
public static void main(String[] args) {
51+
// System.out.println(topKFrequentSort(new String[] {"i", "love", "leetcode", "i", "love", "coding"}, 2));
52+
// System.out.println(topKFrequentHeap(new String[] {"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"}, 2));
53+
54+
String[] array1 = new String[] {"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
55+
String[] array2 = new String[] {"i", "love", "leetcode", "i", "love", "coding"};
56+
{
57+
long start = System.currentTimeMillis();
58+
for (int i=0; i<100000; i++) {
59+
topKFrequentHeap(array1, 4);
60+
topKFrequentHeap(array2, 3);
61+
topKFrequentHeap(array1, 2);
62+
topKFrequentHeap(array2, 2);
63+
}
64+
long end = System.currentTimeMillis();
65+
System.out.println(end-start);
66+
}
67+
{
68+
long start = System.currentTimeMillis();
69+
for (int i=0; i<100000; i++) {
70+
topKFrequentSort(array1, 4);
71+
topKFrequentSort(array2, 3);
72+
topKFrequentSort(array1, 2);
73+
topKFrequentSort(array2, 2);
74+
}
75+
long end = System.currentTimeMillis();
76+
System.out.println(end-start);
77+
}
78+
79+
}
80+
}
81+
82+
class WordAndCount implements Comparable<WordAndCount> {
83+
int count = 1;
84+
String word;
85+
public WordAndCount(String s) {
86+
this.word = s;
87+
}
88+
public void increaseCount() {
89+
this.count ++;
90+
}
91+
@Override
92+
public int compareTo(WordAndCount o) {
93+
if (this.count == o.count) {
94+
return this.word.compareTo(o.word);
95+
}
96+
return this.count < o.count ? 1 : -1; //desend
97+
}
98+
@Override
99+
public boolean equals(Object o) {
100+
if (o == null) return false;
101+
if (o instanceof WordAndCount) {
102+
return ((WordAndCount)o).word.equals(this.word);
103+
}
104+
return false;
105+
}
106+
@Override
107+
public String toString() {
108+
return this.word+":"+this.count;
109+
}
110+
}

‎algorithm/src/main/java/my/algorithm/tree/FullBinaryTree.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package my.algorithm.tree;
2+
3+
/**
4+
* Full Binary Tree means no node has only one child node
5+
*
6+
*/
7+
public class FullBinaryTree {
8+
public static boolean isFull(TreeNode node) {
9+
if (node == null) return false;
10+
return isFull(node.left) == isFull(node.right);
11+
}
12+
13+
public static void main(String[] args) {
14+
TreeNode root = new TreeNode(10);
15+
root.left = new TreeNode(20);
16+
root.right = new TreeNode(30);
17+
root.left.right = new TreeNode(40);
18+
root.left.left = new TreeNode(50);
19+
root.right.left = new TreeNode(60);
20+
root.left.left.left = new TreeNode(80);
21+
root.right.right = new TreeNode(70);
22+
root.left.left.right = new TreeNode(90);
23+
root.left.right.left = new TreeNode(80);
24+
root.left.right.right = new TreeNode(90);
25+
root.right.left.left = new TreeNode(80);
26+
root.right.left.right = new TreeNode(90);
27+
root.right.right.left = new TreeNode(80);
28+
root.right.right.right = new TreeNode(90);
29+
30+
System.out.println(isFull(root));
31+
}
32+
}

‎algorithm/src/main/java/my/algorithm/tree/PreorderTraversalBinarySearchTree.java‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package my.algorithm.tree;
2+
3+
import java.util.Stack;
4+
5+
/**
6+
* http://www.geeksforgeeks.org/check-if-a-given-array-can-represent-preorder-traversal-of-binary-search-tree/
7+
* binary search tree
8+
* 二叉排序树或者是空树，或者是满足如下性质的二叉树：
9+
* 若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
10+
* 若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
11+
* 左、右子树本身又各是一棵二叉排序树。
12+
*
13+
*/
14+
public class PreorderTraversalBinarySearchTree {
15+
16+
public static boolean canRepresentBST(int pre[]) {
17+
int n = pre.length;
18+
// Create an empty stack
19+
Stack<Integer> s = new Stack<Integer>();
20+
21+
// Initialize current root as minimum possible
22+
// value
23+
int root = Integer.MIN_VALUE;
24+
25+
// Traverse given array
26+
for (int i = 0; i < n; i++) {
27+
// If we find a node who is on right side
28+
// and smaller than root, return false
29+
if (pre[i] < root) {
30+
return false;
31+
}
32+
33+
// If pre[i] is in right subtree of stack top,
34+
// Keep removing items smaller than pre[i]
35+
// and make the last removed item as new
36+
// root.
37+
while (!s.empty() && s.peek() < pre[i]) {
38+
root = s.pop();
39+
}
40+
41+
// At this point either stack is empty or
42+
// pre[i] is smaller than root, push pre[i]
43+
s.push(pre[i]);
44+
}
45+
return true;
46+
}
47+
48+
public static void main(String[] args) {
49+
int[] pre1 = new int[]{40, 30, 35, 80, 100};
50+
System.out.println(PreorderTraversalBinarySearchTree.canRepresentBST(pre1));
51+
52+
int[] pre2 = new int[]{40, 30, 35, 20, 80, 100};
53+
System.out.println(PreorderTraversalBinarySearchTree.canRepresentBST(pre2));
54+
}
55+
56+
}

0 commit comments

Comments
 (0)