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

自己有网站怎么做点卡网站建设公司如何转型

自己有网站怎么做点卡,网站建设公司如何转型,服务器上如何建设多个网站,成都论坛198. 打家劫舍 自己的思路: 初始化两个dp数组,dp[i][0]表示不偷第i户,在0-i户可以偷到的最大金额,dp[i][1]表示偷i户在0-i户可以偷到的最大金额。 class Solution:def rob(self, nums: List[int]) -> int:n len(nums)dp […

198. 打家劫舍

自己的思路:

初始化两个dp数组,dp[i][0]表示不偷第i户,在0-i户可以偷到的最大金额,dp[i][1]表示偷i户在0-i户可以偷到的最大金额。

class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)dp = [[0] * 2 for _ in range(n)]dp[0][1] = nums[0]for i in range(1, n):dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])dp[i][1] = dp[i - 1][0] + nums[i]return max(dp[n - 1][0], dp[n - 1][1])

优化:

有一点臃肿,可以优化。dp[i][1]实际上跟dp[i-1][1]就没啥关系,直接把dp数组初始化成一维的就行了。

class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)if n == 1:return nums[0]if n == 2:return max(nums[0], nums[1])dp = [0] * ndp[0] = nums[0]dp[1] = max(nums[0], nums[1])for i in range(2, n):dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])return dp[n - 1]

更优化:

想起了斐波那契数列...

class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)if n == 1:return nums[0]if n == 2:return max(nums[0], nums[1])prev = nums[0]cur = max(nums[0], nums[1])for i in range(2, n):prev, cur = cur, max(cur, prev + nums[i])return cur

 213. 打家劫舍 II

还是比较容易想到的,把环展成两个线性的,一个去头一个去尾即可。

class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)if n == 1:return nums[0]if n == 2:return max(nums[0], nums[1])def helper(n, nums):dp = [0] * ndp[0] = nums[0]dp[1] = max(nums[0], nums[1])for i in range(2, n):dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])return dp[n - 1]return max(helper(n-1, nums[1:]), helper(n-1, nums[:-1]))

337. 打家劫舍 III

我的思路:

有点类似贪心的最后一题。

一顿操作AC了,中间遗漏了几种情况,修改后正确了。

class Solution:def rob(self, root: Optional[TreeNode]) -> int:def helper(root):if not root.left and not root.right:return 0, root.valelif root.left and root.right:left_without_self, left_with_self = helper(root.left)right_without_self, right_with_self = helper(root.right)return max(left_without_self + right_without_self, left_with_self + right_with_self, left_without_self + right_with_self, left_with_self + right_without_self), left_without_self + right_without_self + root.valelif root.left and not root.right:left_without_self, left_with_self = helper(root.left)return max(left_with_self, left_without_self), left_without_self + root.valelif root.right and not root.left:right_without_self, right_with_self = helper(root.right)return max(right_with_self, right_without_self), right_without_self + root.valreturn max(helper(root))

优化:

终止条件从叶子节点改成空节点,可以将之后的情况全部统一起来。

class Solution:def rob(self, root: Optional[TreeNode]) -> int:def helper(root):if not root:return 0, 0left = helper(root.left)right = helper(root.right)not_include = max(left) + max(right)include = left[0] + right[0] + root.valreturn not_include, includereturn max(helper(root))

带备忘的递归:

class Solution:def rob(self, root: Optional[TreeNode]) -> int:memo = {}def helper(node):if not node:return 0if node in memo:return memo[node]val = node.val# 如果偷当前节点,则不能偷其直接的左右子节点,但可以偷其孙子节点if node.left:val += helper(node.left.left) + helper(node.left.right)if node.right:val += helper(node.right.left) + helper(node.right.right)# 不偷当前节点,可以偷其左右子节点not_steal = helper(node.left) + helper(node.right)# 对于当前节点,选择偷与不偷的最大值result = max(val, not_steal)memo[node] = resultreturn resultreturn helper(root)

今日总结:

自己写能AC,都能get到要点~~~精简的代码还是得看题解。

http://www.yayakq.cn/news/559120/

相关文章:

  • 网站建设推广襄樊烟台seo网络推广
  • wordpress怎样建站建设网站多少费用
  • 仕德伟做的网站青岛网站设计机构
  • 网站建设尾款收取wordpress站点打不开
  • 界首网站优化公司led灯网站策划书
  • 我自己做的网站一直没有效果怎么办电商cms
  • 建设手机网站包括哪些费用吗网页关于我们怎么设计
  • 小白建设论坛网站能建商城
  • 下列关于网站开发中网页发布做二手市场类型的网站名字
  • 建设电子商务网站步骤江西网站建设平台
  • 怎么给人介绍自己做的网站九江市建筑公司
  • 山东省建设局网站首页网站整合营销等服务
  • 公司内部网站设计做网站要不要营业执照
  • 小程序网站开发清新区住房和城乡建设局网站
  • 南阳网站建设seo民宿网络营销方式
  • 佛山大良网站建设做系统去哪个网站
  • 网站建设如何学徐州人才网
  • 全新升级网站手机虚拟机哪个好用
  • 石家庄网站建设外包公司排名网站开发 卓优科技
  • 用凡科做的网站保存不了网站seo外包公司有哪些
  • 万州集团网站建设装饰网站建设流程
  • 网站建设规划书结构网站没有做301定向
  • 活动策划网站源码建设公司网站有用吗
  • 内蒙古住房和建设厅网站php网站开发最低配置
  • 网站运营怎么学沈阳网站建设渠道
  • 更改网站备案负责人买域名去哪个网站好
  • 外贸网站推广教程网站建立风格
  • 石家庄h5网站建设有了源码怎么搭建网站
  • 如何选择丹徒网站建设英文网站怎么做外贸推广
  • 网站建设html5农夫山泉品牌vi设计分析