Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitcb89119

Browse files
authored
Added tasks 3492-3495
1 parentfba4231 commitcb89119

File tree

13 files changed

+453
-1
lines changed

13 files changed

+453
-1
lines changed

‎src/main/java/g3401_3500/s3486_longest_special_path_ii/Solution.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
packageg3401_3500.s3486_longest_special_path_ii;
22

3-
// #Hard #Array #Hash_Table #Tree #Prefix_Sum #Depth_First_Search
3+
// #Hard #Array #Hash_Table #Depth_First_Search #Tree #Prefix_Sum
44
// #2025_03_17_Time_166_ms_(100.00%)_Space_105.50_MB_(100.00%)
55

66
importjava.util.ArrayList;
Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
packageg3401_3500.s3492_maximum_containers_on_a_ship;
2+
3+
// #Easy #Math #2025_03_24_Time_0_ms_(100.00%)_Space_40.73_MB_(100.00%)
4+
5+
publicclassSolution {
6+
publicintmaxContainers(intn,intw,intmaxWeight) {
7+
intc =n *n;
8+
intcount =maxWeight /w;
9+
returnMath.min(c,count);
10+
}
11+
}
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
3492\. Maximum Containers on a Ship
2+
3+
Easy
4+
5+
You are given a positive integer`n` representing an`n x n` cargo deck on a ship. Each cell on the deck can hold one container with a weight of**exactly**`w`.
6+
7+
However, the total weight of all containers, if loaded onto the deck, must not exceed the ship's maximum weight capacity,`maxWeight`.
8+
9+
Return the**maximum** number of containers that can be loaded onto the ship.
10+
11+
**Example 1:**
12+
13+
**Input:** n = 2, w = 3, maxWeight = 15
14+
15+
**Output:** 4
16+
17+
**Explanation:**
18+
19+
The deck has 4 cells, and each container weighs 3. The total weight of loading all containers is 12, which does not exceed`maxWeight`.
20+
21+
**Example 2:**
22+
23+
**Input:** n = 3, w = 5, maxWeight = 20
24+
25+
**Output:** 4
26+
27+
**Explanation:**
28+
29+
The deck has 9 cells, and each container weighs 5. The maximum number of containers that can be loaded without exceeding`maxWeight` is 4.
30+
31+
**Constraints:**
32+
33+
*`1 <= n <= 1000`
34+
*`1 <= w <= 1000`
35+
* <code>1 <= maxWeight <= 10<sup>9</sup></code>
Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
packageg3401_3500.s3493_properties_graph;
2+
3+
// #Medium #Array #Hash_Table #Depth_First_Search #Breadth_First_Search #Graph #Union_Find
4+
// #2025_03_24_Time_27_ms_(99.82%)_Space_46.06_MB_(37.59%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.BitSet;
8+
importjava.util.HashSet;
9+
importjava.util.List;
10+
importjava.util.Set;
11+
12+
publicclassSolution {
13+
privateint[]parent;
14+
15+
publicintnumberOfComponents(int[][]properties,intk) {
16+
List<List<Integer>>al =convertToList(properties);
17+
intn =al.size();
18+
List<BitSet>bs =newArrayList<>(n);
19+
for (List<Integer>integers :al) {
20+
BitSetbitset =newBitSet(101);
21+
for (intnum :integers) {
22+
bitset.set(num);
23+
}
24+
bs.add(bitset);
25+
}
26+
parent =newint[n];
27+
for (inti =0;i <n;i++) {
28+
parent[i] =i;
29+
}
30+
for (inti =0;i <n;i++) {
31+
for (intj =i +1;j <n;j++) {
32+
BitSettemp = (BitSet)bs.get(i).clone();
33+
temp.and(bs.get(j));
34+
intcommon =temp.cardinality();
35+
if (common >=k) {
36+
unionn(i,j);
37+
}
38+
}
39+
}
40+
Set<Integer>comps =newHashSet<>();
41+
for (inti =0;i <n;i++) {
42+
comps.add(findp(i));
43+
}
44+
returncomps.size();
45+
}
46+
47+
privateintfindp(intx) {
48+
if (parent[x] !=x) {
49+
parent[x] =findp(parent[x]);
50+
}
51+
returnparent[x];
52+
}
53+
54+
privatevoidunionn(inta,intb) {
55+
intpa =findp(a);
56+
intpb =findp(b);
57+
if (pa !=pb) {
58+
parent[pa] =pb;
59+
}
60+
}
61+
62+
privateList<List<Integer>>convertToList(int[][]arr) {
63+
List<List<Integer>>list =newArrayList<>();
64+
for (int[]row :arr) {
65+
List<Integer>temp =newArrayList<>();
66+
for (intnum :row) {
67+
temp.add(num);
68+
}
69+
list.add(temp);
70+
}
71+
returnlist;
72+
}
73+
}
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
3493\. Properties Graph
2+
3+
Medium
4+
5+
You are given a 2D integer array`properties` having dimensions`n x m` and an integer`k`.
6+
7+
Define a function`intersect(a, b)` that returns the**number of distinct integers** common to both arrays`a` and`b`.
8+
9+
Construct an**undirected** graph where each index`i` corresponds to`properties[i]`. There is an edge between node`i` and node`j` if and only if`intersect(properties[i], properties[j]) >= k`, where`i` and`j` are in the range`[0, n - 1]` and`i != j`.
10+
11+
Return the number of**connected components** in the resulting graph.
12+
13+
**Example 1:**
14+
15+
**Input:** properties =[[1,2],[1,1],[3,4],[4,5],[5,6],[7,7]], k = 1
16+
17+
**Output:** 3
18+
19+
**Explanation:**
20+
21+
The graph formed has 3 connected components:
22+
23+
![](https://assets.leetcode.com/uploads/2025/02/27/image.png)
24+
25+
**Example 2:**
26+
27+
**Input:** properties =[[1,2,3],[2,3,4],[4,3,5]], k = 2
28+
29+
**Output:** 1
30+
31+
**Explanation:**
32+
33+
The graph formed has 1 connected component:
34+
35+
![](https://assets.leetcode.com/uploads/2025/02/27/screenshot-from-2025-02-27-23-58-34.png)
36+
37+
**Example 3:**
38+
39+
**Input:** properties =[[1,1],[1,1]], k = 2
40+
41+
**Output:** 2
42+
43+
**Explanation:**
44+
45+
`intersect(properties[0], properties[1]) = 1`, which is less than`k`. This means there is no edge between`properties[0]` and`properties[1]` in the graph.
46+
47+
**Constraints:**
48+
49+
*`1 <= n == properties.length <= 100`
50+
*`1 <= m == properties[i].length <= 100`
51+
*`1 <= properties[i][j] <= 100`
52+
*`1 <= k <= m`
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg3401_3500.s3494_find_the_minimum_amount_of_time_to_brew_potions;
2+
3+
// #Medium #Array #Simulation #Prefix_Sum #2025_03_24_Time_113_ms_(90.95%)_Space_44.81_MB_(64.17%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
publiclongminTime(int[]skill,int[]mana) {
9+
long[]endTime =newlong[skill.length];
10+
Arrays.fill(endTime,0);
11+
for (intk :mana) {
12+
longt =0;
13+
longmaxDiff =0;
14+
for (intj =0;j <skill.length; ++j) {
15+
maxDiff =Math.max(maxDiff,endTime[j] -t);
16+
t += (long)skill[j] * (long)k;
17+
endTime[j] =t;
18+
}
19+
for (intj =0;j <skill.length; ++j) {
20+
endTime[j] +=maxDiff;
21+
}
22+
}
23+
returnendTime[endTime.length -1];
24+
}
25+
}
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
3494\. Find the Minimum Amount of Time to Brew Potions
2+
3+
Medium
4+
5+
You are given two integer arrays,`skill` and`mana`, of length`n` and`m`, respectively.
6+
7+
In a laboratory,`n` wizards must brew`m` potions_in order_. Each potion has a mana capacity`mana[j]` and**must** pass through**all** the wizards sequentially to be brewed properly. The time taken by the <code>i<sup>th</sup></code> wizard on the <code>j<sup>th</sup></code> potion is <code>time<sub>ij</sub> = skill[i] * mana[j]</code>.
8+
9+
Since the brewing process is delicate, a potion**must** be passed to the next wizard immediately after the current wizard completes their work. This means the timing must be_synchronized_ so that each wizard begins working on a potion**exactly** when it arrives.
10+
11+
Return the**minimum** amount of time required for the potions to be brewed properly.
12+
13+
**Example 1:**
14+
15+
**Input:** skill =[1,5,2,4], mana =[5,1,4,2]
16+
17+
**Output:** 110
18+
19+
**Explanation:**
20+
21+
| Potion Number| Start time| Wizard 0 done by| Wizard 1 done by| Wizard 2 done by| Wizard 3 done by|
22+
|--------------|-----------|------------------|------------------|------------------|------------------|
23+
| 0| 0| 5| 30| 40| 60|
24+
| 1| 52| 53| 58| 60| 64|
25+
| 2| 54| 58| 78| 86| 102|
26+
| 3| 86| 88| 98| 102| 110|
27+
28+
As an example for why wizard 0 cannot start working on the 1<sup>st</sup> potion before time`t = 52`, consider the case where the wizards started preparing the 1<sup>st</sup> potion at time`t = 50`. At time`t = 58`, wizard 2 is done with the 1<sup>st</sup> potion, but wizard 3 will still be working on the 0<sup>th</sup> potion till time`t = 60`.
29+
30+
**Example 2:**
31+
32+
**Input:** skill =[1,1,1], mana =[1,1,1]
33+
34+
**Output:** 5
35+
36+
**Explanation:**
37+
38+
1. Preparation of the 0<sup>th</sup> potion begins at time`t = 0`, and is completed by time`t = 3`.
39+
2. Preparation of the 1<sup>st</sup> potion begins at time`t = 1`, and is completed by time`t = 4`.
40+
3. Preparation of the 2<sup>nd</sup> potion begins at time`t = 2`, and is completed by time`t = 5`.
41+
42+
**Example 3:**
43+
44+
**Input:** skill =[1,2,3,4], mana =[1,2]
45+
46+
**Output:** 21
47+
48+
**Constraints:**
49+
50+
*`n == skill.length`
51+
*`m == mana.length`
52+
*`1 <= n, m <= 5000`
53+
*`1 <= mana[i], skill[i] <= 5000`
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
packageg3401_3500.s3495_minimum_operations_to_make_array_elements_zero;
2+
3+
// #Hard #Array #Math #Bit_Manipulation #2025_03_24_Time_9_ms_(99.71%)_Space_101.35_MB_(52.17%)
4+
5+
publicclassSolution {
6+
publiclongminOperations(int[][]queries) {
7+
longresult =0;
8+
for (int[]query :queries) {
9+
longv =4;
10+
longreq =1;
11+
longtotalReq =0;
12+
while (query[0] >=v) {
13+
v *=4;
14+
req++;
15+
}
16+
longgroup;
17+
if (query[1] <v) {
18+
group =query[1] -query[0] +1L;
19+
totalReq +=group *req;
20+
result += (totalReq +1) /2;
21+
continue;
22+
}
23+
group =v -query[0];
24+
totalReq +=group *req;
25+
longbottom =v;
26+
while (true) {
27+
v *=4;
28+
req++;
29+
if (query[1] <v) {
30+
group =query[1] -bottom +1;
31+
totalReq +=group *req;
32+
break;
33+
}
34+
group =v -bottom;
35+
totalReq +=group *req;
36+
bottom =v;
37+
}
38+
result += (totalReq +1) /2;
39+
}
40+
returnresult;
41+
}
42+
}
Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
3495\. Minimum Operations to Make Array Elements Zero
2+
3+
Hard
4+
5+
You are given a 2D array`queries`, where`queries[i]` is of the form`[l, r]`. Each`queries[i]` defines an array of integers`nums` consisting of elements ranging from`l` to`r`, both**inclusive**.
6+
7+
In one operation, you can:
8+
9+
* Select two integers`a` and`b` from the array.
10+
* Replace them with`floor(a / 4)` and`floor(b / 4)`.
11+
12+
Your task is to determine the**minimum** number of operations required to reduce all elements of the array to zero for each query. Return the sum of the results for all queries.
13+
14+
**Example 1:**
15+
16+
**Input:** queries =[[1,2],[2,4]]
17+
18+
**Output:** 3
19+
20+
**Explanation:**
21+
22+
For`queries[0]`:
23+
24+
* The initial array is`nums = [1, 2]`.
25+
* In the first operation, select`nums[0]` and`nums[1]`. The array becomes`[0, 0]`.
26+
* The minimum number of operations required is 1.
27+
28+
For`queries[1]`:
29+
30+
* The initial array is`nums = [2, 3, 4]`.
31+
* In the first operation, select`nums[0]` and`nums[2]`. The array becomes`[0, 3, 1]`.
32+
* In the second operation, select`nums[1]` and`nums[2]`. The array becomes`[0, 0, 0]`.
33+
* The minimum number of operations required is 2.
34+
35+
The output is`1 + 2 = 3`.
36+
37+
**Example 2:**
38+
39+
**Input:** queries =[[2,6]]
40+
41+
**Output:** 4
42+
43+
**Explanation:**
44+
45+
For`queries[0]`:
46+
47+
* The initial array is`nums = [2, 3, 4, 5, 6]`.
48+
* In the first operation, select`nums[0]` and`nums[3]`. The array becomes`[0, 3, 4, 1, 6]`.
49+
* In the second operation, select`nums[2]` and`nums[4]`. The array becomes`[0, 3, 1, 1, 1]`.
50+
* In the third operation, select`nums[1]` and`nums[2]`. The array becomes`[0, 0, 0, 1, 1]`.
51+
* In the fourth operation, select`nums[3]` and`nums[4]`. The array becomes`[0, 0, 0, 0, 0]`.
52+
* The minimum number of operations required is 4.
53+
54+
The output is 4.
55+
56+
**Constraints:**
57+
58+
* <code>1 <= queries.length <= 10<sup>5</sup></code>
59+
*`queries[i].length == 2`
60+
*`queries[i] == [l, r]`
61+
* <code>1 <= l < r <= 10<sup>9</sup></code>
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
packageg3401_3500.s3492_maximum_containers_on_a_ship;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidmaxContainers() {
11+
assertThat(newSolution().maxContainers(2,3,15),equalTo(4));
12+
}
13+
14+
@Test
15+
voidmaxContainers2() {
16+
assertThat(newSolution().maxContainers(3,5,20),equalTo(4));
17+
}
18+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp