Skip to content

Commit ce18219

Browse files
ThanhNITThanhNIT
authored
Added tasks 1041, 1042, 1043, 1044, 1046.
1 parent 278c2c6 commit ce18219

File tree

15 files changed

+555
-0
lines changed

15 files changed

+555
-0
lines changed

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

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package g1001_1100.s1041_robot_bounded_in_circle;
2+
3+
// #Medium #String #Math #Simulation #2022_02_27_Time_0_ms_(100.00%)_Space_39.9_MB_(14.49%)
4+
5+
public class Solution {
6+
public boolean isRobotBounded(String instructions) {
7+
int[][] dir = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
8+
int i = 0;
9+
int x = 0;
10+
int y = 0;
11+
12+
for (int s = 0; s < instructions.length(); s++) {
13+
if (instructions.charAt(s) == 'L') {
14+
i = (i + 1) % 4;
15+
} else if (instructions.charAt(s) == 'R') {
16+
i = (i + 3) % 4;
17+
} else {
18+
x = x + dir[i][0];
19+
y = y + dir[i][1];
20+
}
21+
}
22+
return x == 0 && y == 0 || i != 0;
23+
}
24+
}

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

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
1041\. Robot Bounded In Circle
2+
3+
Medium
4+
5+
On an infinite plane, a robot initially stands at `(0, 0)` and faces north. Note that:
6+
7+
* The **north direction** is the positive direction of the y-axis.
8+
* The **south direction** is the negative direction of the y-axis.
9+
* The **east direction** is the positive direction of the x-axis.
10+
* The **west direction** is the negative direction of the x-axis.
11+
12+
The robot can receive one of three instructions:
13+
14+
* `"G"`: go straight 1 unit.
15+
* `"L"`: turn 90 degrees to the left (i.e., anti-clockwise direction).
16+
* `"R"`: turn 90 degrees to the right (i.e., clockwise direction).
17+
18+
The robot performs the `instructions` given in order, and repeats them forever.
19+
20+
Return `true` if and only if there exists a circle in the plane such that the robot never leaves the circle.
21+
22+
**Example 1:**
23+
24+
**Input:** instructions = "GGLLGG"
25+
26+
**Output:** true
27+
28+
**Explanation:** The robot is initially at (0, 0) facing the north direction.
29+
30+
"G": move one step. Position: (0, 1). Direction: North.
31+
32+
"G": move one step. Position: (0, 2). Direction: North.
33+
34+
"L": turn 90 degrees anti-clockwise. Position: (0, 2). Direction: West.
35+
36+
"L": turn 90 degrees anti-clockwise. Position: (0, 2). Direction: South.
37+
38+
"G": move one step. Position: (0, 1). Direction: South.
39+
40+
"G": move one step. Position: (0, 0). Direction: South.
41+
42+
Repeating the instructions, the robot goes into the cycle: (0, 0) --> (0, 1) --> (0, 2) --> (0, 1) --> (0, 0).
43+
44+
Based on that, we return true.
45+
46+
**Example 2:**
47+
48+
**Input:** instructions = "GG"
49+
50+
**Output:** false
51+
52+
**Explanation:** The robot is initially at (0, 0) facing the north direction.
53+
54+
"G": move one step. Position: (0, 1). Direction: North.
55+
56+
"G": move one step. Position: (0, 2). Direction: North.
57+
58+
Repeating the instructions, keeps advancing in the north direction and does not go into cycles.
59+
60+
Based on that, we return false.
61+
62+
**Example 3:**
63+
64+
**Input:** instructions = "GL"
65+
66+
**Output:** true
67+
68+
**Explanation:** The robot is initially at (0, 0) facing the north direction.
69+
70+
"G": move one step. Position: (0, 1). Direction: North.
71+
72+
"L": turn 90 degrees anti-clockwise. Position: (0, 1). Direction: West.
73+
74+
"G": move one step. Position: (-1, 1). Direction: West.
75+
76+
"L": turn 90 degrees anti-clockwise. Position: (-1, 1). Direction: South.
77+
78+
"G": move one step. Position: (-1, 0). Direction: South.
79+
80+
"L": turn 90 degrees anti-clockwise. Position: (-1, 0). Direction: East.
81+
82+
"G": move one step. Position: (0, 0). Direction: East.
83+
84+
"L": turn 90 degrees anti-clockwise. Position: (0, 0). Direction: North.
85+
86+
Repeating the instructions, the robot goes into the cycle: (0, 0) --> (0, 1) --> (-1, 1) --> (-1, 0) --> (0, 0).
87+
88+
Based on that, we return true.
89+
90+
**Constraints:**
91+
92+
* `1 <= instructions.length <= 100`
93+
* `instructions[i]` is `'G'`, `'L'` or, `'R'`.

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

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
package g1001_1100.s1042_flower_planting_with_no_adjacent;
2+
3+
// #Medium #Depth_First_Search #Breadth_First_Search #Graph
4+
// #2022_02_27_Time_19_ms_(89.02%)_Space_72.1_MB_(61.13%)
5+
6+
import java.util.ArrayList;
7+
import java.util.List;
8+
9+
public class Solution {
10+
private List<Integer>[] graph;
11+
private int n;
12+
private int[] color;
13+
private boolean[] visited;
14+
15+
public int[] gardenNoAdj(int n, int[][] paths) {
16+
buildGraph(n, paths);
17+
this.color = new int[n];
18+
this.visited = new boolean[n];
19+
20+
for (int i = 0; i < n; i++) {
21+
if (!visited[i]) {
22+
dfs(i);
23+
}
24+
}
25+
26+
return color;
27+
}
28+
29+
private void dfs(int at) {
30+
visited[at] = true;
31+
int used = 0;
32+
33+
for (int to : graph[at]) {
34+
if (color[to] != 0) {
35+
used |= 1 << color[to] - 1;
36+
}
37+
}
38+
39+
// use available color
40+
for (int i = 0; i < 4; i++) {
41+
if ((used & 1 << i) == 0) {
42+
color[at] = i + 1;
43+
break;
44+
}
45+
}
46+
}
47+
48+
private void buildGraph(int n, int[][] paths) {
49+
graph = new ArrayList[n];
50+
51+
for (int i = 0; i < n; i++) {
52+
graph[i] = new ArrayList<>();
53+
}
54+
55+
for (int[] path : paths) {
56+
int u = path[0] - 1;
57+
int v = path[1] - 1;
58+
graph[u].add(v);
59+
graph[v].add(u);
60+
}
61+
}
62+
}

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

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
1042\. Flower Planting With No Adjacent
2+
3+
Medium
4+
5+
You have `n` gardens, labeled from `1` to `n`, and an array `paths` where <code>paths[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> describes a bidirectional path between garden <code>x<sub>i</sub></code> to garden <code>y<sub>i</sub></code>. In each garden, you want to plant one of 4 types of flowers.
6+
7+
All gardens have **at most 3** paths coming into or leaving it.
8+
9+
Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.
10+
11+
Return _**any** such a choice as an array_ `answer`_, where_ `answer[i]` _is the type of flower planted in the_ <code>(i+1)<sup>th</sup></code> _garden. The flower types are denoted_ `1`_,_ `2`_,_ `3`_, or_ `4`_. It is guaranteed an answer exists._
12+
13+
**Example 1:**
14+
15+
**Input:** n = 3, paths = [[1,2],[2,3],[3,1]]
16+
17+
**Output:** [1,2,3]
18+
19+
**Explanation:**
20+
21+
Gardens 1 and 2 have different types.
22+
23+
Gardens 2 and 3 have different types.
24+
25+
Gardens 3 and 1 have different types.
26+
27+
Hence, [1,2,3] is a valid answer. Other valid answers include [1,2,4], [1,4,2], and [3,2,1].
28+
29+
**Example 2:**
30+
31+
**Input:** n = 4, paths = [[1,2],[3,4]]
32+
33+
**Output:** [1,2,1,2]
34+
35+
**Example 3:**
36+
37+
**Input:** n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
38+
39+
**Output:** [1,2,3,4]
40+
41+
**Constraints:**
42+
43+
* <code>1 <= n <= 10<sup>4</sup></code>
44+
* <code>0 <= paths.length <= 2 * 10<sup>4</sup></code>
45+
* `paths[i].length == 2`
46+
* <code>1 <= x<sub>i</sub>, y<sub>i</sub> <= n</code>
47+
* <code>x<sub>i</sub> != y<sub>i</sub></code>
48+
* Every garden has **at most 3** paths coming into or leaving it.

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

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package g1001_1100.s1043_partition_array_for_maximum_sum;
2+
3+
// #Medium #Array #Dynamic_Programming #2022_02_27_Time_5_ms_(90.43%)_Space_41.8_MB_(37.80%)
4+
5+
public class Solution {
6+
public int maxSumAfterPartitioning(int[] arr, int k) {
7+
int n = arr.length;
8+
int[] dp = new int[n];
9+
for (int right = 0; right < n; right++) {
10+
int localMax = arr[right];
11+
for (int left = right; left > Math.max(-1, right - k); left--) {
12+
localMax = Math.max(localMax, arr[left]);
13+
if (left == 0) {
14+
dp[right] = Math.max(dp[right], (right - left + 1) * localMax);
15+
} else {
16+
dp[right] = Math.max(dp[right], dp[left - 1] + (right - left + 1) * localMax);
17+
}
18+
}
19+
}
20+
return dp[n - 1];
21+
}
22+
}

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

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
1043\. Partition Array for Maximum Sum
2+
3+
Medium
4+
5+
Given an integer array `arr`, partition the array into (contiguous) subarrays of length **at most** `k`. After partitioning, each subarray has their values changed to become the maximum value of that subarray.
6+
7+
Return _the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a **32-bit** integer._
8+
9+
**Example 1:**
10+
11+
**Input:** arr = [1,15,7,9,2,5,10], k = 3
12+
13+
**Output:** 84
14+
15+
**Explanation:** arr becomes [15,15,15,9,10,10,10]
16+
17+
**Example 2:**
18+
19+
**Input:** arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
20+
21+
**Output:** 83
22+
23+
**Example 3:**
24+
25+
**Input:** arr = [1], k = 1
26+
27+
**Output:** 1
28+
29+
**Constraints:**
30+
31+
* `1 <= arr.length <= 500`
32+
* <code>0 <= arr[i] <= 10<sup>9</sup></code>
33+
* `1 <= k <= arr.length`

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

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
package g1001_1100.s1044_longest_duplicate_substring;
2+
3+
// #Hard #String #Binary_Search #Sliding_Window #Hash_Function #Rolling_Hash #Suffix_Array
4+
// #2022_02_27_Time_447_ms_(62.53%)_Space_118.6_MB_(57.97%)
5+
6+
import java.util.ArrayList;
7+
import java.util.HashSet;
8+
import java.util.List;
9+
import java.util.Set;
10+
11+
public class Solution {
12+
private final int mod = (int) 1e9 + 7;
13+
private long[] hsh;
14+
private long[] pw;
15+
private final List[] cnt = new List[26];
16+
17+
public String longestDupSubstring(String s) {
18+
int n = s.length(), base = 131;
19+
for (int i = 0; i < 26; i++) cnt[i] = new ArrayList<>();
20+
hsh = new long[n + 1];
21+
pw = new long[n + 1];
22+
pw[0] = 1;
23+
for (int j = 1; j <= n; j++) {
24+
hsh[j] = (hsh[j - 1] * base + s.charAt(j - 1)) % mod;
25+
pw[j] = pw[j - 1] * base % mod;
26+
cnt[s.charAt(j - 1) - 'a'].add(j - 1);
27+
}
28+
String ans = "";
29+
for (int i = 0; i < 26; i++) {
30+
if (cnt[i].size() == 0) {
31+
continue;
32+
}
33+
List<Integer> idx = cnt[i];
34+
Set<Long> set;
35+
int lo = 1, hi = n - idx.get(0);
36+
while (lo <= hi) {
37+
int len = (lo + hi) / 2;
38+
set = new HashSet<>();
39+
boolean found = false;
40+
for (int nxt : idx) {
41+
if (nxt + len > n) {
42+
break;
43+
}
44+
long substrHash = getSubstrHash(nxt, nxt + len);
45+
if (set.contains(substrHash)) {
46+
found = true;
47+
if (len + 1 > ans.length()) {
48+
ans = s.substring(nxt, nxt + len);
49+
}
50+
break;
51+
}
52+
set.add(substrHash);
53+
}
54+
if (found) {
55+
lo = len + 1;
56+
} else hi = len - 1;
57+
}
58+
}
59+
return ans;
60+
}
61+
62+
private long getSubstrHash(int l, int r) {
63+
return (hsh[r] - hsh[l] * pw[r - l] % mod + mod) % mod;
64+
}
65+
}

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

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
1044\. Longest Duplicate Substring
2+
3+
Hard
4+
5+
Given a string `s`, consider all _duplicated substrings_: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap.
6+
7+
Return **any** duplicated substring that has the longest possible length. If `s` does not have a duplicated substring, the answer is `""`.
8+
9+
**Example 1:**
10+
11+
**Input:** s = "banana"
12+
13+
**Output:** "ana"
14+
15+
**Example 2:**
16+
17+
**Input:** s = "abcd"
18+
19+
**Output:** ""
20+
21+
**Constraints:**
22+
23+
* <code>2 <= s.length <= 3 * 10<sup>4</sup></code>
24+
* `s` consists of lowercase English letters.

0 commit comments

Comments
 (0)