Python每日一练(20230218)

目录​​​​​​​

1. 旋转图像

2. 解码方法

3. 二叉树最大路径和

---

1. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

示例 3：

输入：matrix = [[1]]
输出：[[1]]

示例 4：

输入：matrix = [[1,2],[3,4]]
输出：[[3,1],[4,2]]

提示：

• matrix.length == n
• matrix[i].length == n
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

源代码： 

class Solution(object):def rotate(self, matrix):if matrix is None or len(matrix) == 1:return matrixls = len(matrix)for i in range(int(ls / 2)):begin, end = i, ls - 1 - ifor k in range(ls - 2 * i - 1):temp = matrix[end - k][begin]matrix[end - k][begin] = matrix[end][end - k]matrix[end][end - k] = matrix[begin + k][end]matrix[begin + k][end] = matrix[begin][begin + k]matrix[begin][begin + k] = tempreturn matrixif __name__ == "__main__":s = Solution()print(s.rotate([[1,2,3],[4,5,6],[7,8,9]]))print(s.rotate([[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]))print(s.rotate([[1]]))print(s.rotate([[1,2],[3,4]]))

输出：

[[7, 4, 1], [8, 5, 2], [9, 6, 3]]
[[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]
[[1]]
[[3, 1], [4, 2]]

2. 解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> 1 'B' -> 2 ... 'Z' -> 26

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

• "AAJF" ，将消息分组为 (1 1 10 6)
• "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3：

输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。

示例 4：

输入：s = "06"
输出：0
解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。

提示：

• 1 <= s.length <= 100
• s 只包含数字，并且可能包含前导零。

源代码：  

class Solution(object):def numDecodings(self, s:str) -> int:ls = len(s)if ls == 0:return 0dp = [0] * lsfor index in range(ls):if index >= 1 and int(s[index - 1:index + 1]) < 27 and int(s[index - 1:index + 1]) >= 10:if index == 1:dp[index] = 1else:dp[index] += dp[index - 2]if int(s[index]) != 0:if index == 0:dp[index] = 1else:dp[index] += dp[index - 1]return dp[ls - 1]s = Solution()
print(s.numDecodings(s = "12"))
print(s.numDecodings(s = "226"))
print(s.numDecodings(s = "0"))
print(s.numDecodings(s = "06"))

输出： 

2
3
0
0

3. 二叉树最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

• 树中节点数目范围是 [1, 3 * 104]
• -1000 <= Node.val <= 1000

源代码：  

class TreeNode:def __init__(self, val=None):self.val = valself.left = Noneself.right = Nonedef Build(root, nodesList, i=0):if i < len(nodesList):if nodesList[i]:root = TreeNode(nodesList[i])root.left = Build(root.left, nodesList, 2*i+1)root.right = Build(root.right, nodesList, 2*i+2)return rootclass Solution:def __init__(self):self.result = float("-inf")def maxPathSum(self, root: TreeNode) -> int:if root == None:return 0self.getMax(root)return self.resultdef getMax(self, root):if root == None:return 0left = max(0, self.getMax(root.left))right = max(0, self.getMax(root.right))self.result = max(self.result, left + right + root.val)return max(left, right) + root.vals = Solution()
tree = TreeNode()
root = Build(tree, [1,2,3])
print(s.maxPathSum(root))root = Build(tree, [-10,9,20,None,None,15,7]) #null在python语言中表示为None
print(s.maxPathSum(root))

输出： 

6
42