Skip to content

Commit 300c545

Browse files
ThanhNITThanhNIT
authored
Added tasks 1027, 1028, 1029, 1030.
1 parent 8e252bf commit 300c545

File tree

12 files changed

+449
-0
lines changed

12 files changed

+449
-0
lines changed

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

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package g1001_1100.s1027_longest_arithmetic_subsequence;
2+
3+
// #Medium #Array #Hash_Table #Dynamic_Programming #Binary_Search
4+
// #2022_02_26_Time_47_ms_(98.28%)_Space_50.8_MB_(93.45%)
5+
6+
import java.util.Arrays;
7+
8+
public class Solution {
9+
public int longestArithSeqLength(int[] nums) {
10+
int max = maxElement(nums);
11+
int min = minElement(nums);
12+
int diff = max - min;
13+
int n = nums.length;
14+
int[][] dp = new int[n][2 * diff + 2];
15+
for (int[] d : dp) {
16+
Arrays.fill(d, 1);
17+
}
18+
19+
int ans = 0;
20+
for (int i = 0; i < n; i++) {
21+
for (int j = i - 1; j >= 0; j--) {
22+
int difference = nums[i] - nums[j] + diff;
23+
int temp = dp[j][difference];
24+
dp[i][difference] = Math.max(dp[i][difference], temp + 1);
25+
if (ans < dp[i][difference]) {
26+
ans = dp[i][difference];
27+
}
28+
}
29+
}
30+
31+
return ans;
32+
}
33+
34+
public int maxElement(int[] arr) {
35+
int max = Integer.MIN_VALUE;
36+
for (Integer e : arr) {
37+
if (max < e) {
38+
max = e;
39+
}
40+
}
41+
42+
return max;
43+
}
44+
45+
public int minElement(int[] arr) {
46+
int min = Integer.MAX_VALUE;
47+
for (Integer e : arr) {
48+
if (min > e) {
49+
min = e;
50+
}
51+
}
52+
53+
return min;
54+
}
55+
}

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

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
1027\. Longest Arithmetic Subsequence
2+
3+
Medium
4+
5+
Given an array `nums` of integers, return the **length** of the longest arithmetic subsequence in `nums`.
6+
7+
Recall that a _subsequence_ of an array `nums` is a list <code>nums[i<sub>1</sub>], nums[i<sub>2</sub>], ..., nums[i<sub>k</sub>]</code> with <code>0 <= i<sub>1</sub> < i<sub>2</sub> < ... < i<sub>k</sub> <= nums.length - 1</code>, and that a sequence `seq` is _arithmetic_ if `seq[i+1] - seq[i]` are all the same value (for `0 <= i < seq.length - 1`).
8+
9+
**Example 1:**
10+
11+
**Input:** nums = [3,6,9,12]
12+
13+
**Output:** 4
14+
15+
**Explanation:** The whole array is an arithmetic sequence with steps of length = 3.
16+
17+
**Example 2:**
18+
19+
**Input:** nums = [9,4,7,2,10]
20+
21+
**Output:** 3
22+
23+
**Explanation:** The longest arithmetic subsequence is [4,7,10].
24+
25+
**Example 3:**
26+
27+
**Input:** nums = [20,1,15,3,10,5,8]
28+
29+
**Output:** 4
30+
31+
**Explanation:** The longest arithmetic subsequence is [20,15,10,5].
32+
33+
**Constraints:**
34+
35+
* `2 <= nums.length <= 1000`
36+
* `0 <= nums[i] <= 500`

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

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package g1001_1100.s1028_recover_a_tree_from_preorder_traversal;
2+
3+
// #Hard #String #Depth_First_Search #Tree #Binary_Tree
4+
// #2022_02_26_Time_5_ms_(77.57%)_Space_46.5_MB_(30.81%)
5+
6+
import com_github_leetcode.TreeNode;
7+
8+
public class Solution {
9+
private int ptr = 0;
10+
11+
public TreeNode recoverFromPreorder(String traversal) {
12+
return find(traversal, 0);
13+
}
14+
15+
private TreeNode find(String traversal, int level) {
16+
if (ptr == traversal.length()) {
17+
return null;
18+
}
19+
int i = ptr;
20+
int count = 0;
21+
while (traversal.charAt(i) == '-') {
22+
count++;
23+
i++;
24+
}
25+
if (count == level) {
26+
int start = i;
27+
while (i < traversal.length() && traversal.charAt(i) != '-') {
28+
i++;
29+
}
30+
int val = Integer.parseInt(traversal.substring(start, i));
31+
ptr = i;
32+
TreeNode root = new TreeNode(val);
33+
root.left = find(traversal, level + 1);
34+
root.right = find(traversal, level + 1);
35+
return root;
36+
} else {
37+
return null;
38+
}
39+
}
40+
}

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

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
1028\. Recover a Tree From Preorder Traversal
2+
3+
Hard
4+
5+
We run a preorder depth-first search (DFS) on the `root` of a binary tree.
6+
7+
At each node in this traversal, we output `D` dashes (where `D` is the depth of this node), then we output the value of this node. If the depth of a node is `D`, the depth of its immediate child is `D + 1`. The depth of the `root` node is `0`.
8+
9+
If a node has only one child, that child is guaranteed to be **the left child**.
10+
11+
Given the output `traversal` of this traversal, recover the tree and return _its_ `root`.
12+
13+
**Example 1:**
14+
15+
![](https://assets.leetcode.com/uploads/2019/04/08/recover-a-tree-from-preorder-traversal.png)
16+
17+
**Input:** traversal = "1-2--3--4-5--6--7"
18+
19+
**Output:** [1,2,5,3,4,6,7]
20+
21+
**Example 2:**
22+
23+
![](https://assets.leetcode.com/uploads/2019/04/11/screen-shot-2019-04-10-at-114101-pm.png)
24+
25+
**Input:** traversal = "1-2--3---4-5--6---7"
26+
27+
**Output:** [1,2,5,3,null,6,null,4,null,7]
28+
29+
**Example 3:**
30+
31+
![](https://assets.leetcode.com/uploads/2019/04/11/screen-shot-2019-04-10-at-114955-pm.png)
32+
33+
**Input:** traversal = "1-401--349---90--88"
34+
35+
**Output:** [1,401,null,349,88,90]
36+
37+
**Constraints:**
38+
39+
* The number of nodes in the original tree is in the range `[1, 1000]`.
40+
* <code>1 <= Node.val <= 10<sup>9</sup></code>

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

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
package g1001_1100.s1029_two_city_scheduling;
2+
3+
// #Medium #Array #Sorting #Greedy
4+
5+
import java.util.Arrays;
6+
7+
public class Solution {
8+
public int twoCitySchedCost(int[][] costs) {
9+
Arrays.sort(costs, (a, b) -> (a[0] - a[1] - (b[0] - b[1])));
10+
int cost = 0;
11+
for (int i = 0; i < costs.length; i++) {
12+
if (i < costs.length / 2) {
13+
cost += costs[i][0];
14+
} else {
15+
cost += costs[i][1];
16+
}
17+
}
18+
return cost;
19+
}
20+
}

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

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
1029\. Two City Scheduling
2+
3+
Medium
4+
5+
A company is planning to interview `2n` people. Given the array `costs` where <code>costs[i] = [aCost<sub>i</sub>, bCost<sub>i</sub>]</code>, the cost of flying the <code>i<sup>th</sup></code> person to city `a` is <code>aCost<sub>i</sub></code>, and the cost of flying the <code>i<sup>th</sup></code> person to city `b` is <code>bCost<sub>i</sub></code>.
6+
7+
Return _the minimum cost to fly every person to a city_ such that exactly `n` people arrive in each city.
8+
9+
**Example 1:**
10+
11+
**Input:** costs = [[10,20],[30,200],[400,50],[30,20]]
12+
13+
**Output:** 110
14+
15+
**Explanation:**
16+
17+
The first person goes to city A for a cost of 10.
18+
19+
The second person goes to city A for a cost of 30.
20+
21+
The third person goes to city B for a cost of 50.
22+
23+
The fourth person goes to city B for a cost of 20.
24+
25+
The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.
26+
27+
**Example 2:**
28+
29+
**Input:** costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
30+
31+
**Output:** 1859
32+
33+
**Example 3:**
34+
35+
**Input:** costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
36+
37+
**Output:** 3086
38+
39+
**Constraints:**
40+
41+
* `2 * n == costs.length`
42+
* `2 <= costs.length <= 100`
43+
* `costs.length` is even.
44+
* <code>1 <= aCost<sub>i</sub>, bCost<sub>i</sub> <= 1000</code>

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

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package g1001_1100.s1030_matrix_cells_in_distance_order;
2+
3+
// #Easy #Array #Math #Sorting #Matrix #Geometry
4+
// #2022_02_27_Time_15_ms_(69.74%)_Space_72.2_MB_(52.05%)
5+
6+
import java.util.ArrayList;
7+
import java.util.List;
8+
import java.util.Map;
9+
import java.util.TreeMap;
10+
11+
public class Solution {
12+
public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
13+
Map<Integer, List<int[]>> map = new TreeMap<>();
14+
for (int i = 0; i < rows; i++) {
15+
for (int j = 0; j < cols; j++) {
16+
map.computeIfAbsent(
17+
Math.abs(i - rCenter) + Math.abs(j - cCenter),
18+
k -> new ArrayList<>())
19+
.add(new int[] {i, j});
20+
}
21+
}
22+
23+
int[][] res = new int[rows * cols][];
24+
int i = 0;
25+
for (List<int[]> list : map.values()) {
26+
for (int[] each : list) {
27+
res[i++] = each;
28+
}
29+
}
30+
return res;
31+
}
32+
}

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

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
1029\. Two City Scheduling
2+
3+
Medium
4+
5+
A company is planning to interview `2n` people. Given the array `costs` where <code>costs[i] = [aCost<sub>i</sub>, bCost<sub>i</sub>]</code>, the cost of flying the <code>i<sup>th</sup></code> person to city `a` is <code>aCost<sub>i</sub></code>, and the cost of flying the <code>i<sup>th</sup></code> person to city `b` is <code>bCost<sub>i</sub></code>.
6+
7+
Return _the minimum cost to fly every person to a city_ such that exactly `n` people arrive in each city.
8+
9+
**Example 1:**
10+
11+
**Input:** costs = [[10,20],[30,200],[400,50],[30,20]]
12+
13+
**Output:** 110
14+
15+
**Explanation:**
16+
17+
The first person goes to city A for a cost of 10.
18+
19+
The second person goes to city A for a cost of 30.
20+
21+
The third person goes to city B for a cost of 50.
22+
23+
The fourth person goes to city B for a cost of 20.
24+
25+
The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.
26+
27+
**Example 2:**
28+
29+
**Input:** costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
30+
31+
**Output:** 1859
32+
33+
**Example 3:**
34+
35+
**Input:** costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
36+
37+
**Output:** 3086
38+
39+
**Constraints:**
40+
41+
* `2 * n == costs.length`
42+
* `2 <= costs.length <= 100`
43+
* `costs.length` is even.
44+
* <code>1 <= aCost<sub>i</sub>, bCost<sub>i</sub> <= 1000</code>

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

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package g1001_1100.s1027_longest_arithmetic_subsequence;
2+
3+
import static org.hamcrest.CoreMatchers.equalTo;
4+
import static org.hamcrest.MatcherAssert.assertThat;
5+
6+
import org.junit.jupiter.api.Test;
7+
8+
class SolutionTest {
9+
@Test
10+
void longestArithSeqLength() {
11+
assertThat(new Solution().longestArithSeqLength(new int[] {3, 6, 9, 12}), equalTo(4));
12+
}
13+
14+
@Test
15+
void longestArithSeqLength2() {
16+
assertThat(new Solution().longestArithSeqLength(new int[] {9, 4, 7, 2, 10}), equalTo(3));
17+
}
18+
19+
@Test
20+
void longestArithSeqLength3() {
21+
assertThat(
22+
new Solution().longestArithSeqLength(new int[] {20, 1, 15, 3, 10, 5, 8}),
23+
equalTo(4));
24+
}
25+
}

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

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package g1001_1100.s1028_recover_a_tree_from_preorder_traversal;
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 org.junit.jupiter.api.Test;
9+
10+
class SolutionTest {
11+
@Test
12+
void recoverFromPreorder() {
13+
TreeNode expected = TreeNode.create(Arrays.asList(1, 2, 5, 3, 4, 6, 7));
14+
assertThat(
15+
new Solution().recoverFromPreorder("1-2--3--4-5--6--7").toString(),
16+
equalTo(expected.toString()));
17+
}
18+
19+
@Test
20+
void recoverFromPreorder2() {
21+
TreeNode expected = TreeNode.create(Arrays.asList(1, 2, 5, 3, null, 6, null, 4, null, 7));
22+
assertThat(
23+
new Solution().recoverFromPreorder("1-2--3---4-5--6---7").toString(),
24+
equalTo(expected.toString()));
25+
}
26+
27+
@Test
28+
void recoverFromPreorder3() {
29+
TreeNode expected = TreeNode.create(Arrays.asList(1, 401, null, 349, 88, 90));
30+
assertThat(
31+
new Solution().recoverFromPreorder("1-401--349---90--88").toString(),
32+
equalTo(expected.toString()));
33+
}
34+
}

0 commit comments

Comments
 (0)