Skip to content

Commit aa6fb8f

Browse files
GeekUniversityGeekUniversity
authored
Merge pull request algorithm001#382 from Fanlu91/master
Merge Week 2 Homework （Id 26）
2 parents a5b5c5f + a81696d commit aa6fb8f

7 files changed

Lines changed: 709 additions & 0 deletions

File tree

‎Week_01/id_26/TreeNode.java‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
package com.fanlu.leetcode.binarytree;
2+
3+
public class TreeNode {
4+
int val;
5+
TreeNode left;
6+
TreeNode right;
7+
8+
TreeNode(int x) {
9+
val = x;
10+
}
11+
}

‎Week_02/id_26/Leetcode_236_26.java‎

Lines changed: 190 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,190 @@
1+
package com.fanlu.leetcode.binarytree;
2+
// Source : https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
3+
// Id : 236
4+
// Author : Fanlu Hai
5+
// Date : 2018-04-24
6+
// Other : lowest common ancestor (LCA): The lowest common ancestor is defined between two nodes p and q
7+
// as the lowest node in T that has both p and q as descendants
8+
// (where we allow a node to be a descendant of itself).
9+
// Tips :
10+
11+
import java.util.LinkedList;
12+
import java.util.Queue;
13+
14+
/**
15+
* Definition for a binary tree node.
16+
* public class TreeNode {
17+
* int val;
18+
* TreeNode left;
19+
* TreeNode right;
20+
* TreeNode(int x) { val = x; }
21+
* }
22+
*/
23+
24+
public class LowestCommonAncestorOfABinaryTree {
25+
26+
private TreeNode ans;
27+
28+
// This answer is copied from leetcode submission analysis sample
29+
// 100.00% (20% faster than original) 44.21%
30+
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
31+
32+
this.recurse(root, p, q);
33+
return this.ans;
34+
}
35+
36+
private boolean recurse(TreeNode node, TreeNode p, TreeNode q) {
37+
38+
if (node == null) {
39+
return false;
40+
}
41+
42+
// rec left
43+
// it's very hard for me to write below code even though it's nothing hard.
44+
int left = this.recurse(node.left, p, q) ? 1 : 0;
45+
int right = this.recurse(node.right, p, q) ? 1 : 0;
46+
47+
int mid = (node == p) || (node == q) ? 1 : 0;
48+
49+
// this is better than comparing objects
50+
if (mid + left + right >= 2) {
51+
this.ans = node;
52+
}
53+
return (mid + left + right > 0);
54+
55+
}
56+
57+
58+
//65.83% 40.60%
59+
// this is fast enough to my understanding, but there are more elegant and faster ways to do the same steps
60+
public TreeNode lowestCommonAncestorOriginal(TreeNode root, TreeNode p, TreeNode q) {
61+
62+
if (null == root || root == p || root == q)
63+
return root;
64+
TreeNode left = lowestCommonAncestorOriginal(root.left, p, q);
65+
TreeNode right = lowestCommonAncestorOriginal(root.right, p, q);
66+
67+
if (null != left && null != right) {
68+
return root;
69+
} else if (null == right) {
70+
return left;
71+
} else {
72+
// null == left
73+
return right;
74+
}
75+
//return left == null ? right : right == null ? left : root;
76+
}
77+
78+
/**
79+
* below are some no very successfull attampts
80+
*/
81+
Queue<TreeNode> pNodeList = new LinkedList<>();
82+
Queue<TreeNode> qNodeList = new LinkedList<>();
83+
84+
//! Time Limit Exceeded
85+
public TreeNode lowestCommonAncestorTooSlow(TreeNode root, TreeNode p, TreeNode q) {
86+
TreeNode result = root;
87+
dfsNode(root, p, q, new LinkedList<TreeNode>());
88+
while (!pNodeList.isEmpty()) {
89+
TreeNode tmp = pNodeList.poll();
90+
// System.out.println(tmp);
91+
if (tmp != qNodeList.poll()) {
92+
break;
93+
}
94+
result = tmp;
95+
}
96+
return result;
97+
}
98+
99+
public void dfsNode(TreeNode treeNode, TreeNode p, TreeNode q, Queue<TreeNode> queue) {
100+
if (null == treeNode)
101+
return;
102+
103+
Queue<TreeNode> tmpQueue = new LinkedList<>();
104+
tmpQueue.addAll(queue);
105+
106+
tmpQueue.add(treeNode);
107+
if (treeNode.val == p.val) {
108+
pNodeList = tmpQueue;
109+
}
110+
111+
if (treeNode.val == q.val) {
112+
qNodeList = tmpQueue;
113+
}
114+
115+
dfsNode(treeNode.left, p, q, tmpQueue);
116+
dfsNode(treeNode.right, p, q, tmpQueue);
117+
}
118+
119+
120+
Queue<Integer> pList = new LinkedList<>();
121+
Queue<Integer> qList = new LinkedList<>();
122+
123+
124+
// implemented the int version
125+
public int lowestCommonAncestorReturnInt(TreeNode root, TreeNode p, TreeNode q) {
126+
int result = root.val;
127+
dfsValue(root, p.val, q.val, new LinkedList<Integer>());
128+
while (!pList.isEmpty()) {
129+
int tmp = pList.poll();
130+
// System.out.println(tmp);
131+
if (tmp != qList.poll()) {
132+
break;
133+
}
134+
result = tmp;
135+
}
136+
return result;
137+
}
138+
139+
public void dfsValue(TreeNode treeNode, int p, int q, Queue<Integer> queue) {
140+
if (null == treeNode)
141+
return;
142+
143+
Queue<Integer> tmpQueue = new LinkedList<>();
144+
tmpQueue.addAll(queue);
145+
146+
tmpQueue.add(treeNode.val);
147+
if (treeNode.val == p) {
148+
pList = tmpQueue;
149+
}
150+
151+
if (treeNode.val == q) {
152+
qList = tmpQueue;
153+
}
154+
155+
dfsValue(treeNode.left, p, q, tmpQueue);
156+
dfsValue(treeNode.right, p, q, tmpQueue);
157+
}
158+
159+
public static void main(String[] args) {
160+
TreeNode treeNode1 = new TreeNode(1);
161+
TreeNode treeNode2 = new TreeNode(2);
162+
TreeNode treeNode3 = new TreeNode(3);
163+
TreeNode treeNode4 = new TreeNode(4);
164+
TreeNode treeNode5 = new TreeNode(5);
165+
TreeNode treeNode6 = new TreeNode(6);
166+
TreeNode treeNode7 = new TreeNode(7);
167+
168+
treeNode1.left = treeNode2;
169+
treeNode2.left = treeNode4;
170+
treeNode2.right = treeNode5;
171+
treeNode5.right = treeNode3;
172+
treeNode3.left = treeNode6;
173+
treeNode3.right = treeNode7;
174+
175+
LowestCommonAncestorOfABinaryTree lowestCommonAncestorOfABinaryTree = new LowestCommonAncestorOfABinaryTree();
176+
lowestCommonAncestorOfABinaryTree.dfsValue(treeNode1, 7, 6, new LinkedList<Integer>());
177+
178+
for (int i : lowestCommonAncestorOfABinaryTree.pList) {
179+
System.out.print(i + "*");
180+
}
181+
System.out.println();
182+
for (int i : lowestCommonAncestorOfABinaryTree.qList) {
183+
System.out.print(i + "-");
184+
}
185+
System.out.println();
186+
187+
System.out.println("result: " + lowestCommonAncestorOfABinaryTree.lowestCommonAncestorReturnInt(treeNode1, treeNode7, treeNode6));
188+
}
189+
190+
}

