8000 [N-0] add 457 · ljin029/Leetcode-1@084731b · GitHub
[go: up one dir, main page]
Skip to content

Commit 084731b

Browse files
fishercoder1534fishercoder1534
committed
[N-0] add 457
1 parent 90d8d38 commit 084731b

File tree

3 files changed

+106
-0
lines changed

3 files changed

+106
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -230,6 +230,7 @@ Your ideas/fixes/algorithms are more than welcome!
230230
|460|[LFU Cache](https://leetcode.com/problems/lfu-cache/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_460.java) | O(1) |O(n) | Hard| Design, LinkedHashMap, HashMap
231231
|459|[Repeated Substring Pattern](https://leetcode.com/problems/repeated-substring-pattern/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_459.java)| O(n)|O(n) | Easy| String, KMP
232232
|458|[Poor Pigs](https://leetcode.com/problems/poor-pigs/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_458.java) | O(1) |O(1) | Easy| Math
233+
|457|[Circular Array Loop](https://leetcode.com/problems/circular-array-loop/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_457.java) | O(n) |O(1) | Medium |
233234
|456|[132 Pattern](https://leetcode.com/problems/132-pattern/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_456.java) | O(n) |O(n) | Medium| Stack
234235
|455|[Assign Cookies](https://leetcode.com/problems/assign-cookies/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_455.java)| O(n)|O(1) | Easy|
235236
|454|[4Sum II](https://leetcode.com/problems/4sum-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_454.java) | O(n) |O(n) | Medium| HashMap

‎src/main/java/com/fishercoder/solutions/_457.java

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package com.fishercoder.solutions;
2+
3+
/**
4+
* 457. Circular Array Loop
5+
*
6+
* You are given an array of positive and negative integers.
7+
* If a number n at an index is positive, then move forward n steps.
8+
* Conversely, if it's negative (-n), move backward n steps.
9+
*
10+
* Assume the first element of the array is forward next to the last element,
11+
* and the last element is backward next to the first element.
12+
* Determine if there is a loop in this array.
13+
* A loop starts and ends at a particular index with more than 1 element along the loop. The loop must be "forward" or "backward'.
14+
*
15+
* Example 1: Given the array [2, -1, 1, 2, 2], there is a loop, from index 0 -> 2 -> 3 -> 0.
16+
* Example 2: Given the array [-1, 2], there is no loop.
17+
*
18+
* Note: The given array is guaranteed to contain no element "0".
19+
*
20+
* Can you do it in O(n) time complexity and O(1) space complexity?
21+
*/
22+
public class _457 {
23+
public static class Solution1 {
24+
/**
25+
* credit: https://discuss.leetcode.com/topic/66894/java-slow-fast-pointer-solution
26+
*/
27+
public boolean circularArrayLoop(int[] nums) {
28+
int n = nums.length;
29+
for (int i = 0; i < n; i++) {
30+
if (nums[i] == 0) {
31+
continue;
32+
}
33+
// slow/fast pointer
34+
int j = i, k = getIndex(i, nums);
35+
while (nums[k] * nums[i] > 0 && nums[getIndex(k, nums)] * nums[i] > 0) {
36+
if (j == k) {
37+
// check for loop with only one element
38+
if (j == getIndex(j, nums)) {
39+
break;
40+
}
41+
return true;
42+
}
43+
j = getIndex(j, nums);
44+
k = getIndex(getIndex(k, nums), nums);
45+
}
46+
// loop not found, set all element along the way to 0
47+
j = i;
48+
int val = nums[i];
49+
while (nums[j] * val > 0) {
50+
int next = getIndex(j, nums);
51+
nums[j] = 0;
52+
j = next;
53+
}
54+
}
55+
return false;
56+
}
57+
58+
public int getIndex(int i, int[] nums) {
59+
int n = nums.length;
60+
return i + nums[i] >= 0 ? (i + nums[i]) % n : n + ((i + nums[i]) % n);
61+
}
62+
}
63+
}

‎src/test/java/com/fishercoder/_457Test.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._457;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import static org.junit.Assert.assertEquals;
8+
9+
public class _457Test {
10+
private static _457.Solution1 solution1;
11+
private static int[] nums;
12+
13+
@BeforeClass
14+
public static void setup() {
15+
solution1 = new _457.Solution1();
16+
}
17+
18+
@Test
19+
public void test1() {
20+
nums = new int[]{2, -1, 1, 2, 2};
21+
assertEquals(true, solution1.circularArrayLoop(nums));
22+
}
23+
24+
@Test
25+
public void test2() {
26+
nums = new int[]{-1, 2};
27+
assertEquals(false, solution1.circularArrayLoop(nums));
28+
}
29+
30+
@Test
31+
public void test3() {
32+
nums = new int[]{-1, 2, 3};
33+
assertEquals(false, solution1.circularArrayLoop(nums));
34+
}
35+
36+
@Test
37+
public void test4() {
38+
nums = new int[]{2, 1, 9};
39+
assertEquals(false, solution1.circularArrayLoop(nums));
40+
}
41+
42+
}

0 commit comments

Comments
 (0)
0