add a solution for 189

fishercoder1534 · fishercoder1534 · commit 2fe08c3293b6 · 2021-09-13T11:38:52.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_189.java b/src/main/java/com/fishercoder/solutions/_189.java
@@ -61,4 +61,28 @@ private void reverse(int[] nums, int start, int end) {
             }
         }
     }
+
+    public static class Solution4 {
+        /**
+         * O(n) time
+         * O(1) space
+         * The most optimal, we can safely ignore all the above three solutions... :)
+         */
+        public void rotate(int[] nums, int k) {
+            k = k % nums.length;
+            int count = 0;
+            for (int start = 0; count < nums.length; start++) {
+                int current = start;
+                int prev = nums[start];
+                do {
+                    int nextIndex = (current + k) % nums.length;
+                    int tmp = nums[nextIndex];
+                    nums[nextIndex] = prev;
+                    prev = tmp;
+                    current = nextIndex;
+                    count++;
+                } while (start != current);
+            }
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_189Test.java b/src/test/java/com/fishercoder/_189Test.java
@@ -1,42 +1,59 @@
 package com.fishercoder;
 
-import com.fishercoder.common.utils.CommonUtils;
 import com.fishercoder.solutions._189;
 import org.junit.BeforeClass;
 import org.junit.Test;
 
+import static org.junit.Assert.assertArrayEquals;
+
 public class _189Test {
     private static _189.Solution1 solution1;
     private static _189.Solution2 solution2;
     private static _189.Solution3 solution3;
+    private static _189.Solution4 solution4;
     private static int[] nums;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _189.Solution1();
         solution2 = new _189.Solution2();
         solution3 = new _189.Solution3();
+        solution4 = new _189.Solution4();
     }
 
     @Test
     public void test1() {
         nums = new int[]{1, 2, 3};
         solution1.rotate(nums, 1);
-        CommonUtils.printArray(nums);
+        assertArrayEquals(new int[]{3, 1, 2}, nums);
     }
 
     @Test
     public void test2() {
         nums = new int[]{1, 2, 3};
         solution2.rotate(nums, 1);
-        CommonUtils.printArray(nums);
+        assertArrayEquals(new int[]{3, 1, 2}, nums);
     }
 
     @Test
     public void test3() {
         nums = new int[]{1, 2, 3};
         solution3.rotate(nums, 1);
-        CommonUtils.printArray(nums);
+        assertArrayEquals(new int[]{3, 1, 2}, nums);
+    }
+
+    @Test
+    public void test4() {
+        nums = new int[]{1, 2, 3};
+        solution4.rotate(nums, 1);
+        assertArrayEquals(new int[]{3, 1, 2}, nums);
+    }
+
+    @Test
+    public void test5() {
+        nums = new int[]{-1, -100, 3, 99};
+        solution4.rotate(nums, 2);
+        assertArrayEquals(new int[]{3, 99, -1, -100}, nums);
     }
 
 }
