Skip to content

Commit 3ea9c8c

Browse files
ThanhNITThanhNIT
authored
Added tasks 1022, 1023, 1024, 1025, 1026.
1 parent 642b5ba commit 3ea9c8c

File tree

15 files changed

+498
-0
lines changed

15 files changed

+498
-0
lines changed

‎src/main/java/g1001_1100/s1022_sum_of_root_to_leaf_binary_numbers/Solution.java

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package g1001_1100.s1022_sum_of_root_to_leaf_binary_numbers;
2+
3+
// #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Depth_First_Search #Tree #Binary_Tree
4+
// #2022_02_26_Time_3_ms_(28.58%)_Space_43.6_MB_(5.47%)
5+
6+
import com_github_leetcode.TreeNode;
7+
import java.util.ArrayList;
8+
import java.util.List;
9+
10+
public class Solution {
11+
public int sumRootToLeaf(TreeNode root) {
12+
List<List<Integer>> paths = new ArrayList<>();
13+
dfs(root, paths, new ArrayList<>());
14+
int sum = 0;
15+
for (List<Integer> list : paths) {
16+
int num = 0;
17+
for (int i : list) {
18+
num = (num << 1) + i;
19+
}
20+
sum += num;
21+
}
22+
return sum;
23+
}
24+
25+
private void dfs(TreeNode root, List<List<Integer>> paths, List<Integer> path) {
26+
path.add(root.val);
27+
if (root.left != null) {
28+
dfs(root.left, paths, path);
29+
path.remove(path.size() - 1);
30+
}
31+
if (root.right != null) {
32+
dfs(root.right, paths, path);
33+
path.remove(path.size() - 1);
34+
}
35+
if (root.left == null && root.right == null) {
36+
paths.add(new ArrayList<>(path));
37+
}
38+
}
39+
}

