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

Commit54d263d

Browse files
authored
Added tasks 3238-3245
1 parent6b1ee62 commit54d263d

File tree

24 files changed

+1257
-0
lines changed

24 files changed

+1257
-0
lines changed
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
packageg3201_3300.s3238_find_the_number_of_winning_players;
2+
3+
// #Easy #Array #Hash_Table #Counting #2024_08_06_Time_1_ms_(100.00%)_Space_44.5_MB_(99.46%)
4+
5+
@SuppressWarnings({"unused","java:S1172"})
6+
publicclassSolution {
7+
publicintwinningPlayerCount(intn,int[][]pick) {
8+
int[][]dp =newint[11][11];
9+
for (int[]ints :pick) {
10+
intp =ints[0];
11+
intpi =ints[1];
12+
dp[p][pi] +=1;
13+
}
14+
intcount =0;
15+
for (inti =0;i <11;i++) {
16+
booleanwin =false;
17+
for (intj =0;j <11;j++) {
18+
if (dp[i][j] >=i +1) {
19+
win =true;
20+
break;
21+
}
22+
}
23+
if (win) {
24+
count +=1;
25+
}
26+
}
27+
returncount;
28+
}
29+
}
Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
3238\. Find the Number of Winning Players
2+
3+
Easy
4+
5+
You are given an integer`n` representing the number of players in a game and a 2D array`pick` where <code>pick[i] =[x<sub>i</sub>, y<sub>i</sub>]</code> represents that the player <code>x<sub>i</sub></code> picked a ball of color <code>y<sub>i</sub></code>.
6+
7+
Player`i`**wins** the game if they pick**strictly more** than`i` balls of the**same** color. In other words,
8+
9+
* Player 0 wins if they pick any ball.
10+
* Player 1 wins if they pick at least two balls of the_same_ color.
11+
* ...
12+
* Player`i` wins if they pick at least`i + 1` balls of the_same_ color.
13+
14+
Return the number of players who**win** the game.
15+
16+
**Note** that_multiple_ players can win the game.
17+
18+
**Example 1:**
19+
20+
**Input:** n = 4, pick =[[0,0],[1,0],[1,0],[2,1],[2,1],[2,0]]
21+
22+
**Output:** 2
23+
24+
**Explanation:**
25+
26+
Player 0 and player 1 win the game, while players 2 and 3 do not win.
27+
28+
**Example 2:**
29+
30+
**Input:** n = 5, pick =[[1,1],[1,2],[1,3],[1,4]]
31+
32+
**Output:** 0
33+
34+
**Explanation:**
35+
36+
No player wins the game.
37+
38+
**Example 3:**
39+
40+
**Input:** n = 5, pick =[[1,1],[2,4],[2,4],[2,4]]
41+
42+
**Output:** 1
43+
44+
**Explanation:**
45+
46+
Player 2 wins the game by picking 3 balls with color 4.
47+
48+
**Constraints:**
49+
50+
*`2 <= n <= 10`
51+
*`1 <= pick.length <= 100`
52+
*`pick[i].length == 2`
53+
* <code>0 <= x<sub>i</sub> <= n - 1</code>
54+
* <code>0 <= y<sub>i</sub> <= 10</code>
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg3201_3300.s3239_minimum_number_of_flips_to_make_binary_grid_palindromic_i;
2+
3+
// #Medium #Array #Matrix #Two_Pointers #2024_08_06_Time_3_ms_(100.00%)_Space_111.4_MB_(41.81%)
4+
5+
publicclassSolution {
6+
publicintminFlips(int[][]grid) {
7+
intm =grid.length;
8+
intn =grid[0].length;
9+
introwFlips =0;
10+
for (inti =0;i <m /2;i++) {
11+
for (intj =0;j <n;j++) {
12+
intsum =grid[i][j] +grid[m -1 -i][j];
13+
rowFlips +=Math.min(sum,2 -sum);
14+
}
15+
}
16+
intcolumnFlips =0;
17+
for (intj =0;j <n /2;j++) {
18+
for (int[]ints :grid) {
19+
intsum =ints[j] +ints[n -1 -j];
20+
columnFlips +=Math.min(sum,2 -sum);
21+
}
22+
}
23+
returnMath.min(rowFlips,columnFlips);
24+
}
25+
}
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
3239\. Minimum Number of Flips to Make Binary Grid Palindromic I
2+
3+
Medium
4+
5+
You are given an`m x n` binary matrix`grid`.
6+
7+
A row or column is considered**palindromic** if its values read the same forward and backward.
8+
9+
You can**flip** any number of cells in`grid` from`0` to`1`, or from`1` to`0`.
10+
11+
Return the**minimum** number of cells that need to be flipped to make**either** all rows**palindromic** or all columns**palindromic**.
12+
13+
**Example 1:**
14+
15+
**Input:** grid =[[1,0,0],[0,0,0],[0,0,1]]
16+
17+
**Output:** 2
18+
19+
**Explanation:**
20+
21+
![](https://assets.leetcode.com/uploads/2024/07/07/screenshot-from-2024-07-08-00-20-10.png)
22+
23+
Flipping the highlighted cells makes all the rows palindromic.
24+
25+
**Example 2:**
26+
27+
**Input:** grid =[[0,1],[0,1],[0,0]]
28+
29+
**Output:** 1
30+
31+
**Explanation:**
32+
33+
![](https://assets.leetcode.com/uploads/2024/07/07/screenshot-from-2024-07-08-00-31-23.png)
34+
35+
Flipping the highlighted cell makes all the columns palindromic.
36+
37+
**Example 3:**
38+
39+
**Input:** grid =[[1],[0]]
40+
41+
**Output:** 0
42+
43+
**Explanation:**
44+
45+
All rows are already palindromic.
46+
47+
**Constraints:**
48+
49+
*`m == grid.length`
50+
*`n == grid[i].length`
51+
* <code>1 <= m * n <= 2 * 10<sup>5</sup></code>
52+
*`0 <= grid[i][j] <= 1`
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
packageg3201_3300.s3240_minimum_number_of_flips_to_make_binary_grid_palindromic_ii;
2+
3+
// #Medium #Array #Matrix #Two_Pointers #2024_08_06_Time_3_ms_(96.90%)_Space_93.8_MB_(76.14%)
4+
5+
publicclassSolution {
6+
publicintminFlips(int[][]grid) {
7+
intres =0;
8+
intone =0;
9+
intdiff =0;
10+
intm =grid.length;
11+
intn =grid[0].length;
12+
// Handle quadrants
13+
for (inti =0;i <m /2; ++i) {
14+
for (intj =0;j <n /2; ++j) {
15+
intv =
16+
grid[i][j]
17+
+grid[i][n -1 -j]
18+
+grid[m -1 -i][j]
19+
+grid[m -1 -i][n -1 -j];
20+
res +=Math.min(v,4 -v);
21+
}
22+
}
23+
// Handle middle column
24+
if (n %2 >0) {
25+
for (inti =0;i <m /2; ++i) {
26+
diff +=grid[i][n /2] ^grid[m -1 -i][n /2];
27+
one +=grid[i][n /2] +grid[m -1 -i][n /2];
28+
}
29+
}
30+
// Handle middle row
31+
if (m %2 >0) {
32+
for (intj =0;j <n /2; ++j) {
33+
diff +=grid[m /2][j] ^grid[m /2][n -1 -j];
34+
one +=grid[m /2][j] +grid[m /2][n -1 -j];
35+
}
36+
}
37+
// Handle center point
38+
if (n %2 >0 &&m %2 >0) {
39+
res +=grid[m /2][n /2];
40+
}
41+
// Divisible by 4
42+
if (diff ==0 &&one %4 >0) {
43+
res +=2;
44+
}
45+
returnres +diff;
46+
}
47+
}
Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
3240\. Minimum Number of Flips to Make Binary Grid Palindromic II
2+
3+
Medium
4+
5+
You are given an`m x n` binary matrix`grid`.
6+
7+
A row or column is considered**palindromic** if its values read the same forward and backward.
8+
9+
You can**flip** any number of cells in`grid` from`0` to`1`, or from`1` to`0`.
10+
11+
Return the**minimum** number of cells that need to be flipped to make**all** rows and columns**palindromic**, and the total number of`1`'s in`grid`**divisible** by`4`.
12+
13+
**Example 1:**
14+
15+
**Input:** grid =[[1,0,0],[0,1,0],[0,0,1]]
16+
17+
**Output:** 3
18+
19+
**Explanation:**
20+
21+
![](https://assets.leetcode.com/uploads/2024/08/01/image.png)
22+
23+
**Example 2:**
24+
25+
**Input:** grid =[[0,1],[0,1],[0,0]]
26+
27+
**Output:** 2
28+
29+
**Explanation:**
30+
31+
![](https://assets.leetcode.com/uploads/2024/07/08/screenshot-from-2024-07-09-01-37-48.png)
32+
33+
**Example 3:**
34+
35+
**Input:** grid =[[1],[1]]
36+
37+
**Output:** 2
38+
39+
**Explanation:**
40+
41+
![](https://assets.leetcode.com/uploads/2024/08/01/screenshot-from-2024-08-01-23-05-26.png)
42+
43+
**Constraints:**
44+
45+
*`m == grid.length`
46+
*`n == grid[i].length`
47+
* <code>1 <= m * n <= 2 * 10<sup>5</sup></code>
48+
*`0 <= grid[i][j] <= 1`
Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
packageg3201_3300.s3241_time_taken_to_mark_all_nodes;
2+
3+
// #Hard #Dynamic_Programming #Tree #Graph #Depth_First_Search
4+
// #2024_08_06_Time_39_ms_(100.00%)_Space_115.8_MB_(83.90%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
privateint[]head;
10+
privateint[]nxt;
11+
privateint[]to;
12+
privateint[]last;
13+
privateint[]lastNo;
14+
privateint[]second;
15+
privateint[]ans;
16+
17+
publicint[]timeTaken(int[][]edges) {
18+
intn =edges.length +1;
19+
head =newint[n];
20+
nxt =newint[n <<1];
21+
to =newint[n <<1];
22+
Arrays.fill(head, -1);
23+
inti =0;
24+
intj =2;
25+
while (i <edges.length) {
26+
intu =edges[i][0];
27+
intv =edges[i][1];
28+
nxt[j] =head[u];
29+
head[u] =j;
30+
to[j] =v;
31+
j++;
32+
nxt[j] =head[v];
33+
head[v] =j;
34+
to[j] =u;
35+
j++;
36+
i++;
37+
}
38+
last =newint[n];
39+
lastNo =newint[n];
40+
second =newint[n];
41+
ans =newint[n];
42+
dfs(-1,0);
43+
System.arraycopy(last,0,ans,0,n);
44+
dfs2(-1,0,0);
45+
returnans;
46+
}
47+
48+
privatevoiddfs2(intf,intu,intpreLast) {
49+
inte =head[u];
50+
intv;
51+
while (e != -1) {
52+
v =to[e];
53+
if (f !=v) {
54+
intpl;
55+
if (v ==lastNo[u]) {
56+
pl =Math.max(preLast,second[u]) + ((u &1) ==0 ?2 :1);
57+
}else {
58+
pl =Math.max(preLast,last[u]) + ((u &1) ==0 ?2 :1);
59+
}
60+
ans[v] =Math.max(ans[v],pl);
61+
dfs2(u,v,pl);
62+
}
63+
e =nxt[e];
64+
}
65+
}
66+
67+
privatevoiddfs(intf,intu) {
68+
inte =head[u];
69+
intv;
70+
while (e != -1) {
71+
v =to[e];
72+
if (f !=v) {
73+
dfs(u,v);
74+
intt =last[v] + ((v &1) ==0 ?2 :1);
75+
if (last[u] <t) {
76+
second[u] =last[u];
77+
last[u] =t;
78+
lastNo[u] =v;
79+
}elseif (second[u] <t) {
80+
second[u] =t;
81+
}
82+
}
83+
e =nxt[e];
84+
}
85+
}
86+
}

0 commit comments

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