homework_week4

xkluan · xkluan · commit a485aabaa462 · 2020-07-05T23:07:55.000+08:00
diff --git a/Week04/122-买卖股票的最佳时机.py b/Week04/122-买卖股票的最佳时机.py
@@ -0,0 +1,52 @@
+# 给定一个数组，它的第 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 天接连购买股票，之后再将它们卖出。
+#      因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
+#
+#
+#  示例 3:
+#
+#  输入: [7,6,4,3,1]
+# 输出: 0
+# 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
+#
+#
+#
+#  提示：
+#
+#
+#  1 <= prices.length <= 3 * 10 ^ 4
+#  0 <= prices[i] <= 10 ^ 4
+#
+#  Related Topics 贪心算法 数组
+
+
+# leetcode submit region begin(Prohibit modification and deletion)
+class Solution:
+    def maxProfit(self, prices: List[int]) -> int:
+        profit = 0
+        for i in range(1, len(prices)):
+            tmp = prices[i] - prices[i - 1]
+            if tmp > 0: profit += tmp
+        return profit
+
+# leetcode submit region end(Prohibit modification and deletion)
diff --git a/Week04/860-柠檬水找零.py b/Week04/860-柠檬水找零.py
@@ -0,0 +1,78 @@
+# 在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
+#
+#  顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
+#
+#  每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
+#
+#  注意，一开始你手头没有任何零钱。
+#
+#  如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
+#
+#  示例 1：
+#
+#  输入：[5,5,5,10,20]
+# 输出：true
+# 解释：
+# 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
+# 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
+# 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
+# 由于所有客户都得到了正确的找零，所以我们输出 true。
+#
+#
+#  示例 2：
+#
+#  输入：[5,5,10]
+# 输出：true
+#
+#
+#  示例 3：
+#
+#  输入：[10,10]
+# 输出：false
+#
+#
+#  示例 4：
+#
+#  输入：[5,5,10,10,20]
+# 输出：false
+# 解释：
+# 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
+# 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
+# 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
+# 由于不是每位顾客都得到了正确的找零，所以答案是 false。
+#
+#
+#
+#
+#  提示：
+#
+#
+#  0 <= bills.length <= 10000
+#  bills[i] 不是 5 就是 10 或是 20
+#
+#  Related Topics 贪心算法
+
+
+# leetcode submit region begin(Prohibit modification and deletion)
+class Solution:
+    def lemonadeChange(self, bills: List[int]) -> bool:
+        five = ten = 0
+        for bill in bills:
+            if bill == 5:
+                five += 1
+            elif bill == 10:
+                if not five: return False
+                five -= 1
+                ten += 1
+            else:
+                if ten and five:
+                    ten -= 1
+                    five -= 1
+                elif five >= 3:
+                    five -= 3
+                else:
+                    return False
+        return True
+
+
+# leetcode submit region end(Prohibit modification and deletion)
diff --git a/Week04/NOTE.md b/Week04/NOTE.md
@@ -1 +1,17 @@
-学习笔记
+学习笔记
+# 搜索 - 遍历
+• 每个节点都要访问一次
+
+• 每个节点仅仅要访问一次
+
+• 对于节点的访问顺序不限
+- 深度优先:depth first search
+- 广度优先:breadth first search
+
+# 贪心算法
+贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有
+利)的选择，从而希望导致结果是全局最好或最优的算法。
+
+贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不
+能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行
+选择，有回退功能。
