杭州网站建设哪家比较好科技小报手抄报内容

当前位置： 首页 > news >正文

杭州网站建设哪家比较好,科技小报手抄报内容,南宁网站制作公,网站建设实习困难✅作者简介#xff1a;人工智能专业本科在读#xff0c;喜欢计算机与编程#xff0c;写博客记录自己的学习历程。 #x1f34e;个人主页#xff1a;小嗷犬的个人主页 #x1f34a;个人网站#xff1a;小嗷犬的技术小站 #x1f96d;个人信条#xff1a;为天地立心人工智能专业本科在读喜欢计算机与编程写博客记录自己的学习历程。 个人主页小嗷犬的个人主页 个人网站小嗷犬的技术小站 个人信条为天地立心为生民立命为往圣继绝学为万世开太平。 本文目录 打家劫舍题目描述题解 打家劫舍 II题目描述题解 打家劫舍 III题目描述题解 打家劫舍 题目描述 你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 示例 1: 输入: [1,2,3,1] 输出: 4 解释: 偷窃 1 号房屋 (金额 1) 然后偷窃 3 号房屋 (金额 3)。偷窃到的最高金额 1 3 4 。示例 2: 输入[2,7,9,3,1] 输出12 解释偷窃 1 号房屋 (金额 2), 偷窃 3 号房屋 (金额 9)接着偷窃 5 号房屋 (金额 1)。偷窃到的最高金额 2 9 1 12 。来源: 198. 打家劫舍 - 力扣 (LeetCode) 题解 动态规划 首先考虑最简单的情况。如果只有一间房屋则偷窃该房屋可以偷窃到最高总金额。如果只有两间房屋则由于两间房屋相邻不能同时偷窃只能偷窃其中的一间房屋因此选择其中金额较高的房屋进行偷窃可以偷窃到最高总金额。 如果房屋数量大于两间应该如何计算能够偷窃到的最高总金额呢对于第 k ( k 2 ) k (k2) k(k2) 间房屋有两个选项 偷窃第 k k k 间房屋那么就不能偷窃第 k − 1 k−1 k−1 间房屋偷窃总金额为前 k − 2 k−2 k−2 间房屋的最高总金额与第 k k k 间房屋的金额之和。不偷窃第 k k k 间房屋偷窃总金额为前 k − 1 k−1 k−1 间房屋的最高总金额。 在两个选项中选择偷窃总金额较大的选项该选项对应的偷窃总金额即为前 k k k 间房屋能偷窃到的最高总金额。 用 d p [ i ] dp[i] dp[i] 表示前 i i i 间房屋能偷窃到的最高总金额那么就有如下的状态转移方程 d p [ i ] m a x ( d p [ i − 2 ] n u m s [ i ] , d p [ i − 1 ] ) dp[i] max(dp[i-2] nums[i], dp[i-1]) dp[i]max(dp[i−2]nums[i],dp[i−1]) 边界条件为 { d p [ 0 ] n u m s [ 0 ] 只有一间房屋则偷窃该房屋 d p [ 1 ] m a x ( n u m s [ 0 ] , n u m s [ 1 ] ) 只有两间房屋选择其中金额较高的房屋进行偷窃 \begin{cases} dp[0] nums[0] 只有一间房屋则偷窃该房屋\ dp[1] max(nums[0], nums[1]) 只有两间房屋选择其中金额较高的房屋进行偷窃 \end{cases} {dp[0]nums[0]dp[1]max(nums[0],nums[1])​只有一间房屋则偷窃该房屋只有两间房屋选择其中金额较高的房屋进行偷窃​ 最终的答案即为 d p [ n − 1 ] dp[n−1] dp[n−1]其中 n n n 是数组的长度。 class Solution:def rob(self, nums: List[int]) - int:if not nums:return 0size len(nums)if size 1:return nums[0]dp [0] * sizedp[0] nums[0]dp[1] max(nums[0], nums[1])for i in range(2, size):dp[i] max(dp[i - 2] nums[i], dp[i - 1])return dp[size - 1]上述方法使用了数组存储结果。考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关因此可以使用滚动数组在每个时刻只需要存储前两间房屋的最高总金额。 class Solution:def rob(self, nums: List[int]) - int:if not nums:return 0size len(nums)if size 1:return nums[0]first, second nums[0], max(nums[0], nums[1])for i in range(2, size):first, second second, max(first nums[i], second)return second复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是数组长度。只需要对数组遍历一次。空间复杂度 O ( 1 ) O(1) O(1)。使用滚动数组可以只存储前两间房屋的最高总金额而不需要存储整个数组的结果因此空间复杂度是 O ( 1 ) O(1) O(1)。 打家劫舍 II 题目描述 你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。 示例 1 输入nums [2,3,2] 输出3 解释你不能先偷窃 1 号房屋金额 2然后偷窃 3 号房屋金额 2因为他们是相邻的。示例 2 输入nums [1,2,3,1] 输出4 解释你可以先偷窃 1 号房屋金额 1然后偷窃 3 号房屋金额 3。偷窃到的最高金额 1 3 4 。示例 3 输入nums [1,2,3] 输出3来源: 213. 打家劫舍 II - 力扣 (LeetCode) 题解 动态规划 首先考虑最简单的情况。如果只有一间房屋则偷窃该房屋可以偷窃到最高总金额。如果只有两间房屋则由于两间房屋相邻不能同时偷窃只能偷窃其中的一间房屋因此选择其中金额较高的房屋进行偷窃可以偷窃到最高总金额。 注意到当房屋数量不超过两间时最多只能偷窃一间房屋因此不需要考虑首尾相连的问题。如果房屋数量大于两间就必须考虑首尾相连的问题第一间房屋和最后一间房屋不能同时偷窃。 如何才能保证第一间房屋和最后一间房屋不同时偷窃呢如果偷窃了第一间房屋则不能偷窃最后一间房屋因此偷窃房屋的范围是第一间房屋到最后第二间房屋如果偷窃了最后一间房屋则不能偷窃第一间房屋因此偷窃房屋的范围是第二间房屋到最后一间房屋。 假设数组 n u m s nums nums 的长度为 n n n。如果不偷窃最后一间房屋则偷窃房屋的下标范围是 [ 0 , n − 2 ] [0,n−2] [0,n−2]如果不偷窃第一间房屋则偷窃房屋的下标范围是 [ 1 , n − 1 ] [1,n−1] [1,n−1]。在确定偷窃房屋的下标范围之后即可用第 198 题的方法解决。对于两段下标范围分别计算可以偷窃到的最高总金额其中的最大值即为在 n n n 间房屋中可以偷窃到的最高总金额。 假设偷窃房屋的下标范围是 [ s t a r t , e n d ] [start,end] [start,end]用 d p [ i ] dp[i] dp[i] 表示在下标范围 [ s t a r t , i ] [start,i] [start,i] 内可以偷窃到的最高总金额那么就有如下的状态转移方程 d p [ i ] max ⁡ ( d p [ i − 2 ] n u m s [ i ] , d p [ i − 1 ] ) dp[i]\max(dp[i−2]nums[i],dp[i−1]) dp[i]max(dp[i−2]nums[i],dp[i−1]) 边界条件为 { d p [ s t a r t ] n u m s [ s t a r t ] 只有一间房屋则偷窃该房屋 d p [ s t a r t 1 ] max ⁡ ( n u m s [ s t a r t ] , n u m s [ s t a r t 1 ] ) 只有两间房屋偷窃其中金额较高的房屋 \begin{cases} dp[start]nums[start] 只有一间房屋则偷窃该房屋 \ dp[start1]\max(nums[start],nums[start1]) 只有两间房屋偷窃其中金额较高的房屋 \end{cases} {dp[start]nums[start]dp[start1]max(nums[start],nums[start1])​只有一间房屋则偷窃该房屋只有两间房屋偷窃其中金额较高的房屋​ 计算得到 d p [ e n d ] dp[end] dp[end] 即为下标范围 [ s t a r t , e n d ] [start,end] [start,end] 内可以偷窃到的最高总金额。 分别取 ( s t a r t , e n d ) ( 0 , n − 2 ) (start,end)(0,n−2) (start,end)(0,n−2) 和 ( s t a r t , e n d ) ( 1 , n − 1 ) (start,end)(1,n−1) (start,end)(1,n−1) 进行计算取两个 d p [ e n d ] dp[end] dp[end] 中的最大值即可得到最终结果。 根据上述思路可以得到时间复杂度 O ( n ) O(n) O(n) 和空间复杂度 O ( n ) O(n) O(n) 的实现。考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关因此可以使用滚动数组在每个时刻只需要存储前两间房屋的最高总金额将空间复杂度降到 O ( 1 ) O(1) O(1)。 class Solution:def rob(self, nums: List[int]) - int:def robRange(start: int, end: int) - int:first nums[start]second max(nums[start], nums[start 1])for i in range(start 2, end 1):first, second second, max(first nums[i], second)return secondlength len(nums)if length 1:return nums[0]elif length 2:return max(nums[0], nums[1])else:return max(robRange(0, length - 2), robRange(1, length - 1))复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是数组长度。需要对数组遍历两次计算可以偷窃到的最高总金额。空间复杂度 O ( 1 ) O(1) O(1)。 打家劫舍 III 题目描述 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为 root 。 除了 root 之外每栋房子有且只有一个“父“房子与之相连。一番侦察之后聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 房屋将自动报警。 给定二叉树的 root 。返回 在不触动警报的情况下 小偷能够盗取的最高金额 。 示例 1: 输入: root [3,2,3,null,3,null,1] 输出: 7 解释: 小偷一晚能够盗取的最高金额 3 3 1 7示例 2: 输入: root [3,4,5,1,3,null,1] 输出: 9 解释: 小偷一晚能够盗取的最高金额 4 5 9来源: 337. 打家劫舍 III - 力扣 (LeetCode) 题解 动态规划 简化一下这个问题一棵二叉树树上的每个点都有对应的权值每个点有两种状态选中和不选中问在不能同时选中有父子关系的点的情况下能选中的点的最大权值和是多少。 我们可以用 f ( o ) f(o) f(o) 表示选择 o o o 节点的情况下 o o o 节点的子树上被选择的节点的最大权值和 g ( o ) g(o) g(o) 表示不选择 o o o 节点的情况下 o o o 节点的子树上被选择的节点的最大权值和 l l l 和 r r r 代表 o o o 的左右孩子。 当 o o o 被选中时 o o o 的左右孩子都不能被选中故 o o o 被选中情况下子树上被选中点的最大权值和为 l l l 和 r r r 不被选中的最大权值和相加即 f ( o ) g ( l ) g ( r ) f(o)g(l)g® f(o)g(l)g®。当 o o o 不被选中时 o o o 的左右孩子可以被选中也可以不被选中。对于 o o o 的某个具体的孩子 x x x它对 o o o 的贡献是 x x x 被选中和不被选中情况下权值和的较大值。故 g ( o ) m a x { f ( l ) , g ( l ) } m a x { f ( r ) , g ( r ) } g(o)max{f(l),g(l)}max{f®,g®} g(o)max{f(l),g(l)}max{f®,g®}。 至此我们可以用哈希表来存 f f f 和 g g g 的函数值用深度优先搜索的办法后序遍历这棵二叉树我们就可以得到每一个节点的 f f f 和 g g g。根节点的 f f f 和 g g g 的最大值就是我们要找的答案。 我们不难给出这样的实现 class Solution:def rob(self, root: Optional[TreeNode]) - int:f {None:0}g {None:0}def dfs(node):if not node:returndfs(node.left)dfs(node.right)f[node] node.val g[node.left] g[node.right]g[node] max(f[node.left], g[node.left]) max(f[node.right], g[node.right])dfs(root)return max(f[root], g[root])假设二叉树的节点个数为 n n n。 我们可以看出以上的算法对二叉树做了一次后序遍历时间复杂度是 O ( n ) O(n) O(n)由于递归会使用到栈空间空间代价是 O ( n ) O(n) O(n)哈希表的空间代价也是 O ( n ) O(n) O(n)故空间复杂度也是 O ( n ) O(n) O(n)。 我们可以做一个小小的优化我们发现无论是 f ( o ) f(o) f(o) 还是 g ( o ) g(o) g(o)他们最终的值只和 f ( l ) f(l) f(l)、 g ( l ) g(l) g(l)、 f ( r ) f® f®、 g ( r ) g® g® 有关所以对于每个节点我们只关心它的孩子节点们的 f f f 和 g g g 是多少。我们可以设计一个结构表示某个节点的 f f f 和 g g g 值在每次递归返回的时候都把这个点对应的 f f f 和 g g g 返回给上一级调用这样可以省去哈希表的空间。 代码如下 class Solution:def rob(self, root: Optional[TreeNode]) - int:def dfs(node):if not node:return (0, 0)l dfs(node.left)r dfs(node.right)selected node.val l[1] r[1]notSelected max(l) max®return selected, notSelectedans dfs(root)return max(ans)复杂度分析 时间复杂度 O ( n ) O(n) O(n)。上文中已分析。空间复杂度 O ( n ) O(n) O(n)。虽然优化过的版本省去了哈希表的空间但是栈空间的使用代价依旧是 O ( n ) O(n) O(n)故空间复杂度不变。