‎src/main/java/g1001_1100/s1022_sum_of_root_to_leaf_binary_numbers/readme.md

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
1022\. Sum of Root To Leaf Binary Numbers
2+
3+
Easy
4+
5+
You are given the `root` of a binary tree where each node has a value `0` or `1`. Each root-to-leaf path represents a binary number starting with the most significant bit.
6+
7+
* For example, if the path is `0 -> 1 -> 1 -> 0 -> 1`, then this could represent `01101` in binary, which is `13`.
8+
9+
For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return _the sum of these numbers_.
10+
11+
The test cases are generated so that the answer fits in a **32-bits** integer.
12+
13+
**Example 1:**
14+
15+
![](https://assets.leetcode.com/uploads/2019/04/04/sum-of-root-to-leaf-binary-numbers.png)
16+
17+
**Input:** root = [1,0,1,0,1,0,1]
18+
19+
**Output:** 22
20+
21+
**Explanation:** (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
22+
23+
**Example 2:**
24+
25+
**Input:** root = [0]
26+
27+
**Output:** 0
28+
29+
**Constraints:**
30+
31+
* The number of nodes in the tree is in the range `[1, 1000]`.
32+
* `Node.val` is `0` or `1`.

‎src/main/java/g1001_1100/s1023_camelcase_matching/Solution.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package g1001_1100.s1023_camelcase_matching;
2+
3+
// #Medium #String #Two_Pointers #Trie #String_Matching
4+
// #2022_02_26_Time_1_ms_(73.86%)_Space_43_MB_(6.82%)
5+
6+
import java.util.LinkedList;
7+
import java.util.List;
8+
9+
public class Solution {
10+
public List<Boolean> camelMatch(String[] queries, String pattern) {
11+
List<Boolean> ret = new LinkedList<>();
12+
for (String query : queries) {
13+
ret.add(check(query, pattern));
14+
}
15+
return ret;
16+
}
17+
18+
private Boolean check(String query, String pattern) {
19+
int patternLen = pattern.length();
20+
int patternPos = 0;
21+
int uppercaseCount = 0;
22+
for (int i = 0; i < query.length(); i++) {
23+
char c = query.charAt(i);
24+
if (Character.isUpperCase(c)) {
25+
if (patternPos < patternLen && c != pattern.charAt(patternPos)) {
26+
return false;
27+
}
28+
uppercaseCount++;
29+
if (uppercaseCount > patternLen) {
30+
return false;
31+
}
32+
patternPos++;
33+
} else {
34+
if (patternPos < patternLen && c == pattern.charAt(patternPos)) {
35+
patternPos++;
36+
}
37+
}
38+
}
39+
40+
return patternPos == patternLen;
41+
}
42+
}

‎src/main/java/g1001_1100/s1023_camelcase_matching/readme.md

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
1023\. Camelcase Matching
2+
3+
Medium
4+
5+
Given an array of strings `queries` and a string `pattern`, return a boolean array `answer` where `answer[i]` is `true` if `queries[i]` matches `pattern`, and `false` otherwise.
6+
7+
A query word `queries[i]` matches `pattern` if you can insert lowercase English letters pattern so that it equals the query. You may insert each character at any position and you may not insert any characters.
8+
9+
**Example 1:**
10+
11+
**Input:** queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
12+
13+
**Output:** [true,false,true,true,false]
14+
15+
**Explanation:** "FooBar" can be generated like this "F" + "oo" + "B" + "ar".
16+
17+
"FootBall" can be generated like this "F" + "oot" + "B" + "all".
18+
19+
"FrameBuffer" can be generated like this "F" + "rame" + "B" + "uffer".
20+
21+
**Example 2:**
22+
23+
**Input:** queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBa"
24+
25+
**Output:** [true,false,true,false,false]
26+
27+
**Explanation:** "FooBar" can be generated like this "Fo" + "o" + "Ba" + "r".
28+
29+
"FootBall" can be generated like this "Fo" + "ot" + "Ba" + "ll".
30+
31+
**Example 3:**
32+
33+
**Input:** queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBaT"
34+
35+
**Output:** [false,true,false,false,false]
36+
37+
**Explanation:** "FooBarTest" can be generated like this "Fo" + "o" + "Ba" + "r" + "T" + "est".
38+
39+
**Constraints:**
40+
41+
* `1 <= pattern.length, queries.length <= 100`
42+
* `1 <= queries[i].length <= 100`
43+
* `queries[i]` and `pattern` consist of English letters.

‎src/main/java/g1001_1100/s1024_video_stitching/Solution.java

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package g1001_1100.s1024_video_stitching;
2+
3+
// #Medium #Array #Dynamic_Programming #Greedy #2022_02_26_Time_1_ms_(88.78%)_Space_42.3_MB_(11.00%)
4+
5+
import java.util.Arrays;
6+
7+
public class Solution {
8+
public int videoStitching(int[][] clips, int time) {
9+
Arrays.sort(clips, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
10+
int count = 0;
11+
int covered = 0;
12+
for (int i = 0, start = 0; start < time; count++, start = covered) {
13+
for (; i < clips.length && clips[i][0] <= start; i++) {
14+
covered = Math.max(covered, clips[i][1]);
15+
}
16+
if (start == covered) {
17+
return -1;
18+
}
19+
}
20+
return count;
21+
}
22+
}

‎src/main/java/g1001_1100/s1024_video_stitching/readme.md

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
1024\. Video Stitching
2+
3+
Medium
4+
5+
You are given a series of video clips from a sporting event that lasted `time` seconds. These video clips can be overlapping with each other and have varying lengths.
6+
7+
Each video clip is described by an array `clips` where <code>clips[i] = [start<sub>i</sub>, end<sub>i</sub>]</code> indicates that the ith clip started at <code>start<sub>i</sub></code> and ended at <code>end<sub>i</sub></code>.
8+
9+
We can cut these clips into segments freely.
10+
11+
* For example, a clip `[0, 7]` can be cut into segments `[0, 1] + [1, 3] + [3, 7]`.
12+
13+
Return _the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event_ `[0, time]`. If the task is impossible, return `-1`.
14+
15+
**Example 1:**
16+
17+
**Input:** clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
18+
19+
**Output:** 3
20+
21+
**Explanation:** We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
22+
23+
Then, we can reconstruct the sporting event as follows:
24+
25+
We cut [1,9] into segments [1,2] + [2,8] + [8,9].
26+
27+
Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].
28+
29+
**Example 2:**
30+
31+
**Input:** clips = [[0,1],[1,2]], time = 5
32+
33+
**Output:** -1
34+
35+
**Explanation:** We cannot cover [0,5] with only [0,1] and [1,2].
36+
37+
**Example 3:**
38+
39+
**Input:** clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], time = 9
40+
41+
**Output:** 3
42+
43+
**Explanation:** We can take clips [0,4], [4,7], and [6,9].
44+
45+
**Constraints:**
46+
47+
* `1 <= clips.length <= 100`
48+
* <code>0 <= start<sub>i</sub> <= end<sub>i</sub> <= 100</code>
49+
* `1 <= time <= 100`

‎src/main/java/g1001_1100/s1025_divisor_game/Solution.java

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
package g1001_1100.s1025_divisor_game;
2+
3+
// #Easy #Dynamic_Programming #Math #Game_Theory #Brainteaser
4+
// #2022_02_26_Time_0_ms_(100.00%)_Space_40.7_MB_(27.10%)
5+
6+
public class Solution {
7+
public boolean divisorGame(int n) {
8+
return n % 2 == 0;
9+
}
10+
}

‎src/main/java/g1001_1100/s1025_divisor_game/readme.md

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
1025\. Divisor Game
2+
3+
Easy
4+
5+
Alice and Bob take turns playing a game, with Alice starting first.
6+
7+
Initially, there is a number `n` on the chalkboard. On each player's turn, that player makes a move consisting of:
8+
9+
* Choosing any `x` with `0 < x < n` and `n % x == 0`.
10+
* Replacing the number `n` on the chalkboard with `n - x`.
11+
12+
Also, if a player cannot make a move, they lose the game.
13+
14+
Return `true` _if and only if Alice wins the game, assuming both players play optimally_.
15+
16+
**Example 1:**
17+
18+
**Input:** n = 2
19+
20+
**Output:** true
21+
22+
**Explanation:** Alice chooses 1, and Bob has no more moves.
23+
24+
**Example 2:**
25+
26+
**Input:** n = 3
27+
28+
**Output:** false
29+
30+
**Explanation:** Alice chooses 1, Bob chooses 1, and Alice has no more moves.
31+
32+
**Constraints:**
33+
34+
* `1 <= n <= 1000`

‎src/main/java/g1001_1100/s1026_maximum_difference_between_node_and_ancestor/Solution.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package g1001_1100.s1026_maximum_difference_between_node_and_ancestor;
2+
3+
// #Medium #Depth_First_Search #Tree #Binary_Tree
4+
// #2022_02_26_Time_1_ms_(65.84%)_Space_42.6_MB_(6.52%)
5+
6+
import com_github_leetcode.TreeNode;
7+
8+
public class Solution {
9+
private int max = 0;
10+
11+
public int maxAncestorDiff(TreeNode root) {
12+
traverse(root, -1, -1);
13+
return max;
14+
}
15+
16+
private void traverse(TreeNode root, int maxAncestor, int minAncestor) {
17+
if (root == null) {
18+
return;
19+
}
20+
21+
if (maxAncestor == -1) {
22+
traverse(root.left, root.val, root.val);
23+
traverse(root.right, root.val, root.val);
24+
}
25+
26+
if (maxAncestor != -1) {
27+
max = Math.max(max, Math.abs(maxAncestor - root.val));
28+
max = Math.max(max, Math.abs(minAncestor - root.val));
29+
30+
traverse(root.left, Math.max(root.val, maxAncestor), Math.min(root.val, minAncestor));
31+
traverse(root.right, Math.max(root.val, maxAncestor), Math.min(root.val, minAncestor));
32+
}
33+
}
34+
}

‎src/main/java/g1001_1100/s1026_maximum_difference_between_node_and_ancestor/readme.md

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
1026\. Maximum Difference Between Node and Ancestor
2+
3+
Medium
4+
5+
Given the `root` of a binary tree, find the maximum value `v` for which there exist **different** nodes `a` and `b` where `v = |a.val - b.val|` and `a` is an ancestor of `b`.
6+
7+
A node `a` is an ancestor of `b` if either: any child of `a` is equal to `b` or any child of `a` is an ancestor of `b`.
8+
9+
**Example 1:**
10+
11+
![](https://assets.leetcode.com/uploads/2020/11/09/tmp-tree.jpg)
12+
13+
**Input:** root = [8,3,10,1,6,null,14,null,null,4,7,13]
14+
15+
**Output:** 7
16+
17+
**Explanation:** We have various ancestor-node differences, some of which are given below :
18+
19+
|8 - 3| = 5
20+
|3 - 7| = 4
21+
|8 - 1| = 7
22+
|10 - 13| = 3
23+
24+
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.
25+
26+
**Example 2:**
27+
28+
![](https://assets.leetcode.com/uploads/2020/11/09/tmp-tree-1.jpg)
29+
30+
**Input:** root = [1,null,2,null,0,3]
31+
32+
**Output:** 3
33+
34+
**Constraints:**
35+
36+
* The number of nodes in the tree is in the range `[2, 5000]`.
37+
* <code>0 <= Node.val <= 10<sup>5</sup></code>

‎src/test/java/g1001_1100/s1022_sum_of_root_to_leaf_binary_numbers/SolutionTest.java

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package g1001_1100.s1022_sum_of_root_to_leaf_binary_numbers;
2+
3+
import static org.hamcrest.CoreMatchers.equalTo;
4+
import static org.hamcrest.MatcherAssert.assertThat;
5+
6+
import com_github_leetcode.TreeNode;
7+
import java.util.Arrays;
8+
import java.util.Collections;
9+
import org.junit.jupiter.api.Test;
10+
11+
class SolutionTest {
12+
@Test
13+
void sumRootToLeaf() {
14+
TreeNode root = TreeNode.create(Arrays.asList(1, 0, 1, 0, 1, 0, 1));
15+
assertThat(new Solution().sumRootToLeaf(root), equalTo(22));
16+
}
17+
18+
@Test
19+
void sumRootToLeaf2() {
20+
TreeNode root = TreeNode.create(Collections.singletonList(0));
21+
assertThat(new Solution().sumRootToLeaf(root), equalTo(0));
22+
}
23+
}

0 commit comments

Comments
 (0)