Skip to content

Commit 3e64dc8

Browse files
javadevjavadev
authored
Added tasks 421, 423, 424, 437.
1 parent 1a08077 commit 3e64dc8

14 files changed

Lines changed: 439 additions & 2 deletions

File tree

‎.github/workflows/maven.yml‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -21,8 +21,7 @@ jobs:
2121
- name: Set up JDK 11
2222
uses: actions/setup-java@v2
2323
with:
24-
distribution: 'temurin'
25-
java-version: '11'
24+
java-version: 11
2625
cache: 'gradle'
2726
- name: Cache SonarCloud packages
2827
uses: actions/cache@v1

‎src/main/java/g0401_0500/s0421_maximum_xor_of_two_numbers_in_an_array/Solution.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package g0401_0500.s0421_maximum_xor_of_two_numbers_in_an_array;
2+
3+
// #Medium #Array #Hash_Table #Bit_Manipulation #Trie
4+
5+
import java.util.HashSet;
6+
import java.util.Set;
7+
8+
public class Solution {
9+
public int findMaximumXOR(int[] nums) {
10+
int max = 0;
11+
int mask = 0;
12+
Set<Integer> set = new HashSet<>();
13+
int maxNum = 0;
14+
for (int i : nums) {
15+
maxNum = Math.max(maxNum, i);
16+
}
17+
for (int i = 31 - Integer.numberOfLeadingZeros(maxNum); i >= 0; i--) {
18+
set.clear();
19+
int bit = 1 << i;
20+
mask = mask | bit;
21+
int temp = max | bit;
22+
for (int prefix : nums) {
23+
if (set.contains((prefix & mask) ^ temp)) {
24+
max = temp;
25+
break;
26+
}
27+
set.add(prefix & mask);
28+
}
29+
}
30+
return max;
31+
}
32+
}

‎src/main/java/g0401_0500/s0421_maximum_xor_of_two_numbers_in_an_array/readme.md‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
421\. Maximum XOR of Two Numbers in an Array
2+
3+
Medium
4+
5+
Given an integer array `nums`, return _the maximum result of_ `nums[i] XOR nums[j]`, where `0 <= i <= j < n`.
6+
7+
**Example 1:**
8+
9+
**Input:** nums = \[3,10,5,25,2,8\]
10+
11+
**Output:** 28
12+
13+
**Explanation:** The maximum result is 5 XOR 25 = 28.
14+
15+
**Example 2:**
16+
17+
**Input:** nums = \[14,70,53,83,49,91,36,80,92,51,66,70\]
18+
19+
**Output:** 127
20+
21+
**Constraints:**
22+
23+
* <code>1 <= nums.length <= 2 * 10<sup>5</sup></code>
24+
* <code>0 <= nums[i] <= 2<sup>31</sup> - 1</code>

‎src/main/java/g0401_0500/s0423_reconstruct_original_digits_from_english/Solution.java‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package g0401_0500.s0423_reconstruct_original_digits_from_english;
2+
3+
// #Medium #String #Hash_Table #Math
4+
5+
public class Solution {
6+
public String originalDigits(String s) {
7+
int[] count = new int[26];
8+
int[] digits = new int[10];
9+
StringBuilder str = new StringBuilder();
10+
for (char c : s.toCharArray()) {
11+
++count[c - 'a'];
12+
}
13+
digits[0] = count[25];
14+
digits[2] = count[22];
15+
digits[4] = count[20];
16+
digits[6] = count[23];
17+
digits[8] = count[6];
18+
digits[1] = count[14] - digits[0] - digits[2] - digits[4];
19+
digits[3] = count[7] - digits[8];
20+
digits[5] = count[5] - digits[4];
21+
digits[7] = count[18] - digits[6];
22+
digits[9] = count[8] - digits[5] - digits[6] - digits[8];
23+
for (int i = 0; i < 10; i++) {
24+
while (digits[i]-- != 0) {
25+
str.append((char) (i + 48));
26+
}
27+
}
28+
return str.toString();
29+
}
30+
}

‎src/main/java/g0401_0500/s0423_reconstruct_original_digits_from_english/readme.md‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
423\. Reconstruct Original Digits from English
2+
3+
Medium
4+
5+
Given a string `s` containing an out-of-order English representation of digits `0-9`, return _the digits in **ascending** order_.
6+
7+
**Example 1:**
8+
9+
**Input:** s = "owoztneoer"
10+
11+
**Output:** "012"
12+
13+
**Example 2:**
14+
15+
**Input:** s = "fviefuro"
16+
17+
**Output:** "45"
18+
19+
**Constraints:**
20+
21+
* <code>1 <= s.length <= 10<sup>5</sup></code>
22+
* `s[i]` is one of the characters `["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"]`.
23+
* `s` is **guaranteed** to be valid.

