做数据可视化的网站自建商城网站

做数据可视化的网站,自建商城网站,dw中旅游网站怎么做,如何制作网站详细教程198.打家劫舍 文章讲解/视频讲解 题目描述#xff1a; 你是一个专业的小偷#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 。提示0 nums.length 1000 nums[i] 400思路当前房屋偷不偷取决于前一个房屋和前两个房屋偷没偷这种当前状态与前面状态有关的很容易想到动态规划1.确定dp数组及其下标含义dp[i]表示i以内的房屋包括i最多可以偷dp[i]元2.确定递推公式决定dp[i]的因素就是第i房间偷还是不偷。这里分为两种情况偷i和不偷i。如果偷i的话那就不能偷i-1所以是dp[i-2] 加上第i房间偷到的钱。如果不偷i那就考虑dp[i - 1]这里注意考虑不代表就一定偷i - 1房。dp要取二者的最大值所以dp[i] max(dp[i - 2] nums[i], dp[i - 1])3.dp数组的初始化本题我们要考虑的是dp[0]和dp[1]这是从递推公式中得来的信息。首先dp[0]肯定等于nums[0]而dp[1]就是nums[0]和nums[1]的最大值。4.确定遍历顺序dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的那么一定是从前到后遍历而且是从i 2开始遍历的。5.举例推导dp数组以示例二输入[2,7,9,3,1]为例。红框dp[nums.size() - 1]为结果。代码示例function rob(nums: number[]): number { const length:number nums.length const dp:number[] [] if(length 1) return nums[0] dp[0] nums[0] dp[1] Math.max(nums[0], nums[1]) for(let i 2; i length; i){ dp[i] Math.max(dp[i - 2] nums[i], dp[i - 1]) } return dp[length - 1] };213.打家劫舍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 [0]输出0提示1 nums.length 1000 nums[i] 1000思路与上题相比本题又进阶了现在房屋群变成一个环形了。但是我们可以通过把它拆分成三种情况来解决1.头尾都不偷 2.不偷尾 3.不偷头情况一考虑不包含首尾元素情况二考虑包含首元素不包含尾元素情况三考虑包含尾元素不包含首元素注意这里都只是考虑不是说考虑包含尾元素就一定要偷最后一座房子了比如上图考虑包含尾元素就是偷1和3没偷尾元素4.而情况一其实被包含在了情况二和情况三里所以我们只需额外写一个工具函数把情况二和情况三单独拎出来比较谁大即可谁大谁就是最优解。代码示例function rob(nums: number[]): number { const length: number nums.length if (length 0) return 0 if (length 1) return nums[0] return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1)) }; function robRange(nums: number[], start: number, end: number): number { if (start end) return nums[start] const dp: number[] [] dp[start] nums[start] dp[start 1] Math.max(nums[start], nums[start 1]) for (let i start 2; i end; i) { dp[i] Math.max(dp[i - 1], dp[i - 2] nums[i]) } return dp[end] }337.打家劫舍III文章讲解/视频讲解题目描述在上次打劫完一条街道之后和一圈房屋后小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为“根”。 除了“根”之外每栋房子有且只有一个“父“房子与之相连。一番侦察之后聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫房屋将自动报警。计算在不触动警报的情况下小偷一晚能够盗取的最高金额。思路本题是打家劫舍的最终形态了动态规划与二叉树结合。看到树首先就要想到遍历方式前中后序遍历本题显然用的是后序遍历我们需要先得到左右孩子才能去计算父节点。我们还是要讨论抢不抢当前房子本题就是抢不抢当前节点如果抢了就不能抢左右孩子了如果没抢没抢当前节点就去考虑是否要抢左右孩子了不是一定抢本题我们使用动规五部曲结合递归三部曲1.确定递归函数的参数及其返回值传入的参数就是当前节点我们要返回偷或者不偷的金钱也就是说我们要返回一个长度为2的数组下标为0记录着不偷得到的最大金额下标为1记录着偷该节点得到的最大金额。2.确定终止条件如果遇到空节点不管偷不偷都是0了直接返回即可3.确定遍历顺序先递归左结点得到左结点偷与不偷的金钱。再递归右节点得到右节点偷与不偷的金钱4.确定单层递归的逻辑如果偷当前节点就不偷左右孩子 如下const val2: number leftArr[0] rightArr[0] node.val如果不偷当前节点就可以偷左右孩子但是不是一定就要偷左右都要选最大的看看是不偷大还是偷大把左右孩子加起来如下const val1: number Math.max(leftArr[0], leftArr[1]) Math.max(rightArr[0], rightArr[1])最后得到的节点状态就是 不偷当前节点得到的最大金钱和偷当前节点得到的最大金钱5.举例推导dp数组以示例1为例dp数组状态如下注意用后序遍历的方式推导最后头结点就是 取下标0 和 下标1的最大值就是偷得的最大金钱。代码示例/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val (valundefined ? 0 : val) * this.left (leftundefined ? null : left) * this.right (rightundefined ? null : right) * } * } */ function rob(root: TreeNode | null): number { return Math.max(...robNode(root)) }; type MaxValueArr [number, number] function robNode(node: TreeNode | null): MaxValueArr { if (node null) return [0, 0] const leftArr: MaxValueArr robNode(node.left) const rightArr: MaxValueArr robNode(node.right) const val1: number Math.max(leftArr[0], leftArr[1]) Math.max(rightArr[0], rightArr[1]) const val2: number leftArr[0] rightArr[0] node.val return [val1, val2] }