用vuejs做网站,怎样做后端数据传输前端的网站,怎么做展示型网站,管理系统考生端重置密码参考文献 代码随想录
一、打家劫舍 你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#xff0c;系统会自动报警…参考文献 代码随想录
一、打家劫舍 你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 示例 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 问题分析当前房间是否偷是不是取决于前一个房间的状态和前2个房间的状态如果当前房间偷那么最大价值是不是取决于前2个房间的最大价值 当前房间的最大值如果不偷那么是不是取决于前一个房间的最大价值那么是不是要取一个最大值而dp[i]代表的是第 包含i之前的房间0 到 i房间的最大值最大价值。 class Solution(object):def rob(self, nums)::type nums: List[int]:rtype: intif len(nums) 0: # 如果没有房屋返回0return 0if len(nums) 1: # 如果只有一个房屋返回其金额return nums[0]dp [0 for _ in range(len(nums))]dp[0] nums[0]dp[1] max(nums[0], nums[1])print(dp)for i in range(2, len(nums)):dp[i] max(dp[i - 2] nums[i], dp[i - 1])return dp[-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
问题分析这个问题形成了一个环首尾相连那么我们可以分成3种情况第一种不包含尾第二种不包含首第三种不包含首尾其实情况一和情况二的范围都包含了第三种所以只有考虑到2种情况我们这里dp[i]考虑下标i包括i以内的房屋最多可以偷窃的金额为dp[i]。 class Solution(object):def __init__(self):self.dp []def rob(self, nums)::type nums: List[int]:rtype: intif len(nums) 0:return 0if len(nums) 1:return nums[0]if len(nums) 2 or len(nums) 3:return max(nums)self.dp [0 for _ in range(len(nums) - 1)]self.d(nums[1:])tm self.dp[-1]self.d(nums[0: len(nums) - 1])return max(tm, self.dp[-1])def d(self, li):self.dp[0] li[0]self.dp[1] max(li[0], li[1])for i in range(2, len(li)):print(self.dp)self.dp[i] max(self.dp[i - 2] li[i], self.dp[i - 1]) 把dp数组变成2个变量来存储 因为当前房间根前一个前2个有关然后需要2个变量来接受前一个前2个在求第三个的时候滚动移动比如dp数组[1,2]然后求当前的房间的最大值时如果此时的最大值为4那么dp为[1,2,4]然后此时是不是只依赖2和4的值所以利用2个变量来进行滚动 class Solution:def rob(self, nums: List[int]) - int:if len(nums) 0:return 0if len(nums) 1:return nums[0]result1 self.robRange(nums, 0, len(nums) - 2) # 情况二result2 self.robRange(nums, 1, len(nums) - 1) # 情况三return max(result1, result2)# 198.打家劫舍的逻辑def robRange(self, nums: List[int], start: int, end: int) - int:if end start:return nums[start]prev_max nums[start] # pre_max代替的是dp数组的第一个初始化的元素curr_max max(nums[start], nums[start 1]) # curr_max代替的是dp数组的第二个初始化的元素for i in range(start 2, end 1): # 为什么start要加2因为前面已经初始化了2个因为要遍历到end所以要加1temp curr_max # 因为当前房间根前一个前2个有关然后需要2个变量来接受前一个前2个在求第三个的时候滚动移动比如dp数组[1,2]然后求当前的房间的最大值时如果此时的最大值为4那么dp为[1,2,4]然后此时是不是只依赖2和4的值所以利用2个变量来进行滚动curr_max max(prev_max nums[i], curr_max)prev_max tempreturn curr_max 三、打家劫舍 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
问题分析当前节点要么偷要么不偷那么我们返回这2个的最大值遇到二叉树就要考虑到遍历顺序答案是后序为什么是后序呢我们这里的dp数组的长度只有2dp[0]表示不偷dp[1]表示偷然后我们该如何把dp数组给初始化每个节点的状态呢递归如果我们求当前结果有2种情况如果偷那么它的孩子就不偷那么它的孩子不偷时的最大价值是多少呢如果当前节点不偷那么就要偷它的孩子问题来了它的孩子不偷与偷的价值分别是多小呢要想知道孩子是多少首先返回值就是dp然后遍历的顺序是后序遍历这样才能知道它的孩子的dp. # Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution(object):def __init__(self):self.li []def rob(self, root)::type root: TreeNode:rtype: intdp self.d(root)return max(dp)def d(self, root):if not root:return (0,0)left self.d(root.left) # 返回值是一个dp[i]且长度为2right self.d(root.right)# 如果当前节点偷孩子节点不偷那么就要加上孩子不偷的价值是多少0为不偷1为偷value1 root.val left[0] right[0]# 当前节点不偷那么就要考虑孩子偷与不偷每个孩子是偷呢还是不偷呢所以要取一个最大值value2 max(left[0], left[1]) max(right[0], right[1])return [value2, value1]
