update algorithm

leosanqing · leosanqing · commit fe13be758356 · 2019-05-02T23:34:41.000+08:00
diff --git a/Algorithm/java/leetcode/out/production/LeetCode/easy/array/_121_BestTimeToBuyAndSellStock.class b/Algorithm/java/leetcode/out/production/LeetCode/easy/array/_121_BestTimeToBuyAndSellStock.class
diff --git a/Algorithm/java/leetcode/src/easy/array/_121_BestTimeToBuyAndSellStock.java b/Algorithm/java/leetcode/src/easy/array/_121_BestTimeToBuyAndSellStock.java
@@ -0,0 +1,70 @@
+package easy.array;
+
+/**
+ *描述 ：    给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
+ *          如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
+ *          注意你不能在买入股票前卖出股票。
+ *
+ *示例1：    输入: [7,1,5,3,6,4]
+ *          输出: 5
+ *          解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
+ *          注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
+ *
+ *示例2      输入: [7,6,4,3,1]
+ *          输出: 0
+ *          解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
+ */
+
+public class _121_BestTimeToBuyAndSellStock {
+
+    /**
+     *
+     * 直接暴力求解，遍历两次数组，求出最优解
+     */
+
+    public static int violence(int[] prices){
+        if(prices == null || prices.length ==0){
+            return 0;
+        }
+        int maxProfit = 0;
+        for (int i = 0; i < prices.length; i++) {
+            for (int j = i+1; j < prices.length; j++) {
+                if(prices[j]-prices[i] >maxProfit){
+                    maxProfit = prices[j]-prices[i];
+                }
+
+            }
+        }
+        return maxProfit;
+    }
+
+
+    /**
+     *  动态规划：
+     *      1.定义一个从最开始到当前位置的最小值
+     *      2.计算今天减去最小值的值，也就是当天的利润
+     *      3.比较当天的利润和之前的最大利润
+     */
+    public static int dp(int[] prices){
+        if(prices == null || prices.length == 0)
+            return 0;
+
+        int mixProfit = Integer.MAX_VALUE;
+        int maxProfit = 0;
+
+        for (int i = 0; i < prices.length; i++) {
+            //找到最小值
+            mixProfit = Math.min(mixProfit,prices[i]);
+            //比较当天的利润和最大利润
+            maxProfit = Math.max(maxProfit,(prices[i]-mixProfit));
+
+        }
+        return maxProfit;
+
+    }
+
+    public static void main(String[] args) {
+        int a[] ={7,6,4,3,1};
+        System.out.println(violence(a) == dp(a));
+    }
+}
diff --git a/Algorithm/java/leetcode/src/easy/array/_122_BestTimeToBuyAndSellStock2.java b/Algorithm/java/leetcode/src/easy/array/_122_BestTimeToBuyAndSellStock2.java
@@ -0,0 +1,43 @@
+package easy.array;
+
+/**
+ * 描述：  给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
+ *        设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
+ *        注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
+ *
+ * 示例1： 输入: [7,1,5,3,6,4]
+ *        输出: 7
+ *        解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
+ *             随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
+ * 示例2： 输入: [1,2,3,4,5]
+ *        输出: 4
+ *        解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
+ *        注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
+ *        因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
+ *
+ * 思路：使用两个变量 一个valley表示当天天数中最低价，
+ *                 一个peek表示当前所有的天数中的最高价
+ *      因为我们可以买卖股票且是不用付手续费的，也就是我们可以卖了这一只股票，然后再把它买回来
+ *      所以上面示例2中，5-1和 （2-1）+（3-2）+（4-3）+（5-4）的效果是一样的，所以顶峰就找递增的，底就找递减的
+ *
+ */
+public class _122_BestTimeToBuyAndSellStock2 {
+    public int maxProfit(int[] prices) {
+        if(prices.length == 0 || prices == null)
+            return 0;
+        int valley = prices[0],peek = prices[0];
+        int i =0;
+        int maxProfit = 0;
+        while(i < prices.length-1){
+            while(i<prices.length-1 && prices[i]>=prices[i+1])
+                i++;
+            valley = prices[i];
+            while(i<prices.length-1 && prices[i]<=prices[i+1])
+                i++;
+            peek = prices[i];
+            maxProfit += peek-valley;
+            }
+        
+        return maxProfit;
+        }
+    }
diff --git a/Algorithm/java/leetcode/src/easy/array/_136_singleNum.java b/Algorithm/java/leetcode/src/easy/array/_136_singleNum.java
@@ -0,0 +1,34 @@
+package easy.array;
+
+/**描述：
+ *     Given a non-empty array of integers, every element appears twice except for one. Find that single one.
+ *     给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
+ * 说明：
+ *     你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
+ * 输入: [4,1,2,1,2]
+ * 输出: 4
+ *
+ *
+ * 思路：使用异或运算：
+ *      异或运算有三个特征：
+ *      1、0 ^ 任何数都为 那个数   0^a = a；
+ *      2、两个相同的数异或结果为 0 a^a = 0;
+ *      3、异或具有交换律  a^b^c = a^c^b
+ *
+ */
+public class _136_singleNum {
+    public static void main(String[] args) {
+        int[] nums = {4,2,1,2,1};
+        System.out.println("singleNum(nums) = " + singleNum(nums));
+
+    }
+
+    public static int singleNum(int[] nums){
+        int result = 0;
+        for (int num :
+                nums) {
+            result ^=num;
+        }
+        return result;
+    }
+}
