8000 20200911 · BoscoSuen/leetcode@55f7baf · GitHub
[go: up one dir, main page]
Skip to content

Commit 55f7baf

Browse files
BoscoSuenBoscoSuen
committed
20200911
1 parent b71081b commit 55f7baf

File tree

5 files changed

+151
-0
lines changed

5 files changed

+151
-0
lines changed

‎Java/1022.sum-of-root-to-leaf-binary-numbers.java

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
/*
2+
* @lc app=leetcode id=1022 lang=java
3+
*
4+
* [1022] Sum of Root To Leaf Binary Numbers
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* Definition for a binary tree node.
10+
* public class TreeNode {
11+
* int val;
12+
* TreeNode left;
13+
* TreeNode right;
14+
* TreeNode() {}
15+
* TreeNode(int val) { this.val = val; }
16+
* TreeNode(int val, TreeNode left, TreeNode right) {
17+
* this.val = val;
18+
* this.left = left;
19+
* this.right = right;
20+
* }
21+
* }
22+
*/
23+
class Solution {
24+
public int sumRootToLeaf(TreeNode root) {
25+
return dfs(root, 0);
26+
}
27+
28+
private int dfs(TreeNode root, int sum) {
29+
if (root == null) return 0;
30+
sum = (sum << 1) + root.val;
31+
if (root.left == null && root.right == null) return sum;
32+
return dfs(root.left, sum) + dfs(root.right, sum);
33+
}
34+
}
35+
// @lc code=end
36+

‎Java/165.compare-version-numbers.java

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
/*
2+
* @lc app=leetcode id=165 lang=java
3+
*
4+
* [165] Compare Version Numbers
5+
*/
6+
7+
// @lc code=start
8+
class Solution {
9+
/*
10+
"." 和"|"都是转义字符，需要加\\才能分割
11+
time:O(n)
12+
space: O(n)
13+
*/
14+
public int compareVersion(String version1, String version2) {
15+
< 8000 span class=pl-smi>String[] v1 = version1.split("\\.");
16+
String[] v2 = version2.split("\\.");
17+
int i = 0, j = 0;
18+
while (i < v1.length || j < v2.length) {
19+
int num1 = i < v1.length ? Integer.parseInt(v1[i]) : 0;
20+
int num2 = j < v2.length ? Integer.parseInt(v2[j]) : 0;
21+
if (num1 != num2) {
22+
return num1 < num2 ? -1 : 1;
23+
}
24+
i++;
25+
j++;
26+
}
27+
return 0;
28+
}
29+
}
30+
// @lc code=end
31+

‎Java/204.count-primes.java

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
/*
2+
* @lc app=leetcode id=204 lang=java
3+
*
4+
* [204] Count Primes
5+
*/
6+
7+
// @lc code=start
8+
class Solution {
9+
/*
10+
O(n) * O(1/2 + 1/3 + 1/5 + ... + 1/(last prime before n))
11+
= O(n) * O(log(log(n)))
12+
= O(nlog(log(n)))
13+
*/
14+
public int countPrimes(int n) {
15+
int count = 0;
16+
boolean[] notPrime = new boolean[n + 1];
17+
for (int i = 2; i < n; ++i) {
18+
if (!notPrime[i]) {
19+
count++;
20+
for (int j = 2; i * j <= n; ++j) {
21+
notPrime[i * j] = true;
22+
}
23+
}
24+
}
25+
return count;
26+
}
27+
}
28+
// @lc code=end
29+