‎src/main/java/g0401_0500/s0424_longest_repeating_character_replacement/Solution.java‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package g0401_0500.s0424_longest_repeating_character_replacement;
2+
3+
// #Medium #String #Hash_Table #Sliding_Window
4+
5+
public class Solution {
6+
public int characterReplacement(String s, int k) {
7+
int left = 0;
8+
int right = 0;
9+
int len = s.length();
10+
int[] count = new int[256];
11+
char[] sArr = s.toCharArray();
12+
int currMax = 0;
13+
int maxLen = 0;
14+
char curr;
15+
while (right < len) {
16+
curr = sArr[right];
17+
count[curr]++;
18+
currMax = Math.max(currMax, count[curr]);
19+
if (right - left + 1 <= currMax + k) {
20+
maxLen = Math.max(maxLen, right - left + 1);
21+
}
22+
while (right - left + 1 > currMax + k) {
23+
curr = sArr[left];
24+
count[curr]--;
25+
left++;
26+
}
27+
right++;
28+
}
29+
return maxLen;
30+
}
31+
}

‎src/main/java/g0401_0500/s0424_longest_repeating_character_replacement/readme.md‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
424\. Longest Repeating Character Replacement
2+
3+
Medium
4+
5+
You are given a string `s` and an integer `k`. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most `k` times.
6+
7+
Return _the length of the longest substring containing the same letter you can get after performing the above operations_.
8+
9+
**Example 1:**
10+
11+
**Input:** s = "ABAB", k = 2
12+
13+
**Output:** 4
14+
15+
**Explanation:** Replace the two 'A's with two 'B's or vice versa.
16+
17+
**Example 2:**
18+
19+
**Input:** s = "AABABBA", k = 1
20+
21+
**Output:** 4
22+
23+
**Explanation:** Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4.
24+
25+
**Constraints:**
26+
27+
* <code>1 <= s.length <= 10<sup>5</sup></code>
28+
* `s` consists of only uppercase English letters.
29+
* `0 <= k <= s.length

‎src/main/java/g0401_0500/s0427_construct_quad_tree/Node.java‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
package g0401_0500.s0427_construct_quad_tree;
2+
3+
@SuppressWarnings("java:S1104")
4+
public class Node {
5+
public boolean val;
6+
public boolean isLeaf;
7+
public Node topLeft;
8+
public Node topRight;
9+
public Node bottomLeft;
10+
public Node bottomRight;
11+
12+
public Node() {
13+
this.val = false;
14+
this.isLeaf = false;
15+
this.topLeft = null;
16+
this.topRight = null;
17+
this.bottomLeft = null;
18+
this.bottomRight = null;
19+
}
20+
21+
public Node(boolean val, boolean isLeaf) {
22+
this.val = val;
23+
this.isLeaf = isLeaf;
24+
this.topLeft = null;
25+
this.topRight = null;
26+
this.bottomLeft = null;
27+
this.bottomRight = null;
28+
}
29+
30+
public Node(
31+
boolean val,
32+
boolean isLeaf,
33+
Node topLeft,
34+
Node topRight,
35+
Node bottomLeft,
36+
Node bottomRight) {
37+
this.val = val;
38+
this.isLeaf = isLeaf;
39+
this.topLeft = topLeft;
40+
this.topRight = topRight;
41+
this.bottomLeft = bottomLeft;
42+
this.bottomRight = bottomRight;
43+
}
44+
45+
@Override
46+
public String toString() {
47+
if (topLeft != null && topRight != null && bottomLeft != null && bottomRight != null) {
48+
return getNode(this)
49+
+ getNode(topLeft)
50+
+ getNode(topRight)
51+
+ getNode(bottomLeft)
52+
+ getNode(bottomRight);
53+
}
54+
return "";
55+
}
56+
57+
private String getNode(Node node) {
58+
return "[" + (node.isLeaf ? "1" : "0") + "," + (node.val ? "1" : "0") + "]";
59+
}
60+
}

‎src/main/java/g0401_0500/s0427_construct_quad_tree/Solution.java‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package g0401_0500.s0427_construct_quad_tree;
2+
3+
// #Medium #Array #Tree #Matrix #Divide_and_Conquer
4+
5+
public class Solution {
6+
public Node construct(int[][] grid) {
7+
return optimizedDfs(grid, 0, 0, grid.length);
8+
}
9+
10+
private Node optimizedDfs(int[][] grid, int rowStart, int colStart, int len) {
11+
int zeroCount = 0;
12+
int oneCount = 0;
13+
for (int row = rowStart; row < rowStart + len; row++) {
14+
boolean isBreak = false;
15+
for (int col = colStart; col < colStart + len; col++) {
16+
if (grid[row][col] == 0) {
17+
zeroCount++;
18+
} else {
19+
oneCount++;
20+
}
21+
if (oneCount > 0 && zeroCount > 0) {
22+
// We really no need to scan all.
23+
// Once we know there are both 0 and 1 then we can break.
24+
isBreak = true;
25+
break;
26+
}
27+
}
28+
if (isBreak) {
29+
break;
30+
}
31+
}
32+
33+
if (oneCount > 0 && zeroCount > 0) {
34+
int midLen = len / 2;
35+
Node topLeft = optimizedDfs(grid, rowStart, colStart, midLen);
36+
Node topRight = optimizedDfs(grid, rowStart, colStart + midLen, midLen);
37+
Node bottomLeft = optimizedDfs(grid, rowStart + midLen, colStart, midLen);
38+
Node bottomRight = optimizedDfs(grid, rowStart + midLen, colStart + midLen, midLen);
39+
boolean isLeaf = false;
40+
return new Node(true, isLeaf, topLeft, topRight, bottomLeft, bottomRight);
41+
} else {
42+
boolean resultVal = oneCount > 0;
43+
boolean isLeaf = true;
44+
return new Node(resultVal, isLeaf);
45+
}
46+
}
47+
}

‎src/main/java/g0401_0500/s0427_construct_quad_tree/readme.md‎

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
427\. Construct Quad Tree
2+
3+
Medium
4+
5+
Given a `n * n` matrix `grid` of `0's` and `1's` only. We want to represent the `grid` with a Quad-Tree.
6+
7+
Return _the root of the Quad-Tree_ representing the `grid`.
8+
9+
Notice that you can assign the value of a node to **True** or **False** when `isLeaf` is **False**, and both are **accepted** in the answer.
10+
11+
A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:
12+
13+
* `val`: True if the node represents a grid of 1's or False if the node represents a grid of 0's.
14+
* `isLeaf`: True if the node is leaf node on the tree or False if the node has the four children.
15+
16+
class Node { public boolean val; public boolean isLeaf; public Node topLeft; public Node topRight; public Node bottomLeft; public Node bottomRight; }
17+
18+
We can construct a Quad-Tree from a two-dimensional area using the following steps:
19+
20+
1. If the current grid has the same value (i.e all `1's` or all `0's`) set `isLeaf` True and set `val` to the value of the grid and set the four children to Null and stop.
21+
2. If the current grid has different values, set `isLeaf` to False and set `val` to any value and divide the current grid into four sub-grids as shown in the photo.
22+
3. Recurse for each of the children with the proper sub-grid.
23+
24+
![](https://assets.leetcode.com/uploads/2020/02/11/new_top.png)
25+
26+
If you want to know more about the Quad-Tree, you can refer to the [wiki](https://en.wikipedia.org/wiki/Quadtree).
27+
28+
**Quad-Tree format:**
29+
30+
The output represents the serialized format of a Quad-Tree using level order traversal, where `null` signifies a path terminator where no node exists below.
31+
32+
It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list `[isLeaf, val]`.
33+
34+
If the value of `isLeaf` or `val` is True we represent it as **1** in the list `[isLeaf, val]` and if the value of `isLeaf` or `val` is False we represent it as **0**.
35+
36+
**Example 1:**
37+
38+
![](https://assets.leetcode.com/uploads/2020/02/11/grid1.png)
39+
40+
**Input:** grid = \[\[0,1\],\[1,0\]\]
41+
42+
**Output:** \[\[0,1\],\[1,0\],\[1,1\],\[1,1\],\[1,0\]\]
43+
44+
**Explanation:**
45+
46+
The explanation of this example is shown below:
47+
Notice that 0 represnts False and 1 represents True in the photo representing the Quad-Tree.
48+
49+
![](https://assets.leetcode.com/uploads/2020/02/12/e1tree.png)
50+
51+
**Example 2:**
52+
53+
![](https://assets.leetcode.com/uploads/2020/02/12/e2mat.png)
54+
55+
**Input:** grid = \[\[1,1,1,1,0,0,0,0\],\[1,1,1,1,0,0,0,0\],\[1,1,1,1,1,1,1,1\],\[1,1,1,1,1,1,1,1\],\[1,1,1,1,0,0,0,0\],\[1,1,1,1,0,0,0,0\],\[1,1,1,1,0,0,0,0\],\[1,1,1,1,0,0,0,0\]\]
56+
57+
**Output:** \[\[0,1\],\[1,1\],\[0,1\],\[1,1\],\[1,0\],null,null,null,null,\[1,0\],\[1,0\],\[1,1\],\[1,1\]\]
58+
59+
**Explanation:**
60+
61+
All values in the grid are not the same. We divide the grid into four sub-grids.
62+
The topLeft, bottomLeft and bottomRight each has the same value.
63+
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
64+
Explanation is shown in the photo below:
65+
66+
![](https://assets.leetcode.com/uploads/2020/02/12/e2tree.png)
67+
68+
**Constraints:**
69+
70+
* `n == grid.length == grid[i].length`
71+
* <code>n == 2<sup>x</sup></code> where `0 <= x <= 6`

0 commit comments

Comments
 (0)