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

Commit8800c47

Browse files
authored
Added tasks 2580-2584
1 parentaff631d commit8800c47

File tree

15 files changed

+627
-0
lines changed

15 files changed

+627
-0
lines changed
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
packageg2501_2600.s2580_count_ways_to_group_overlapping_ranges;
2+
3+
// #Medium #Array #Sorting #2023_08_22_Time_16_ms_(98.28%)_Space_76.7_MB_(93.97%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
privatestaticfinalintMOD = (int)1e9 +7;
9+
10+
privatelongpowMod(longe) {
11+
longans =1;
12+
longb =2;
13+
while (e !=0) {
14+
if ((e &1) ==1) {
15+
ans *=b;
16+
ans %=MOD;
17+
}
18+
b *=b;
19+
b %=MOD;
20+
e >>=1;
21+
}
22+
returnans;
23+
}
24+
25+
publicintcountWays(int[][]ranges) {
26+
intcnt =1;
27+
Arrays.sort(ranges, (a,b) ->a[0] !=b[0] ?a[0] -b[0] :a[1] -b[1]);
28+
int[]curr =ranges[0];
29+
for (inti =1;i <ranges.length;i++) {
30+
if (ranges[i][1] <curr[0] ||ranges[i][0] >curr[1]) {
31+
++cnt;
32+
curr =ranges[i];
33+
}else {
34+
curr[1] =Math.max(curr[1],ranges[i][1]);
35+
}
36+
}
37+
return (int)powMod(cnt);
38+
}
39+
}
Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
2580\. Count Ways to Group Overlapping Ranges
2+
3+
Medium
4+
5+
You are given a 2D integer array`ranges` where <code>ranges[i] =[start<sub>i</sub>, end<sub>i</sub>]</code> denotes that all integers between <code>start<sub>i</sub></code> and <code>end<sub>i</sub></code> (both**inclusive**) are contained in the <code>i<sup>th</sup></code> range.
6+
7+
You are to split`ranges` into**two** (possibly empty) groups such that:
8+
9+
* Each range belongs to exactly one group.
10+
* Any two**overlapping** ranges must belong to the**same** group.
11+
12+
Two ranges are said to be**overlapping** if there exists at least**one** integer that is present in both ranges.
13+
14+
* For example,`[1, 3]` and`[2, 5]` are overlapping because`2` and`3` occur in both ranges.
15+
16+
Return_the**total number** of ways to split_`ranges`_into two groups_. Since the answer may be very large, return it**modulo** <code>10<sup>9</sup> + 7</code>.
17+
18+
**Example 1:**
19+
20+
**Input:** ranges =[[6,10],[5,15]]
21+
22+
**Output:** 2
23+
24+
**Explanation:**
25+
26+
The two ranges are overlapping, so they must be in the same group.
27+
28+
Thus, there are two possible ways:
29+
30+
- Put both the ranges together in group 1.
31+
32+
- Put both the ranges together in group 2.
33+
34+
**Example 2:**
35+
36+
**Input:** ranges =[[1,3],[10,20],[2,5],[4,8]]
37+
38+
**Output:** 4
39+
40+
**Explanation:**
41+
42+
Ranges[1,3], and[2,5] are overlapping. So, they must be in the same group.
43+
44+
Again, ranges[2,5] and[4,8] are also overlapping. So, they must also be in the same group.
45+
46+
Thus, there are four possible ways to group them:
47+
48+
- All the ranges in group 1.
49+
50+
- All the ranges in group 2.
51+
52+
- Ranges[1,3],[2,5], and[4,8] in group 1 and[10,20] in group 2.
53+
54+
- Ranges[1,3],[2,5], and[4,8] in group 2 and[10,20] in group 1.
55+
56+
**Constraints:**
57+
58+
* <code>1 <= ranges.length <= 10<sup>5</sup></code>
59+
*`ranges[i].length == 2`
60+
* <code>0 <= start<sub>i</sub> <= end<sub>i</sub> <= 10<sup>9</sup></code>
Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
packageg2501_2600.s2581_count_number_of_possible_root_nodes;
2+
3+
// #Hard #Hash_Table #Dynamic_Programming #Depth_First_Search #Tree
4+
// #2023_08_22_Time_38_ms_(100.00%)_Space_106.2_MB_(96.15%)
5+
6+
importjava.util.LinkedList;
7+
importjava.util.List;
8+
9+
publicclassSolution {
10+
publicintrootCount(int[][]eg,int[][]gu,intk) {
11+
intn =eg.length +1;
12+
List<Integer>[]g =newList[n];
13+
for (inti =0;i <n;i++) {
14+
g[i] =newLinkedList<>();
15+
}
16+
for (int[]a :eg) {
17+
g[a[0]].add(a[1]);
18+
g[a[1]].add(a[0]);
19+
}
20+
intall =0;
21+
int[]add =newint[n];
22+
int[]par =newint[n];
23+
dfs1(g,0, -1,par);
24+
for (int[]a :gu) {
25+
if (par[a[1]] ==a[0]) {
26+
all++;
27+
add[a[1]]--;
28+
}else {
29+
add[a[0]]++;
30+
}
31+
}
32+
dfs2(g,0, -1,add);
33+
intans =0;
34+
for (inti :add) {
35+
if (i +all >=k) {
36+
ans++;
37+
}
38+
}
39+
returnans;
40+
}
41+
42+
privatevoiddfs1(List<Integer>[]g,ints,intp,int[]par) {
43+
par[s] =p;
44+
for (inti :g[s]) {
45+
if (i !=p) {
46+
dfs1(g,i,s,par);
47+
}
48+
}
49+
}
50+
51+
privatevoiddfs2(List<Integer>[]g,ints,intp,int[]add) {
52+
for (inti :g[s]) {
53+
if (i !=p) {
54+
add[i] +=add[s];
55+
dfs2(g,i,s,add);
56+
}
57+
}
58+
}
59+
}
Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
2581\. Count Number of Possible Root Nodes
2+
3+
Hard
4+
5+
Alice has an undirected tree with`n` nodes labeled from`0` to`n - 1`. The tree is represented as a 2D integer array`edges` of length`n - 1` where <code>edges[i] =[a<sub>i</sub>, b<sub>i</sub>]</code> indicates that there is an edge between nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code> in the tree.
6+
7+
Alice wants Bob to find the root of the tree. She allows Bob to make several**guesses** about her tree. In one guess, he does the following:
8+
9+
* Chooses two**distinct** integers`u` and`v` such that there exists an edge`[u, v]` in the tree.
10+
* He tells Alice that`u` is the**parent** of`v` in the tree.
11+
12+
Bob's guesses are represented by a 2D integer array`guesses` where <code>guesses[j] =[u<sub>j</sub>, v<sub>j</sub>]</code> indicates Bob guessed <code>u<sub>j</sub></code> to be the parent of <code>v<sub>j</sub></code>.
13+
14+
Alice being lazy, does not reply to each of Bob's guesses, but just says that**at least**`k` of his guesses are`true`.
15+
16+
Given the 2D integer arrays`edges`,`guesses` and the integer`k`, return_the**number of possible nodes** that can be the root of Alice's tree_. If there is no such tree, return`0`.
17+
18+
**Example 1:**
19+
20+
![](https://assets.leetcode.com/uploads/2022/12/19/ex-1.png)
21+
22+
**Input:** edges =[[0,1],[1,2],[1,3],[4,2]], guesses =[[1,3],[0,1],[1,0],[2,4]], k = 3
23+
24+
**Output:** 3
25+
26+
**Explanation:**
27+
28+
Root = 0, correct guesses =[1,3],[0,1],[2,4]
29+
30+
Root = 1, correct guesses =[1,3],[1,0],[2,4]
31+
32+
Root = 2, correct guesses =[1,3],[1,0],[2,4]
33+
34+
Root = 3, correct guesses =[1,0],[2,4]
35+
36+
Root = 4, correct guesses =[1,3],[1,0]
37+
38+
Considering 0, 1, or 2 as root node leads to 3 correct guesses.
39+
40+
**Example 2:**
41+
42+
![](https://assets.leetcode.com/uploads/2022/12/19/ex-2.png)
43+
44+
**Input:** edges =[[0,1],[1,2],[2,3],[3,4]], guesses =[[1,0],[3,4],[2,1],[3,2]], k = 1
45+
46+
**Output:** 5
47+
48+
**Explanation:**
49+
50+
Root = 0, correct guesses =[3,4]
51+
52+
Root = 1, correct guesses =[1,0],[3,4]
53+
54+
Root = 2, correct guesses =[1,0],[2,1],[3,4]
55+
56+
Root = 3, correct guesses =[1,0],[2,1],[3,2],[3,4]
57+
58+
Root = 4, correct guesses =[1,0],[2,1],[3,2]
59+
60+
Considering any node as root will give at least 1 correct guess.
61+
62+
**Constraints:**
63+
64+
*`edges.length == n - 1`
65+
* <code>2 <= n <= 10<sup>5</sup></code>
66+
* <code>1 <= guesses.length <= 10<sup>5</sup></code>
67+
* <code>0 <= a<sub>i</sub>, b<sub>i</sub>, u<sub>j</sub>, v<sub>j</sub> <= n - 1</code>
68+
* <code>a<sub>i</sub> != b<sub>i</sub></code>
69+
* <code>u<sub>j</sub> != v<sub>j</sub></code>
70+
*`edges` represents a valid tree.
71+
*`guesses[j]` is an edge of the tree.
72+
*`guesses` is unique.
73+
*`0 <= k <= guesses.length`
Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
packageg2501_2600.s2582_pass_the_pillow;
2+
3+
// #Easy #Math #Simulation #2023_08_22_Time_0_ms_(100.00%)_Space_39.3_MB_(46.65%)
4+
5+
publicclassSolution {
6+
publicintpassThePillow(intn,inttime) {
7+
introundTrip = (n -1) *2;
8+
time =time %roundTrip;
9+
if (time <n) {
10+
returntime +1;
11+
}
12+
returnn - (time -n +1);
13+
}
14+
}
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
2582\. Pass the Pillow
2+
3+
Easy
4+
5+
There are`n` people standing in a line labeled from`1` to`n`. The first person in the line is holding a pillow initially. Every second, the person holding the pillow passes it to the next person standing in the line. Once the pillow reaches the end of the line, the direction changes, and people continue passing the pillow in the opposite direction.
6+
7+
* For example, once the pillow reaches the <code>n<sup>th</sup></code> person they pass it to the <code>n - 1<sup>th</sup></code> person, then to the <code>n - 2<sup>th</sup></code> person and so on.
8+
9+
Given the two positive integers`n` and`time`, return_the index of the person holding the pillow after_`time`_seconds_.
10+
11+
**Example 1:**
12+
13+
**Input:** n = 4, time = 5
14+
15+
**Output:** 2
16+
17+
**Explanation:** People pass the pillow in the following way: 1 -> 2 -> 3 -> 4 -> 3 -> 2. Afer five seconds, the pillow is given to the 2<sup>nd</sup> person.
18+
19+
**Example 2:**
20+
21+
**Input:** n = 3, time = 2
22+
23+
**Output:** 3
24+
25+
**Explanation:** People pass the pillow in the following way: 1 -> 2 -> 3. Afer two seconds, the pillow is given to the 3<sup>r</sup><sup>d</sup> person.
26+
27+
**Constraints:**
28+
29+
*`2 <= n <= 1000`
30+
*`1 <= time <= 1000`
Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
packageg2501_2600.s2583_kth_largest_sum_in_a_binary_tree;
2+
3+
// #Medium #Breadth_First_Search #Tree #Binary_Search
4+
// #2023_08_22_Time_13_ms_(99.83%)_Space_60.3_MB_(92.18%)
5+
6+
importcom_github_leetcode.TreeNode;
7+
importjava.util.ArrayList;
8+
importjava.util.Collections;
9+
importjava.util.LinkedList;
10+
importjava.util.List;
11+
importjava.util.Queue;
12+
importjava.util.Random;
13+
14+
/*
15+
* Definition for a binary tree node.
16+
* public class TreeNode {
17+
* int val;
18+
* TreeNode left;
19+
* TreeNode right;
20+
* TreeNode() {}
21+
* TreeNode(int val) { this.val = val; }
22+
* TreeNode(int val, TreeNode left, TreeNode right) {
23+
* this.val = val;
24+
* this.left = left;
25+
* this.right = right;
26+
* }
27+
* }
28+
*/
29+
@SuppressWarnings("java:S2245")
30+
publicclassSolution {
31+
privatefinalRandomrandom =newRandom();
32+
33+
publiclongkthLargestLevelSum(TreeNoderoot,intk) {
34+
List<Long>ans =newArrayList<>();
35+
Queue<TreeNode>q =newLinkedList<>();
36+
q.add(root);
37+
while (!q.isEmpty()) {
38+
longsum =0;
39+
intsize =q.size();
40+
for (inti =0;i <size;i++) {
41+
TreeNodecurr =q.remove();
42+
sum +=curr.val;
43+
if (curr.left !=null) {
44+
q.add(curr.left);
45+
}
46+
if (curr.right !=null) {
47+
q.add(curr.right);
48+
}
49+
}
50+
ans.add(sum);
51+
}
52+
if (k >ans.size()) {
53+
return -1;
54+
}
55+
k =ans.size() -k;
56+
intstart =0;
57+
intidx;
58+
intend =ans.size() -1;
59+
while (true) {
60+
idx =random.nextInt(end -start +1) +start;
61+
Longpiv =ans.get(idx);
62+
Collections.swap(ans,idx,end);
63+
idx =start;
64+
for (inti =start;i <=end;i++) {
65+
if (ans.get(i) <=piv) {
66+
Collections.swap(ans,i,idx++);
67+
}
68+
}
69+
idx--;
70+
if (idx <k) {
71+
start =idx +1;
72+
}elseif (idx >k) {
73+
end =idx -1;
74+
}else {
75+
break;
76+
}
77+
}
78+
returnans.get(idx);
79+
}
80+
}

0 commit comments

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