‎Java/310.minimum-height-trees.java

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
/*
2+
* @lc app=leetcode id=310 lang=java
3+
*
4+
* [310] Minimum Height Trees
5+
*/
6+
7+
// @lc code=start
8+
class Solution {
9+
/*
10+
类似剥洋葱的方法，就是一层一层的褪去叶节点，最后剩下的一个或两个节点就是我们要求的最小高度树的根节点，
11+
这种思路非常的巧妙，而且实现起来也不难，跟之前那到课程清单的题一样，我们需要建立一个图g，
12+
是一个二维数组，其中g[i]是一个一维数组，保存了i节点可以到达的所有节点。我们开始将所有只有一个
13+
连接边的节点(叶节点)都存入到一个队列queue中，然后我们遍历每一个叶节点，通过图来找到和其相连的节点，
14+
并且在其相连节点的集合中将该叶节点删去，如果删完后此节点也也变成一个叶节点了，加入队列中，再下一轮删除。
15+
那么我们删到什么时候呢，当节点数小于等于2时候停止，此时剩下的一个或两个节点就是我们要求的最小高度树的根节点
16+
time: O(n) V= n E = n + 1
17+
space: O(n)
18+
*/
19+
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
20+
List<Integer> res = new ArrayList<>();
21+
if (n == 1) {
22+
res.add(0);
23+
return res;
24+
}
25+
Map<Integer, Set<Integer>> graph = new HashMap<>();
26+
for (int[] edge : edges) {
27+
graph.putIfAbsent(edge[0], new HashSet<>());
28+
graph.putIfAbsent(edge[1], new HashSet<>());
29+
graph.get(edge[0]).add(edge[1]);
30+
graph.get(edge[1]).add(edge[0]);
31+
}
32+
Queue<Integer> q = new LinkedList<>();
33+
for (int i = 0; i < n; ++i) {
34+
if (graph.get(i).size() == 1) q.offer(i);
35+
}
36+
while (n > 2) {
37+
int size = q.size();
38+
n -= size;
39+
for (int i = 0; i < size; ++i) {
40+
int cur = q.poll();
41+
for (int next : graph.get(cur)) {
42+
graph.get(next).remove(cur);
43+
if (graph.get(next).size() == 1) q.offer(next);
44+
}
45+
}
46+
}
47+
while (!q.isEmpty()) {
48+
res.add(q.poll());
49+
}
50+
return res;
51+
}
52+
}
53+
// @lc code=end
54+

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -134,6 +134,7 @@
134134
[90.subsets II](https://leetcode.com/problems/subsets-ii/) | [subset去重](https://github.com/Yukinichi/leetcode/blob/master/Java/90.subsets-ii.java)
135135
[127. Word Ladder](https://leetcode.com/problems/word-ladder/) | [双向BFS](https://github.com/Yukinichi/leetcode/blob/master/Java/127.word-ladder.java)
136136
[126. Word Ladder II](https://leetcode.com/problems/word-ladder-ii/) | [双向BFS + DFS + path建图(Java)](https://github.com/Yukinichi/leetcode/blob/master/Java/126.word-ladder-ii.java) \| [单向BFS(C++)](https://github.com/Yukinichi/leetcode/blob/master/Cpp/126.word-ladder-ii.cpp)
137+
[310. Minimum Height Trees](https://leetcode.com/problems/minimum-height-trees/) | [建图+BFS](https://github.com/Yukinichi/leetcode/blob/master/Java/310.minimum-height-trees.java)
137138
[140. Word Break II](https://leetcode.com/problems/word-break-ii/) | [DFS + memo](https://github.com/Yukinichi/leetcode/blob/master/Java/140.word-break-ii.java)
138139
[329. Longest Increasing Path in a Matrix](https://leetcode.com/problems/longest-increasing-path-in-a-matrix/) | [DFS + memo](https://github.com/Yukinichi/leetcode/blob/master/Java/329.longest-increasing-path-in-a-matrix.java)
139140
[472. Concatenated Words](https://leetcode.com/problems/concatenated-words/) | [DFS + memo Solution(C++)](https://github.com/Yukinichi/leetcode/blob/master/Cpp/472.concatenated-words.cpp) \| [Trie Solution(Java)](https://github.com/Yukinichi/leetcode/blob/master/Java/472.concatenated-words.java)

0 commit comments

Comments
 (0)
0