‎Week_02/id_26/Leetcode_242_26.java‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
package com.fanlu.leetcode.hashtable;
2+
// Source : https://leetcode.com/problems/valid-anagram/
3+
// Id : 242
4+
// Author : Fanlu Hai
5+
// Date : 2018-04-22
6+
// Other : anagram noun. a word, phrase, or name formed by rearranging the letters of another, such as cinema, formed from iceman.
7+
// Tips : 1.Use int[] with ascii as hash table; 2.use 'for i certain numbers' instead of 'for reach'.
8+
9+
public class ValidAnagram {
10+
11+
//38.34% 70.24%
12+
public boolean isAnagramSlow(String s, String t) {
13+
if (null == s || null == t)
14+
return false;
15+
if (s.length() != t.length())
16+
return false;
17+
18+
int[] letters = new int[26];
19+
for (int i = 0; i < s.length(); i++) {
20+
int tmpS = s.charAt(i) - 'a';
21+
int tmpT = t.charAt(i) - 'a';
22+
letters[tmpS]++;
23+
letters[tmpT]--;
24+
}
25+
26+
for (int i = 0; i < 26; i++) {
27+
if (letters[i] != 0)
28+
return false;
29+
}
30+
return true;
31+
}
32+
33+
// try to remove tmp variables to see if it runs faster
34+
// And it does
35+
// 72.38% 70.94%
36+
public boolean isAnagramFast(String s, String t) {
37+
if (null == s || null == t)
38+
return false;
39+
if (s.length() != t.length())
40+
return false;
41+
42+
int[] letters = new int[26];
43+
for (int i = 0; i < s.length(); i++) {
44+
letters[s.charAt(i) - 'a']++;
45+
letters[t.charAt(i) - 'a']--;
46+
}
47+
48+
for (int i : letters) {
49+
if (letters[i] != 0)
50+
return false;
51+
}
52+
return true;
53+
}
54+
55+
56+
// try to remove tmp variables to see if it runs faster
57+
// And it does
58+
// use for i instead of for reach, it becomes even faster
59+
// 90.46% 71.14%
60+
public boolean isAnagram(String s, String t) {
61+
if (null == s || null == t)
62+
return false;
63+
if (s.length() != t.length())
64+
return false;
65+
66+
int[] letters = new int[26];
67+
for (int i = 0; i < s.length(); i++) {
68+
letters[s.charAt(i) - 'a']++;
69+
letters[t.charAt(i) - 'a']--;
70+
}
71+
72+
for (int i = 0; i < 26; i++) {
73+
if (letters[i] != 0)
74+
return false;
75+
}
76+
return true;
77+
}
78+
79+
80+
public static void main(String[] args) {
81+
ValidAnagram validAnagram = new ValidAnagram();
82+
System.out.println(validAnagram.isAnagram("abcdefg", "abcdefg"));
83+
System.out.println(validAnagram.isAnagram("abcdefg", "abcdefgg"));
84+
System.out.println(validAnagram.isAnagram("abcdefg", "gbcdefa"));
85+
System.out.println(validAnagram.isAnagram("aaaaaaa", "aaaaaba"));
86+
System.out.println(validAnagram.isAnagram(null, null));
87+
}
88+
}

‎Week_02/id_26/Leetcode_609_26.java‎

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
package com.fanlu.leetcode.hashtable;
2+
// Source : https://leetcode.com/problems/find-duplicate-file-in-system/
3+
// Id : 609
4+
// Author : Fanlu Hai
5+
// Date : 2018-04-23
6+
// Other :
7+
// Tips :
8+
9+
import java.util.*;
10+
11+
/**
12+
* Input:
13+
* ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"]
14+
* Output:
15+
* [["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]
16+
*/
17+
18+
public class FindDuplicateFileInSystem {
19+
Map<String, ArrayList<String>> map = new HashMap<>();
20+
21+
//75.63% 20.59%
22+
public List<List<String>> findDuplicateOriginal(String[] paths) {
23+
for (String s : paths) {
24+
getContentMapFromPath(s);
25+
}
26+
//! below codes cause concurrent modification exception, use iterator instead
27+
// for(String key : map.keySet()){
28+
// if (map.get(key).size()==1)
29+
// map.remove(key);
30+
// }
31+
Iterator<Map.Entry<String, ArrayList<String>>> iterator = map.entrySet().iterator();
32+
while (iterator.hasNext()) {
33+
Map.Entry<String, ArrayList<String>> entry = iterator.next();
34+
if (entry.getValue().size() == 1) {
35+
iterator.remove();
36+
}
37+
}
38+
return new ArrayList<List<String>>(map.values());
39+
}
40+
41+
public void getContentMapFromPath(String path) {
42+
String[] tmp = path.split(" ");
43+
String prefix = tmp[0] + "/";
44+
for (int i = 1; i < tmp.length; i++) {
45+
String[] foo = tmp[i].split("\\(");
46+
// use content value as key, an arrayList of paths as value.
47+
String key = foo[1].substring(0, foo[1].length() - 1);
48+
ArrayList<String> value = map.getOrDefault(key, new ArrayList<String>());
49+
value.add(prefix + foo[0]);
50+
map.put(key, value);
51+
}
52+
}
53+
54+
55+
//63.86% 76.47%
56+
public List<List<String>> findDuplicate(String[] paths) {
57+
Map<String, Set<String>> map = new HashMap<>();
58+
59+
for (String path : paths) {
60+
String[] tmp = path.split(" ");
61+
62+
for (int i = 1; i < tmp.length; i++) {
63+
String[] foo = tmp[i].split("\\(");
64+
// use content value as key, an arrayList of paths as value.
65+
String key = foo[1].substring(0, foo[1].length() - 1);
66+
Set<String> value = map.getOrDefault(key, new HashSet<String>());
67+
value.add(tmp[0] + "/" + foo[0]);
68+
map.put(key, value);
69+
}
70+
}
71+
72+
List<List<String>> result = new ArrayList<List<String>>();
73+
for (Set<String> list : map.values()) {
74+
if (list.size() != 1)
75+
result.add(new ArrayList<>(list));
76+
}
77+
78+
return result;
79+
}
80+
}

0 commit comments

Comments
 (0)