Skip to content

Commit 71ecf3f

Browse files
yanglbmeyanglbme
committed
feat: update solutions to lc problem: No.1559
No.1559.Detect Cycles in 2D Grid
1 parent ba32d1b commit 71ecf3f

File tree

7 files changed

+115
-12
lines changed

7 files changed

+115
-12
lines changed

‎solution/1500-1599/1559.Detect Cycles in 2D Grid/README.md

Lines changed: 40 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -141,7 +141,7 @@ class Solution:
141141
for j in range(n):
142142
for a, b in [[0, 1], [1, 0]]:
143143
x, y = i + a, j + b
144-
if 0 <= x < m and 0 <= y < n and grid[x][y] == grid[i][j]:
144+
if x < m and y < n and grid[x][y] == grid[i][j]:
145145
if find(x * n + y) == find(i * n + j):
146146
return True
147147
p[find(x * n + y)] = find(i * n + j)
@@ -169,7 +169,7 @@ class Solution {
169169
for (int k = 0; k < 2; ++k) {
170170
int x = i + dirs[k];
171171
int y = j + dirs[k + 1];
172-
if (x >= 0 && x < m && y >= 0 && y < n && grid[i][j] == grid[x][y]) {
172+
if (x < m && y < n && grid[i][j] == grid[x][y]) {
173173
if (find(x * n + y) == find(i * n + j)) {
174174
return true;
175175
}
@@ -209,7 +209,7 @@ public:
209209
for (int k = 0; k < 2; ++k)
210210
{
211211
int x = i + dirs[k], y = j + dirs[k + 1];
212-
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == grid[i][j])
212+
if (x < m && y < n && grid[x][y] == grid[i][j])
213213
{
214214
if (find(x * n + y) == find(i * n + j)) return 1;
215215
p[find(x * n + y)] = find(i * n + j);
@@ -248,7 +248,7 @@ func containsCycle(grid [][]byte) bool {
248248
for j := 0; j < n; j++ {
249249
for k := 0; k < 2; k++ {
250250
x, y := i+dirs[k], j+dirs[k+1]
251-
if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == grid[i][j] {
251+
if x < m && y < n && grid[x][y] == grid[i][j] {
252252
if find(x*n+y) == find(i*n+j) {
253253
return true
254254
}
@@ -261,6 +261,42 @@ func containsCycle(grid [][]byte) bool {
261261
}
262262
```
263263

264+
### **JavaScript**
265+
266+
```js
267+
/**
268+
* @param {character[][]} grid
269+
* @return {boolean}
270+
*/
271+
var containsCycle = function (grid) {
272+
const m = grid.length;
273+
const n = grid[0].length;
274+
let p = Array.from({ length: m * n }, (_, i) => i);
275+
function find(x) {
276+
if (p[x] != x) {
277+
p[x] = find(p[x]);
278+
}
279+
return p[x];
280+
}
281+
const dirs = [0, 1, 0];
282+
for (let i = 0; i < m; ++i) {
283+
for (let j = 0; j < n; ++j) {
284+
for (let k = 0; k < 2; ++k) {
285+
const x = i + dirs[k];
286+
const y = j + dirs[k + 1];
287+
if (x < m && y < n && grid[x][y] == grid[i][j]) {
288+
if (find(x * n + y) == find(i * n + j)) {
289+
return true;
290+
}
291+
p[find(x * n + y)] = find(i * n + j);
292+
}
293+
}
294+
}
295+
}
296+
return false;
297+
};
298+
```
299+
264300
### **...**
265301

266302
```

‎solution/1500-1599/1559.Detect Cycles in 2D Grid/README_EN.md

Lines changed: 40 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -77,7 +77,7 @@ class Solution:
7777
for j in range(n):
7878
for a, b in [[0, 1], [1, 0]]:
7979
x, y = i + a, j + b
80-
if 0 <= x < m and 0 <= y < n and grid[x][y] == grid[i][j]:
80+
if x < m and y < n and grid[x][y] == grid[i][j]:
8181
if find(x * n + y) == find(i * n + j):
8282
return True
8383
p[find(x * n + y)] = find(i * n + j)
@@ -103,7 +103,7 @@ class Solution {
103103
for (int k = 0; k < 2; ++k) {
104104
int x = i + dirs[k];
105105
int y = j + dirs[k + 1];
106-
if (x >= 0 && x < m && y >= 0 && y < n && grid[i][j] == grid[x][y]) {
106+
if (x < m && y < n && grid[i][j] == grid[x][y]) {
107107
if (find(x * n + y) == find(i * n + j)) {
108108
return true;
109109
}
@@ -143,7 +143,7 @@ public:
143143
for (int k = 0; k < 2; ++k)
144144
{
145145
int x = i + dirs[k], y = j + dirs[k + 1];
146-
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == grid[i][j])
146+
if (x < m && y < n && grid[x][y] == grid[i][j])
147147
{
148148
if (find(x * n + y) == find(i * n + j)) return 1;
149149
p[find(x * n + y)] = find(i * n + j);
@@ -182,7 +182,7 @@ func containsCycle(grid [][]byte) bool {
182182
for j := 0; j < n; j++ {
183183
for k := 0; k < 2; k++ {
184184
x, y := i+dirs[k], j+dirs[k+1]
185-
if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == grid[i][j] {
185+
if x < m && y < n && grid[x][y] == grid[i][j] {
186186
if find(x*n+y) == find(i*n+j) {
187187
return true
188188
}
@@ -195,6 +195,42 @@ func containsCycle(grid [][]byte) bool {
195195
}
196196
```
197197

198+
### **JavaScript**
199+
200+
```js
201+
/**
202+
* @param {character[][]} grid
203+
* @return {boolean}
204+
*/
205+
var containsCycle = function (grid) {
206+
const m = grid.length;
207+
const n = grid[0].length;
208+
let p = Array.from({ length: m * n }, (_, i) => i);
209+
function find(x) {
210+
if (p[x] != x) {
211+
p[x] = find(p[x]);
212+
}
213+
return p[x];
214+
}
215+
const dirs = [0, 1, 0];
216+
for (let i = 0; i < m; ++i) {
217+
for (let j = 0; j < n; ++j) {
218+
for (let k = 0; k < 2; ++k) {
219+
const x = i + dirs[k];
220+
const y = j + dirs[k + 1];
221+
if (x < m && y < n && grid[x][y] == grid[i][j]) {
222+
if (find(x * n + y) == find(i * n + j)) {
223+
return true;
224+
}
225+
p[find(x * n + y)] = find(i * n + j);
226+
}
227+
}
228+
}
229+
}
230+
return false;
231+
};
232+
```
233+
198234
### **...**
199235

200236
```

‎solution/1500-1599/1559.Detect Cycles in 2D Grid/Solution.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@ class Solution {
1414
for (int k = 0; k < 2; ++k)
1515
{
1616
int x = i + dirs[k], y = j + dirs[k + 1];
17-
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == grid[i][j])
17+
if (x < m && y < n && grid[x][y] == grid[i][j])
1818
{
1919
if (find(x * n + y) == find(i * n + j)) return 1;
2020
p[find(x * n + y)] = find(i * n + j);

‎solution/1500-1599/1559.Detect Cycles in 2D Grid/Solution.go

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -16,7 +16,7 @@ func containsCycle(grid [][]byte) bool {
1616
for j := 0; j < n; j++ {
1717
for k := 0; k < 2; k++ {
1818
x, y := i+dirs[k], j+dirs[k+1]
19-
if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == grid[i][j] {
19+
if x < m && y < n && grid[x][y] == grid[i][j] {
2020
if find(x*n+y) == find(i*n+j) {
2121
return true
2222
}

‎solution/1500-1599/1559.Detect Cycles in 2D Grid/Solution.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@ public boolean containsCycle(char[][] grid) {
1414
for (int k = 0; k < 2; ++k) {
1515
int x = i + dirs[k];
1616
int y = j + dirs[k + 1];
17-
if (x >= 0 && x < m && y >= 0 && y < n && grid[i][j] == grid[x][y]) {
17+
if (x < m && y < n && grid[i][j] == grid[x][y]) {
1818
if (find(x * n + y) == find(i * n + j)) {
1919
return true;
2020
}

‎solution/1500-1599/1559.Detect Cycles in 2D Grid/Solution.js

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
/**
2+
* @param {character[][]} grid
3+
* @return {boolean}
4+
*/
5+
var containsCycle = function (grid) {
6+
const m = grid.length;
7+
const n = grid[0].length;
8+
let p = Array.from({ length: m * n }, (_, i) => i);
9+
function find(x) {
10+
if (p[x] != x) {
11+
p[x] = find(p[x]);
12+
}
13+
return p[x];
14+
}
15+
const dirs = [0, 1, 0];
16+
for (let i = 0; i < m; ++i) {
17+
for (let j = 0; j < n; ++j) {
18+
for (let k = 0; k < 2; ++k) {
19+
const x = i + dirs[k];
20+
const y = j + dirs[k + 1];
21+
if (x < m && y < n && grid[x][y] == grid[i][j]) {
22+
if (find(x * n + y) == find(i * n + j)) {
23+
return true;
24+
}
25+
p[find(x * n + y)] = find(i * n + j);
26+
}
27+
}
28+
}
29+
}
30+
return false;
31+
};

‎solution/1500-1599/1559.Detect Cycles in 2D Grid/Solution.py

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@ def find(x):
1111
for j in range(n):
1212
for a, b in [[0, 1], [1, 0]]:
1313
x, y = i + a, j + b
14-
if 0 <= x < m and 0 <= y < n and grid[x][y] == grid[i][j]:
14+
if x < m and y < n and grid[x][y] == grid[i][j]:
1515
if find(x * n + y) == find(i * n + j):
1616
return True
1717
p[find(x * n + y)] = find(i * n + j)

0 commit comments

Comments
 (0)