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

Commitc8468e8

Browse files
authored
Added tasks 2682-2693
1 parent8ad626c commitc8468e8

File tree

15 files changed

+506
-0
lines changed

15 files changed

+506
-0
lines changed
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
packageg2601_2700.s2682_find_the_losers_of_the_circular_game;
2+
3+
// #Easy #Array #Hash_Table #Simulation #2023_09_12_Time_1_ms_(100.00%)_Space_43.6_MB_(51.49%)
4+
5+
publicclassSolution {
6+
publicint[]circularGameLosers(intn,intk) {
7+
int[]pointsMap =newint[n];
8+
intfriend =0;
9+
intturn =1;
10+
while (true) {
11+
pointsMap[friend] =pointsMap[friend] +1;
12+
if (pointsMap[friend] ==2) {
13+
break;
14+
}
15+
friend = (friend +turn *k) %n;
16+
turn++;
17+
}
18+
int[]result =newint[n - (turn -1)];
19+
inti =0;
20+
for (intindex =0;index <pointsMap.length;index++) {
21+
if (pointsMap[index] ==0) {
22+
result[i] =index +1;
23+
i++;
24+
}
25+
}
26+
returnresult;
27+
}
28+
}
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
2682\. Find the Losers of the Circular Game
2+
3+
Easy
4+
5+
There are`n` friends that are playing a game. The friends are sitting in a circle and are numbered from`1` to`n` in**clockwise order**. More formally, moving clockwise from the <code>i<sup>th</sup></code> friend brings you to the <code>(i+1)<sup>th</sup></code> friend for`1 <= i < n`, and moving clockwise from the <code>n<sup>th</sup></code> friend brings you to the <code>1<sup>st</sup></code> friend.
6+
7+
The rules of the game are as follows:
8+
9+
<code>1<sup>st</sup></code> friend receives the ball.
10+
11+
* After that, <code>1<sup>st</sup></code> friend passes it to the friend who is`k` steps away from them in the**clockwise** direction.
12+
* After that, the friend who receives the ball should pass it to the friend who is`2 * k` steps away from them in the**clockwise** direction.
13+
* After that, the friend who receives the ball should pass it to the friend who is`3 * k` steps away from them in the**clockwise** direction, and so on and so forth.
14+
15+
In other words, on the <code>i<sup>th</sup></code> turn, the friend holding the ball should pass it to the friend who is`i * k` steps away from them in the**clockwise** direction.
16+
17+
The game is finished when some friend receives the ball for the second time.
18+
19+
The**losers** of the game are friends who did not receive the ball in the entire game.
20+
21+
Given the number of friends,`n`, and an integer`k`, return_the array answer, which contains the losers of the game in the**ascending** order_.
22+
23+
**Example 1:**
24+
25+
**Input:** n = 5, k = 2
26+
27+
**Output:**[4,5]
28+
29+
**Explanation:** The game goes as follows:
30+
1) Start at 1<sup>st</sup> friend and pass the ball to the friend who is 2 steps away from them - 3<sup>rd</sup> friend.
31+
2) 3<sup>rd</sup> friend passes the ball to the friend who is 4 steps away from them - 2<sup>nd</sup> friend.
32+
3) 2<sup>nd</sup> friend passes the ball to the friend who is 6 steps away from them - 3<sup>rd</sup> friend.
33+
4) The game ends as 3<sup>rd</sup> friend receives the ball for the second time.
34+
35+
**Example 2:**
36+
37+
**Input:** n = 4, k = 4
38+
39+
**Output:**[2,3,4]
40+
41+
**Explanation:** The game goes as follows:
42+
1) Start at the 1<sup>st</sup> friend and pass the ball to the friend who is 4 steps away from them - 1<sup>st</sup> friend.
43+
2) The game ends as 1<sup>st</sup> friend receives the ball for the second time.
44+
45+
**Constraints:**
46+
47+
*`1 <= k <= n <= 50`
Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
packageg2601_2700.s2683_neighboring_bitwise_xor;
2+
3+
// #Medium #Array #Bit_Manipulation #2023_09_12_Time_2_ms_(100.00%)_Space_59.9_MB_(62.03%)
4+
5+
publicclassSolution {
6+
publicbooleandoesValidArrayExist(int[]derived) {
7+
intxor =0;
8+
for (intj :derived) {
9+
xor =xor ^j;
10+
}
11+
returnxor ==0;
12+
}
13+
}
Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
2683\. Neighboring Bitwise XOR
2+
3+
Medium
4+
5+
A**0-indexed** array`derived` with length`n` is derived by computing the**bitwise XOR** (⊕) of adjacent values in a**binary array**`original` of length`n`.
6+
7+
Specifically, for each index`i` in the range`[0, n - 1]`:
8+
9+
* If`i = n - 1`, then`derived[i] = original[i] ⊕ original[0]`.
10+
* Otherwise,`derived[i] = original[i] ⊕ original[i + 1]`.
11+
12+
Given an array`derived`, your task is to determine whether there exists a**valid binary array**`original` that could have formed`derived`.
13+
14+
Return_**true** if such an array exists or**false** otherwise._
15+
16+
* A binary array is an array containing only**0's** and**1's**
17+
18+
**Example 1:**
19+
20+
**Input:** derived =[1,1,0]
21+
22+
**Output:** true
23+
24+
**Explanation:** A valid original array that gives derived is[0,1,0].
25+
26+
derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1
27+
28+
derived[1] = original[1] ⊕ original[2] = 1 ⊕ 0 = 1
29+
30+
derived[2] = original[2] ⊕ original[0] = 0 ⊕ 0 = 0
31+
32+
**Example 2:**
33+
34+
**Input:** derived =[1,1]
35+
36+
**Output:** true
37+
38+
**Explanation:** A valid original array that gives derived is[0,1].
39+
40+
derived[0] = original[0] ⊕ original[1] = 1
41+
42+
derived[1] = original[1] ⊕ original[0] = 1
43+
44+
**Example 3:**
45+
46+
**Input:** derived =[1,0]
47+
48+
**Output:** false
49+
50+
**Explanation:** There is no valid original array that gives derived.
51+
52+
**Constraints:**
53+
54+
*`n == derived.length`
55+
* <code>1 <= n <= 10<sup>5</sup></code>
56+
* The values in`derived` are either**0's** or**1's**
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg2601_2700.s2684_maximum_number_of_moves_in_a_grid;
2+
3+
// #Medium #Array #Dynamic_Programming #Matrix #2023_09_12_Time_4_ms_(97.95%)_Space_54.4_MB_(68.34%)
4+
5+
publicclassSolution {
6+
publicintmaxMoves(int[][]grid) {
7+
intm =Integer.MIN_VALUE;
8+
int[][]vis =newint[grid.length][grid[0].length];
9+
for (inti =0;i <grid.length;i++) {
10+
m =Math.max(m,mov(i,0,grid,Integer.MIN_VALUE,vis));
11+
}
12+
returnm -1;
13+
}
14+
15+
privateintmov(inti,intj,int[][]g,intp,int[][]vis) {
16+
if (i <0 ||j <0 ||i >=g.length ||j >=g[0].length ||g[i][j] <=p ||vis[i][j] ==1) {
17+
return0;
18+
}
19+
vis[i][j] =1;
20+
intur =1 +mov(i -1,j +1,g,g[i][j],vis);
21+
intdr =1 +mov(i +1,j +1,g,g[i][j],vis);
22+
intr =1 +mov(i,j +1,g,g[i][j],vis);
23+
returnMath.max(ur,Math.max(dr,r));
24+
}
25+
}
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
2684\. Maximum Number of Moves in a Grid
2+
3+
Medium
4+
5+
You are given a**0-indexed**`m x n` matrix`grid` consisting of**positive** integers.
6+
7+
You can start at**any** cell in the first column of the matrix, and traverse the grid in the following way:
8+
9+
* From a cell`(row, col)`, you can move to any of the cells:`(row - 1, col + 1)`,`(row, col + 1)` and`(row + 1, col + 1)` such that the value of the cell you move to, should be**strictly** bigger than the value of the current cell.
10+
11+
Return_the**maximum** number of**moves** that you can perform._
12+
13+
**Example 1:**
14+
15+
![](https://assets.leetcode.com/uploads/2023/04/11/yetgriddrawio-10.png)
16+
17+
**Input:** grid =[[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
18+
19+
**Output:** 3
20+
21+
**Explanation:** We can start at the cell (0, 0) and make the following moves:
22+
- (0, 0) -> (0, 1).
23+
- (0, 1) -> (1, 2).
24+
- (1, 2) -> (2, 3).
25+
26+
It can be shown that it is the maximum number of moves that can be made.
27+
28+
**Example 2:**
29+
30+
![](https://assets.leetcode.com/uploads/2023/04/12/yetgrid4drawio.png)**Input:** grid =[[3,2,4],[2,1,9],[1,1,7]]
31+
32+
**Output:** 0
33+
34+
**Explanation:** Starting from any cell in the first column we cannot perform any moves.
35+
36+
**Constraints:**
37+
38+
*`m == grid.length`
39+
*`n == grid[i].length`
40+
*`2 <= m, n <= 1000`
41+
* <code>4 <= m * n <= 10<sup>5</sup></code>
42+
* <code>1 <= grid[i][j] <= 10<sup>6</sup></code>
Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
packageg2601_2700.s2685_count_the_number_of_complete_components;
2+
3+
// #Medium #Array #Dynamic_Programming #Depth_First_Search #Breadth_First_Search #Matrix #Graph
4+
// #2023_09_12_Time_5_ms_(98.65%)_Space_43.8_MB_(65.96%)
5+
6+
publicclassSolution {
7+
privatestaticclassDSU {
8+
int[]roots;
9+
int[]sizes;
10+
11+
DSU(intn) {
12+
roots =newint[n];
13+
sizes =newint[n];
14+
for (inti =0;i <n;i++) {
15+
sizes[i] =1;
16+
roots[i] =i;
17+
}
18+
}
19+
20+
publicintfind(intv) {
21+
if (roots[v] !=v) {
22+
roots[v] =find(roots[v]);
23+
}
24+
returnroots[v];
25+
}
26+
27+
publicvoidunion(inta,intb) {
28+
introotA =find(a);
29+
introotB =find(b);
30+
if (rootA ==rootB) {
31+
return;
32+
}
33+
roots[rootB] =rootA;
34+
sizes[rootA] +=sizes[rootB];
35+
}
36+
}
37+
38+
publicintcountCompleteComponents(intn,int[][]edges) {
39+
DSUdsu =newDSU(n);
40+
int[]indegree =newint[n];
41+
for (int[]e :edges) {
42+
dsu.union(e[0],e[1]);
43+
indegree[e[0]]++;
44+
indegree[e[1]]++;
45+
}
46+
int[]gcount =newint[n];
47+
intres =0;
48+
for (inti =0;i <n;i++) {
49+
introot =dsu.find(i);
50+
if (dsu.sizes[root] == (indegree[i] +1)) {
51+
gcount[root]++;
52+
}
53+
if (gcount[root] ==dsu.sizes[root]) {
54+
res++;
55+
}
56+
}
57+
returnres;
58+
}
59+
}
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
2685\. Count the Number of Complete Components
2+
3+
Medium
4+
5+
You are given an integer`n`. There is an**undirected** graph with`n` vertices, numbered from`0` to`n - 1`. You are given a 2D integer array`edges` where <code>edges[i] =[a<sub>i</sub>, b<sub>i</sub>]</code> denotes that there exists an**undirected** edge connecting vertices <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code>.
6+
7+
Return_the number of**complete connected components** of the graph_.
8+
9+
A**connected component** is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.
10+
11+
A connected component is said to be**complete** if there exists an edge between every pair of its vertices.
12+
13+
**Example 1:**
14+
15+
**![](https://assets.leetcode.com/uploads/2023/04/11/screenshot-from-2023-04-11-23-31-23.png)**
16+
17+
**Input:** n = 6, edges =[[0,1],[0,2],[1,2],[3,4]]
18+
19+
**Output:** 3
20+
21+
**Explanation:** From the picture above, one can see that all of the components of this graph are complete.
22+
23+
**Example 2:**
24+
25+
**![](https://assets.leetcode.com/uploads/2023/04/11/screenshot-from-2023-04-11-23-32-00.png)**
26+
27+
**Input:** n = 6, edges =[[0,1],[0,2],[1,2],[3,4],[3,5]]
28+
29+
**Output:** 1
30+
31+
**Explanation:** The component containing vertices 0, 1, and 2 is complete since there is an edge between every pair of two vertices. On the other hand, the component containing vertices 3, 4, and 5 is not complete since there is no edge between vertices 4 and 5. Thus, the number of complete components in this graph is 1.
32+
33+
**Constraints:**
34+
35+
*`1 <= n <= 50`
36+
*`0 <= edges.length <= n * (n - 1) / 2`
37+
*`edges[i].length == 2`
38+
* <code>0 <= a<sub>i</sub>, b<sub>i</sub> <= n - 1</code>
39+
* <code>a<sub>i</sub> != b<sub>i</sub></code>
40+
* There are no repeated edges.
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
2693\. Call Function with Custom Context
2+
3+
Medium
4+
5+
Enhance all functions to have the`callPolyfill` method. The method accepts an object`obj` as it's first parameter and any number of additional arguments. The`obj` becomes the`this` context for the function. The additional arguments are passed to the function (that the`callPolyfill` method belongs on).
6+
7+
For example if you had the function:
8+
9+
function tax(price, taxRate) { const totalCost = price\* (1 + taxRate); console.log(\`The cost of ${this.item} is ${totalCost}\`); }
10+
11+
Calling this function like`tax(10, 0.1)` will log`"The cost of undefined is 11"`. This is because the`this` context was not defined.
12+
13+
However, calling the function like`tax.callPolyfill({item: "salad"}, 10, 0.1)` will log`"The cost of salad is 11"`. The`this` context was appropriately set, and the function logged an appropriate output.
14+
15+
Please solve this without using the built-in`Function.call` method.
16+
17+
**Example 1:**
18+
19+
**Input:**
20+
21+
fn = function add(b) {
22+
return this.a + b;
23+
}
24+
25+
args = [{"a": 5}, 7]
26+
27+
**Output:** 12
28+
29+
**Explanation:**
30+
31+
fn.callPolyfill({"a": 5}, 7); // 12
32+
33+
callPolyfill sets the "this" context to {"a": 5}. 7 is passed as an argument.
34+
35+
**Example 2:**
36+
37+
**Input:**
38+
39+
fn = function tax(price, taxRate) {
40+
return \`The cost of the ${this.item} is ${price \* taxRate}\`;
41+
}
42+
43+
args = [{"item": "burger"}, 10, 1.1]
44+
45+
**Output:** "The cost of the burger is 11"
46+
47+
**Explanation:** callPolyfill sets the "this" context to {"item": "burger"}. 10 and 1.1 are passed as additional arguments.
48+
49+
**Constraints:**
50+
51+
*`typeof args[0] == 'object' and args[0] != null`
52+
*`1 <= args.length <= 100`
53+
* <code>2 <= JSON.stringify(args[0]).length <= 10<sup>5</sup></code>
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
// #Medium #Array #Dynamic_Programming #Matrix #2023_07_28_Time_51_ms_(97.92%)_Space_43_MB_(91.84%)
2+
3+
declare global{
4+
interfaceFunction{
5+
callPolyfill(context:Record<any,any>, ...args:any[]):any
6+
}
7+
}
8+
9+
Function.prototype.callPolyfill=function(context, ...args):any{//NOSONAR
10+
letfn=this.bind(context)
11+
returnfn(...args)
12+
}
13+
14+
/*
15+
* function increment() { this.count++; return this.count; }
16+
* increment.callPolyfill({count: 1}); // 2
17+
*/
18+
19+
export{}

0 commit comments

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