add a solution to 70 and tests

fishercoder1534 · fishercoder1534 · commit 75654d35a8f6 · 2020-01-29T17:26:26.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_70.java b/src/main/java/com/fishercoder/solutions/_70.java
@@ -4,26 +4,21 @@
  * 70. Climbing Stairs
 
  You are climbing a stair case. It takes n steps to reach to the top.
-
  Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
 
  Note: Given n will be a positive integer.
 
  Example 1:
-
  Input: 2
  Output:  2
  Explanation:  There are two ways to climb to the top.
-
  1. 1 step + 1 step
  2. 2 steps
 
  Example 2:
-
  Input: 3
  Output:  3
  Explanation:  There are three ways to climb to the top.
-
  1. 1 step + 1 step + 1 step
  2. 1 step + 2 steps
  3. 2 steps + 1 step
@@ -32,6 +27,10 @@
 
 public class _70 {
   public static class Solution1 {
+    /**
+     * O(n) time
+     * O(n) space
+     * */
     public int climbStairs(int n) {
       if (n == 1) {
         return n;
@@ -45,4 +44,24 @@ public int climbStairs(int n) {
       return dp[n];
     }
   }
+
+  public static class Solution2 {
+    /**
+     * O(n) time
+     * O(1) space
+     * */
+    public int climbStairs(int n) {
+      if (n == 1) {
+        return n;
+      }
+      int stepOne = 1;
+      int stepTwo = 2;
+      for (int i = 3; i <= n; i++) {
+        int tmp = stepTwo;
+        stepTwo = stepOne + stepTwo;
+        stepOne = tmp;
+      }
+      return stepTwo;
+    }
+  }
 }
diff --git a/src/test/java/com/fishercoder/_70Test.java b/src/test/java/com/fishercoder/_70Test.java
@@ -8,14 +8,21 @@
 
 public class _70Test {
     private static _70.Solution1 solution1;
+    private static _70.Solution2 solution2;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _70.Solution1();
+        solution2 = new _70.Solution2();
     }
 
     @Test
     public void test1() {
         assertEquals(3, solution1.climbStairs(3));
     }
+
+    @Test
+    public void test2() {
+        assertEquals(3, solution2.climbStairs(3));
+    }
 }

Original file line number	Diff line number	Diff line change
`@@ -8,14 +8,21 @@`
`8`	`8`
`9`	`9`	`public class _70Test {`
`10`	`10`	`private static _70.Solution1 solution1;`
	`11`	`+ private static _70.Solution2 solution2;`
`11`	`12`
`12`	`13`	`@BeforeClass`
`13`	`14`	`public static void setup() {`
`14`	`15`	`solution1 = new _70.Solution1();`
	`16`	`+ solution2 = new _70.Solution2();`
`15`	`17`	`}`
`16`	`18`
`17`	`19`	`@Test`
`18`	`20`	`public void test1() {`
`19`	`21`	`assertEquals(3, solution1.climbStairs(3));`
`20`	`22`	`}`
	`23`	`+`
	`24`	`+ @Test`
	`25`	`+ public void test2() {`
	`26`	`+ assertEquals(3, solution2.climbStairs(3));`
	`27`	`+ }`
`21`	`28`	`}`