add 121

fishercoder1534 · fishercoder1534 · commit 7f4d6c38c556 · 2017-05-14T15:12:05.000-07:00
diff --git a/README.md b/README.md
@@ -242,7 +242,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |243|[Shortest Word Distance](https://leetcode.com/problems/shortest-word-distance/)|[Solution](../master/src/main/java/com/stevesun/solutions/ShortestWordDistance.java) | O(n) | O(1) | 
 |240|[Search a 2D Matrix II](https://leetcode.com/problems/search-a-2d-matrix-ii/)|[Solution](../master/src/main/java/com/stevesun/solutions/Searcha2DMatrixII.java)| O(log(m*n))|O(1) | Medium| Binary Search
 |239|[Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/)|[Solution](../master/src/main/java/com/stevesun/solutions/SlidingWindowMaximum.java)| O(nlogn)|O(k) | Hard| Heap
-|238|[Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/)|[Solution](../master/src/main/java/com/stevesun/solutions/ProductofArrayExceptSelf.java)| O(n)|O(1) | Medium| Array
+|238|[Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/)|[Solution](../master/src/main/java/com/stevesun/solutions/_238.java)| O(n)|O(1) | Medium| Array
 |237|[Delete Node in a Linked List](https://leetcode.com/problems/delete-node-in-a-linked-list/)|[Solution](../master/src/main/java/com/stevesun/solutions/_237.java)| O(1)|O(1) | Easy| LinkedList
 |236|[Lowest Common Ancestor of a Binary Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/)|[Solution](../master/src/main/java/com/stevesun/solutions/_236.java)| O(n)|O(h) | Medium| DFS
 |235|[Lowest Common Ancestor of a Binary Search Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/)|[Solution](../master/src/main/java/com/stevesun/solutions/_235.java)| O(h)|O(1) | Easy| DFS
@@ -321,7 +321,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |124|[Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/)|[Solution](../master/src/main/java/com/stevesun/solutions/BinaryTreeMaximumPathSum.java)| O(n)|O(h) | Hard | Tree
 |123|[Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/)|[Solution](../master/src/main/java/com/stevesun/solutions/BestTimeToBuyAndSellStockIII.java)| O(?)|O(?) | Hard |
 |122|[Best Time to Buy and Sell Stock II](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/)|[Solution](../master/src/main/java/com/stevesun/solutions/BestTimeToBuyAndSellStockII.java)| O(n)|O(1) | Medium | Greedy
-|121|[Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)|[Solution](../master/src/main/java/com/stevesun/solutions/BestTimeToBuyAndSellStock.java)| O(n)|O(1) | Easy| DP
+|121|[Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)|[Solution](../master/src/main/java/com/stevesun/solutions/_121.java)| O(n)|O(1) | Easy| DP
 |120|[Triangle](https://leetcode.com/problems/triangle/)|[Solution](../master/src/main/java/com/stevesun/solutions/Triangle.java)| O(m*n)|O(n) | Medium| DP
 |119|[Pascal's Triangle II](https://leetcode.com/problems/pascals-triangle-ii/)|[Solution](../master/src/main/java/com/stevesun/solutions/PascalsTriangleII.java)| O(n^2)|O(1) | Easy| 
 |118|[Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/)|[Solution](../master/src/main/java/com/stevesun/solutions/PascalsTriangle.java)| O(n^2)|O(1) | Easy| 
diff --git a/src/main/java/com/stevesun/solutions/_121.java b/src/main/java/com/stevesun/solutions/_121.java
@@ -4,19 +4,36 @@
  *
 Say you have an array for which the ith element is the price of a given stock on day i.
 
-If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
+If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock),
+ design an algorithm to find the maximum profit.
 
 Example 1:
 Input: [7, 1, 5, 3, 6, 4]
 Output: 5
 
 max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
-Example 2:
+
+
+ Example 2:
 Input: [7, 6, 4, 3, 1]
 Output: 0
 
 In this case, no transaction is done, i.e. max profit = 0.*/
-public class BestTimeToBuyAndSellStock {
+
+public class _121 {
+    /**Pretty straightforward, sell before you buy, keep a global maxProfit variable, update it along the way if necessary.*/
+    public int maxProfit_20160924(int[] prices) {
+        if(prices == null || prices.length < 2) return 0;
+        int minBuy = prices[0];
+        int maxSell = prices[1];
+        int maxProfit = (maxSell - minBuy) > 0 ? (maxSell - minBuy) : 0;
+        for(int i = 1; i < prices.length; i++){
+            minBuy = Math.min(minBuy, prices[i]);
+            maxProfit = Math.max(maxProfit, prices[i] - minBuy);
+        }
+        return maxProfit;
+    }
+
 /**The key here is that you'll have to buy first, before you can sell.
  * That means, if the lower price comes after a higher price, their combination won't work! Since you cannot sell first
  * before you buy it.*/
@@ -37,21 +54,7 @@ public static void main(String...strings){
 //        int[] prices = new int[]{7,6,4,3,1};
 //        int[] prices = new int[]{2,4,1};
         int[] prices = new int[]{1,2};
-        BestTimeToBuyAndSellStock test = new BestTimeToBuyAndSellStock();
+        _121 test = new _121();
         System.out.println(test.maxProfit(prices));
     }
-    
-
-    /**Pretty straightforward, sell before you buy, keep a global maxProfit variable, update it along the way if necessary.*/
-    public int maxProfit_20160924(int[] prices) {
-        if(prices == null || prices.length == 0 || prices.length < 2) return 0;
-        int minBuy = prices[0];
-        int maxSell = prices[1];
-        int maxProfit = (maxSell - minBuy) > 0 ? (maxSell - minBuy) : 0;
-        for(int i = 1; i < prices.length; i++){
-            minBuy = Math.min(minBuy, prices[i]);
-            maxProfit = Math.max(maxProfit, prices[i] - minBuy);
-        }
-        return maxProfit;
-    }
 }
diff --git a/src/main/java/com/stevesun/solutions/_238.java b/src/main/java/com/stevesun/solutions/_238.java
@@ -10,7 +10,7 @@ Solve it without division and in O(n).
  Follow up:
  Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
  */
-public class ProductofArrayExceptSelf {
+public class _238 {
 
     public int[] productExceptSelf(int[] nums) {
         int n = nums.length;
diff --git a/src/test/java/com/stevesun/_238Test.java b/src/test/java/com/stevesun/_238Test.java
@@ -1,21 +1,21 @@
 package com.stevesun;
 
-import com.stevesun.solutions.ProductofArrayExceptSelf;
+import com.stevesun.solutions._238;
 import org.junit.Before;
 import org.junit.BeforeClass;
 import org.junit.Test;
 
 import static org.junit.Assert.assertArrayEquals;
 
-public class ProductofArrayExceptSelfTest {
-    private static ProductofArrayExceptSelf test;
+public class _238Test {
+    private static _238 test;
     private static int[] expected;
     private static int[] actual;
     private static int[] nums;
 
     @BeforeClass
     public static void setup(){
-        test = new ProductofArrayExceptSelf();
+        test = new _238();
     }
 
     @Before
