homework_week6

xkluan · xkluan · commit f4163d755519 · 2020-07-19T23:04:56.000+08:00
diff --git a/Week06/221-最大正方形.py b/Week06/221-最大正方形.py
@@ -0,0 +1,30 @@
+# 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
+#
+#  示例:
+#
+#  输入:
+#
+# 1 0 1 0 0
+# 1 0 1 1 1
+# 1 1 1 1 1
+# 1 0 0 1 0
+#
+# 输出: 4
+#  Related Topics 动态规划
+
+
+# leetcode submit region begin(Prohibit modification and deletion)
+class Solution:
+    def maximalSquare(self, matrix: List[List[str]]) -> int:
+        if not matrix:
+            return 0
+        res = 0
+        dp = [[0 for _ in range(len(matrix[0])+1)] for _ in range(len(matrix)+1)]
+        for i in range(1, len(dp)):
+            for j in range(1, len(dp[0])):
+                if matrix[i-1][j-1] == "1":
+                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
+                    res = max(dp[i][j], res)
+
+        return pow(res, 2)
+# leetcode submit region end(Prohibit modification and deletion)
diff --git a/Week06/64-最小路径和.py b/Week06/64-最小路径和.py
@@ -0,0 +1,29 @@
+# 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
+#
+#  说明：每次只能向下或者向右移动一步。
+#
+#  示例:
+#
+#  输入:
+# [
+#   [1,3,1],
+#   [1,5,1],
+#   [4,2,1]
+# ]
+# 输出: 7
+# 解释: 因为路径 1→3→1→1→1 的总和最小。
+#
+#  Related Topics 数组 动态规划
+
+
+# leetcode submit region begin(Prohibit modification and deletion)
+class Solution:
+    def minPathSum(self, grid: List[List[int]]) -> int:
+        for i in range(len(grid)):
+            for j in range(len(grid[0])):
+                if i == j == 0: continue
+                elif i == 0: grid[i][j] = grid[i][j-1] + grid[i][j]
+                elif j == 0: grid[i][j] = grid[i-1][j] + grid[i][j]
+                else: grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
+        return grid[-1][-1]
+# leetcode submit region end(Prohibit modification and deletion)
diff --git a/Week06/91-解码方法.py b/Week06/91-解码方法.py
@@ -0,0 +1,43 @@
+# 一条包含字母 A-Z 的消息通过以下方式进行了编码：
+#
+#  'A' -> 1
+# 'B' -> 2
+# ...
+# 'Z' -> 26
+#
+#
+#  给定一个只包含数字的非空字符串，请计算解码方法的总数。
+#
+#  示例 1:
+#
+#  输入: "12"
+# 输出: 2
+# 解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
+#
+#
+#  示例 2:
+#
+#  输入: "226"
+# 输出: 3
+# 解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
+#
+#  Related Topics 字符串 动态规划
+
+
+# leetcode submit region begin(Prohibit modification and deletion)
+class Solution:
+    def numDecodings(self, s: str) -> int:
+        n = len(s)
+        if n == 0: return 0
+        dp = [1, 0]
+        dp[1] = 1 if s[0] != '0' else 0
+        for i in range(1, n):
+            dp.append(0)
+            if s[i] != '0':
+                dp[i + 1] += dp[i]
+            if '10' <= s[i - 1:i + 1] <= '26':
+                dp[i + 1] += dp[i - 1]
+
+        return dp[-1]
+
+# leetcode submit region end(Prohibit modification and deletion)
diff --git a/Week06/NOTE.md b/Week06/NOTE.md
@@ -1 +1,6 @@
-学习笔记
+学习笔记
+
+动态规划和递归或者分治没有本质上的区别（关键看有误最优的子结构）
+共性：找到重复子问题
+差异性：最优子结构，中途可以淘汰次优解
+
