Merge pull request algorithm001#722 from ellie88/master

GeekUniversity · web-flow · commit 2afe77916294 · 2019-05-13T17:17:31.000+08:00
第四周
diff --git a/Week_04/id_94/LeetCode_241_094.py b/Week_04/id_94/LeetCode_241_094.py
@@ -0,0 +1,34 @@
+from typing import List
+
+
+class Solution(object):
+    def diffWaysToCompute(self, input: str) -> List[int]:
+
+        list = []
+        for i in range(len(input)):
+            c = input[i]
+            if c == "+" or c =="-" or c =="*" or c=="/":
+
+                left = self.diffWaysToCompute(input[:i])
+                right = self.diffWaysToCompute(input[i+1:])
+
+                for le in left:
+                    for ri in right:
+                        if c == "+":
+                            list.append(int(le)+int(ri))
+                        elif c == "-":
+                            list.append(int(le)-int(ri))
+                        elif c == "*" :
+                            list.append(int(le)*int(ri))
+                        elif c == "/":
+                            list.append(int(le) / int(ri))
+
+        if len(list)==0:
+            list.append(int(input))
+        return list
+
+
+
+if __name__=="__main__":
+    result = Solution().diffWaysToCompute("11/2")
+    print(result)
diff --git a/Week_04/id_94/LeetCode_455_094.py b/Week_04/id_94/LeetCode_455_094.py
@@ -0,0 +1,37 @@
+from typing import List
+
+
+class Solution:
+    def findContentChildren( g: List[int], s: List[int]) -> int:
+
+        g = sorted(g)
+        s = sorted(s)
+        num = 0
+        for v in g:
+            for k in s:
+                if v <= k:
+                    num+=1
+                    s.remove(k)
+                    break
+
+        return num
+
+if __name__=="__main__":
+
+
+    g=  [262, 437, 433, 102, 438, 346, 131, 160, 281, 34, 219, 373, 466, 275, 51, 118, 209, 32, 108, 57, 385, 514, 439, 73,
+     271, 442, 366, 515, 284, 425, 491, 466, 322, 34, 484, 231, 450, 355, 106, 279, 496, 312, 96, 461, 446, 422, 143,
+     98, 444, 461, 142, 234, 416, 45, 271, 344, 446, 364, 216, 16, 431, 370, 120, 463, 377, 106, 113, 406, 406, 481,
+     304, 41, 2, 174, 81, 220, 158, 104, 119, 95, 479, 323, 145, 205, 218, 482, 345, 324, 253, 368, 214, 379, 343, 375,
+     134, 145, 268, 56, 206]
+    s = [149, 79, 388, 251, 417, 82, 233, 377, 95, 309, 418, 400, 501, 349, 348, 400, 461, 495, 104, 330, 155, 483, 334,
+     436, 512, 232, 511, 40, 343, 334, 307, 56, 164, 276, 399, 337, 59, 440, 3, 458, 417, 291, 354, 419, 516, 4, 370,
+     106, 469, 254, 274, 163, 345, 513, 130, 292, 330, 198, 142, 95, 18, 295, 126, 131, 339, 171, 347, 199, 244, 428,
+     383, 43, 315, 353, 91, 289, 466, 178, 425, 112, 420, 85, 159, 360, 241, 300, 295, 285, 310, 76, 69, 297, 155, 416,
+     333, 416, 226, 262, 63, 445, 77, 151, 368, 406, 171, 13, 198, 30, 446, 142, 329, 245, 505, 238, 352, 113, 485, 296,
+     337, 507, 91, 437, 366, 511, 414, 46, 78, 399, 283, 106, 202, 494, 380, 479, 522, 479, 438, 21, 130, 293, 422, 440,
+     71, 321, 446, 358, 39, 447, 427, 6, 33, 429, 324, 76, 396, 444, 519, 159, 45, 403, 243, 251, 373, 251, 23, 140, 7,
+     356, 194, 499, 276, 251, 311, 10, 147, 30, 276, 430, 151, 519, 36, 354, 162, 451, 524, 312, 447, 77, 170, 428, 23,
+     283, 249, 466, 39, 58, 424, 68, 481, 2, 173, 179, 382, 334, 430, 84, 151, 293, 95, 522, 358, 505, 63, 524, 143,
+     119, 325, 401, 6, 361, 284, 418, 169, 256, 221, 330, 23, 72, 185, 376, 515, 84, 319, 27, 66, 497]
+    print(Solution.findContentChildren(g,s))
diff --git a/Week_04/id_94/LeetCode_714_094.py b/Week_04/id_94/LeetCode_714_094.py
@@ -0,0 +1,21 @@
+from typing import List
+
+
+class Solution:
+    def maxProfit( prices: List[int], fee: int) -> int:
+        n = len(prices)
+        if n<2:
+            return 0
+        dp1 = [0 for _ in range(n)] #第i天手上有股票时的最大收益
+        dp2 = [0 for _ in range(n)] #第i天手上无股票时的最大收益
+        dp1[0] = -prices[0]
+        for i in range(1,n):
+            dp1[i] = max(dp1[i-1],dp2[i-1]-prices[i])  #昨天手上有股票与今天手上有股票的收益对比
+            dp2[i] = max(dp2[i-1],dp1[i-1]+prices[i]-fee)  #昨天手上 无股票的收益和今天手上无股票的收益对比
+        return dp2[n-1]
+
+
+if __name__=="__main__":
+    prices = [1, 3, 2, 8, 4, 9]
+    fee = 2
+    print(Solution.maxProfit(prices,fee))
