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

Commit1339de0

Browse files
authored
Added tasks 2857-2861
1 parent3cd22a8 commit1339de0

File tree

15 files changed

+643
-0
lines changed

15 files changed

+643
-0
lines changed
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
packageg2801_2900.s2857_count_pairs_of_points_with_distance_k;
2+
3+
// #Medium #Array #Hash_Table #Bit_Manipulation
4+
// #2023_12_19_Time_250_ms_(84.21%)_Space_68.6_MB_(89.47%)
5+
6+
importjava.util.HashMap;
7+
importjava.util.List;
8+
importjava.util.Map;
9+
10+
publicclassSolution {
11+
publicintcountPairs(List<List<Integer>>c,intk) {
12+
intans =0;
13+
Map<Long,Integer>map =newHashMap<>();
14+
for (List<Integer>p :c) {
15+
intp0 =p.get(0);
16+
intp1 =p.get(1);
17+
for (inti =0;i <=k;i++) {
18+
intx1 =i ^p0;
19+
inty1 = (k -i) ^p1;
20+
longkey2 =hash(x1,y1);
21+
if (map.containsKey(key2)) {
22+
ans +=map.get(key2);
23+
}
24+
}
25+
longkey =hash(p0,p1);
26+
map.put(key,map.getOrDefault(key,0) +1);
27+
}
28+
returnans;
29+
}
30+
31+
privatelonghash(intx1,inty1) {
32+
longr = (long)1e8;
33+
returnx1 *r +y1;
34+
}
35+
}
Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
2857\. Count Pairs of Points With Distance k
2+
3+
Medium
4+
5+
You are given a**2D** integer array`coordinates` and an integer`k`, where <code>coordinates[i] =[x<sub>i</sub>, y<sub>i</sub>]</code> are the coordinates of the <code>i<sup>th</sup></code> point in a 2D plane.
6+
7+
We define the**distance** between two points <code>(x<sub>1</sub>, y<sub>1</sub>)</code> and <code>(x<sub>2</sub>, y<sub>2</sub>)</code> as`(x1 XOR x2) + (y1 XOR y2)` where`XOR` is the bitwise`XOR` operation.
8+
9+
Return_the number of pairs_`(i, j)`_such that_`i < j`_and the distance between points_`i`_and_`j`_is equal to_`k`.
10+
11+
**Example 1:**
12+
13+
**Input:** coordinates =[[1,2],[4,2],[1,3],[5,2]], k = 5
14+
15+
**Output:** 2
16+
17+
**Explanation:** We can choose the following pairs:
18+
- (0,1): Because we have (1 XOR 4) + (2 XOR 2) = 5.
19+
- (2,3): Because we have (1 XOR 5) + (3 XOR 2) = 5.
20+
21+
**Example 2:**
22+
23+
**Input:** coordinates =[[1,3],[1,3],[1,3],[1,3],[1,3]], k = 0
24+
25+
**Output:** 10
26+
27+
**Explanation:** Any two chosen pairs will have a distance of 0. There are 10 ways to choose two pairs.
28+
29+
**Constraints:**
30+
31+
*`2 <= coordinates.length <= 50000`
32+
* <code>0 <= x<sub>i</sub>, y<sub>i</sub> <= 10<sup>6</sup></code>
33+
*`0 <= k <= 100`
Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
packageg2801_2900.s2858_minimum_edge_reversals_so_every_node_is_reachable;
2+
3+
// #Hard #Dynamic_Programming #Graph #Depth_First_Search #Breadth_First_Search
4+
// #2023_12_19_Time_52_ms_(92.31%)_Space_119.5_MB_(75.38%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.LinkedList;
8+
importjava.util.List;
9+
importjava.util.Queue;
10+
11+
publicclassSolution {
12+
publicint[]minEdgeReversals(intn,int[][]edges) {
13+
List<int[]>[]nexts =newList[n];
14+
for (inti =0;i <n;i++) {
15+
nexts[i] =newArrayList<>();
16+
}
17+
for (int[]edge :edges) {
18+
intu =edge[0];
19+
intv =edge[1];
20+
nexts[u].add(newint[] {1,v});
21+
nexts[v].add(newint[] {-1,u});
22+
}
23+
int[]res =newint[n];
24+
for (inti =0;i <n;i++) {
25+
res[i] = -1;
26+
}
27+
res[0] =dfs(nexts,0, -1);
28+
Queue<Integer>queue =newLinkedList<>();
29+
queue.add(0);
30+
while (!queue.isEmpty()) {
31+
Integerindex =queue.remove();
32+
intval =res[index];
33+
List<int[]>next =nexts[index];
34+
for (int[]node :next) {
35+
if (res[node[1]] == -1) {
36+
if (node[0] ==1) {
37+
res[node[1]] =val +1;
38+
}else {
39+
res[node[1]] =val -1;
40+
}
41+
queue.add(node[1]);
42+
}
43+
}
44+
}
45+
returnres;
46+
}
47+
48+
privateintdfs(List<int[]>[]nexts,intindex,intpre) {
49+
intres =0;
50+
List<int[]>next =nexts[index];
51+
for (int[]node :next) {
52+
if (node[1] !=pre) {
53+
if (node[0] == -1) {
54+
res++;
55+
}
56+
res +=dfs(nexts,node[1],index);
57+
}
58+
}
59+
returnres;
60+
}
61+
}
Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
2858\. Minimum Edge Reversals So Every Node Is Reachable
2+
3+
Hard
4+
5+
There is a**simple directed graph** with`n` nodes labeled from`0` to`n - 1`. The graph would form a**tree** if its edges were bi-directional.
6+
7+
You are given an integer`n` and a**2D** integer array`edges`, where <code>edges[i] =[u<sub>i</sub>, v<sub>i</sub>]</code> represents a**directed edge** going from node <code>u<sub>i</sub></code> to node <code>v<sub>i</sub></code>.
8+
9+
An**edge reversal** changes the direction of an edge, i.e., a directed edge going from node <code>u<sub>i</sub></code> to node <code>v<sub>i</sub></code> becomes a directed edge going from node <code>v<sub>i</sub></code> to node <code>u<sub>i</sub></code>.
10+
11+
For every node`i` in the range`[0, n - 1]`, your task is to**independently** calculate the**minimum** number of**edge reversals** required so it is possible to reach any other node starting from node`i` through a**sequence** of**directed edges**.
12+
13+
Return_an integer array_`answer`_, where_`answer[i]`_is the__**minimum** number of**edge reversals** required so it is possible to reach any other node starting from node_`i`_through a**sequence** of**directed edges**._
14+
15+
**Example 1:**
16+
17+
![](https://assets.leetcode.com/uploads/2023/08/26/image-20230826221104-3.png)
18+
19+
**Input:** n = 4, edges =[[2,0],[2,1],[1,3]]
20+
21+
**Output:**[1,1,0,2]
22+
23+
**Explanation:** The image above shows the graph formed by the edges.
24+
25+
For node 0: after reversing the edge[2,0], it is possible to reach any other node starting from node 0.
26+
27+
So, answer[0] = 1.
28+
29+
For node 1: after reversing the edge[2,1], it is possible to reach any other node starting from node 1.
30+
31+
So, answer[1] = 1.
32+
33+
For node 2: it is already possible to reach any other node starting from node 2.
34+
35+
So, answer[2] = 0.
36+
37+
For node 3: after reversing the edges[1,3] and[2,1], it is possible to reach any other node starting from node 3.
38+
39+
So, answer[3] = 2.
40+
41+
**Example 2:**
42+
43+
![](https://assets.leetcode.com/uploads/2023/08/26/image-20230826225541-2.png)
44+
45+
**Input:** n = 3, edges =[[1,2],[2,0]]
46+
47+
**Output:**[2,0,1]
48+
49+
**Explanation:** The image above shows the graph formed by the edges.
50+
51+
For node 0: after reversing the edges[2,0] and[1,2], it is possible to reach any other node starting from node 0.
52+
53+
So, answer[0] = 2.
54+
55+
For node 1: it is already possible to reach any other node starting from node 1.
56+
57+
So, answer[1] = 0.
58+
59+
For node 2: after reversing the edge[1, 2], it is possible to reach any other node starting from node 2.
60+
61+
So, answer[2] = 1.
62+
63+
**Constraints:**
64+
65+
* <code>2 <= n <= 10<sup>5</sup></code>
66+
*`edges.length == n - 1`
67+
*`edges[i].length == 2`
68+
* <code>0 <= u<sub>i</sub> == edges[i][0] < n</code>
69+
* <code>0 <= v<sub>i</sub> == edges[i][1] < n</code>
70+
* <code>u<sub>i</sub> != v<sub>i</sub></code>
71+
* The input is generated such that if the edges were bi-directional, the graph would be a tree.
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
packageg2801_2900.s2859_sum_of_values_at_indices_with_k_set_bits;
2+
3+
// #Easy #Array #Bit_Manipulation #2023_12_19_Time_1_ms_(100.00%)_Space_43.3_MB_(64.43%)
4+
5+
importjava.util.List;
6+
7+
publicclassSolution {
8+
publicintsumIndicesWithKSetBits(List<Integer>nums,intk) {
9+
intsum =0;
10+
for (inti =0;i <nums.size();i++) {
11+
if (countSetBits(i) ==k) {
12+
sum +=nums.get(i);
13+
}
14+
}
15+
returnsum;
16+
}
17+
18+
publicstaticintcountSetBits(intnum) {
19+
intcount =0;
20+
while (num >0) {
21+
num =num & (num -1);
22+
count++;
23+
}
24+
returncount;
25+
}
26+
}
Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
2859\. Sum of Values at Indices With K Set Bits
2+
3+
Easy
4+
5+
You are given a**0-indexed** integer array`nums` and an integer`k`.
6+
7+
Return_an integer that denotes the**sum** of elements in_`nums`_whose corresponding**indices** have**exactly**_`k`_set bits in their binary representation._
8+
9+
The**set bits** in an integer are the`1`'s present when it is written in binary.
10+
11+
* For example, the binary representation of`21` is`10101`, which has`3` set bits.
12+
13+
**Example 1:**
14+
15+
**Input:** nums =[5,10,1,5,2], k = 1
16+
17+
**Output:** 13
18+
19+
**Explanation:** The binary representation of the indices are:
20+
21+
0 = 000<sub>2</sub>
22+
23+
1 = 001<sub>2</sub>
24+
25+
2 = 010<sub>2</sub>
26+
27+
3 = 011<sub>2</sub>
28+
29+
4 = 100<sub>2</sub>
30+
31+
Indices 1, 2, and 4 have k = 1 set bits in their binary representation. Hence, the answer is nums[1] + nums[2] + nums[4] = 13.
32+
33+
**Example 2:**
34+
35+
**Input:** nums =[4,3,2,1], k = 2
36+
37+
**Output:** 1
38+
39+
**Explanation:** The binary representation of the indices are:
40+
41+
0 = 00<sub>2</sub>
42+
43+
1 = 01<sub>2</sub>
44+
45+
2 = 10<sub>2</sub>
46+
47+
3 = 11<sub>2</sub>
48+
49+
Only index 3 has k = 2 set bits in its binary representation. Hence, the answer is nums[3] = 1.
50+
51+
**Constraints:**
52+
53+
*`1 <= nums.length <= 1000`
54+
* <code>1 <= nums[i] <= 10<sup>5</sup></code>
55+
*`0 <= k <= 10`
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
packageg2801_2900.s2860_happy_students;
2+
3+
// #Medium #Array #Sorting #Enumeration #2023_12_19_Time_33_ms_(91.76%)_Space_55.3_MB_(82.94%)
4+
5+
importjava.util.Collections;
6+
importjava.util.List;
7+
8+
publicclassSolution {
9+
publicintcountWays(List<Integer>nums) {
10+
Collections.sort(nums);
11+
intcnt =0;
12+
intn =nums.size();
13+
if (nums.get(0) !=0) {
14+
cnt++;
15+
}
16+
for (inti =0;i <n -1;i++) {
17+
if (nums.get(i) < (i +1) && (nums.get(i +1) > (i +1))) {
18+
cnt++;
19+
}
20+
}
21+
if (n >nums.get(n -1)) {
22+
cnt++;
23+
}
24+
returncnt;
25+
}
26+
}
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
2860\. Happy Students
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums` of length`n` where`n` is the total number of students in the class. The class teacher tries to select a group of students so that all the students remain happy.
6+
7+
The <code>i<sup>th</sup></code> student will become happy if one of these two conditions is met:
8+
9+
* The student is selected and the total number of selected students is**strictly greater than**`nums[i]`.
10+
* The student is not selected and the total number of selected students is**strictly****less than**`nums[i]`.
11+
12+
Return_the number of ways to select a group of students so that everyone remains happy._
13+
14+
**Example 1:**
15+
16+
**Input:** nums =[1,1]
17+
18+
**Output:** 2
19+
20+
**Explanation:**
21+
22+
The two possible ways are:
23+
24+
The class teacher selects no student.
25+
26+
The class teacher selects both students to form the group.
27+
28+
If the class teacher selects just one student to form a group then the both students will not be happy.
29+
30+
Therefore, there are only two possible ways.
31+
32+
**Example 2:**
33+
34+
**Input:** nums =[6,0,3,3,6,7,2,7]
35+
36+
**Output:** 3
37+
38+
**Explanation:**
39+
40+
The three possible ways are:
41+
42+
The class teacher selects the student with index = 1 to form the group.
43+
44+
The class teacher selects the students with index = 1, 2, 3, 6 to form the group.
45+
46+
The class teacher selects all the students to form the group.
47+
48+
**Constraints:**
49+
50+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
51+
*`0 <= nums[i] < nums.length`

0 commit comments

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