add 509

fishercoder1534 · fishercoder1534 · commit 14b7c2dd7faf · 2019-01-07T20:23:38.000-08:00
diff --git a/README.md b/README.md
@@ -267,6 +267,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |515|[Find Largest Value in Each Tree Row](https://leetcode.com/problems/find-largest-value-in-each-tree-row/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_515.java) | O(n) |O(k) | |Medium| BFS
 |514|[Freedom Trail](https://leetcode.com/problems/freedom-trail/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_514.java) | O(?) |O(?) | |Hard | DP
 |513|[Find Bottom Left Tree Value](https://leetcode.com/problems/find-bottom-left-tree-value/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_513.java) | O(n) |O(k) | |Medium| BFS
+|509|[Fibonacci Number](https://leetcode.com/problems/fibonacci-number/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_509.java) | O(n) |O(n) | |Easy| Array 
 |508|[Most Frequent Subtree Sum](https://leetcode.com/problems/most-frequent-subtree-sum/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_508.java) | O(n) |O(n) | |Medium| DFS, Tree
 |507|[Perfect Number](https://leetcode.com/problems/perfect-number/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_507.java) | O(sqrt(n)) |O(1) | |Easy| Math
 |506|[Relative Ranks](https://leetcode.com/problems/relative-ranks/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_506.java) | O(nlogn) |O(n) | |Easy|
diff --git a/src/main/java/com/fishercoder/solutions/_509.java b/src/main/java/com/fishercoder/solutions/_509.java
@@ -0,0 +1,50 @@
+package com.fishercoder.solutions;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * 509. Fibonacci Number
+ *
+ * The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
+ *
+ * F(0) = 0,   F(1) = 1
+ * F(N) = F(N - 1) + F(N - 2), for N > 1.
+ * Given N, calculate F(N).
+ *
+ *
+ *
+ * Example 1:
+ *
+ * Input: 2
+ * Output: 1
+ * Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
+ * Example 2:
+ *
+ * Input: 3
+ * Output: 2
+ * Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
+ * Example 3:
+ *
+ * Input: 4
+ * Output: 3
+ * Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
+ *
+ *
+ * Note:
+ *
+ * 0 ≤ N ≤ 30.
+ */
+public class _509 {
+  public static class Solution1 {
+    public int fib(int N) {
+      List<Integer> list = new ArrayList<>();
+      list.add(0);
+      list.add(1);
+      for (int i = 2; i <= N; i++) {
+        list.add(list.get(i - 1) + list.get(i - 2));
+      }
+      return list.get(N);
+    }
+  }
+}
diff --git a/src/test/java/com/fishercoder/_509Test.java b/src/test/java/com/fishercoder/_509Test.java
@@ -0,0 +1,36 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._509;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _509Test {
+  private static _509.Solution1 solution1;
+
+  @BeforeClass
+  public static void setup() {
+    solution1 = new _509.Solution1();
+  }
+
+  @Test
+  public void test1() {
+    assertEquals(1, solution1.fib(2));
+  }
+
+  @Test
+  public void test2() {
+    assertEquals(2, solution1.fib(3));
+  }
+
+  @Test
+  public void test3() {
+    assertEquals(3, solution1.fib(4));
+  }
+
+  @Test
+  public void test4() {
+    assertEquals(0, solution1.fib(0));
+  }
+}
