Skip to content

Commit 34c47cc

Browse files
author
Tianye
committed
add week2
1 parent f5bd7e4 commit 34c47cc

8 files changed

Lines changed: 224 additions & 0 deletions

‎Week02/BinaryTreeInorderTraversal.java‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* public class TreeNode {
4+
* int val;
5+
* TreeNode left;
6+
* TreeNode right;
7+
* TreeNode(int x) { val = x; }
8+
* }
9+
*/
10+
class BinaryTreeInorderTraversal {
11+
public List<Integer> inorderTraversal(TreeNode root) {
12+
List<Integer> res = new ArrayList<>();
13+
if(root == null){
14+
return res;
15+
}
16+
17+
List<Integer> leftResList = inorderTraversal(root.left);
18+
List<Integer> rightResList = inorderTraversal(root.right);
19+
res.addAll(leftResList);
20+
res.add(root.val);
21+
res.addAll(rightResList);
22+
return res;
23+
}
24+
}

‎Week02/BinaryTreePreorderTraversal.java‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* public class TreeNode {
4+
* int val;
5+
* TreeNode left;
6+
* TreeNode right;
7+
* TreeNode(int x) { val = x; }
8+
* }
9+
*/
10+
class Solution {
11+
public List<Integer> preorderTraversal(TreeNode root) {
12+
List<Integer> res = new ArrayList<>();
13+
if(root == null){
14+
return res;
15+
}
16+
17+
List<Integer> leftResList = preorderTraversal(root.left);
18+
List<Integer> rightResList = preorderTraversal(root.right);
19+
res.add(root.val);
20+
res.addAll(leftResList);
21+
res.addAll(rightResList);
22+
return res;
23+
}
24+
}

‎Week02/GroupAnagrams.java‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
class GroupAnagrams {
2+
public List<List<String>> groupAnagrams(String[] strs) {
3+
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
4+
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
5+
73, 79, 83, 89, 97, 101};
6+
7+
HashMap<Integer, List<String>> map = new HashMap<>();
8+
for(String str: strs){
9+
int hashValue = 1;
10+
char[] chars = str.toCharArray();
11+
for(char c: chars){
12+
hashValue *= primes[c - 'a'];
13+
}
14+
if (map.containsKey(hashValue)){
15+
map.get(hashValue).add(str);
16+
}else{
17+
List<String> newStrList = new ArrayList<>();
18+
newStrList.add(str);
19+
map.put(hashValue, newStrList);
20+
}
21+
}
22+
return new ArrayList<>( map.values());
23+
24+
}
25+
}

‎Week02/NAryTreeLevelOrderTraversal.java‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
/*
2+
// Definition for a Node.
3+
class Node {
4+
public int val;
5+
public List<Node> children;
6+
7+
public Node() {}
8+
9+
public Node(int _val) {
10+
val = _val;
11+
}
12+
13+
public Node(int _val, List<Node> _children) {
14+
val = _val;
15+
children = _children;
16+
}
17+
};
18+
*/
19+
20+
class NAryTreeLevelOrderTraversal {
21+
public List<List<Integer>> levelOrder(Node root) {
22+
List<List<Integer>> res = new ArrayList<>();
23+
if (root == null){
24+
return res;
25+
}
26+
27+
withDepth(root,0, res);
28+
return res;
29+
}
30+
31+
public void withDepth(Node root, int depth, List<List<Integer>> res){
32+
if(depth+ 1 >res.size()){
33+
List<Integer> levelList = new ArrayList<>();
34+
res.add(levelList);
35+
}
36+
37+
res.get(depth).add(root.val);
38+
for(Node node: root.children){
39+
withDepth(node, depth + 1, res);
40+
}
41+
42+
43+
}
44+
}

‎Week02/NAryTreePreorderTraversal.java‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
2+
// Definition for a Node.
3+
/*class Node {
4+
public int val;
5+
public List<Node> children;
6+
7+
public Node() {}
8+
9+
public Node(int _val) {
10+
val = _val;
11+
}
12+
13+
public Node(int _val, List<Node> _children) {
14+
val = _val;
15+
children = _children;
16+
}
17+
};
18+
*/
19+
20+
21+
class NAryTreePreorderTraversal {
22+
List<Integer> res = new ArrayList<>();
23+
24+
public List<Integer> preorder(Node root) {
25+
26+
if(root != null){
27+
res.add(root.val);
28+
}else{
29+
return res;
30+
}
31+
List<Node> children = root.children;
32+
33+
if(children.size() > 0){
34+
for (Node n: children){
35+
preorder(n);
36+
}
37+
}
38+
return res;
39+
}
40+
}

‎Week02/TopkFrequentElements.java‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
class TopkFrequentElements {
2+
public int[] topKFrequent(int[] nums, int k) {
3+
4+
HashMap<Integer, Integer> frequencyMap = new HashMap<>();
5+
for(int i =0 ;i < nums.length; i++){
6+
frequencyMap.put(nums[i],frequencyMap.getOrDefault(nums[i],0)+1);
7+
}
8+
9+
10+
Queue<Integer> heap = new PriorityQueue<>(
11+
((o1, o2) -> frequencyMap.get(o1) -frequencyMap.get(o2))
12+
);
13+
14+
for(int num : frequencyMap.keySet()){
15+
heap.add(num);
16+
if(heap.size() > k) heap.poll();
17+
}
18+
int [] result = new int[heap.size()];
19+
for (int i = 0; i < result.length; i++) {
20+
result[i] = heap.poll();
21+
}
22+
return result;
23+
24+
}
25+
}

‎Week02/TwoSum.java‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
class TwoSum {
2+
public int[] twoSum(int[] nums, int target) {
3+
HashMap<Integer, Integer> cache = new HashMap<>();
4+
int[] res = new int[2];
5+
for(int i = 0; i < nums.length; i++) {
6+
int secondValue = target - nums[i];
7+
Integer secondIndex = cache.get(secondValue);
8+
if (secondIndex != null && secondIndex >= 0 && secondIndex != i ){
9+
if (secondIndex > i ){
10+
res[0] = i;
11+
res[1] = secondIndex;
12+
}else{
13+
res[0] = secondIndex;
14+
res[1] = i;
15+
}
16+
17+
return res;
18+
}
19+
cache.put(nums[i], i);
20+
}
21+
return res;
22+
}
23+
}

‎Week02/ValidAnagram.java‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
class ValidAnagram {
2+
public boolean isAnagram(String s, String t) {
3+
if(s.length() != t.length()){
4+
return false;
5+
}
6+
int[] map = new int[26];
7+
for(int i =0; i < s.length(); i++){
8+
map[s.charAt(i) -'a'] += 1;
9+
map[t.charAt(i) -'a'] -= 1;
10+
}
11+
for(int v : map){
12+
if(v!= 0){
13+
return false;
14+
}
15+
}
16+
17+
return true;
18+
}
19+
}

0 commit comments

Comments
 (0)